Chess: Extracting the principal variation from the transposition table
Earlier, I was having an issue involving my principal variation becoming truncated by an alpha-beta search. Indeed, this appears to be a common issue. From the authors of Crafty:
Another solution with even worse properties is to extract the full PV from the transposition table, and avoid using the triangular array completely. If the transposition table is large enough so that nothing gets overwritten at all, this would almost work. But there is a hidden “gotcha”. Once you search the PV, you continue to search other parts of the tree, and you will frequently encounter some of those same positions again, but the hash draft will not be deep enough to allow the entry to be used. You continue searching and now have to overwrite that entry (exact hash signature match requires this) and you now leave a transposition “trail” to a different endpoint, one which does not match the original score. Or any one of the trans/ref entries between the root and the actual PV endpoint get overwritten by a different position completely, and you now have no way to search the transposition table to find the actual endpoint you want to display. Several use this approach to produce the PV, and the complaints are generally frequent and loud, because an evaluation paired with an unrelated PV is not very useful, either for debugging or for analyzing your own games.
This makes a lot of sense.
Consider that the principal variation is ABCDEF, but AB returns the board to its original position. Then, an alternative line examined later might be CDEFGH, which results in a different evaluation than the earlier search of just CDEF. Thus, the transposition table entry for the board state after AB is overwritten, potentially with a node that will be cut off by alpha-beta (!!), and the PV of ABCDEF is destroyed forever.
Is there any way around this problem, or do I have to use an external data structure to save the PV?
Specifically, what is wrong with replacing if and only if the new entry is deeper and exact? This doesn't seem to work, but I'm not sure why.
链接地址: http://www.djcxy.com/p/56336.html上一篇: 寻找AI在Gomoku中的举动
下一篇: 国际象棋：从转位表中提取主要差异