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
< Prev | Next > |
---|
Last Updated (Tuesday, 11 March 2008 15:50)