idea: null-move analogy

[hgm]

Sometimes, in a superficially good position (i.e. eval > beta) the null move fails, because of some deep, hard-to-find threat. Many other moves are effectively null moves too, doing nothing useful, but also not giving something obvious away. These then likely have to be refuted in the same way as the null move.

But the search will have to rediscover that threat time after time. It is possibly a bit helped on the first ply of the refutation by the killer, which it inherits from its sibblings, but deeper down in the refutation tree it is on its own, and has to rediscover the thing from scratch. Only after many moves have been refuted in the same way the history heuristic might start to pick up the pattern. This problem is especially apparent in large variants with many pieces, (many hidden deep in their own camp), such as Chu Shogi or Tenjiku Shogi.

So what is needed is not just a cut-move hint on the first ply, (i.e. killer), but for the entire refutation tree. Now fortunately the tree that refuted the null move will be remembered in the hash table. All we have to do in the sub-tree of a useless move is probe the hash for the analogous position in the null-move refutation tree (i.e. that positions with the uselessly moved piece still in the original location). This position will have a hash key that always differs from the key of the current position by the mutation brought about by the alledgedly useless move we try to refute.

So what we could do is, after a null-move fail low, pass along to the sub-tree after any other move the mutation in board key that these moves cause. When this 'analogy key' is non-null the nodes in this sub-tree can use it as a secondary hash move; if the ordinary hash move doesn't work, or does not exist, they can probe the analogous position, and see if that can provide a hash move. This way it tries to copy the entire refutation tree, and if the original null-move alternative indeed had no effect at all, it would find the refutation in a perfectly efficient way. (Presumably the null-move reduction is matched by the LMR of such moves.)

Of course even when there is an anlogy key available, the node can still start by searching a null move. It will then pass that analogy key on to the null-move search, which will presumably benefit from it by making the refutation fast. This leads to a new refuted null move, which would define a new analogy key for the alternative moves. This new key will be preferred over the old one, as the difference of the analogous positions reached through this key will be smaller. So a refuted null-move search will possibly replace an existing analogy by a newer one.

[Michael Sherwin]

It used to be that a verification search was done after nullmove. Just yesterday I thought why not do a really shallow 1 ply verification search first. And if it returns a score < beta there would be no need to even try nullmove. But I have not tested that idea yet.

[Michael Sherwin]

It used to be that a verification search was done after nullmove. Just yesterday I thought why not do a really shallow 1 ply verification search first. And if it returns a score < beta there would be no need to even try nullmove. But I have not tested that idea yet.

RomiChess - RomiChess64P3n : 54.0/100 29-21-50 (=====111=1=110==11=====00110======01====1=0=0=0010==00=1=0=00=111=0==01011=11=0=====1101=1===11=10==) 54% +28

The only difference is this code added.

Code: Select all

if(depth > 3) {
  score = Search(beta-1, beta, 1);
  if(score < beta) goto skipnull;

If it is better it is not because it was faster. I think it might be because it avoids false negatives or something. I will test different depth parameters.

[hgm]

In some of my engines I do Internal Iterative Deepening also on the null move, and stop doing it as soon as the null move fails low. This sort of includes your idea.

[Michael Sherwin]

In some of my engines I do Internal Iterative Deepening also on the null move, and stop doing it as soon as the null move fails low. This sort of includes your idea.

I tried that but it did not work for me. I started if(depth > 2 ... but ended that test after 40 games as it was a much worse result. Then I tried depth > 4.

RomiChess - RomiChess64P3n : 55.0/100 27-17-56 (==1=01=1=11=1===10=0=1======1=0=1===1==110010=====011=1=1=10===010=====1=0=0====0=1==11=11====00=1=0) 55% +35

so I guess depth > 5 is next. And I guess this idea says, "if the danger is so high that I have no immediate move that can save me" then don't waste any more time.

[Michael Sherwin]

In some of my engines I do Internal Iterative Deepening also on the null move, and stop doing it as soon as the null move fails low. This sort of includes your idea.

I tried that but it did not work for me. I started if(depth > 2 ... but ended that test after 40 games as it was a much worse result. Then I tried depth > 4.

RomiChess - RomiChess64P3n : 55.0/100 27-17-56 (==1=01=1=11=1===10=0=1======1=0=1===1==110010=====011=1=1=10===010=====1=0=0====0=1==11=11====00=1=0) 55% +35

so I guess depth > 5 is next. And I guess this idea says, "if the danger is so high that I have no immediate move that can save me" then don't waste any more time.

Seems the test depth > 4 is best. Now I'm doing a 1000 game test using the Noomen 6 ply test suite of 500 positions. The results are good so far. RomiChess - RomiChess64P3n 105.0/190 66-46-78

[xr_a_y]

In test in Minic :

Code: Select all

do null move only if  pvs<false,true>(beta-1,beta,p,depth/2,ply,nullPV,seldepth) >= beta

for it is 78-63-194, so a little better but not sure.

I'll try depth/4 maybe.

[Michael Sherwin]

In test in Minic :

Code: Select all

do null move only if  pvs<false,true>(beta-1,beta,p,depth/2,ply,nullPV,seldepth) >= beta

for it is 78-63-194, so a little better but not sure.

I'll try depth/4 maybe.

Seems about right!

I have continued to get consistent results of about 5 additional points above 50% for every hundred games. I have yet to try anything deeper than a 1 ply pre search though. Thanks for your reply. Keep us posted.

[jackd]

...

[xr_a_y]

Ok I found +20 elo with depth/2
depth/4 running ...