null move

[flok]

Hi,

Regarding null moves. I noticed that my chess program fails horribly when null moves are enabled. E.g. doing moves like a2-a3 or h2-h4.
I would like to describe what I'm doing, maybe someone spots the problem?

My chess program has a search(depth, color, alpha, beta) function. Furthermore it has an evaluate(color) function which returns the score of a position seen from the `color' point of view.
While doing a search, it calls itself with

Code: Select all

score = -search(depth - 1, opponentColor, -beta, -alpha)
if (score > bestVal) { bestVal = score; }
if (score > alpha) { alpha = score; if (score > beta) beta_cutoff = true; }

bestVal is the score that is eventually returned by the search() function.
So far so good.

Now for the null-move.
First I check if depth > 3 (e.g. there are more than 3 moves left before we enter quiescence search, I also check for being-in-check-status), then I invoke search:

Code: Select all

score = search(depth - 3, color, beta - 1, beta);

So I invoke it with the current color and a very small window
I don't negate the values because (and I'm not sure about this) the search is invoked with the current color (e.g. not the opponent).
Then, I do:

Code: Select all

if (score > beta) { beta_cutoff = true; bestVal = score; }

So no updating of alpha/beta or bestVal when there's no beta-cut-off.
I also don't update the transpositiontable because it is an incomplete search.

Any ideas?

regards

[hgm]

Code: Select all

score = search(depth - 3, color, beta - 1, beta);

This should be

Code: Select all

score = -search(depth - 3, opponentColor, -beta, -(beta-1));

The null move is not different from any other move as far as that after it the opponent is on move (and so all scores have to be negated, and alpha and beta swapped).

What you wrote does not do a null move at all: it leaves the same side on move, and will search exactly the same moves as you would be doing in the current node, except at lower depth. It is a wrongly (and inefficiently) implemented form of Internal Iterative Deepening, where you would decide that if a reduced-depth search fails high, you take that as a fail high for the full-depth search, rather than as an indication you should try the move that caused it first in the full-depth search. Note that in your code search() will keep on calling itself with depth lowered by 3 more until no depth is left, so that effectively you would never search more than 1 or 2 ply deep in any cut node.

[flok]

Thanks but I don't understand it: the null move was about skipping a move (and then searching with reduced depth), right?

[hgm]

The null move is about passing your turn. That means bringing the other side on move. Your code did not skip anything. The call to search() does exactly the same as what the node should do anyway, except at lower depth.

[flok]

Oh right so you mean that the null-move should do:

Code: Select all

int search()
{
    if (null_move_allowed) {
        // do null-move
        search()
    }

    if (!beta_cut_off) {
       for(int i=0; i<n_moves; i++) {
            search()
            // etc
       }
    }

    return bestVal;
}

[hgm]

Exactly. So the null move sort of symbolizes an arbitrary quiet move, of which you can be sure that it did not initiate any delaying tactics.

This is why you can afford a lower depth on it. When you would search a real non-capture in that node, say a Knight move, there always is the risk that this Knight move attacked the opponent's Queen, which he then has to rescue first before he can start to cash the threat he has waiting for you. So you would have to search 2 ply deeper to see that same threat as what the null move needs to see it.

An unnecessarily deep search on the null move would just make you aware of threats that then seem solved by one of the real moves that in fact only delays it without solving anything. This is actually the true problem near the leaves: the null move will accurately identify threats, but some of the real moves then falsely seem to solve them, while in reality they only delay the inevitable.

[flok]

Ah right. I was actually doing that, only a bit different implemented:

Code: Select all

int search() {
   int bestVal = -infinite;

   bool beta_cut_off = false;
   for(int i=0; i<n_moves; i++) {
      if (null_move_allowed) {
          int temp = search(my_color, beta - 1, beta);
          if (temp >= beta)
             beta_cut_off =true;
      }

      if (!beta_cut_off)
          score = search(opponent_color, -beta, -alpha);

      etc.
    }

    return bestVal;
}

[hgm]

That is NOT "a bit different implemented". It is doing something completely different (because you call search with my_color instead of opponent_color), implemented in a horribly inefficient way. You would make the first search again and again for every move, while nothing in it actually depends on the move.

[flok]

I don't understand what you mean.
I don't see why it is the same search every time because the position would be different everytime.
In my example code-fragment I did not add the do/undo for brevity. Or do you means something else?

Code: Select all

int search() { 
   int bestVal = -infinite; 

   bool beta_cut_off = false; 
   for(int i=0; i<n_moves; i++) {
      do_move();
      if (null_move_allowed) { 
          int temp = search(my_color, beta - 1, beta); 
          if (temp >= beta) 
             beta_cut_off =true; 
      } 

      if (!beta_cut_off) 
          score = search(opponent_color, -beta, -alpha); 

      etc. 
      undo_move();
    } 

    return bestVal; 
}

[flok]

I don't understand what you mean.
I don't see why it is the same search every time because the position would be different everytime.
In my example code-fragment I did not add the do/undo for brevity. Or do you means something else?

Code: Select all

 
int search() { 
 int bestVal = -infinite; 

 bool beta_cut_off = false; 
 for(int i=0; i<n_moves; i++) { 
  do_move(); 
  if (null_move_allowed) { 
   int temp = search(my_color, beta - 1, beta); 
   if (temp >= beta) 
    beta_cut_off =true; 
   } 

   if (!beta_cut_off) 
    score = search(opponent_color, -beta, -alpha); 

   etc. 
   undo_move(); 
 }

 return bestVal; 
}