Creating a chess engine (Part 2: Move search)

So in the first part we looked at the components of a chess engine. After 10 days of coding I now have a working chess engine. Its not fast enough yet and the evaluation function is still primitive, but it works and it does not make obvious blunders (the rating now is probably around 1400-1600 I would think) Part 2 will focus on how an engine searches for the best move. How does Rybka and Fritz find the best line? Part 3 - next time - will deal with the evaluation function of a position in details.

A chess engine chooses the next move by building a game tree of positions - see the image below (from wikipedia)

The root - the top node - is the current starting position and the leaves at the buttom are the resulting positions after 4 plys - i.e. 4 halfmoves (white, black, white, black for instance). The nodes in the middle layers are intermediary positions reached during the way to the resulting positions. How much is 4 ply - well, any state of the art engine can do 20 ply in less than a minute these days, so this is a fairly small tree.

How does the computer find the moves. Well, as you can see at the buttom the best possible position is given +9 (i.e. white is up 9 pawns) and the lowest is given +3 (white is up 3 pawns). So all positions in the example favour white - positions favoring black is negative numbers. Now, unfortunately we cannot just choose the path from the start to the +9 position, as black moves every other time and can prevent this. In fact - with best play from both players the best line is +6 (as indicated in the top node). 

You can see that there are two kinds of layers in the game tree - max and min. When it is whites turn to play we do a maxium of the next nodes - so 6 is the top because it is the maxium of 3,5,6. The node with 6 in the next layer is 6 because it is the minimum of 6 and 7 - remember it is now black's turn and with best play he will of course go for the position with a score of +6 instead of +7 as it is better for him to have +6 instead of +7. In the next layer it is again white's turn and you do a maximum. And in that fashion you continue down the tree until you reach the bottom and then the path is your best line! Now, in an actual implemenation this tree is built from the bottom up - i.e. starting with the bottom nodes and calculating backwards to the top.

Now, this game tree gets huge very fast. In chess you have on average about let us say 30 legal moves or so. So after 5 plys you have 30^5=24 million positions, after 7 plys you have 30^7 = 21 billion positions! So engines usually implement a lot of optimizing tricks. One such technique is alfa-beta search which cuts off a lot of nodes in the tree that you do not need to look at - in the picture these are marked with grey. You can read about this in detail in other places on the web - it gets a bit advanced and there are also even more advanced techniques than alfa-beta in order to cut down the search tree. 

Of course even if you can look 50 moves ahead you will not be good chess player if you do not know if a position is good or bad. That is the topic for next time - how to do the evaluation of a position. Right now my engine evaluates positions in a very simplistic way - but it can easily be improved. See you next time!