"No progress" and Graph History Interaction
Posted: Sun Jan 23, 2011 10:16 pm
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.
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.
