This is very late, but here's the info on my Nine Men's Morris algorithm. I ended up writing it in C++. I'm still new to the language and I was working with it at the time for another class. Ultimately the decision to use C++ was based on getting more experience with the language while benefiting my studies with the other class. Here is the code to Morris. It's a Visual Studio project, but I didn't write anything Microsoft specific (I'm just too lazy to write a makefile and test building it).
While I did well on the project as a graded piece of work, my showing at the tournament was quite poor. I attribute this to running out of time, which is my own fault. I didn't spend nearly enough time tuning my eval function to determine the 'goodness' of a board. I actually wrote the program to be able to play against itself using different eval weights and/or different eval functions. I had grand plans to have it play hundreds of games against itself testing different weights. Unfortunately, I ran out of time and had to submit the project. Thus the most import part of the program received very little attention. I also wanted to implement some form of killer heuristic so the program could get further down the game tree. The current version gets anywhere from 4 to 8 moves down the tree given a 10 second window. Deeper game tree = better moves. Suprisingly it still managed to beat me every time I played it. I guess this just shows how poor of a player I am.
Some observations from this project:
- Visual Studio is a kick ass IDE. I knew this from my .NET dev days, but all my C++ projects up to this one were written in vim. I forgot how much I love the integrated debugger and intellisense (code completion). If you can use Visual Studio for a C++ project I don't know why you'd use anything else (other than a fanatical hatred for anything Microsoft).
- I probably could have written this in any language. My guess is that the algorithm would have been able to get the same distance down the game tree in Ruby, Lisp, C#, Java, C++, Python or whatever. The choke points were when the branching factor got out of hand and there were just too many game nodes to evaluate. Differences in execution time probably wouldn't have mattered with this kind of exponential expansion.
- Writing code in C++ makes me really miss dynamic languages like Ruby. This program could probably be written in 500 lines in a much shorter amount of time using a dynamic language.
- Writing the program in Ruby probably would have resulted in a better performing (better move decisions) algorithm. This is becasue I would have had more time to focus on improving the eval function and adding in some killer heuristics instead of wrestling with the language. All this despite the fact that I'm still a ruby newbie.
Here are some notes about the code. There are six classes and the main driver representing around 1500 lines. Some of it is ugly as all hell, but I tried to put in comments where I thought things might not make sense. Most of this is the result of a marathon weekend coding session. There is a known bug in the GameController class. I know what it is and how to fix it, but I ran out of time at the end and didn't have a chance. It's not fatal and I'm leaving out the details just to see if anyone is curious enough to poke around and find it. The meaty interesting sections are the eval functions and the ab mini-max implementation. There are six eval functions: three test and three production for each stage of the game. These can be found in the Board class. The ab mini-max implementation can be found in the GameController class.
