Null Move Assistance

Code, algorithms, languages, construction...

Null Move Assistance

Postby 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
theturk1234
 
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm

Re: Null Move Assistance

Postby 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.
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: Null Move Assistance

Postby 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!
theturk1234
 
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm

Re: Null Move Assistance

Postby 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...???
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: Null Move Assistance

Postby theturk1234 » Wed Mar 09, 2016 3:36 pm

Thank you Bob!
I'll try this out as soon as I can.
theturk1234
 
Posts: 7
Joined: Mon Mar 07, 2016 5:01 pm


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Yahoo [Bot] and 2 guests