Turn Based Games

Hello all,

I'm a professor that has been given the honorable task of creating a
video game programming course. One of my assignments in AI will be to
have the students implement a function called algorithm() using a code
base that I would provide.

Using a common protocol (tcp/ip of course) I was hoping to have the
students pair off, complete algorithm(), and have a tournament to see
who's algorithm worked the best.

I'm having a hard time trying to find a good turn based game to base
the lesson on. I was thinking tic tac toe, but using a* you can come
up with the best solution in near nano-seconds. I want something with
a little more variance than that, but not too complex.

I was looking into Othello, but I wanted your input before I made
anything concrete.

Thanks,

Jason Reposa
http://www.reposagroup.com