Memory-PV-Search

[Onno Garms]

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.

[Gerd Isenberg]

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.

Hi Onno,

I am not sure what to say on all your posts to reveal your secrets, ideas and internals as a professional chess programmer. It has something final.

Anyway, thanks a lot for your contribution. I will certainly mention and cite your posts elsewhere.

Keeping nodes near the root in memory reminds me on some best-first searches like Conspiracy Number Search, which may use alpha-beta/PVS at it leaves.

Best Regards,
Gerd

[Gerd Isenberg]

I am not sure what to say on all your posts to reveal your secrets, ideas and internals as a professional chess programmer. It has something final.

I first missed your post in the general forum:
http://www.talkchess.com/forum/viewtopic.php?t=38403

Many thanks again and respect for your decision to stop the development on Onno and to reveal what made it stronger.

Gerd

[Onno Garms]

Keeping nodes near the root in memory

Without having tried (this was on my todo list) I would assume that PV/non-PV is a better criterion than distance to root. My plan was to keep only PV nodes in memory. If not all of them fit, restrict to PV nodes that are close to the root.

If you keep non-PV nodes in memory, you will not be able to do this for more than a few plies. But if you run statistics how many PV nodes there are, you will see that they are not many.

[Dann Corbit]

Keeping nodes near the root in memory

Without having tried (this was on my todo list) I would assume that PV/non-PV is a better criterion than distance to root. My plan was to keep only PV nodes in memory. If not all of them fit, restrict to PV nodes that are close to the root.

If you keep non-PV nodes in memory, you will not be able to do this for more than a few plies. But if you run statistics how many PV nodes there are, you will see that they are not many.

This is a good idea as relates to permanent hash.

I have about 1.5 million moves played frequently by very strong players {machine and human} that have been analyzed. Since a strong player made the move, it is a pv move. If we keep it in memory as a pv hash table element, then we can also gradually improve the permanent hash until it plays near perfect chess. Of course, that will take a very long time.

[Onno Garms]

This is a good idea as relates to permanent hash.

I have about 1.5 million moves played frequently by very strong players {machine and human} that have been analyzed. Since a strong player made the move, it is a pv move. If we keep it in memory as a pv hash table element, then we can also gradually improve the permanent hash until it plays near perfect chess. Of course, that will take a very long time.

Sorry, I don't understand what you want to say. (I even asked myself if your remark somehow ironic. Sometimes I am bad at detecting irony.)

I don't see a relationship between keeping the PV in memory (which is applicable to any position) and building a database of human games (which is applicable to known positions only).