Page 1 of 1

Null Move Assistance

Posted: Mon Mar 07, 2016 5:11 pm
by theturk1234
Hi all,

I have written a chess engine that is UCI functional and is reasonably strong. My question though is concerning null move pruning. I have not been able to get it to work despite many hours of work.
I think my main problem is that I am searching with the wrong bounds. I have heard of a "null move window" and a "zero width window". However, all examples of null move pruning are using Negamax. I am using two separate functions for search(SearchMin and SearchMax) and as such I cannot convert the null move windows in the examples to the appropriate windows in my two functions. I have tried in SearchMax: SearchMin(alpha, beta), SearchMin(alpha, beta - 1), and pretty much all other combinations. I even ran a tournament amongst all these versions and none of them were even noticeably stronger than the rest. I think I am using the wrong bounds but am correct with null move pruning in everything else. I know everyone is using Negamax these days, but surely some of you must have been in my situation before.

Your comments would be greatly appreciated!

David

Re: Null Move Assistance

Posted: Tue Mar 08, 2016 12:20 am
by hyatt
Null-move is comprised of two parts.

(1) you search with a null window, typically using {beta-1, beta)} for the bounds;

(2) you search with a reduced depth to limit the effort this expends. Most are now using R=3 or more depending on remaining depth.

If the null-move search fails high, you return beta immediately, otherwise you continue normally.

Re: Null Move Assistance

Posted: Tue Mar 08, 2016 3:46 pm
by theturk1234
Hi Mr. Hyatt,

Thanks for the help! I do have one more question though. Like I said in my original post, I'm using two different functions for my search(SearchMin and SearchMax). Your suggestion would seem to only work in a Negamax framework. How would I convert your parameters(beta-1, beta) to two different functions? I think they need to be two different sets of parameters, right? I think I should use beta-1, beta in SearchMax, but what do I do in SearchMin?

Thank you very much!

Re: Null Move Assistance

Posted: Tue Mar 08, 2016 8:01 pm
by hyatt
theturk1234 wrote:Hi Mr. Hyatt,

Thanks for the help! I do have one more question though. Like I said in my original post, I'm using two different functions for my search(SearchMin and SearchMax). Your suggestion would seem to only work in a Negamax framework. How would I convert your parameters(beta-1, beta) to two different functions? I think they need to be two different sets of parameters, right? I think I should use beta-1, beta in SearchMax, but what do I do in SearchMin?

Thank you very much!
The basic idea is that at any point in the tree, you are used to calling the search function that "changes sides" it would seem? If so, you do EXACTLY that, but with a reduced R, and a window of current beta - 1 and beta values. It would seem to me that in search max or search min, the same logic applies, except that for one you would use beta - 1, beta and for the other you would use alpha and alpha + 1...???

Re: Null Move Assistance

Posted: Wed Mar 09, 2016 3:36 pm
by theturk1234
Thank you Bob!
I'll try this out as soon as I can.