clb.demon.fi

Writing a Chess AI using the minimax is a nice exercise in programming. A simple game tree search for something like 3-4 plies doesn't require too much hackery and it will give you an AI that compares to an old 8-bit NES game. At some point I took it as a challenge to evolve the AI to play better than I do. It turned out not to be too difficult, perhaps because I'm not very strong a player.

What it took was

• alpha-beta cutoffs
• iterative deepening
• quiescent searches
• transposition tables
• Some work on dynamic move ordering (remember moves that were previously good)
• bitboards form for optimization to be able to go as far as 7 plies.

If I play carelessly without paying too much attention, I usually get myself beat. But after playing for a while it is easy to see obvious mistakes the AI repeatedly does. It's far from being an AI that could challenge any serious chess players, but still I think I achieved my own goals.

Great sources for learning were Bruce Moreland's site and McGill University CS class notes.

The next goal I have set is to separate the minimax algorithm from the chess AI, and make it easier to write AI opponents for other board games as well. One such board game I like is Pente, which should be a bit easier for the minimax than Chess.

Edit: Added the most important thing, which is the download link to the program: 2005-11-02.Win32.Chess.with.AI.v11.bin.rar