The horizon effect

After some weeks I spend time on the endgame table bases I went back to the engine search algorithms. I let it play some games against other engines and as usual it lost most of them. It is still pretty weak. But from watching the games I try to spot the areas were it is especially weak.

In one game it encountered the following position playing with White

rnbq1rk1/pp3ppp/3b1n2/1Nppp3/8/1P1BPN2/P1PP1PPP/R1BQ1RK1 w - - 0 8

Its time control allowed it a search 8 plys deep. It came up with the move Bb2 (and expecting black to play Re8 as response). Of course black did play e4-e5, forking the knight and the bishop with its pawn and White lost the game.

I tried to find out why White did make such an easy mistake and did not see this obvious threat. It is quite difficult to debug the recursive search algorithm, but at the end I think it lost because it pushed the threat e4-e5 beyond its search horizon of 8 ply.

I check what it calculated for the sequence 8. Bb2 e5. It showed 9. Nxd6 Qxd6 10. Be5 Qd7 11. Bxf6 as principle variation leading to the position

 rnb2rk1/pp2qppp/5B2/2pp4/4p3/1P1BPN2/P1PP1PPP/R2Q1RK1 b - - 0 12

This position was its search horizon and got evaluated. Quiescence search did not help because after black capturing the bishop white cannot make a winning capture and QS terminates.

So white was able to push the loss of the bishop or knight by the pawn fork beyond its horizon by playing a series of equal captures and played a weak move because of that.

How do I prevent this from happening again. I came up with 2 possible solutions. The first is to try to handle such threats like a pawn fork in the evaluation, but this might be difficult, the forking pawn must be protected if a bishop mover is forked in order for the fork to work. One of the forked pieces might move away and building up a threat that must be handled (e.g checking the opponents king), then the fork is also not a real threat because both pieces can move away.

The second is the implementation of a recapture extension, whenever a piece of the board is captured after it captured a piece of the same value (a recapture) search is extended one ply. This makes it more difficult for the engine to push something beyond its horizon with equal captures but it also slows down the search in general.

Probably I go for the 2nd option, I will post my progress in a later post then.

Making the 4 man endgame tables available to the engine

After finishing the KPKP end game table I thought it is time now to make them available to the engine. For that I wrote a endgame advisor class that is able to access the stored table information.

Whenever the engine encounters a position with 4 or less pieces it asks the advisor whether it has a known score for that position, and if the answer is yes, it takes its score as value for the position and terminates the search in that branch of the search tree.

To ask the advisor upfront is necessary because not all possible 4 man positions are available. So far I only generated the ones where each side has one piece left. All positions where one side has 2 pieces and the other side has none are not available yet.

Those positions are not particular interesting as in general they are easy to win. It does not seem to make a lot of sense to dedicate disk space or memory to a table like king and 2 queens vs lone king. However tables like king and 2 bishops or king, bishop and knight vs king might be interesting. Because they contain long sometimes hard to might mate sequences.

On the other hand those endgames are very rare in practice and probably the engine will never encounter one in an actual game.

So this concludes my work on the endgame knowledge. With the 3 and 4 man tables available my engine has now a cheap and very accurate endgame DRAW detection. It took quite some time and was an very interesting exercise to work with the tables.

I will not continue with 5 man tables. There are some very important ones, like king, rook and pawn vs. king and rook, but the time to generate the tables is too long and they require to much space. So I will not include them into the engine package anyway. Those positions my engine has to solve by calculating.

Success with the KPKP endgame table

After fixing all known problems with the king queen vs king pawn table I regenerated also all the king and piece vs king pawn tables so they are at least consitent.

I now proceed to the king pawn vs king pawn table. This is in a way special compared to the king and piece tables as with two opposite pawns on the board they possibility of "en passent" arises. All previous combination of 4 pieces did not have that problem.

To demonstrate this look at the following board

With Black to move White will win in 17 moves, so the value of that position is Mated in 17. But if the last move of white was f2-f4 then black can play g4 x f3 and wins in 11 moves (Mate in 11).

Unfortunately the table base has no history information of played moves because it is generated backwards from Mate positions. A clean solution would be to evaluate this position twice, with and without en passent possibility, but then you have to store whether you captured "en passent" or not as in the next iteration of retro table analysis the move generator may in case of en passent may only generate a single move (f2-f4).

This is quite tricky to implement as the data model so far does not allow the storage of a en passent flag. So I decided to implement a little hack here.

Whenever the move generator generates a move that will allow en passent captures for the opponent next turn (pawn double step with end position next to the opponent pawn) this move is deleted from the list of available moves and not considered in the analysis.

The assumption behind this is that a move that allows the opponent to capture the pawn will never be the best move, it is at most as good as another move from the list (e.g. the single pawn step move). This in fact seems to work quite well. The generated table is consistent and as far as I can tell correct.