In sunfish the main iterative deepening loop looks something like this:
Code: Select all
gamma = 0
for depth in range(1, 1000):
# Inv: lower <= score <= upper
lower, upper = -MATE_LOWER, MATE_LOWER
while lower < upper:
score = self.bound(pos, gamma, depth)
if score >= gamma:
lower = score
if score < gamma:
upper = score
# Option 2: Yield inside binary search
yield depth, self.tt_move.get(pos), score
gamma = (lower + upper + 1) // 2
# Option 1: Yield after depth completed
yield depth, self.tt_move.get(pos), gamma
The dictionary self.tt_move is the last move that failed-high at the root position.
(Let's assume for now that this was not overwritten by anything other than the outermost call to bound.)
The question is: If I run out of time in the inner loop, it means that I haven't finished searching the given depth, but only have an upper and lower bound on the score.
I could thus fall back to returning what was the best move after fully searching the previous depth (Option 2), or I could pick whatever is the tt_move when I run out of time.
Option 2 will produce a move that has been searched to a greater depth, but Option 1 will produce a move that didn't just randomly fail high because gamma was set way too low.
I'm tempted to use Option 1 because it seems safer. But in testing Option 2 was much stronger.
I've also considered counting how many codes each move has actually visited, trying to mimic Leela's search.
I couldn't find any discussion of this in the MTD paper or on the chess programming wiki.
Has anyone put more thought into it?
What do people use with Aspiration Windows?
