Memory-PV-Search
Posted: Sun Mar 13, 2011 8:44 pm
search". It would take some time to implement it. Also the algorithmic
concept is not yet complete and needs to be elaborated.
My thoughts are the following:
1. There are relatively few PV nodes. Even fewer of them are close to
the root. This would allow to keep a large portion of the PV nodes in
the memory. I am not talking of the transposition table or similar. I
am talking of keeping everything, i.e. a tree containing all PV nodes
that are close to the root.
2. Changes in the PV are expensive (take a lot of time in
search).
Suppose at depth 1 to 16 move A is the best. All other moves fail
low. At depth 17, a tactical refutation of move A is found, so we have
to go for an alternative. But as all the remaining moves have always
failed low, they are hardly sorted. Suppose the last of these moves,
Z, is the best. A conventional search will search them all with depth
17 immediately.
Sure, there is internal iterative deeping. But this first searches
move B with depth 1, 3, 5, ..., 17, then searches move C with these
depths etc. It would be better to search all moves B, C, ..., Z with
depth 1, then all of them with depth 3 etc. This way, move Z could go to
an early position at a low depth, and we could use cutoffs at larger
depths for the other moves B, ..., Y.
This means that at a PV node, we should remember for each of the
children the largest depth D for that it was searched as a PV
node. Maybe we should additionally remember the scout search values
for each depth. If A's value has dropped and B fails high, resume
searching of B at depth D+1.
3. An additional problem are search extensions that are only done in
the PV, and pruning techniques (namely bad pruning) that are only done
outside the PV. This means, that depth d for move A is not comparable
to depth d for move B.
Suppose A leads to few extensions. That means, you arrive at large
search depths soon. (Further moves have pruning and no extensions
outside PV, so they normally take much less time than A.) At some
depth, the scout search reports that B is better than A, so we start a
PV search for B. But B leads to many extensions. Before B actually
becomes PV, the PV search must finish. But because of the extensions,
this takes a very long time. Users have reported positions where
Onno virtually hangs at some depth, that means after arriving at depth
d quickly and seeing that move A is bad at depth d, Onno does not
update the PV with move B for hours.
The suggestion in 2. would make an engine search not just B but also
C, D, ... But this alone does not help. We would also have to update
the PV earlier. I do not yet have an idea how to do this.
4. All of above might be possible without keeping a tree of PV nodes
in memory. But when the PV switches and switches back, it is certainly
good to have the old PV nodes still in memory. Based on the node
counting by type I think that this is possible for PV nodes that are
close to the root.
concept is not yet complete and needs to be elaborated.
My thoughts are the following:
1. There are relatively few PV nodes. Even fewer of them are close to
the root. This would allow to keep a large portion of the PV nodes in
the memory. I am not talking of the transposition table or similar. I
am talking of keeping everything, i.e. a tree containing all PV nodes
that are close to the root.
2. Changes in the PV are expensive (take a lot of time in
search).
Suppose at depth 1 to 16 move A is the best. All other moves fail
low. At depth 17, a tactical refutation of move A is found, so we have
to go for an alternative. But as all the remaining moves have always
failed low, they are hardly sorted. Suppose the last of these moves,
Z, is the best. A conventional search will search them all with depth
17 immediately.
Sure, there is internal iterative deeping. But this first searches
move B with depth 1, 3, 5, ..., 17, then searches move C with these
depths etc. It would be better to search all moves B, C, ..., Z with
depth 1, then all of them with depth 3 etc. This way, move Z could go to
an early position at a low depth, and we could use cutoffs at larger
depths for the other moves B, ..., Y.
This means that at a PV node, we should remember for each of the
children the largest depth D for that it was searched as a PV
node. Maybe we should additionally remember the scout search values
for each depth. If A's value has dropped and B fails high, resume
searching of B at depth D+1.
3. An additional problem are search extensions that are only done in
the PV, and pruning techniques (namely bad pruning) that are only done
outside the PV. This means, that depth d for move A is not comparable
to depth d for move B.
Suppose A leads to few extensions. That means, you arrive at large
search depths soon. (Further moves have pruning and no extensions
outside PV, so they normally take much less time than A.) At some
depth, the scout search reports that B is better than A, so we start a
PV search for B. But B leads to many extensions. Before B actually
becomes PV, the PV search must finish. But because of the extensions,
this takes a very long time. Users have reported positions where
Onno virtually hangs at some depth, that means after arriving at depth
d quickly and seeing that move A is bad at depth d, Onno does not
update the PV with move B for hours.
The suggestion in 2. would make an engine search not just B but also
C, D, ... But this alone does not help. We would also have to update
the PV earlier. I do not yet have an idea how to do this.
4. All of above might be possible without keeping a tree of PV nodes
in memory. But when the PV switches and switches back, it is certainly
good to have the old PV nodes still in memory. Based on the node
counting by type I think that this is possible for PV nodes that are
close to the root.