Where we started
It was the first time we wrote a program that decides on its own. We came in knowing very little game theory or search algorithms, and learned them while building. Seen from there, 72 % against the medium engine is a result I am glad of.
The game
Nine small grids inside a big one. Where you play inside a small grid sends your opponent to the matching small grid. Win three small grids in a row to win the game. Every move is two decisions at once: the square you take, and where you send the other player.
The engine
- Minimax with alpha-beta pruning and iterative deepening.
- A transposition table with Zobrist hashing.
- Move ordering with killer moves and a history table.
- A positional evaluation, and an opening book that fills itself from tournament games.
- About 1,800 lines of C++, plugged into the teacher's engine through a fixed interface.
How it got to 72 %
The first version won between 0 and 20 % against MEDIUM_2, at about 350 ms per move. Going to depth 14 with a 10-second budget and adding the opening book brought it to 72 % over 100 games, with an average depth of 11.3 and 319 moves served by the book.
What I learned
- Samples of 10 games are noise. Only 100-game runs told us anything.
- Debug and Release builds play like two different engines; always measure with -O3.
- Mate scores stored in the table must be corrected by distance, or the engine believes nonsense.
- An opening book goes wrong as soon as the evaluation changes.
- Not done: quiescence search, multi-threading, Monte Carlo tree search, which is what wins at this game.