Building A Chess Computer Using Python

Simple Evaluation Heuristic¶

The first component is the evaluation heuristic. It is a simple one invented by Tomasz Michniewski. The so called simple evaluation heuristic consists of two parts: Simple piece values and piece-squared tables.

The piece values are the values the pieces have by simply existing. The easiest metric to see, which player is in front, is to count the pieces' values and compare it to the enemy's one. However, it is not only important how many pieces you have, but where they are located. This is where piece-squared tables come into play. They give bonuses for good positions and sanction bad positions.

I do not want to into detail how these values were examined. Checkout the paper to find out more.

Alpha-Beta Pruning¶

The second component is Alpha-Beta Pruning. A computer cannot evaluate all possible positions. Okay, maybe a big one with enough computational power and memory can do this, but not a computer everyone has at home. So the idea is to cut all branches of the game tree that seem not worth to evaluate them. This way, the computer is able to reduce the game tree and only evaluates the important moves and positions.

Move Ordering¶

Move ordering is the first enhancement of Alpha-Beta Pruning. Instead of randomly choose a position or move from the list of possible ones and evaluate it, the computer sorts them beforehand. The good news: Evaluating good moves and positions first, the Alpha-Beta Pruning can cut more branches and therefore can evaluate more positions in advance.

Quiescence Search¶

The second enhancement of Alpha-Beta Pruning is quiescence search. Let's suppose the computer reaches depth 8 and wants to evaluate the position, return everything and decide on the best move. What if the position is not a quite position? A quite position is a position, where no player can capture another player's piece. The idea is to check whether a position is a quite position and if not, go deeper into that branch.

This way, the computer is able to make even better decisions, even though it might loose one additional depth level.

Transposition Tables¶

The third enhancement we implemented are transposition tables. In chess there are many transpositions. Assume that player A can make a a1 on which the player B reacts with b1. Player A now can make an independent move a2 where player B reacts with b2. The two resulting sequences [a1, b1, a2, b2] and [a2, b2, a1, b1] are transpositions leading to the same position.

If the first sequence was already evaluated, it is good to store the result in a hash table. When the second sequence needs to be evaluated, the already computed result can be used instead of re-calculating it. This safes a lot of time!