by H.G.Muller » 20 Feb 2007, 12:34
I try to avoid any path dependence in the hash table completely, and I think I finally succeeded in finding a very simple way to do this:
For positions that have occurred in the game already twice, scoring them as a draw does not introduce path dependency, as the really are draws irrespective of path, the first time you encounter them in the tree.
If their scoring as a draw is dependent on an earlier occurence in the tree, though (i.e. they occur 0 or 1 time in the game), you have to be careful. What I do then is forbid hash probing of the second occurence and score the third occurrence in the tree as a draw.
So in particular there cannot be pruning based on the hashed score on a second occurrence, as the hash score was supposed to be a 'repetition-free' score, and thus not applicable to a state that is repeated. The search goes on beyond the second repetition (i.e. if the second occurrence was a leaf node, it receives evaluation if there are no better captures, etc.) There it will typically encounter only hash hits to positions that were already searched at much larger depth, from the first occurrence. Only the first move on the path between first and second occurrence will not be pruned by hash hits, as it is also a repetition.
This will remain true for larger depth: after reaching the second tree occurrence, the search can only retrace the path between first and second occurence, until it reaches the third occurrence. Every deviation will result in a hash hit with sufficient depth. The stored score of these positions will tell the search if it should continue to follow the path to the third occurrence, or if it is better to break the repetiton cycle.
Whatever it decides, the score of the second repetition will eventually be based on this. If either side finds it better to deviate, based on a hashed score, it will do so. If it is best for both to return to the position, it is a draw. Since all nodes on the path between second and third occurrence are (second) repetitions, their minimax score will not be stored in the hash (just as they were not probed either). Their earlier occurences on the path would overwrite such a hash anyway.
If the second occurrence receives the score, (draw or otherwise), this score is not hashed (the position being a repetition). But even if it is a draw, it is now not a path-dependent draw score, because it was based on the fact that this position was repeated later in the tree, not earlier. So if this score starts to propagate towards the root, it will not contaminate the positions below it (which are hashed) with path-dependence, even if it remains on the PV. So no path-dependent scores will ever be stored in the hash.
In summary:
* Do not allow pruning of tree-repetitions by hash hits
* Score positions that occurred twice in game or twice in tree before as draws (but not once game + once tree!).
The only disadvantage of this algorithm is that you need quite large search depth to recognize draws. If that bothers you, you can extend the search of a tree repetition by one ply. All moves lead to positons that were (or have to be) searched at least 4 ply deeper than the currently requested depth anyway, so even with extension the hash will satisfy the request. Only the move on the repetition path will thus be searched with this extension, and from there the next move on the repetition path, with its own extension. And so on, until the search has extended itself to the third occurrence, or saw a profitable point to break the repetition cycle before reaching that occurrence (by immediate hash hits).
I am not sure if such extensions are worth it. At least, before you are pretty sure that you don't want to deviate already before reaching the second occurence. So you might want to award such repetition extensions only if the remaining depth is at least 1 or two in the second occurence. If you do it at d=0, you might do a lot of such 'repetition verifications' on moves that lead to a repetition and happened to be sorted in front, before an alternative that could have been judged to be better without such a repetition verification, cutting the repetition move from the tree. An alternative would be to sort repetition moves (for the leading side) with the bad captures in the back.
