H.G.Muller
Joined: 10 Mar 2006
Posts: 12906
Location: Amsterdam
|
 Post subject: restartable nodes and the tri-angular array Posted: Wed Jul 11, 2012 7:58 am |
  |
|
Two things have always bothered me about search:
1) The root node is usually treated differently from other nodes, while logically it is like any PV node. So what is good for the root, (e.g. sorting on node count), should also be good for other PV nodes.
2) When I abort a search (e.g. ponder or analysis because there is input), restarting it does not perfectly resume it at the point where it was aborted. Hash hits go a long way towards that, but in a resumed search all nodes in the aborted branch could have different internal states, e.g. different move ordering if IID was used to order moves. (Plus that hash entries could have been lost.)
It seems both problems can be cured the same way, by somehow saving the complete state of a node when you leave it (i.e. includig its move list), so that it can be restored perfectly whenever you re-enter it. This of course means that the critical state info cannot be stored on the system stack, which is not safe after the instance of the routine returns, but could be overwritten. But I store moves on a software-maintained stack anyway, and a struct with other info could easily be put on there too.
The restart information for a node could then also be used when the node is revisited in a later iteration of the Iterative Deepening. It would not really have been 'aborted' in the previous iteration, of course, but you could view the normal return as an abort of an IID process, and resume that with the newly requested depth. That would especially make sense in a PV node, where you normally do IID, which could then make use of the complete info gathered in previous iterations on the move ordering.
So we want to save the node state for PV nodes and for the current branch (in case of an abort). The latter is automatic, as searching a branch would leave all instances of the nodes along it alive on the stack; we just have to refrain from deleting it when we abort the branch, and only do so when it becomes clear we would not want to resume (e.g. on ponder miss). The question is how to store this info for PV nodes.
One way to do that would be the old-fashoned tri-angular-array method that is normally used for storing the PV move. In stead of a move you would store the entire node state. Now an array with fixed-size elements is not very suitable for storing move lists, which could have highly variable size. But one can base it on the Fairy-Max implementation for storing the PV, which is logically equivalent to the tri-angular array, but uses a stack:
| Code: |
MOVE pvStack[LARGE];
MOVE *pvStackPtr = pvStack;
Search(alpha, beta)
{
MOVE *myPV = pvStackPtr;
*pvStackPtr++ = INVALID; // initialize empty best PV on top of stack
for(ALL_MOVES) {
MakeMove(move);
score = -Search(-beta, -alpha);
UnMake();
if(score > alpha) {
alpha = score;
if(score >= beta) break; // beta cutoff
// PV node; copy PV that was left just above stack top
MOVE *p = pvStackPtr; // remember PV 'returned' by daughter
pvStackPtr = myPV; // pop previous best PV
*pvStackPtr++ = move; // start with newly found best move
while( (*pvStackPtr++ = *p++) != INVALID ); // copy daughter PV behind it (leaves pvStackPtr at end of new PV)
}
}
pvStackPtr = myPV; // pop the best PV (but leave it just above the stack top so the caller can still fetch it)
}
|
This method does store all rows of the triangular array contiguously (separated by the INVALID sentinel). It could be used to store pretty much anything, i.e. stuff of any size. You just slam it onto the stack. So the statement to initialize an empty best PV might as well push the entire move list. (That is, the move generator run after it would just use the PV stack also as move stack.) You would not have to push that again when you find a move between alpha and beta; it would still be there. But of course finding such a move might require some reordering of the move list, (putting the move in front), which would be done in the usual way. In the copying process the state information of all the nodes would overwrite that of the PV that was just overturned. (If there are any pointers in that info, they should be made relative to the stack frame of the node, so that they can be moved in memory without losing validity.)
So basically it amounts to this: when you return from a PV node, you don't discard its state information (and move list), but leave it on the move stack, squeezing out the info of the PV that it is replacing from that stack. When you abort a node you would also not pop the node state from the stack. On starting a search you would 'follow the PV' in the usual way, as first thing you do on entering a node, but doing so now retrieves the complete state the node was in after you left it last time. So it effectively restarts the preceding search, each aborted node continuing where it was, and each completed PV node starting on a next-higher iteration like it was a root node (e.g. first sorting the move list based on the retrieved node counts for each move).
Is this a new idea, (and is it any good), or am I re-inventing the wheel (and is it a square one)? |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
restartable nodes and the tri-angular array