In my current chess program I use transposition table hits with a depth >= the current depth to produce early fail high/low cutoffs (provided the score and bounds stored in the TT entry fit the bill of course).
This causes some search instability due to TT hits with a greater depth than the current depth. In other words, the entry with greater depth does not always contain the same move that would be chosen with a search at the current depth. It's very difficult to debug, but I suspect this sometime causes selection of inferior branches of the search tree due to branches being discarded via these higher depth TT cutoffs. My thinking is that a uniform depth analysis may find the discarded branch to be best and keep it in the PV. Once the higher depth is reached via uniform depth increments the value of the PV may be less than the lower depth search found it to be, but it could still be the best available line.
Does anybody have experience with this issue? Do some engines only use TT entries for cutoffs if the depth is equal to the current depth? Are there other solutions to this problem? Am I envisioning a problem that doesn't exist?
Z
Transposition table induced search instability
-
hyatt
- Posts: 1242
- Joined: Thu Jun 10, 2010 2:13 am
- Real Name: Bob Hyatt (Robert M. Hyatt)
- Location: University of Alabama at Birmingham
- Contact:
Re: Transposition table induced search instability
Nothing you can do unless you want to not allow "draft >= depth" and restrict it to "draft == depth".
The odious case is where you ponder the wrong move for a long time and fill the ttable with big draft entries but of the form "lower" or "upper" only. When your opponent makes a different move, you still get hash hits that can cause you to fail high with a deep-draft entry hit, but then the re-search will fail low because you are now on your own, that deep draft entry doesn't work because you changed alpha or beta. But it is correct to play such a move, even though you don't know how good it is.
The odious case is where you ponder the wrong move for a long time and fill the ttable with big draft entries but of the form "lower" or "upper" only. When your opponent makes a different move, you still get hash hits that can cause you to fail high with a deep-draft entry hit, but then the re-search will fail low because you are now on your own, that deep draft entry doesn't work because you changed alpha or beta. But it is correct to play such a move, even though you don't know how good it is.