...
if( nullMoveValue >= beta ) {
return beta;
}
...
if( player == Max && nullMoveValue >= beta ) {
return beta;
}
if( player == Min && nullMoveValue <= alpha ) {
return alpha;
}
Null move questions
Author
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
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?
Author
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!
Author
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.
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.
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.
Author
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?
Quote:Original post by crypto_rsaQuote: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.
Author
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).
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
