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?

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?

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!

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.

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

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.