Question on Null Move Pruning

[Michael Sherwin]

Okay thanks HG! But then what is right? Are both my null and zero window search wrong?

[hgm]

Sorry, my bad. I don't know what I was thinking. What you have is correct after all. The point is that in negamax the window bounds should be swapped and negated. In the node before null move you want the window to be {beta-1, beta}, so that fail high means >= beta. That means in the node after null move {-beta, -beta + 1}, as you have.

[Michael Sherwin]

Thanks HG for getting back to me! It took me a couple of days to figure it out and I was never really sure I got it right.

[jfern2011]

The arguments I pass in are -beta, -beta+1 so that the child node at the next ply sees the window [beta-1, beta]. Setting beta-1 as the input argument alpha (as HG suggested) gives you [alpha, alpha+1].

Cheers,
Jason

[Michael Sherwin]

The arguments I pass in are -beta, -beta+1 so that the child node at the next ply sees the window [beta-1, beta]. Setting beta-1 as the input argument alpha (as HG suggested) gives you [alpha, alpha+1].

Cheers,
Jason

So you are also saying that my code snippets are correct?

[jfern2011]

I agree with your first code snippet. I haven't yet studied how zero window search works, but it looks to me like you're trying to avoid a full window search if you can quickly determine that the search will fail low. If that's the case, then what you're doing makes sense conceptually, i.e. passing in a null window around the lower bound.

If we're currently in a min node, then its parent max node passed it [-beta, -alpha]. So when the min node calls Search(), its child max node will have [beta-1, beta], according to your code. However, this ends up being a null window around the upper bound, which is not what you want. So in your 2nd code snippet, I'd change -alpha-1, -alpha to -beta, -beta+1.

[Michael Sherwin]

I'll try it. However i'm not sure that is correct. But I will try your suggestion.

I tried it but it was much slower as though it was doing the verification search every time.

Let's think about this. I am only interested in finding out if this node is greater than alpha so beta should not be a consideration. So I pass alpha negated as usual as the next nodes beta. This has to be correct. So the only thing in question is this nodes beta should be lowered to alpha + 1 so -(alpha+1) would be correct. That is the same as -alpha - 1. Does that make sense? Gee I have a headache now. I'm glad i'm not the only one that has difficulty with this negamax algorithm!

[jfern2011]

[quote="Michael Sherwin"]I am only interested in finding out if this node is greater than alpha so beta should not be a consideration.[/quote]

I would argue that actually it is because with negamax, beta and alpha basically switch roles. Remember that negamax is just a fancy way of implementing minimax, where max nodes raise alpha and min nodes decrease beta. So for max nodes (in a minimax framework), a zero window search ought to be conducted around alpha and for min nodes, around beta.

BTW if you can educate me on properly quoting that would be awesome.

[Michael Sherwin]

I am only interested in finding out if this node is greater than alpha so beta should not be a consideration.

I would argue that actually it is because with negamax, beta and alpha basically switch roles. Remember that negamax is just a fancy way of implementing minimax, where max nodes raise alpha and min nodes decrease beta. So for max nodes (in a minimax framework), a zero window search ought to be conducted around alpha and for min nodes, around beta.

BTW if you can educate me on properly quoting that would be awesome.

"["quote"]" text "["/quote"]" but without the quote marks.

[petero2]

I am only interested in finding out if this node is greater than alpha so beta should not be a consideration.

BTW if you can educate me on properly quoting that would be awesome.

Your quote syntax is correct but you have to uncheck the "Disable BBCode in this post" checkbox (below the text editing area) before you submit your message.