Programming a board game AI

This semester, the final project of the problem solving class, which belongs to the computer science department, was to program an AI for a board game called Halma, whose variant is often known by the name Chinese Checkers.

Typical board game AI consists of following parts: move generator, evaluation function, and tree search. As the name implies, move generator generates possible moves; it encodes the rule of the game, judging which moves are legal and which moves are not. If move generator encodes the rule, evalution function encodes the "intelligence"; it is a function from the state of the game to some number. Usually, larger number means that the game is favorable to the player. But evaluation function doesn't need to be perfect; that's where tree search comes in. Tree search can "amplify" the minimal intelligence of evaluation function.

Because of such amplification effects, programming a board game AI is an eerie experience. When you program an unfamiliar game, it is a routine experience for your program to outperform you. It is more surprising since even the dumbest evaluation function can beat you. Often evalution function as simple as "substract the number of moves I can make from the number of moves the opponent can make" works surprisingly well. Notice that this function is not even game-specific.

In tree search, the program considers all moves I and the opponent can make to certain "depth", and passes resulting positions to evaluation function. The program assumes that the opponent tries to minimize the value of evaluation function, and tries to maximize the value of evaluation function after its move. The secret is that the program can examine a lot of positions quickly. In my case, the program searched to depth of 5 moves and examined millions of positions for a single move. This sheer quantity of positions compensate for poor quality of evalution function.

There are rich literatures concerning the programming of a board game AI. After all, people programmed computers to play chess as early as 1956. At this dawn of the programming, valiant programmers of Los Alamos laboratory programmed their huge cranking machine, which was actually less capable than cheap graphing calculators of today, to play a simplified version of chess on 6 by 6 board (see Wikipedia, Los Alamos chess). It won a game against a human who just had learned the game. We came a long way since then.