How to correctly implement the null move heuristic when using normal minimax

[jauska]

Hi, I'm new here,

Just programming my first serious attempt at a chess engine, and I'm having a bit of trouble with null move pruning.
I've got my evaluation function set up so it's always relative to the player we started the search with, instead of alternating (negamax?) which is what I see in most of other people's code I've found (i.e. if at depth 0 it's black to play, +5 will mean a black advantage at any depth).

So from mediocre chess I found it implemented something like this:

Code: Select all

if(allowNull && !usingPreviousLine)
{
  if(!isInCheck(board))
  {
    board.toMove *= -1; // Making a null-move
    eval = -alphaBeta(board, ply-1-R, -beta,
                      -beta+1, localpv, false);
    board.toMove *= -1; // Unmaking the null-move

    if(eval >= beta) return eval; // Cutoff
  }
}

So I figured this wouldn't work in my case, because I never call alphaBeta with negation - the minimising player is always trying to reduce alpha and the maximising player is always trying to increase beta. So I guessed two things: the windows would have to be different for min and max nodes, and the cutoff condition should also vary.

So my code currently looks like this:

Code: Select all

if(allowNull){
      Move _nullMove = Move.nullMove(pos); // this inverts the player to move
      List bounds = isMaxNode?[beta, beta+0.01]:[alpha-0.01, alpha];
      List _nabm = abm(_nullMove.endPosition, player, !isMaxNode, depth - 3, stage + 1, bounds[0], bounds[1], false, false); // abm is alpha-beta-with-memory, one of those falses sets allowNull for the next node
      double eval = _nabm[0];
      if((eval >= beta && isMaxNode) || eval <= alpha && !isMaxNode){
        //print("null cutoff at ${isMaxNode?'max node':'min node'} ${pos.previousMove.name} depth: $stage, beta: $beta, eval: $eval");
        pos.eval = eval;
        return [eval];
      }
    }

In this form, it definitely doesn't break my engine, but I do get some unexpected cutoffs that I can't make much sense of, so I was wondering if anyone can see anything obvious that I'm missing here, or just some advice in general. I am quite new to this so please be kind

Thanks!

edit: this code is near the start of abm, after transposition table lookup but before normal search.

edit 2: also if anyone has any suggestions of open source chess engines that use the same evaluation pattern as me I would appreciate links!

[hgm]

It looks OK. Null move is not really much different from any other move; you want to know if it scores better than the 'good' side of your search window, and if it does, take a cutoff. The difference is that when it scores worse, you are not going to use the result at all. So that it is more efficient to also not ask the search to precisely determine that score, but collapse the window to the smallest possible width near its good side.

Virtually everyone uses negamax. By just adding 4 minus signs it reduces the rest of your program by a factor 2, by not having to have separate white and black code.

[Sven]

Your null window bounds might be slightly wrong, I would try to use these in your case:

[beta-0.01, beta] for max nodes
[alpha, alpha+0.01] for min nodes

With negamax, [-beta, -beta+1] is the result of negating and swapping [beta-1, beta].

[hgm]

Be careful, his score is floating point. So beta and beta - 0.01 are not adjacent, as in principle he can also get score beta - 0.005, So his seemingly generous windo setting is a necessity.

[Sven]

Be careful, his score is floating point. So beta and beta - 0.01 are not adjacent, as in principle he can also get score beta - 0.005, So his seemingly generous windo setting is a necessity.

That was not my point, it was about correct lower and upper bounds of his null window.

[hgm]

Sure, but I don't think what you propose is any more correct than what he already had. The point is that you cannot have a true null window when the score is a real number; alpha = beta is not allowed, as it would cause a self-inflicted cutoff, and for any alpha < beta there would always be numbers in between. So the best he can do to determine whether a score is >= beta is take a small window that includes beta, and whether that is [beta, beta+epsilon], [beta-epsilon, beta] or [beta-epsilon/2, beta+epsilon/2] is rather immaterial.

This is not really a matter of life and death anyway, as it is rather arbitrary how good you want the null move to be before you decide it isn't worth searching real moves to try to do better. E.g. when you would put the null-move window at [beta-5, beta-4], and have the node return beta when the null move returned a score >= beta-4, your engine will not be disastrously broken. It is not inconceivable that it would actually be stronger; the speculation that in a non-zugzwang situation at least one real move will be at least 4 score quanta better than the null move might backfire infrequently enough to not hurt more than the speed gain you obtained from extra null-move cutoffs gained you.

[jauska]

Sorry I didn't reply immediately, but yeah thanks a lot. I switched everything over to negamax and it's much easier to read. I was just having trouble getting all the minus signs in the right places the first time I tried it, but I've since changed how my evaluation works anyway so it just worked more or less immediately anyway.
I'm still having some problems but I'll make another post.