An alternative means of PV recovery

[sje]

An alternative means of PV recovery:

A traditional A/B searcher can at times lose the tail portion of the predicted variation due to forward pruning caused by certain transposition table entry matches. One idea is to avoid transposition pruning at PV nodes and another is to use a separate transposition table for PV moves. In the new CIL Toolkit, I employ an alternative means.

This alternative means for PV recovery uses a pair (one per color) of binary trees. Each node in one of these trees is keyed by position hash and has a node value of the most recent PV move associated with the position key. At the start of the search, the trees are cleared. During the search the tree pair is updated with a new or revised entry whenever a PV move is discovered. At the end of each iteration, the tree pair is probed starting with the root position and continuing with successor positions (made by playing found PV moves) until a game over condition (draw/mate) is detected or until no more move probe matches are found. The moves found form the reconstructed PV.

This alternative is superior to the no-prune PV node method as it supports a smaller tree size. It is also superior to the separate PV transposition table method as it only uses as much storage as needed and there is no danger of overwriting causing a loss of information.

The only drawback of this tree pair method is that each access time is now O(log2 N) instead of O(1). However, in practice the number of distinct positions corresponding to PV moves is relatively very small and so the total time used to measure the tree pair access is almost too tiny to measure.

[sje]

Mea culpa, the above post should have been placed in the tech forum.

[bob]

An alternative means of PV recovery:

A traditional A/B searcher can at times lose the tail portion of the predicted variation due to forward pruning caused by certain transposition table entry matches. One idea is to avoid transposition pruning at PV nodes and another is to use a separate transposition table for PV moves. In the new CIL Toolkit, I employ an alternative means.

This alternative means for PV recovery uses a pair (one per color) of binary trees. Each node in one of these trees is keyed by position hash and has a node value of the most recent PV move associated with the position key. At the start of the search, the trees are cleared. During the search the tree pair is updated with a new or revised entry whenever a PV move is discovered. At the end of each iteration, the tree pair is probed starting with the root position and continuing with successor positions (made by playing found PV moves) until a game over condition (draw/mate) is detected or until no more move probe matches are found. The moves found form the reconstructed PV.

This alternative is superior to the no-prune PV node method as it supports a smaller tree size. It is also superior to the separate PV transposition table method as it only uses as much storage as needed and there is no danger of overwriting causing a loss of information.

The only drawback of this tree pair method is that each access time is now O(log2 N) instead of O(1). However, in practice the number of distinct positions corresponding to PV moves is relatively very small and so the total time used to measure the tree pair access is almost too tiny to measure.

There's an alternative as used in Crafty. Whenever I store an EXACT hash entry, which is not often, I have a second hash table where I store the path that connects that position to the endpoint backing up the terminal score. Then when I get a hash hit for an EXACT entry, I can tack this saved PV fragment on to the rest of the PV (leading up to this node) to reconstruct the entire PV. works well...

[sje]

There's an alternative as used in Crafty. Whenever I store an EXACT hash entry, which is not often, I have a second hash table where I store the path that connects that position to the endpoint backing up the terminal score. Then when I get a hash hit for an EXACT entry, I can tack this saved PV fragment on to the rest of the PV (leading up to this node) to reconstruct the entire PV. works well...

You are certainly correct that PV moves are rare in any search that has half-way decent move ordering. I was unsure of this until recently, so I instrumented the CIL Toolkit to expose the PV move detection process as a trace output to see exactly what was happening. And what was happening was that I didn't have to worry about my little tree pair growing out of control.

After I grafted the tree pair PV recovery scheme into the search I considered the idea of compacting the tree pair storage by tossing it altogether after each iteration and then building a new, minimal tree pair using only the already recovered PV. But this won't work! Why? Because the main transposition table is not cleared after each iteration and without the established data in the PV move tree pair, the same old PV chopping bug rears its head.

As for your approach, what does Crafty do if there's a collision when storing a new PV in the secondary transposition table? Who gets the boot, the earlier entry or the later one? Either way, it's possible that data critical for PV recovery may be lost.

[bob]

There's an alternative as used in Crafty. Whenever I store an EXACT hash entry, which is not often, I have a second hash table where I store the path that connects that position to the endpoint backing up the terminal score. Then when I get a hash hit for an EXACT entry, I can tack this saved PV fragment on to the rest of the PV (leading up to this node) to reconstruct the entire PV. works well...

You are certainly correct that PV moves are rare in any search that has half-way decent move ordering. I was unsure of this until recently, so I instrumented the CIL Toolkit to expose the PV move detection process as a trace output to see exactly what was happening. And what was happening was that I didn't have to worry about my little tree pair growing out of control.

After I grafted the tree pair PV recovery scheme into the search I considered the idea of compacting the tree pair storage by tossing it altogether after each iteration and then building a new, minimal tree pair using only the already recovered PV. But this won't work! Why? Because the main transposition table is not cleared after each iteration and without the established data in the PV move tree pair, the same old PV chopping bug rears its head.

As for your approach, what does Crafty do if there's a collision when storing a new PV in the secondary transposition table? Who gets the boot, the earlier entry or the later one? Either way, it's possible that data critical for PV recovery may be lost.

That can certainly happen. But with a large PV table, and given the small number of PV updates needed, it is rare enough that I don't notice it very often. Short PVs use to happen _very_ frequently without this assist...

[sje]

There was a minor bug in my first implementation of the scheme. The program had been updating the tree pair whenever a candidate PV move was detected. This was incorrect as it is possible for a candidate PV move to be invalidated when the same node later fails high. This allows bogus PV moves into the tree pair and this in turn can cause a bogus PV to be generated when the tree pair is probed.

To prevent this from occurring, the candidate PV move isn't stored in the tree pair until after the node is completed and is determined not to be fail-high. This forces a minor change at ply zero; instead of building a result PV from the root position, the PV is built from the position that appears after a candidate PV move is found and includes the candidate move (not yet entered into the tree pair) as its first move. This works because the scan at the root position is known to not being able to fail high.

[sje]

Aw, nuts. It looks like there's another bug and it appears to be related to an interaction between mate/lose scores and fail-soft value return. So for now there are still some truncated PV results although the score always comes back correctly. This needs more work.

[sje]

Clamping the score prior to its return seems to fix the latest problem. Maybe fail-soft is overrated?

Code: Select all

(defun clamp-score (my-score my-window)
  "Turn a fail-soft score into a fail-hard score."
  (cond
    ((<= my-score &#40;window-alfa my-window&#41;)
      &#40;window-alfa my-window&#41;)
    ((>= my-score &#40;window-beta my-window&#41;)
      &#40;window-beta my-window&#41;)
    &#40;t
      my-score&#41;))

[sje]

The program no longer gets a PV that's shorter than the iteration depth measured in ply, but the PV in some cases doesn't lead all the way to the position that generated the predicted score. So the code will be switched back to just avoid transposition pruning at potential PV nodes (all nodes without a zero width A/B window).