Jump to content
  • Advertisement
Sign in to follow this  
crypto_rsa

Null move questions

This topic is 3673 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I am currently struggling with null move heuristic implementation and I have a couple of questions. 1. Null move doesn't generate a cutoff whenever a regular search does, does it? If I understand it correctly, it generates a cutoff only if the current position is very strong for the player who is making the null move. 2. My implementation doesn't use negamax for various reasons, I use separate Min and Max routines. How does the code for null move differ? I think that instead of
...
if( nullMoveValue >= beta ) {
    return beta;
}
I would use
...
if( player == Max && nullMoveValue >= beta ) {
    return beta;
}

if( player == Min && nullMoveValue <= alpha ) {
    return alpha;
}
Is that correct?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by crypto_rsa
Hi, I am currently struggling with null move heuristic implementation and I have a couple of questions.

1. Null move doesn't generate a cutoff whenever a regular search does, does it? If I understand it correctly, it generates a cutoff only if the current position is very strong for the player who is making the null move.

You understand it correctly.

Quote:
2. My implementation doesn't use negamax for various reasons, I use separate Min and Max routines.

What are those reasons?

Quote:
How does the code for null move differ?

Mostly, it differs in that you have to write it twice, like everything else.

Quote:
I think that instead of

...
if( nullMoveValue >= beta ) {
return beta;
}


I would use

...
if( player == Max && nullMoveValue >= beta ) {
return beta;
}

if( player == Min && nullMoveValue <= alpha ) {
return alpha;
}


Is that correct?


That part looks correct, but you didn't post how you compute nullMoveValue. You want to make a 0-window search just to know if the value is above beta or not (in the max or negamax case), and you want to reduce depth by 2 or 3 plies.

I assume you are programming chess, right?

Share this post


Link to post
Share on other sites
Quote:
You understand it correctly.


Good :-)

Quote:
What are those reasons?


Mainly historical. At the time I started programming this I didn't realize that having separate routines is a bad idea. I am planning a rewrite but it won't be that easy and there is no time for it at the moment.

Quote:

That part looks correct, but you didn't post how you compute nullMoveValue. You want to make a 0-window search just to know if the value is above beta or not (in the max or negamax case), and you want to reduce depth by 2 or 3 plies.


I am using (beta - 1, beta) interval for the Max player and (alpha, alpha + 1) interval for the Min player, so I assume this is correct.

Quote:
I assume you are programming chess, right?


No, I am working on a Gobblet computer player. I have tweaked some settings and the version using null move seems to be more successful than the version without it. Anyway, thanks for your reply!

Share this post


Link to post
Share on other sites
One more question: If the null move heuristic is successful (it generates a cutoff) is it a good idea to store this upper/lower bound in the transposition table? I don't think so, because it is not a "true" result, just a guess based on shallower search.

Share this post


Link to post
Share on other sites
I suppose you could save it in the hash table. I don't do that in my chess program, but now that I think about it, it would probably work. The only complication I can think of is that it might interfere with not allowing more than one of two null-moves in a row, so it would be a little tricky.

By not saving this in the hash table I don't lose a whole lot of performance, since the position after the null move will be stored in the hash normally.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
The only complication I can think of is that it might interfere with not allowing more than one of two null-moves in a row, so it would be a little tricky.


Talking of which, I saw different opinions about this "rule" - some people suggest having several null moves in a row is not a mistake. What do you think?

Share this post


Link to post
Share on other sites
Quote:
Original post by crypto_rsa
Quote:
Original post by alvaro
The only complication I can think of is that it might interfere with not allowing more than one of two null-moves in a row, so it would be a little tricky.


Talking of which, I saw different opinions about this "rule" - some people suggest having several null moves in a row is not a mistake. What do you think?


I was convinced at one point that a maximum of two in a row was the right thing to do, and it has some features that avoid making mistakes in the presence of zugzwang, but I haven't thought about it in a long time.

Share this post


Link to post
Share on other sites
Does the null move method cause a significant (or at least noticeable) increase in the algorithm performance? I am not able to notice any difference. Maybe my implementation is wrong or it generally does not help much in my game (not chess).

Share this post


Link to post
Share on other sites
Quote:
Original post by crypto_rsa
Does the null move method cause a significant (or at least noticeable) increase in the algorithm performance? I am not able to notice any difference. Maybe my implementation is wrong or it generally does not help much in my game (not chess).

This varies a lot from game to game. In chess it improves performance a lot, but in some other games (e.g., checkers) it's useless.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!