Question about PVS and nodes type

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Patrice Duhamel
Posts: 135
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

Question about PVS and nodes type

Post by Patrice Duhamel » Tue May 28, 2013 4:36 pm

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 (&#40;score > alpha&#41; && &#40;score < beta&#41;) 
			score = -search&#40;-beta, -alpha, depth - 1, NODE_IS_PV&#41;;
	&#125;
Thanks.

User avatar
hgm
Posts: 24025
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Question about PVS and nodes type

Post by hgm » Tue May 28, 2013 5:44 pm

In non-PV nodes the full window is a null window to start with. So it does not matter whether you use full window or null window for the first move in those nodes.

Patrice Duhamel
Posts: 135
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

Re: Question about PVS and nodes type

Post by Patrice Duhamel » Tue May 28, 2013 6:47 pm

So there is no need for a special case in non PV nodes ?
Except choosing the right node type when calling the search function for the first move.

bob
Posts: 20776
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Question about PVS and nodes type

Post by bob » Tue May 28, 2013 7:55 pm

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 (&#40;first_move&#41; && &#40;nodetype == NODE_IS_PV&#41;) &#123;

		score = -search&#40;-beta, -alpha, depth - 1, NODE_IS_PV&#41;;

	&#125; else &#123;

		score = -search&#40;-alpha - 1, -alpha, depth - 1, NODE_NOT_PV&#41;;

		if (&#40;score > alpha&#41; && &#40;score < beta&#41;) 
			score = -search&#40;-beta, -alpha, depth - 1, NODE_IS_PV&#41;;
	&#125;
Thanks.
You do exactly the same thing regardless of the node type. In fact, you don't even know the node type until AFTER the node has been searched...

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Question about PVS and nodes type

Post by Don » Wed May 29, 2013 12:01 pm

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 (&#40;first_move&#41; && &#40;nodetype == NODE_IS_PV&#41;) &#123;

		score = -search&#40;-beta, -alpha, depth - 1, NODE_IS_PV&#41;;

	&#125; else &#123;

		score = -search&#40;-alpha - 1, -alpha, depth - 1, NODE_NOT_PV&#41;;

		if (&#40;score > alpha&#41; && &#40;score < beta&#41;) 
			score = -search&#40;-beta, -alpha, depth - 1, NODE_IS_PV&#41;;
	&#125;
Thanks.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

Patrice Duhamel
Posts: 135
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

Re: Question about PVS and nodes type

Post by Patrice Duhamel » Wed May 29, 2013 6:28 pm

I understand, I thought PVS code need to be different at PV and non PV nodes, but I must have done something wrong when testing.
Don wrote: Then you have "cut nodes" and "all nodes." ...
I'm using only 2 types "PV nodes" and "non PV nodes", to use IID only at PV nodes, and disable null moves, LMR, and prunning at PV nodes.

Thanks.

Post Reply