Paul Dix Explains Nothing

Game Playing Algorithm for Nine Men's Morris

I'm starting a project in a week to create an algorithm to play the game Nine Men's Morris.  This is an assignment for my AI class that ends with a Nine Men's Morris Tournament between the student's algorithms.  Pretty cool huh?  The reason I bring it up here is because I'm looking for advice (I'll also be documenting my progress).

Before I ask for help, let me provide some details about the implementation.  I can write the program in any language I want.  I have to use the alpha-beta pruning technique on the minimax algorithm in the game playing program.  I have to write my own heuristics/evaluations for making moves.  These can be based on my own strategies or ones found elsewhere.  Our programs have somewhere around 10 seconds to make each move.

So here are the things I'm looking for advice on.  First, the language.  I'm thinking about writing in C++, Lisp, Ruby, or C#.  My first concern on language choice is execution speed.  How fast will the program execute in each language?  Will one be fast enough to get me farther down the game tree than another?  Here's my list for how fast I think each language will be (with 1 being fastest):

1. C++
2. C#
3. Lisp
4. Ruby

The reverse order of that list happens to be the order of my language preference for writing this particular program.  I realize that the only real way to find out how fast each will be is to write in each and make some empirical observations, but since I don't have the luxury of time I'm looking for some basic guidance.  Only a running time difference that would get me another two ply down the game tree (no small amount of processing) will interest me.  Does anyone have suggestions on how to make Lisp or Ruby execute considerably faster?  Keep in mind that I'll have access only to freely available tools.  I've been developing Lisp in SLIME on emacs and the execution is not very fast (I'm sure there are ways to speed it up).  I'm a newb with both languages which is why I want to use one of them for this project!

The second thing I'm looking for advice with is developing good heuristics/evaluations for this game.  I've never played Morris before so I have little to bring to the table for strategy.  Does anyone know of good resources for Morris game playing strategies?  Does anyone know of good research papers that deal with developing heuristics for Morris?  I'll be looking for information myself when I start the project, but just in case anyone is able to point me in the right direction it will be appreciated and helpful!

nyc.rb meeting notes

I went to the 2 year anniversary meeting of the NYC Ruby users group last night.  There were three presentations and the usual bantering about all things development related.  The presentation I found the most interesting was given by Zed Shaw.   He talked about using statistics and analysis when tuning performance on web applications.  The presentation was adapted from his rant about why programmers must learn statistics.  He provided some good examples and showed some gathering and reporting on-the-fly.

I have to admit that I'm one of the unwashed masses that doesn't know anything about statistics.  However, his arguments made sense to me and I like the idea of using empirical results over big-oh analysis in complicated systems.  I've been planning to focus some of my coursework on statistics and this just whetted my appetite for it.

Trotter Cashion gave a presentation about higher order procedures that was informative.

Greg Brown gave a presentation about a ruby reporting library called Ruport that he has been working on.

It was a great meeting with record attendance (around 28 people).  I hope to see everyone at the hack-fest in two weeks!