Tuning PVS

[Aleks Peshkov]

AFAIK it is not uncommon to have different search functions with different selective and move ordering rules for PV and zero-window nodes.

Am I right with:
1) Only nodes with non-zero parent window need research.
2) PV-nodes in PVS are the only nodes that have to be searched with non-zero-window.
3) Zero-window node can become a PV-node only when its direct parent is a PV-node.
4) PV-node fail high means that research with raised aspiration window should start immediately. There is no good Principal Variation in that case and thinking time should be extended if timeout occured.
5) First child of a PV-node can fail high only if PVS was run with aspiration windows.
6) PVS research with raised aspiration window should begin with depth 1, but not with a number from where previous failed high occur.
7) PV-node null-move fail-high means nothing for pruning and need normal research anyway.
8) It is not common to use IID for zero-window nodes mainly because IID is redundant at ALL-nodes. IID iteration steps greater then 1 ply does not change this property.
9) I know there were attempts to recognize ALL-nodes and CUT-nodes and apply different selective and move ordering rules in each case. Anyone found a valuable gain in this approach?

[Pradu]

AFAIK it is not uncommon to have different search functions with different selective and move ordering rules for PV and zero-window nodes.

Am I right with:
1) Only nodes with non-zero parent window need research.

Yes

2) PV-nodes in PVS are the only nodes that have to be searched with non-zero-window.

I guess PV nodes are the only nodes you need to do a zero-window search on.

3) Zero-window node can become a PV-node only when its direct parent is a PV-node.

I don't think a zero-window node directly becomes a PV-node. It either fails high (CUT node) or fails low (ALL node). I guess it depends on your terminology by what exactly you mean by changing to a PV-node.

4) PV-node fail high means that research with raised aspiration window should start immediately. There is no good Principal Variation in that case and thinking time should be extended if timeout occured.

Not sure about time management and stuff because mine is crap, but yes it should work. If you had a perfectly safe alphabeta, you could assume that if you had a fail high, that it becomes the best move to play. I haven't done any tests seeing how often you get search instability at the root but I guess if it is really low, you could just assume the fail high move to become the best move to play.

5) First child of a PV-node can fail high only if PVS was run with aspiration windows.

Yes.

6) PVS research with raised aspiration window should begin with depth 1, but not with a number from where previous failed high occur.

You mean do IID for the re-search? I guess you don't need to do depth 1 as you already know the best move so far is because the failed high. Move ordering should be decent because all the CUT nodes failed low so they were entirely searched and all the ALL nodes failed high, so the "PV" you have so far gives a bounds update. However I'm not very familiar with IID so it might work but IMO, I don't think it's necessary.

7) PV-node null-move fail-high means nothing for pruning and need normal research anyway.

8) It is not common to use IID for zero-window nodes mainly because IID is redundant at ALL-nodes. IID iteration steps greater then 1 ply does not change this property.

Indeed move ordering doesn't matter on ALL nodes, unless one of the moves is capable of changing the bounds and cuts off. I suppose IID will be useful on CUT node when you don't have a best move.

9) I know there were attempts to recognize ALL-nodes and CUT-nodes and apply different selective and move ordering rules in each case. Anyone found a valuable gain in this approach?

Yes. By just assuming that the first move searched is the best one, prediction rates are quite high (usually >90% for CUT nodes): http://www.netlib.org/utk/lsi/pcwLSI/text/node351.html . To extend this to imperfectly ordered trees I guess you just have to allow for node types to change. This is what I use to get node types for imperfectly ordered trees.

[Aleks Peshkov]

I define 3 types of nodes in a PVS (NegaScout) algorithm:
a) PV-nodes -- are searched wide open window. PV-nodes are the one and only one that are a part of Principal Variation. The value of the last PV-node in principal variation is a value a whole minimax search tree.

b) ALL and CUT nodes. Nevertheless they are very numerous, all of them are bounded by zero-window search and non of them are very interesting, unless the nodes have to be researched as descendants of PV-candidate research. This type of nodes often pruned/reduced more agressively then type (a).

c) PV-candidate -- a child of a PV-node. When PV-candidate zero-window search is found to fail high upper-bound of the current PV score, PV-candidate node will be researched with open wide window and can potentially substitute current sibling PV-node and create a new chain of following PV-nodes. Triangular PV-array is keeping all PV-nodes and all current PV-candidates with their descendants.

No PV-candidates can become a PV-node in perfectly ordered tree, but in real search they are interesting because in PVS they are searched twice: as (b) first and as (a) again.

I am thinking about creating 3 different search functions for (a), (b), (c).

[Aleks Peshkov]

Search order of PV-candidate nodes is important, so IMHO it is practical to keep searched subtree size counters as a merit of move importance not only for root positions, but for all positions in a PV. An array of about 40 moves wide x 20 plies deep is not a huge memory waste.

[yoshiharu]

Search order of PV-candidate nodes is important, so IMHO it is practical to keep searched subtree size counters as a merit of move importance not only for root positions, but for all positions in a PV. An array of about 40 moves wide x 20 plies deep is not a huge memory waste.

At the moment I am giving a try to a connected idea: I define history counters as living on those PV or PV-candidate nodes you mentioned.
Meaning that they are updated only in those nodes.
My hope is, this should avoid tree search statistics which are too noisy, and if noise still occurs, I take it as an indicator that my engine is into deep water (well, murky at least...).
This is because I want to extract "positional" informations out of statistics (I view my engine more as a "computational tool").

Probably storing a more detailed information for every node (what you are advocating) could be a more complete description, I hope not too much.

Cheers, Mauro

PS BTW, the "reduced" history counters work well, for me