Patrice,
First, the definition of a node to make sure we are talking the same language.
A node is a position, a move connects one node to another.
I'll assume you are using PVS search as it makes it easier to promote a node.
The starting position is a PV node. The first move you search should connect to another PV node. In other words you would call the PV search if you have 2 different searches, or else identify it somehow as a pv node. The rest are non-pv nodes unless one of them fails high, in which case it is researched as a PV node. Does that make sense? When your search finishes and you return a PV, the moves in the PV will connect one "pv node" to another.
Then you have "cut nodes" and "all nodes." They are all non-pv nodes. That is a bit trickier but in Komodo we do something very simple - we count the distance from the last PV node and if it's odd it's a cut node, otherwise it's an all node. This works very well in practice because this is how it should be with perfect move ordering and if there are any exceptions it will trigger a cutoff which will set things straight again.
To clarify, the first node searched from a PV node other than the first (which is also a PV node) will be a cut node and then it toggles after that.
So really in Komodo we "expect" a node to be either a cut node or an all node and hence the language "expected cut node" and "expected all node." We treat the node as if we already know in advance even though you might get a cutoff in an all node.
Another distinction to make is that a PV node is also an ALL node meaning we expect to search all the moves. If you use an aspiration windows, you will get cutoffs at all nodes even with perfect move ordering but that's ok because of the research mechanism.
With PVS search you have a quick and dirty definition of a PV node. If the alpha/beta window is not zero width, it's a PV node, otherwise it's an all node. That only works if use PVS strictly, always search zero width if it's the second move or beyond and use the full range alpha, beta when you research.
There is no point in doing a re-search on fail high in non-pv nodes because the window will always be zero width anyway. It only makes sense if the beta you use during the search is less than the "real" beta.
Patrice Duhamel wrote:I'm not sure my code for PVS is correct.
In the PVS, we search the first move with a full window, then we use a null window for other moves and research if it fails...
But what to do at different nodes types ?
The full search for the first move must be done only at PV nodes ?
pseudo code :
Code: Select all
if ((first_move) && (nodetype == NODE_IS_PV)) {
score = -search(-beta, -alpha, depth - 1, NODE_IS_PV);
} else {
score = -search(-alpha - 1, -alpha, depth - 1, NODE_NOT_PV);
if ((score > alpha) && (score < beta))
score = -search(-beta, -alpha, depth - 1, NODE_IS_PV);
}
Thanks.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.