null move

[bob]

search(beta - 1, beta) <> -search(-beta, -(beta -1)) and -search(-beta, -(beta -1)) is correct or not ?

Please note that the color was not swapped at the point where search() was invoked for null-move and thus the negating not required (nor the negating of beta and swapping)

Yes, but that is BROKEN for null-move. You have to swap sides, otherwise you will try moves for the current side which is not what null-move is supposed to do.

[flok]

Hi,

search(beta - 1, beta) <> -search(-beta, -(beta -1)) and -search(-beta, -(beta -1)) is correct or not ?

Please note that the color was not swapped at the point where search() was invoked for null-move and thus the negating not required (nor the negating of beta and swapping)

Yes, but that is BROKEN for null-move. You have to swap sides, otherwise you will try moves for the current side which is not what null-move is supposed to do.

But if I swap sides, then I would not skip an opponent-move? Then it would be regular w/b/w/b/etc.

Please note that I do NOT do:

Code: Select all

int search() {
   // null move check
...
   for(moves)
     // regular checks

   return score
}

I do:

Code: Select all

int search() { 
 int bestVal = -infinite; 

 bool beta_cut_off = false; 
 for&#40;int i=0; i<n_moves; i++) &#123; 
  do_move&#40;); 
  if &#40;null_move_allowed&#41; &#123; 
   int temp = search&#40;my_color, beta - 1, beta&#41;; 
   if &#40;temp >= beta&#41; 
    nm_beta_cut_off =true;
    score = temp;
   &#125; 

   if (!nm_beta_cut_off&#41; 
    score = search&#40;opponent_color, -beta, -alpha&#41;; 

   etc. 
   undo_move&#40;); 
 &#125; 

 return bestVal; 
&#125;

[Henk]

I'm not sure what you're saying.

What happens:

- a for-loop iterating through all moves
- do move
- skip opponent color and do a reduced set with current color
- if null-move did not produce a beta-cutoff
- do a full search
- undo move

O I use for null move something like this
..
change player
val = -search (-ub, -ub +1)
change player
if (val >= ub)
return val;
..
where ub == beta

I don't know what

"skip opponent color and do a reduced set with current color"

means.

[hgm]

I'm not sure what you're saying.

What happens:

- a for-loop iterating through all moves
- do move
- skip opponent color and do a reduced set with current color
- if null-move did not produce a beta-cutoff
- do a full search
- undo move

The problem is that you clear beta_cutoff only outside the loop. So if one of the moves (say pulling your Knight back from f3 to g1) is refuted by a null move, beta_cutoff will be set, and prevent any other move to be searched. Even moves that fork a King and Queen, or deliver mate in one. The fact that there also was a worthless Knight move in this position, that happenend to be searched first, makes you also lose interest in capturing Queens and delivering mate. You won;t search them, which is equivalent to assuming they will fail low and won't affect the score of the node.

[flok]

I'm not sure what you're saying.

What happens:

- a for-loop iterating through all moves
- do move
- skip opponent color and do a reduced set with current color
- if null-move did not produce a beta-cutoff
- do a full search
- undo move

The problem is that you clear beta_cutoff only outside the loop. So if one of the moves (say pulling your Knight back from f3 to g1) is refuted by a null move, beta_cutoff will be set, and prevent any other move to be searched. Even moves that fork a King and Queen, or deliver mate in one. The fact that there also was a worthless Knight move in this position, that happenend to be searched first, makes you also lose interest in capturing Queens and delivering mate.

Yes, I've fixed that now. Thanks. It got worse now (almost all iteration depths give a2-a3) though Annoying because it keeps me from toying with the really interesting ideas (backport some ideas from pos).

It makes totally sense what you say but I'm trying to find out why Robert H. says it is still wrong. Or maybe he did not read the whole thread? @bob

[hgm]

He says that because it has not sunk in with him yet that your implementation moved the null move search to the parent node from where it is usually done (where all colors are flipped compared to the latter).

This is a bad idea, btw, for other reasons. For instance, it prevents that killers can be transferred from the null-move search to the real search, because your colors get out of phase. If there is a non-obvious non-capture that refutes the null move, you would like it to be preferentially tried against all alternatives for the null move as well, as many of these alternatives would not threat.

[bob]

Hi,

search(beta - 1, beta) <> -search(-beta, -(beta -1)) and -search(-beta, -(beta -1)) is correct or not ?

Please note that the color was not swapped at the point where search() was invoked for null-move and thus the negating not required (nor the negating of beta and swapping)

Yes, but that is BROKEN for null-move. You have to swap sides, otherwise you will try moves for the current side which is not what null-move is supposed to do.

But if I swap sides, then I would not skip an opponent-move? Then it would be regular w/b/w/b/etc.

Please note that I do NOT do:

Code: Select all

int search() {
   // null move check
...
   for(moves)
     // regular checks

   return score
}

I do:

Code: Select all

int search() { 
 int bestVal = -infinite; 

 bool beta_cut_off = false; 
 for&#40;int i=0; i<n_moves; i++) &#123; 
  do_move&#40;); 
  if &#40;null_move_allowed&#41; &#123; 
   int temp = search&#40;my_color, beta - 1, beta&#41;; 
   if &#40;temp >= beta&#41; 
    nm_beta_cut_off =true;
    score = temp;
   &#125; 

   if (!nm_beta_cut_off&#41; 
    score = search&#40;opponent_color, -beta, -alpha&#41;; 

   etc. 
   undo_move&#40;); 
 &#125; 

 return bestVal; 
&#125;

First thing you should always strive for is simple-to-understand code. It will always have fewer bugs, AND cause fewer bugs in the future when you forget your trickiness and change something. The idea looks barely workable, but what about hash table data? killer moves? history counters? Seems like a lot that will go wrong compared to the more natural "change sides and call negamax search the normal way, and if it fails high you return that value immediately."

[Rebel]

Yes, I've fixed that now. Thanks. It got worse now (almost all iteration depths give a2-a3) though

Maybe this will help. At the time I implemented null-move I kept the following logic in mind:

With nullmove you are moving twice in a row for the same given color with reduced depth. If this advantage (2 moves in a row) doesn't bring the score above alpha then the reduction is safe. However if the reduced search brings the score above alpha you need to research that node at full depth.

[flok]

I've bitten the bitter pil and rewrote things. I could throw away a lot of code. In the software development business that is an indication you're on the right track. Now the "funny moves" (a2-a3 and friends) no longer appear. Unfortunately fixing one of the bugs makes it a lot slower. Well we can't have it all I guess.

Code: Select all

info string cfg:
info string  no FORK_AT_FIRST_MOVE
info string     DO_PONDER
info string     THREADING
info string  no TRACE_THREADS
info string     USE_TT
info string     QUIESCENCE
info string     MAX_QUIESCENCE_DEPTH: 99
info string     NULL_MOVE
info string     MAX_NULLMOVE_DEPTH 1, NULLMOVE_JUMP_MIN 2, NULLMOVE_JUMP_MAX 3
info string     TPT_IO_BUFFER_SIZE 1048576
info string     VERY_BASIC_EVAL
info string     ASPIRATION_WINDOW_SIZE 75
info string     POLLING_TIMEOUT 250
info string     BOOK_WDL_MIN_HITS 12
info string  no WITH_MYSQL_BOOKS
info string     DEFAULT_HASHTABLE_SIZE 256
info string     AVERAGE_MOVELIST_SIZE 31
info string 2 thread groups
info string Embla v0.5 
info string info string initial move list size: 36
info string info string 12 threads
info string time: -10000, max depth: 7
info string current depth: 1, time left: -10.000391
info string move: e2-e3 (1), alpha/score/beta: -32767/30/32767, took 0.00/0.00, 14.60knps
info string current depth: 2, time left: -10.003377
info string move: e2-e4 (2), alpha/score/beta: -45/0/105, took 0.02/0.02, 28.03knps
info string current depth: 3, time left: -10.023053
info string move: e2-e3 (3), alpha/score/beta: -75/45/75, took 0.04/0.07, 105.23knps
info string current depth: 4, time left: -10.067544
info string move: e2-e3 (4), alpha/score/beta: -30/12/120, took 0.14/0.21, 258.02knps
info string current depth: 5, time left: -10.212027
info string move: e2-e3 (5), alpha/score/beta: -63/36/87, took 1.03/1.24, 359.44knps
info string current depth: 6, time left: -11.241942
info string move: e2-e3 (6), alpha/score/beta: -39/12/111, took 6.05/7.29, 455.39knps
info string current depth: 7, time left: -17.288668
info string move: e2-e3 (7), alpha/score/beta: -63/30/87, took 35.81/43.10, 514.08knps
info string nps 500608.692221 (q: 12466602, reg: 9108691, q limit: 0), total thread count: 258327, threads/s: 5993.92, qtt: 0, tt: 634607, nodes: 9108691, nullmove: 30455
info score cp 30
bestmove e2e3
info string TERMINATE
info string Terminating
info string Storing TT to .//regular.tpt.new
info string Moving temporary TT file to .//regular.tpt
info string 846354 TT entries written to .//regular.tpt.new in 1.028899 seconds
info string Embla terminating