Monday, November 22, 2010

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.