Creating a chess engine (part 5: Endgames)

This part will focus on the most difficult part in modern engine design today in my opinion - endgames. While openings are covered by having opening books and the middle game is dealt with by the large search depth of engine (20-25 ply  - or 10-12 full moves) the endgames still pose problems. Yes, for sure we now have the 6-men tablebases covering all positions of 6 pieces on the board or less which computers can use to know wether a position is won, draw or lost with 100 % certainty (with 6 or less pieces). But many common (and complex) endgames have more than 6 pieces - such as King, Rook, 2 pawns vs King, Rook, 1 pawn totalling 7 pieces and the endgame tablebases are worthless. Many endgames are also very technical in nature and the large search depth does not really help if the engine does not know the technique. Furtheremore, there is the 50 move rule and the 3. time repetition draw rule that often comes into play in the endgames as well as zugswang and stale mate motives. So this area is really challenging in engine design. For instance doing a mate with bishop+knight vs king cannot be solved by search depth alone (at the current depths possible for engines) - there you need to know the technique (the W path knight stuff) so most engines have specialized code for that (or use a table base).

Most engines try to incorporate some special functions to deal with endgames. Often they will change the evaluation of the position - i.e. a king is usually more valuable in the center in the endgame, while in the opening/middle game you probably do not want your king in the center! So the engine will try to recognise the position and see if it is one of the endgame types that it has some special evalution code for and then execute it. Also usually an engine will have a list of endgames that are known to be drawish or known to be won for the stronger side. For instance opposite colored bishop end games are often very drawish. 

Also you can use a form of transitivity to determine if a position is won. For instance if you know that an endgame is won where the stronger part has a set of pieces, X, and the weaker part has a set of pieces, Y, then all other games where the pieces of the stronger part has at least X pieces and the weaker part has Y pieces are also won . An example would be that King+rook vs king is won - then you can infer that King+rook+pawn vs king is won and king+rook+bishop vs king is won and so on. This lets you build a pretty large collection of sets (X,Y), (X1,Y)...(Xn,Y) which you know are won. The engine can then evaluation any position that is included in one of the sets as a good position to reach. My engine uses this technique - it does not use the 6 men tablebases  (tablebases are not really any fun when you are a programmer - its just a huge database that you plug in - there is no challenge).

In general, the reason why endgames are still difficult for engines is because position evaluation is often more important here than raw search depth and as discussed in a previous part I do not believe engines are better at evaluating positions than super GMs. But no doubt - engines will probably catch up in this area. Since CPU power is increasing exponentially (Moores Law) it is probably only a matter of time before engines will also reign supreme in the end game. For sure, at some point in time we will have the 12 men-tablebase and that would cover pretty much all end-games. But it will take years and years  - I think the current estimate is that the 7-men tablebase is going to be finished around 2015....:-)