Project: Chess Playing Engine
I started playing chess when I was in first grade, played in my first rated game in second grade, and have since won four first place state titles and two national titles; even still I would've never known how to write an intelligent chess playing program... until 15-211. (Read about my chess career).
During the course's lectures on game trees, the lab assignment (a partner project for which we were given about 3 weeks) was to write a chess playing program in Java. We had covered a few relevant concepts in class, such as Alpha Beta pruning, the Minimax heuristic, and the NegaScout algorithm, along with a few chess-specific optimizations such as move-ordering and static opening books.
The idea behind the AI for a chess playing program is relatively simple. The first thing to code is a board evaluate function; as you might guess, this returns a number given a board position where higher numbers indicate a better board position for the calling player. Although there are many ways to incorporate positional advantages (such as past pawns) and disadvantages (such as doubled up pawns), the main component of this evaluator was to account for all of the pieces on the board. For instance, some people use the following table to roughly gauge how many points, relatively, each piece is worth. Note that all of the values are multiples of 100 so that positional advantages and disadvantages (which have much smaller impacts) can also be factored into the evaluation score without having to resort to floating point values.
| Piece | Value |
|---|---|
| Pawn | 100 |
| Knight | 250 or 300 |
| Bishop | 300 or 350 |
| Rook | 500 |
| Queen | 900 |
After writing a board evaluator, the program was able to come up with a virtual game tree and, given certain time constraints, select the best move it sees. More specifically, the "best move" in a position is the move which minimizes the value (to the opponent) of the opponent's "best move" from the new board position. As you can see, because of the recursive definition of the best move, our programs would have to look ahead a few moves during each turn, anticipating what the opponent might do.
