"No progress" and Graph History Interaction

[BB+]

One of the problems with trying to detect "no progress" in various endgames is the Graph History Interaction problem (GHI). The idea here is that many transposition table schemes do not contain "path" information, so if you reach a position in search at depth X, and then reach it again 10 ply deeper, the previous score will typically be used and thus you really won't realise that you've been doing nothing for 5 moves (note that the search "tree" is actually a graph). A similar consideration holds for repetitions. There are various ways to try to get around this, but most engines (for many different games other than chess) choose simply to ignore it [for instance, Campbell in 1985 indicated that in practise iterative deepening avoids many difficulties].

The last paper on the above linked GHI page seeks to solve this rigourously in a manner with sufficiently little overhead so that it is still practical. The main idea (from what I gather) is to ignore scoring information in any case where GHI might occur, but still to use the "best move" information to direct the search in such situations (this is called Kawano's simulation technique). One drawback is that it requires an extra 8 bytes (maybe 4 if you are willing to err occasionally) for each table entry to store the path info. [The authors are academics, and are more concerned with proof trees than general search, it seems, particularly for solving checkers]. For instance, the position after 1. e4 c5 2. b4 would be stored according to its "positional hash", and one field would be the "path information" hash. The position after 1. b4 c5 2. e4 is the same, and when looking this up, the "path information" hashes would be different, so the only information the search could use from the entry is that cxb4 is the preferred move (and so it should be searched first).

A variation of this might be to ignore the scoring information if the "path distance" is not the same (this requires care when multiple related root positions are searched, as in a game), which would likely be more efficacious for "no progress" than for repetitions. An advantage would be that this need only be one additional byte.

[BB+]

Beats me how the title got morphed into "pagress" -- should be "progress" of course...

[zwegner]

I came up with the same idea independently a few years later: http://talkchess.com/forum/viewtopic.php?t=21343

I can't get the PDF for the thesis to work though.

[BB+]

I can't get the PDF for the thesis to work though.

Really? I did. http://www.is.titech.ac.jp/~kishi/pdf_f ... thesis.pdf

[BB+]

I might say that, from my standpoint it was "no progress" (particularly fortresses) that brought this back to my mind. For instance, if you have a consistent +3.05 eval from depths 15-25 [and there are no captures and/or pawn moves in the PV], you can start to wonder whether you are just seeing the local maximum of PST/mobility as the evaluation point. Of course, if you take this too far, false positives of "fortresses" might occur (where you can win after ~25 moves of semi-understandable maneuvering), but then, you probably only want to be going down such a line if you have to do so.

For instance, a position from George Tsavdaris:

Only 1.e7!! draws all other moves lose.
OK this is too much for computers. They are standing helpless looking at this problem.
6N1/6p1/1B2P3/6r1/6Pk/5ppP/6P1/7K w - - 0 1

By putting a "no-progress" throttle at something like eval/16 per ply, the fortress becomes recognised, and it becomes reasonable to expect 1. e7 to be played. As Uri Blass (and likely others) have pointed out in similar situations, there are maximally 64^2 positions with the bQ/wB (and maybe another factor of 64 for the wK if you insist), but the GHI effect stops the hash from being all that useful in showing the draw. In contrast, as Fine #70 is a win, any GHI effects are less likely to preclude a solution from appearing.