Null Move Assistance

Code, algorithms, languages, construction...
Post Reply
theturk1234
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm
Real Name: David Simalista

Null Move Assistance

Post by theturk1234 » Mon Mar 07, 2016 5:11 pm

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

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Null Move Assistance

Post by hyatt » Tue Mar 08, 2016 12:20 am

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.

theturk1234
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm
Real Name: David Simalista

Re: Null Move Assistance

Post by theturk1234 » Tue Mar 08, 2016 3:46 pm

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!

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Null Move Assistance

Post by hyatt » Tue Mar 08, 2016 8:01 pm

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...???

theturk1234
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm
Real Name: David Simalista

Re: Null Move Assistance

Post by theturk1234 » Wed Mar 09, 2016 3:36 pm

Thank you Bob!
I'll try this out as soon as I can.

Post Reply