chessnegamax

Negamax: what to do with "partial" results after canceling a search?

I'm implementing negamax with alpha/beta transposition table based on the pseudo code here, with roughly this algorithm:

NegaMax():
1. Transposition Table lookup
2. Loop through moves
  2a. **Bail if I'm out of time**
  2b. Make move, call -NegaMax, undo move
  2c. Update bestvalue, alpha/beta but if appropriate
3. Transposition table store/update
4. Return bestvalue

I'm also using iterative deepening, calling NegaMax with progressively higher depths.

My question is: when I determine I've run out of time (2a. in the beginning of move loop) what is the right thing to do? Do I bail immediately (not updating the transposition table) or do I just break the loop (saving whatever partial work I've done)?

Currently, I return null at that point, signifying that the search was canceled before "completing" that node (whether by trying every move or the alpha/beta cut). The null gets propagated up and up the stack, and each node on the way up bails by return, so step 3 never runs.

Essentially, I only store values in the TT if the node "completed". The scenario I keep seeing with the iterative deepening:

  1. I get through depths 1-5 really quick, so the TT has a depth = 5, type = Exact entry.
  2. The depth = 6 search is taking a long time, so I bail.

I ultimately return the best move in the transposition table, which is the move I found during the depth = 5 search. The problem is, if I start a new depth = 6 search, it feels like I'm starting it from scratch. However, if I save whatever partial results I found, I worry that I'll have corrupted my TT, potentially by overwriting the completed depth = 5 entry with an incomplete depth = 6 entry.

Solution

  • If the search wasn't completed, the score is inaccurate and should likely not be added to the TT. If you have a best move from the previous ply and it is still best and the score hasn't dropped significantly, you might play that.

    On the other hand, if at depth 6 you discover that the opponent has a mate in 3 (oops!) or could win your queen, you might have to spend even more time to try to resolve that.

    That would leave you with less time for the remaining moves (if any...), but it might be better to be slightly short on time than to get mated with plenty of time remaining. :-)