Tic-Tac-Toe

Here's a very modest game project that's been sitting around a while, but I haven't finished it until tonight.

I coded this up in Python after reading about the minimax algorithm in Russell and Norvig's Artificial Intelligence: A Modern Approach. (I ignored the available Python code on their web site to challenge my programming skills.) I expected Tic-Tac-Toe to be straightforward, but the code grew a lot larger than I expected (especially for Python). The other surprising result was that standard minimax seemed to be too conservative for Tic-Tac-Toe -- the algorithm would evaluate paths with eventual wins with the same weight as quick or immediate wins. I had to tweak the algorithm slightly to compensate for this.

Now it seems to play aggressively, as it should. Of course, tic-tac-toe isn't a big test for minimax. (Or for a human for that matter!) However, maybe now I can adapt this code and resuscitate my long-abandoned Checkers project. I'm not making any promises though.

Update: I checked, and the Python code from the AIMA website (games.py) is definitely still in a rough state. I had to modify their version of Tic-Tac-Toe to even get it working, and it has the exact same problems with the standard minimax algorithm that I mentioned above. Why isn't this limitation of minimax mentioned in the book? Beats me.