Reductions and null move refutations

[Tord Romstad]

Hi all,

This evening I made a little experiment: At a node directly following a reduction, if the null move fails low, and the moving piece in the move which refutes the null move is the same as the moving piece in the reduced move, immediately cancel the reduced-depth search and re-search with normal depth. The idea is that when this happens, the reduced-depth move is likely to contain some kind of serious tactical or positional threat, and deserves a non-reduced search.

In pseudo code, it looks approximately like this:

Code: Select all

  if(ok_to_do_nullmove()) {
    make_nullmove();
    nullvalue = -search(-beta, -beta+1, depth-(R+1));
    unmake_nullmove();

    if(nullvalue >= beta)
      return nullvalue;
    else {
      threat_move = move_that_refuted_nullmove();
      if(SearchStack[Ply-1].reduction &&
         To(SearchStack[Ply-1].move) == From(threat_move))
        depth += SearchStack[Ply-1].reduction_amount;
    }
  }


I have no available CPU time for testing this change in real games at the moment, but it seems to be extremely effective in tactical positions. On my iMac G5 1.8 GHz, Glaurung scores 153/183 at ECMGCP at 10 seconds per move with the new trick enabled (the best score I have ever seen from Glaurung). Without the trick, the score drops to 144/183.

Perhaps something similar would be worth trying even in engines which do not use reductions. If a null move is refuted by a move which was made possible by the move at the previous ply, make a small fractional extension.

Has anyone experimented with similar ideas?

Tord

[Pallav Nawani]

Hi all,

This evening I made a little experiment: At a node directly following a reduction, if the null move fails low, and the moving piece in the move which refutes the null move is the same as the moving piece in the reduced move, immediately cancel the reduced-depth search and re-search with normal depth. The idea is that when this happens, the reduced-depth move is likely to contain some kind of serious tactical or positional threat, and deserves a non-reduced search.

In pseudo code, it looks approximately like this:

Code: Select all

  if(ok_to_do_nullmove()) {
    make_nullmove();
    nullvalue = -search(-beta, -beta+1, depth-(R+1));
    unmake_nullmove();

    if(nullvalue >= beta)
      return nullvalue;
    else {
      threat_move = move_that_refuted_nullmove();
      if(SearchStack[Ply-1].reduction &&
         To(SearchStack[Ply-1].move) == From(threat_move))
        depth += SearchStack[Ply-1].reduction_amount;
    }
  }


Tord

Hi,

From you psuedo code, it seem that you are doing this every time the null move does not fail high ( of course it also includes when it fails low).
Is that the case?

Pallav

[Tord Romstad]

Hi all,

This evening I made a little experiment: At a node directly following a reduction, if the null move fails low, and the moving piece in the move which refutes the null move is the same as the moving piece in the reduced move, immediately cancel the reduced-depth search and re-search with normal depth. The idea is that when this happens, the reduced-depth move is likely to contain some kind of serious tactical or positional threat, and deserves a non-reduced search.

In pseudo code, it looks approximately like this:

Code: Select all

  if(ok_to_do_nullmove()) {
    make_nullmove();
    nullvalue = -search(-beta, -beta+1, depth-(R+1));
    unmake_nullmove();

    if(nullvalue >= beta)
      return nullvalue;
    else {
      threat_move = move_that_refuted_nullmove();
      if(SearchStack[Ply-1].reduction &&
         To(SearchStack[Ply-1].move) == From(threat_move))
        depth += SearchStack[Ply-1].reduction_amount;
    }
  }


Tord

Hi,

From you psuedo code, it seem that you are doing this every time the null move does not fail high ( of course it also includes when it fails low).
Is that the case?

Hi!

As you can see from my code, I always do my null move searches with a zero-width window. Hence "failing low" and "not failing high" mean exactly the same thing for my null move searches.

Tord

[Daniel Shawul]

Hi Tord
If i understand correctly, the idea is similar to not reducing after
you extend with Bovinnik extensions. since i use this extensions,it should
be no problem for me. Generally,reducing captures of the previous moved piece has a signifcant effect on tactical strength of danchess.
so i am not reducing captures right now.
i tried to statically determine if a move is tactical (i can do this since i have
attack tables at hand). This brought me nothing, infact it slowed me down a bit. I don' use history data as a criteria. So far the following simple
pseudo code works best for me.

if(!depth_reduced_before
&& !extended
&& !in_check
&& all non captures except the first ) {
reduce
}

BTW is it safe to reduce after using R=3 for null move?
not reducing after null move in general seems a very bad idea.

best wishes
daniel

[Naum]

Hi Tord,

I think your idea is very nice, but it will probably be benefitial only to people who do a lot of reductions (like you do in Glaurung).
It won't work for me, because I do almost no reductions, but it may help for history pruning.

BTW, I really have a hard time beleiving that reductions you do actually work. I don't even dare trying something like that in Naum.

Even the history pruning seems to me like a pretty bad idea, since the move that was not so good (poor history value) for the first 10 plies, may become a winner on ply 11, but you won't see that, because you are going to prune it. This logic also applies to all other reductions, so I think that algorithm deciding on reductions should be much more complex.

Regards,
Alex

[Tord Romstad]

Hi Daniel!

Hi Tord
If i understand correctly, the idea is similar to not reducing after
you extend with Bovinnik extensions. since i use this extensions,it should
be no problem for me.

No, as far as I can see, it is not similar at all. The Botvinnik-Markoff extension is triggered when the threat move at the current ply is the same as the threat move two plies earlier (or if the two threat moves have the same target). My new trick consists of canceling a reduction at the previous ply if the current threat move was made possible by the move one ply earlier.

Generally,reducing captures of the previous moved piece has a signifcant effect on tactical strength of danchess.
so i am not reducing captures right now.

Neither am I. Captures and promotions are never reduced.

i tried to statically determine if a move is tactical (i can do this since i have
attack tables at hand).

I did this in Gothmog, and it seemed to work well there. In Glaurung and Scatha, I try to limit the use of such static techniques (not because I think they are necessarily bad, but because I think it is a good idea to experiment with several different ways of doing things).

This brought me nothing, infact it slowed me down a bit. I don' use history data as a criteria. So far the following simple
pseudo code works best for me.

Code: Select all

   if(!depth_reduced_before
      && !extended
      && !in_check
      && all non captures except the first )  {
           reduce
   }

This is not too different from what I do, except that I allow several reductions in the same path.

BTW is it safe to reduce after using R=3 for null move?

It seems to work well in Glaurung. YMMV, as always.

Tord

[Tord Romstad]

Hi Alex!

I think your idea is very nice, but it will probably be benefitial only to people who do a lot of reductions (like you do in Glaurung).
It won't work for me, because I do almost no reductions, but it may help for history pruning.

You probably cannot use the idea exactly as described, but the observation the idea is based on can perhaps be utilised in other ways as well. In case my original explanation wasn't clear enough, I will try to phrase it somewhat differently. Assume that the current line of search looks like this:

Code: Select all

move_1 move_2 ... move_n

.
We now try a null move, which is refuted by move_(n+2);

Code: Select all

move_1 move_2 ... move_n NULLMOVE move_(n+2)

If the move 'move_(n+2)' was made possible by the move 'move_n' (for instance, if the moving piece is the same for the two moves), we have obtained an interesting piece of information about 'move_n'. We know that this move contains some kind of tactical or positional threat. It is worth considering if there are ways to use this information.

BTW, I really have a hard time beleiving that reductions you do actually work. I don't even dare trying something like that in Naum.

They definitely work for me, but without doubt this can be explained by the simple fact that in sufficiently weak programs, everything seems to work (as Vincent likes to point out). Glaurung is a very simple and unsophisticated program, and it is not surprising that techniques which are too unsound for stronger and more mature engines are effective for me.

Even the history pruning seems to me like a pretty bad idea, since the move that was not so good (poor history value) for the first 10 plies, may become a winner on ply 11, but you won't see that, because you are going to prune it. This logic also applies to all other reductions, so I think that algorithm deciding on reductions should be much more complex.

The algorithms for deciding on reductions are much more complex in Gothmog, and indeed they seem to work better. On the other hand, the more complex algorithms are also much more expensive, and Gothmog's more accurate search is more than compensated by Glaurung's higher speed.

A fact which deserves to be mentioned more often is that even very simple and theoretically unsound pruning and reduction techniques can be used without much practical risk if you use a layered approach. Instead of pruning when a certain set of conditions are satisfied at a single node in the tree, you prune when the same set of conditions are satisfied at several nodes in the same path. By collecting some statistics from your searches, you can basically make the risk exactly as small as you want (but of course, reducing the risk tends to increase the tree size).

Tord

[Steve Maughan]

Tord,

It's an interesting idea. Here's another suggestion - why not also cancel the reduction if the threat is a mate (or a very low value) i.e.

Code: Select all

  if(ok_to_do_nullmove()) {
    make_nullmove();
    nullvalue = -search(-beta, -beta+1, depth-(R+1));
    unmake_nullmove();

    if(nullvalue >= beta)
      return nullvalue;
    else {
      threat_move = move_that_refuted_nullmove();

      if(SearchStack[Ply-1].reduction){
        if(nullvalue < alpha - margin ||
          To(SearchStack[Ply-1].move) == From(threat_move))
          depth += SearchStack[Ply-1].reduction_amount;
    }
  }


The idea is that the threat may also come from another peice - not just the piece moves last.

What do you think?

Steve

[Naum]

Hi Tord,

Your idea is definitely worth playing with. Yes, it may also be used to identify interesting moves that I may want to extend. It doesn't have to be used only to cancel the reduction.

More conditions is neccessary I think. There are many situations that may trigger 'interesting move' code, but are obviously not worth the extension.

The same applies to null-moves. I have on my to-do list to create a simple function that will decide whether it's worthed doing null-move in a particular position. For instance, if the previous move is an obvious threat (like N attacks Q), there is no need to do the null-move search, because N will just take the Q. This would also trigger your 'interesting move' code even though, N may be taken by pawn in the next move, so it's probably a bad move and shouldn't be extended.

Alex

[Anthony Cozzie]

Honestly, I don't think ECMGCP (or any test suite) is a good benchmark. I'd rather see results from games. So many of these ideas for higher selectivity hurt positional play, and that is what is important nowadays.

anthony

[Tom Likens]

Hey Anthony,

I'd also be curious how it performs in real games, but my guess is that
it's likely an improvement since it should reduce *fewer* branches
than the original search. Of course, as always the proof is in the pudding.

--tom

[Tord Romstad]

It's an interesting idea. Here's another suggestion - why not also cancel the reduction if the threat is a mate (or a very low value) i.e.

Code: Select all

  if(ok_to_do_nullmove()) {
    make_nullmove();
    nullvalue = -search(-beta, -beta+1, depth-(R+1));
    unmake_nullmove();

    if(nullvalue >= beta)
      return nullvalue;
    else {
      threat_move = move_that_refuted_nullmove();

      if(SearchStack[Ply-1].reduction){
        if(nullvalue < alpha - margin ||
          To(SearchStack[Ply-1].move) == From(threat_move))
          depth += SearchStack[Ply-1].reduction_amount;
    }
  }


This wouldn't work for me, I'm afraid. I use something very close to fail-hard, which means that the condition (nullvallue < alpha - margin) would almost never be satisfied. The exception is when the refutation of the null move is a mate in 1, and in this case I already cancel the reduction.

Your idea is definitely worth playing with. Yes, it may also be used to identify interesting moves that I may want to extend. It doesn't have to be used only to cancel the reduction.

More conditions is neccessary I think. There are many situations that may trigger 'interesting move' code, but are obviously not worth the extension.

Absolutely. Blindly extending all such moves would certainly not work, even with very small fractional extensions. Several additional, strong conditions are needed.

The same applies to null-moves. I have on my to-do list to create a simple function that will decide whether it's worthed doing null-move in a particular position. For instance, if the previous move is an obvious threat (like N attacks Q), there is no need to do the null-move search, because N will just take the Q.

Gothmog does this. It seems to save a considerable number of nodes (the tree size was reduced by around 10%, IIRC), without any obvious disadvantages. If the null move search is used to detect mate threats, you will of course miss some of these mate threats if you restrict the null move search in this way, but I don't think this is a big problem in practise.

Honestly, I don't think ECMGCP (or any test suite) is a good benchmark. I'd rather see results from games.

I agree entirely, of course, but at the moment I have no time for running games.

So many of these ideas for higher selectivity hurt positional play, and that is what is important nowadays.

This depends on the level of play. You just can't hurt the positional play of a simple engine like Glaurung, which has hardly any positional understanding whatsoever. The only way it can win games is by outsearching the opponent in endgames or tactical middlegames.

Except for very strong engines, it just isn't true that positional play is what is important nowadays. Positional play becomes a decisive factor only when the engines are sufficiently strong not to make lots of serious tactical mistakes. At Glaurung's level, games are decided by tactics all the time.

Nevertheless, you do have a point in the sense that many techniques which are very effective in weak chess engines can be an impediment to long-term progress, and that high selectivity is one of the most important examples.

Tord

[Steve Maughan]

Tord,

This wouldn't work for me, I'm afraid. I use something very close to fail-hard

Out of interest why do you do fail-hard? You end up doing more researches but I guess fail hard may give a more stable search at the root.

Steve

[Uri Blass]

[
This depends on the level of play. You just can't hurt the positional play of a simple engine like Glaurung, which has hardly any positional understanding whatsoever. The only way it can win games is by outsearching the opponent in endgames or tactical middlegames.

Tord

Tord,I think that you are wrong if you think positional play is only about evaluation.

Good positional play is result of search and some search ideas can help engines to find sacrifices faster but cause the engine to search less plies.

I found that changing pruning parameters helped movei to get better results in games but also caused it to score worse in test suites.

The reason is that chess is not a game of sacrifices and it is better to be slower in finding sacrifices but search deeper in quiet positions as compensation.

Uri

[Tord Romstad]

This wouldn't work for me, I'm afraid. I use something very close to fail-hard

Out of interest why do you do fail-hard? You end up doing more researches but I guess fail hard may give a more stable search at the root.

The reason is simple, but not very interesting. I agree that fail-soft is theoretically a bit more efficient, but I think the practical difference is rather small. Fail-hard is easier to implement without introducing subtle bugs and search instabilities, and for this reason I prefer to stick to fail-hard until my program is more mature.

If you look closely at my code, you will find that I do many small things which are done slightly sub-optimally, but which makes debugging a little bit easier. The most obvious examples are that I don't allow hash table cutoffs at PV nodes, and that I don't use any kind of aspiration windows.

Tord,I think that you are wrong if you think positional play is only about evaluation.

I never meant to claim that, and if I appeared to do so, I apologize for not expressing myself more clearly.

Good positional play is result of search and some search ideas can help engines to find sacrifices faster but cause the engine to search less plies.

I found that changing pruning parameters helped movei to get better results in games but also caused it to score worse in test suites.

The reason is that chess is not a game of sacrifices and it is better to be slower in finding sacrifices but search deeper in quiet positions as compensation.

I agree with all of this, of course, and I am sure we have all seen many examples of tricks which help in tactical test suites, but makes the program play much worse in real games. This is not only because of the balance between tactics and positional play, but also because the types of tactics encountered in tactical test suites are usually very different from the tactics the engine encounters in real games. Test suites emphasize flashy, brilliant tactics, where the key moves are counter-intuitive and usually appear to lose material. The tactics which decide real games are usually much more mundane.

Tord





Steve[/quote]

[Volker Annuss]

Hi all,

I still did not try Tords Idea, but something similar.

Hermann perfers to use moves that refute the nullmove as killer moves. Move ordering seems to be a little better, when moves where the same piece has moved twice are not used as killer moves.

Volker

[Anonymous]

Hermann perfers to use moves that refute the nullmove as killer moves. Move ordering seems to be a little better, when moves where the same piece has moved twice are not used as killer moves.

I am using the "null move killer" idea, too; with the same result - seems the move ordering is slightly better. I also check every null move with reduced depth and without null move. This is of course some overhead, but it gives even a better killer. Very similar to Crafty's internal iterative deepening.

The idea about the same piece moving twice in a row sounds interesting. I might try it - but some care is probably needed. Say you have a passed pawn that runs. Or a typical mate threat where black K on g8, bPs f7, g6, h7. White has a B on f6 (or a pawn) - Qh6 ... Qg7#. Often even a third Q move before is needed. BTW: These sort of positions are really hurt by null move. On the way to h6, white may give some material, and with the reduced null move depth, the mate is not seen yet, and black null moves fail high. So a seemingly simple mate may need a very high depth, to be seen.

Regards,
Dieter