Fixing the repetition detection hash table

Currently I try to speed up iCE a bit and investigate where iCE spends its time, yeah I'm profiling it a bit. One of the functions that used more than it should was the calculateRepetitions() function.

This function is used to determine whether this position was encountered before so a 3fold repetition is likely. The function has to parts, whenever a new position is entered it increments for this position (zobrist key & size_of_hash -1) a counter in a small hash table by 1 and then checks the value of the counter. If it is now 1 this means it was 0 before and we have never seen this position before. We can be sure this position is not repeated and exit. If the counter is 2 or more we might have a repetition or a hash key collision (we don't know). We now scan through the list of previous positions up to the latest non reversible move. This takes a bit longer.

When we unmake a move we decrement the counter in the hash table. This means the hash table is always almost empty. It only takes 1 slot for every real move on the board + 1 slot for every ply of search.

To see why this function takes so long despite its hash early exit I measured how many early exits I take and how often I scan through the list of keys after all. To my surprise I only had an early exit rate of at most 20% and in longer searches it went down to 10%.

How could that be ?

I looked at the content of the table and it contained negative values, it was full of them. This should not have happened. It is of course not possible to encounter a position less than never.

It turned out that I introduced an inconsistency when I added Null Move. I did not increment the hash slot when doing a Null Move but I decremented it when I undid the Null Move. So after a while most of the slots contained negative values and provided no value anymore.

After fixing that my early exit rate went up to 99,95% and calculateRepetitions() went almost into non existence in my function profile list.

iCE is a winner in the local newspaper chess study challenge

Our local newspaper organizes once a year a local chess challenge with 1 chess study a week (5 in total) of increasing difficulty. Me and my engine were taking part this year and with a bit of luck we were the lucky winners of the 3rd challenge, a really nice Mate in 4 problem.

Mate in 4, Study by Frank Fiedler

White must take care not to stalemate the black king, so the rook must be blocked in its mobility for a moment. The correct solution is 1. Rh4 !

iCE 0.3 v2058 by Thomas Petzke
position fen 2b5/1p1p4/1P1P4/ppBP1B2/k2p1R2/N2P4/K1P1P3/8 w - - 0 1
go depth 10
info depth 1 seldepth 7 time 0 nodes 72 pv c5d4  nps 71999 score cp 1526
info depth 2 seldepth 8 time 0 nodes 186 pv c5d4 b5b4  nps 185999 score cp 1510
info depth 3 seldepth 10 time 0 nodes 813 pv c5d4 b5b4 nps 812999 score cp 1518
info depth 4 seldepth 12 time 16 nodes 1894 pv c5d4 b5b4 nps 118375 score cp 1507 
info depth 5 seldepth 18 time 15 nodes 6381 pv c5d4 b5b4  nps 425400 score cp 1531 
info depth 6 seldepth 20 time 63 nodes 13244 pv c5d4 b5b4 nps 210222 score cp 1629 
info depth 7 seldepth 28 time 94 nodes 53632 pv c2c4 b5b4 nps 570553 score cp 1660 
info depth 8 seldepth 41 time 156 nodes 289838 pv f5g4 b5b4 nps 1857935 score mate 5 
info depth 9 seldepth 9 time 125 nodes 375331 pv f4h4 b5b4 f5g4 b4a3 c2c4 d4c3 g4d7  nps 3002648 score mate 4
bestmove f4h4 ponder b5b4

So as iCE really needs a hardware upgrade, I'm running and developing it on a 6 year old desktop PC which must be replaced urgently the prize money of 30€ might earn it an additional GB of RAM in the new system.

New compiler and an old bug

I just installed gcc 4.6.2 and gave it a try on my sources to see whether it performs better than old gcc 4.5.2 I'm currently using. The sources compiled without any problems (I did not include the Gaviota TBS support however) and to my disappointment it did not gave any speed improvement. It was also somewhat slower than the MS Visual C++ compiler, so probably slower than the Intel ICC as well.

However I noticed in one of the test positions a tiny node difference at higher plys between the MSVC compiled code and the code from gcc 4.6.2. This is always a bad sign because it indicates a bug.

So I did some research to spot the exact node where both editions start behaving differently and it turned out to be a problem in the KBKP evaluator. In one version the position was announced as DRAW and in the other not so from here on both versions produced different results.

So after I knew where to look for the problem, it was rather easy to find. I mixed a square value with a bitboard in a comparison operation and the result of that was random. So I fixed it and the search of gcc and the MSVC was identical again, but unfortunately identically wrong.

The old bug disguised a logical problem in the evaluator that became visible now, so I had to recode the KBKP module and I had to do a complete verification cycle against a table base again which took several hours. But now it is fixed and I improved the performance of the module significantly. I does a much better job in spotting the draws than it did before. It is now spotting 90% of all draws using a few known patterns

KBKP Recognizer Performance
Incorrect Evals :         0
Spotted   Draws : 6.355.575
Missed    Draws :   607.948
Spotted   Wins  : 1.248.570

The Lucena position in a King Rook and Pawn vs King and Rook endgame

After spotting the draws in the Philidor position I now wanted to enable to spot the Wins of the Lucena position. The Lucena position has the attacker king on the 8th rank in front of its pawn, which is not a rook pawn. The defender king is cut off from the pawn by own file or more by the attacker rook. The defender rook prevents the attacker king to leave the promotion square at one side.

The winning strategy from the Lucena position involves building a bridge with the attacker rook that shields the king from checks of the defender so the pawn can advance.

To teach the engine the rules of that positions is not so difficult. The tricky thing is the score that is awarded when this position is recognized.  When the score is to high the engine will play towards that position but then will try to stay in it. In order to win the attacker king must of course leave the promotion square which is then not the Lucena position anymore.

I decided to award a bonus worth the material of a pawn when the Lucena position or a position close to it is recognized. This seems to do the trick.

I tested the KRPKR module in a winning position with iCE 0.2 and iCE 0.3.


This is a typical position that you might encounter in a KRPKR endgame. White moves and this position is won for White. The only winning move is Rd4!

 White moves and Mates in 29 moves. 1. Rd4 !

I searched this position allowing both engines 60 seconds for the move. Both engines found the winning move almost instantly however when analyzing the output iCE 0.3 understands the position as winning where iCE 0.2 has no clue and just awards a better score for the more advanced pawn.

iCE 0.2 (reaching 18 ply in 60 sec)

info depth 2 seldepth 3 time 0 nodes 150 pv b4d4 c6h6  nps 150000 score cp 44 

info depth 18 seldepth 34 time 16094 nodes 25335132 pv b4d4 c6e6 ...  nps 1574197 score cp 94

iCE 0.3 (reaching 19 ply in 60 sec)
info depth 2 seldepth 3 time 0 nodes 160 pv b4d4 c6c1  nps 159999 score cp 47
info depth 17 seldepth 32 time 8391 nodes 12690308 pv b4d4 c6h6  nps 1512371 score cp 97
info depth 18 seldepth 32 time 9921 nodes 13093163 pv b4d4 c6h6  nps 1319742 score cp 205
info depth 19 seldepth 35 time 16219 nodes 21335820 pv b4d4 c6h6  nps 1315483 score cp 205

At ply 18 iCE 0.3 spotted the possibility to reach the Lucena position and awarded the bonus of 100 cp therefore the sudden rise in its score. When looking at the moves iCE thinks that will be played it reaches this position

White moves and Mates in 22. e7 !

The line of play iCE calculated is not optimal but forcing towards a closer win. This position is the position from the 18 ply search that was already awarded with the bonus. The Lucena position is not yet reached but the engine understands that Black is not able to prevent it anymore.

After 1. e7 Re1 2. Kf7 Rf1 3.Ke8  we are finally there

The Lucena position ! Black moves and loses in 19. (Ra1)

After 3. ... Ra1 iCE has no problem calculating the remaining moves

info depth 8 time 93 nodes 134444 pv d4d2 a1b1 d2d8 b1f1 d8c8 c6b5 nps 1445634 score cp 215
info depth 9 time 422 nodes 574486 pv d4c4 c6d6 c4f4 a1a7 f4f6 d6e5  nps 1361341 score cp 413
info depth 10 time 313 nodes 421256 pv d4c4 c6d6 c4c2 a1b1 c2f2 b1h1 e8d8 h1d1 e7e8q nps 1345865 score cp 990

In less than 1 sec it sees the queening of its pawn and raising the score.

So it seems I was able to teach the engine a fundamental chess lesson. Giving it access to a table base would probably be easier but also less fun and so I did learn my chess lesson too as I had no clue about the Lucena position either till I started programming it.

The Philidor Position in a King Rook and Pawn vs King and Rook endgame

I just worked on fixing the errors in the King Rook and Pawn vs King and Rook endgame evaluation. This endgame is very common and is dominated by two fundamental positions. The Philidor position where the defender can draw and the Lucena position where the attacker can win.

As this KRP vs KR endgame contains more than 50% won positions it is very difficult to find patterns that rule out all the winning positions to be left with the draws. Here instead I try to find positive rules that mark the draw and announce a UNKNOWN if no rules match.  

To find those patterns the chess theory helps. The characteristics of the Philidor position are

•     the defending king is on the queening square of the pawn or adjacent to it
•     the opposing pawn has not yet reached its sixth rank
•     the opposing king is beyond the defender's third rank
•     the defender's rook is on the third rank

Draw

My first unverified version of the patterns was very buggy. I corrected the patterns and added also some rules when the attacker pawn is not very advanced. The engine has now a good understanding of the Philidor position and will try to reach it when losing or try to prevent it when winning.

This is the final performance of the fixed code compared with the first version

                      iCE 0.2          iCE 0.3

Incorrect Draws :      83.061                0
Spotted   Draws :   1.551.216        9.012.914
Missed    Draws : 210.404.306      202.942.608
Spotted   Wins  : 271.313.885      271.396.946        

I now have to have a look at the evaluation of this endgame to spot the Lucena position and give it a higher score so the engine will play / exchange pieces towards it when winning.

KBNKN improvement and next step

I thought before I move on to the next step I try an early exit idea in the KBNKN recognizer. As the position is more likely a DRAW if defender king and knight have good mobility I added 2 rules (1 for black and 1 for white) that classify a position as DRAW if King and Knight have 4 or more safe squares to move to.

Those rules are on top of all the other rules, so if their conditions are met I get an early exit. Measurement shows that about 16% of recognizable draws are already recognized by the early exit rule. An additional benefit is that I get a slight improvement in the number of recognized draws as a small number of positions is now correctly announced as draw that would otherwise be announced as unknown because they are covered by one of the "not draw" patterns.

                          Old           New
Incorrect Draws :           0             0                                     
Spotted   Draws :  64.403.306    65.560.677
Missed    Draws : 117.746.021   116.588.650
Spotted   Wins  :  37.532.061    37.532.061

So this is enough now for KBNKN and I move on.

When I started with 5 man endgames I implemented a simple recognizer for KRPKR because I read this is the most common endgame of all and I wanted iCE to recognize the Philidor and Lucena positions. As I had no 5 man tablebase I was not able to verify whether the recognizer works correctly I just had some sample positions where it did.

I now checked it against the table base and its performance is terrible. It misses most of the DRAWs and has a 5% error rate where it announces a DRAW which is in fact not a DRAW. This requires definitely some immediate fixing. I hope it is not as difficult as the the previous one, having no knights certainly helps but then again having a pawn now on the board makes it more difficult.

Endgame King Bishop and Knight vs. King and Knight

All my latest efforts to improve the play of iCE went into mastering the endgame of King Knight and Bishop vs King and Knight. The theory does not say much about this endgame, obviously it is not interesting enough for human play and chess engine play it via table bases.

However I want to build some endgame knowledge into iCE directly so I tried to figure out some basic properties about it.

It seems overall it is drawish, so there are a lot of drawn positions. But there is also a significant amount positions that look drawish but are winnable by the stronger side. The line of play from those positions is sometimes not clear. So an engine without any knowledge of this endgame might easily move from a drawn into a lost position as it cannot tell the difference.

White moves and Mates in 101 !

Black moves and loses in 95 !

So it is very hard to tell whether a position is drawn or won. Some general principles for winnable positions are

• the attacker king is actively placed
• the distance between defender knight and defender king is big
• the defender knight is restricted in its mobility
• the attacker king is closer than the defender king to the defender knight

I then coded a module that detects dangerous patterns in a position. If a position does not contain any dangerous pattern it is a draw. A knight on the board makes patterns difficult and in this endgame 2 knights are on the board. So the pattern module is now a very comprehensive chunk of code, it took a lot of time to build it and it is far from perfect. It never announces a won/lost position as draw but does miss a lot of drawn positions.

Incorrect Draws : 0
Spotted   Draws : 64.403.306
Missed    Draws : 117.746.021
Spotted   Wins  : 37.532.061

So about a third of the drawn positions are recognized, two thirds are missed but this is as good as I could make it. The effort is still worth it in my opinion because if a draw is recognized search stops at this node cutting of potential huge sub trees that otherwise would have been searched. So there is still a significant savings potential.

I now have a neat little number of special endgame modules for different kinds of endgames. The code that forks the evaluation into one of this modules is a bit messy. I will clean that up and then I have to do some extensive testing whether those modules integrate correctly into search and evaluation.

More fun to come...