History pruning / move ordering question

[hgm]

I once experimented with a third local killer, which was from the normal killer table, in a slot reserved for the null-move refutation. The idea was that this would provide a more consistent refutation than the refutation of the previous sibbling move (which could be exploiting a specific weakness created by that move). However, a null-move refutation might not be good enough to refute positionally good non-captures, so I only tried it after the other killers, as an insurance that if both of those would be specific for the previous two move, it would still have a more general refutation to try.

It did not clearly improve time-to-depth, though.

[jd1]

I do maintain a refutation table that is used to help make decisions. These are specific moves that have been seen to refute another specific move.

Thanks for sharing this Don.
I know that refutation table is a very old technique. And I think it's more or less standard trick in all Go-engines. Strange that it never came to my mind that this trick could be successfully applied to chess engines as well...

Anyway, with a quick test, it looks like that Stockfish could benefit from this trick. I just implemented a simple always-overwrite [pieceType][to_square] table, and ordered the refuting moves in the top of the move list (behind good-captures and killers).

The first results with short time control (15+0.05) are very promising:
LLR: 2.95 (-2.94,2.94)
Total: 2803 W: 596 L: 483 D: 1724

It appears to be good for Toga too: >3000 games +3 elo at short TC, +14 elo 300 games at long TC (60' + 0.5'), test ongoing.

There are two bugs in my implementation tested - sometimes the move is played twice if it is also a killer; and I need to account for null moves in the previous ply. I'll fix and retest, but it looks very promising

Thanks a lot,
Jerry

[zamar]

Cool! I hope that it helps. I think I use it to replace killer B, to NOT do most forward pruning and in LMR I still reduce if the standard formula calls for it but I might reduce a fully ply less than the normal amount.

Did you try those things? I think it's most effective (if I remember this right) as a forward pruning veto.

Well, because move is currently order on the top section of the list, LMR is much smaller (In SF, it's based on moveCount and Depth) and LMP (late move pruning) doesn't hit it either.

So in the default implementation, the behaviour is already very much as you describe. Of course, I could try not to do move reording and only add exceptions for LMP and LMR... But I don't expect this to make a big difference...

[dchoman]

In EXchess, I found that a standard refutation move which is not reduced or pruned is worth about +10 elo. Better than this (+25 elo or so) was a combination move hash table which is indexed by the hash signature of the previous two moves. I reported on it in a thread about a year ago. Turns out others had tried something similar without much benefit in the past, but it really works well for my program. I use it for move ordering, but again, I think most of the benefit comes from not reducing or pruning that move, and it didn't help to store winning captures (actually hurt as those filled up space in the table), just storing non-captures or non-winning captures was best. The context (previous two moves) is much more specific than a refutation move which is probably why it is more effective... at least in EXchess which does a lot of heavy reducing and pruning.

- Dan

[zamar]

In EXchess, I found that a standard refutation move which is not reduced or pruned is worth about +10 elo. Better than this (+25 elo or so) was a combination move hash table which is indexed by the hash signature of the previous two moves.

Hi,

I had a similar idea in mind (well.. again this is nothing new), but I thought that this is likely not going to work...

But now as you've reported that this is idea is working for you, i'll definitely give it a try in the near future.

[Don]

In EXchess, I found that a standard refutation move which is not reduced or pruned is worth about +10 elo. Better than this (+25 elo or so) was a combination move hash table which is indexed by the hash signature of the previous two moves.

Hi,

I had a similar idea in mind (well.. again this is nothing new), but I thought that this is likely not going to work...

But now as you've reported that this is idea is working for you, i'll definitely give it a try in the near future.

It's clearly one of those deals where you mileage will vary as they say. It was non-trivial in Komodo but I don't remember the numbers. We have a bunch of 1 or 2 ELO things in Komodo but this was something beyond that.

Not reducing one of these moves did not work in Komodo, but reducing it less DOES work. However Komodo can be pretty aggressive about reducing moves late in the list and perhaps this goes a long way in saving the day when such a surprise move is a refutation.

[lucasart]

- remove the 2nd killer and use the refutation move in its stead (for ordering and as LMR veto)
- try other variations like fsq/tsq instead of piece/tsq. perhaps even your piece/fsq/tsq.

Since the move is intended to be a refutation, I am pretty sure you need to be pretty specific about what it is you are refuting, and even then it's a generalization because a true refutation is based on a specific position. The hash table move is a specific refutation.

I have run my tests, and the conclusion, as far as DiscoCheck is concerned is that:
(1) refutation[color][piece][tsq] used as a 3-rd killer for move ordering is a clear gain (about +9 ELO after 10000 games in 10"+0.1")
(2) refutation[color][fsq][tsq] instead performs almost equally well (diff impossible to really measure as results too close to call, so looking at some average node counts to get an idea)

Now for using the refutation in LMR, I will simply try to use it as an LMR veto (like killers). Given the way DiscoCheck does search reductions (not quite standard and probably lame) reducing the reduction by one ply as you suggest, or not reducing at all the refutation move, would amount to the same.

But when using the refutation move as an LMR veto, I will use (2), because the fact that it's more specific probably means the cost is going to be less. For the moment it's looking very good, but I've just started the test, so I'm a bit worried to post early results and get too excited

[Don]

- remove the 2nd killer and use the refutation move in its stead (for ordering and as LMR veto)
- try other variations like fsq/tsq instead of piece/tsq. perhaps even your piece/fsq/tsq.

Since the move is intended to be a refutation, I am pretty sure you need to be pretty specific about what it is you are refuting, and even then it's a generalization because a true refutation is based on a specific position. The hash table move is a specific refutation.

I have run my tests, and the conclusion, as far as DiscoCheck is concerned is that:
(1) refutation[color][piece][tsq] used as a 3-rd killer for move ordering is a clear gain (about +9 ELO after 10000 games in 10"+0.1")
(2) refutation[color][fsq][tsq] instead performs almost equally well (diff impossible to really measure as results too close to call, so looking at some average node counts to get an idea)

That's not a surprise I guess. I have tried both in the history table too and it doesn't seem to matter so I went with the more compact color/fpce/tsq - you trade a little bit of generalization for a little bit of specificity. I would not be surprised if you discover that the more general method is even slightly better if could measure it. Perhaps I'll change over since I prefer more compact data structures.

Now for using the refutation in LMR, I will simply try to use it as an LMR veto (like killers). Given the way DiscoCheck does search reductions (not quite standard and probably lame) reducing the reduction by one ply as you suggest, or not reducing at all the refutation move, would amount to the same.

But when using the refutation move as an LMR veto, I will use (2), because the fact that it's more specific probably means the cost is going to be less. For the moment it's looking very good, but I've just started the test, so I'm a bit worried to post early results and get too excited

Yes, this can be embarrassing. I sometimes call Larry and say, "it's off to a great start!!!" only be made a fool out of. Of course I know better but you want to see improvement so you get excited.

[tpetzke]

Hi,

how do you calculate the hash signature of two moves ?

key = boardkey XOR boardkey_two_moves ago ?

Thomas...

[lucasart]

Hi,

how do you calculate the hash signature of two moves ?

key = boardkey XOR boardkey_two_moves ago ?

Thomas...

Yes, that's the beauty.

On another subject, Marcel Van Kervick posted a very interesting paper on Open Chess that uses this property (for a different purpose though)
http://open-chess.org/viewtopic.php?f=5&t=2300