A Tricky Position For Chess Programs

In Chess and Go and other games there are often multiple paths to the same position p. If a value v for p has already been computed while expanding the first path, storing v in a master hash table H at location H[h(p)] can save great amounts of time on later visits. Here is an overview of how hash tables are used in chess programs, and here is more on the Zobrist hashing scheme which is most commonly employed.

The problem comes when the program wants to store the value v' of a position p' for which the hash function h gives h(p') = h(p). Probing is possible but requires storing extra position-ID information alongside the value v, and takes more time. Speediest is just overwriting v by v', but what if the search comes back to p again, from some position r? Even if probing is done in clusters of four, as practiced by Fruit and related programs, a search through tens of millions per second for several minutes is bound to encounter five-way collisions.

If neither v nor v' is greater than all values v'' of other moves in position r, then the overwrite makes no difference. Some other move from position r will be chosen, and the collision does not affect the value v'' returned to the caller from position r. However, when v or v' is greater and thus becomes the value of position r, then it sticks out as a value to avoid for the opponent's choice in positions q that can lead to r. Thus hash errors will usually be "minimaxed away" within a few levels of the search. Indeed, a paper by Robert Hyatt and Anthony Cozzie---two authors of champion programs---showed that even a high rate of collisions usually has little effect on the playing strength. There is still only one case I know where a reproducible collision cost a high-level game by a major program.

It takes an unusual position with long, forcing lines to make hash collisions rise to the root. I came across the above position while analyzing the endgame of the pivotal second game of the 2006 world championship match between Veselin Topalov and Vladimir Kramnik, at the heart of the "Toiletgate" cheating scandal. Why is this position rife for collisions to propagate up the search tree? In brief, it has long, forcing lines, a horizon effect, a premature quiescence situation that inflates the values of some branches of the search, and direct attacking lines that get early bonuses for activity.

White has chased Black's King all the way down to White's own first row and has tied down Black's army. White is to play Move 74, and White's King wishes to find squares that don't allow diagonal checks from Black's Queen. Accordingly White plays 74. Ke7, and Black must temporize by giving check by 74...Rb7+, since any other move opens the floodgates. This is the main juncture in the experiment described in the post.

After 75. Kd6, checking with Black's Queen by 75...Qa6+? leaves Black with no more checks and a defenseless King after 76.Ke5. The move 75...Qb2 initially looks good to many programs, but White starts a decisive attack by 76.Qd3+ Ke1 77.Bg5! menacing 78.Bh4+ and swift mate. Hence Black must abjectly return with the Rook to cover the checkmate threat on the square c1, by playing 75...Rb1. This leaves White to play at move 76:

The horizon effect shows after White plays 76. Qd4+ Kc2 77. Qc5+, when Black's King cannot return to d1 because the square c3 has been vacated for a "Family Fork" by the Knight. So Black plays 77...Kb3 (77...Kb2 allows 78.Bd4+ winning) 78.Qb6+ Kc2. Here and later, White has the option of sacrificing by capturing Black's Rook to carry out that fork: 79. Qxb1+!? Kxb1 80. Nc3+ Kc2 81. Nxe2. At this point we have quiescence, meaning neither King is in check and there are no captures. If the program stops here, it will recognize that Bishop plus Knight is a winning advantage against a bare King, and score at least the face value 3.5+3.0 of these pieces in the standard "Pawns" units of chess programs, showing at least +6.50 advantage to White. However it is Black's move, and 81...Kd3! is a payback fork that regains either the Bishop or the Knight, leaving a position all programs know is completely unwinnable.

The "horizon" aspect is that White can postpone this reckoning by giving more checks first, e.g. 79. Qc7+ Kb3 80. Qb8+ Kc2, and further 81. Qc8+ Kb3 82. Qb7+ Kc2, without repeating the position. Until the search is deep enough to exhaust all such checking sequences, the bottom may come before ...Kd3 and mislead the path into propagating a White win. Black has no room to deviate. Finally White can instead start a dangerous attack by 76. Qd4+ Kc2 77. Qa4+ rather than 77. Qc5+.

As shown in my analysis file, Black must find ten harrowing moves in a row to survive. Nevertheless I have proved to my standard that this position is drawn, so that a computer should score at most a two-pawns-or-so advantage to White, since Bishop plus Knight worth 6.5 outpace a Rook worth 5.0. It should certainly not give White an advantage approaching 7.0, almost a Queen ahead, which correctly designates a win in all but a trace of contrived positions. And most of the chess programs themselves usually agree---!---except when particular hash-table settings lead them not to. This constitutes the anomaly.