History pruning / move ordering question

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
zamar
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: History pruning / move ordering question

Post by zamar » Sun May 12, 2013 10:37 pm

Don wrote: 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
Joona Kiiski

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: History pruning / move ordering question

Post by Don » Mon May 13, 2013 2:17 am

zamar wrote:
Don wrote: 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
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.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: History pruning / move ordering question

Post by Gerd Isenberg » Mon May 13, 2013 10:06 am

zamar wrote:
Don wrote: 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
This sounds very much like the countermove heuristic, introduced by Jos Uiterwijk in 1992. Already at the Advances in Computer Chess 6 conference in London 1990, Dap Hartman and Peter Kouwenhoven proposed a refutation or killer table using two butterfly boards to store refutation moves for both sides. Similar to hash- and killer moves the aim was to safe move generation by proving only legality. If both TT and killer table fail to supply a move, then 1 in 5 times the butterfly board was able to supply a legal killer which saved the complete move gen.

Source:
Paul Lu (1990). Report on the Advances in Computer Chess 6 Conference. ICCA Journal, Vol. 13, No. 3
Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6

User avatar
lucasart
Posts: 3046
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: History pruning / move ordering question

Post by lucasart » Mon May 13, 2013 11:56 am

Don wrote:
zamar wrote:
Don wrote: 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
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.
Very interesting stuff. I've just coded the patch and DiscoCheck, and will test it when I finally have some spare CPU time.

So this "Counter Move Heuristic" basically gives us a third killer move. I wonder if the killers can be removed in the presence of a good History table and Coutner Move Heuristic. First thing I'll try if it works, is to remove the second killer and see what happens.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: History pruning / move ordering question

Post by Don » Mon May 13, 2013 12:14 pm

lucasart wrote:
Don wrote:
zamar wrote:
Don wrote: 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
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.
Very interesting stuff. I've just coded the patch and DiscoCheck, and will test it when I finally have some spare CPU time.

So this "Counter Move Heuristic" basically gives us a third killer move. I wonder if the killers can be removed in the presence of a good History table and Coutner Move Heuristic. First thing I'll try if it works, is to remove the second killer and see what happens.
I don't use it as a 3rd killer but it could be tried. I actually forgot precisely what I currently do (and this changes from version to version sometimes) but I think it is this:

1. if the refutiation is the hash move do nothing.
2. if the refutation is NOT killer A, set it as killer B.

There is no third killer. But that doesn't mean that should not be tried and what I do is not necessarily the best.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: History pruning / move ordering question

Post by Evert » Mon May 13, 2013 12:48 pm

lucasart wrote:So this "Counter Move Heuristic" basically gives us a third killer move. I wonder if the killers can be removed in the presence of a good History table and Coutner Move Heuristic. First thing I'll try if it works, is to remove the second killer and see what happens.
It was a nice improvement when I added it to Jazz ages ago, but not huge; not sure what it's worth now (there have been quite a few changes).

The idea is at least partly redundant with history (which I don't have in the traditional sense) and killers, but I don't think it can replace killers outright.
It helps to "transpose" killers from one part of the tree to another part. Once the move produces a cut-off it becomes a killer (for that depth) and it's no longer relevant that it's also a "counter move"...
Bear in mind that I also consider the killers from 2 plies earlier in the tree, if you don't do that the counter move may help more.

I got best results from storing "counter moves" well below the killers, but ahead of other quiet moves. They're currently about as far down as they can be without triggering reductions, so maybe the real win does indeed come from not reducing these moves, I haven't tried that.

I've also tried two variations: "combination moves" and "good captures". "Combination moves" are indexed the same way as counter moves, but using your own last move. This didn't actually help in any way. "Good captures" are more like killers (indexed by ply), except that they are captures with negative SEE ("unexpected good captures" may be more accurate). Again an idea that I didn't get to work in practice, but perhaps just flagging them as "don't reduce me" would work better...

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: History pruning / move ordering question

Post by Evert » Mon May 13, 2013 12:50 pm

Don wrote: There is no third killer. But that doesn't mean that should not be tried and what I do is not necessarily the best.
I found having a third killer slot to be slightly better in Jazz, but it's never going to be a huge win...

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: History pruning / move ordering question

Post by Don » Mon May 13, 2013 12:52 pm

Evert wrote:
Don wrote: There is no third killer. But that doesn't mean that should not be tried and what I do is not necessarily the best.
I found having a third killer slot to be slightly better in Jazz, but it's never going to be a huge win...
This is the least interesting usage of the refutation move anyway and if that was the only thing it was used for it would not be worth the implementation overhead and extra code complexity.

It's far more useful in pruning and LMR decisions, at least for Komodo.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

User avatar
lucasart
Posts: 3046
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: History pruning / move ordering question

Post by lucasart » Mon May 13, 2013 1:59 pm

Don wrote:
Evert wrote:
Don wrote: There is no third killer. But that doesn't mean that should not be tried and what I do is not necessarily the best.
I found having a third killer slot to be slightly better in Jazz, but it's never going to be a huge win...
This is the least interesting usage of the refutation move anyway and if that was the only thing it was used for it would not be worth the implementation overhead and extra code complexity.

It's far more useful in pruning and LMR decisions, at least for Komodo.
Well if you also do not reduce the third killer... It gets used both to improve move ordering and to prevent LMR accidents. Besides, good move ordering and preventing LMR accidents is already partially redundant since LMR reduces more and more as moves are late.

Anyway, there are many variations of the idea to test, and it's very possible that what works best for Komodo is not what works best for Jazz, Stockfish or DiscoCheck. For now I'll try things one at a time:
- use it as a third killer for move ordering
- use it as an LMR veto
- 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.

We shall see :D
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: History pruning / move ordering question

Post by Don » Mon May 13, 2013 2:26 pm

lucasart wrote:
Don wrote:
Evert wrote:
Don wrote: There is no third killer. But that doesn't mean that should not be tried and what I do is not necessarily the best.
I found having a third killer slot to be slightly better in Jazz, but it's never going to be a huge win...
This is the least interesting usage of the refutation move anyway and if that was the only thing it was used for it would not be worth the implementation overhead and extra code complexity.

It's far more useful in pruning and LMR decisions, at least for Komodo.
Well if you also do not reduce the third killer... It gets used both to improve move ordering and to prevent LMR accidents. Besides, good move ordering and preventing LMR accidents is already partially redundant since LMR reduces more and more as moves are late.
There is definitely some redundancy here as you say. However it is a lot more complicated than that. Here is why:

In LMR we find it is over-kill to simply push a move to the top so that it doesn't get reduced. And when you do that you are also taking some high scoring history move and reducing it where it would not have been previously reduced.

Additionally we have proved to our satisfaction that not reducing these is overkill but reducing them less is the right thing to do. I think it has to do with the effectiveness of the history table for us, it is hard to beat the performance of that and the killers for move ordering decisions - and we have tried. It seems that the killers are still better than the refutation most of the time and at least for us the only good move ordering attempt is to put this in for killer B and even that is still in question. So for whatever reason it seems that in Komodo we have to treat the refutation move special but not special enough to make a major change to move ordering based on it.

This is nothing odd about that because we (and everyone else) does this with checks too. We do not reduce checks even if it's the last move in the move list, and yet if it's really that special why don't we sort it to the top? It's because such moves are generally no better than any other move and do not deserve high move ordering, yet they can have a big impact on the search.

As you probably know, a lot of this is black magic, it's really difficult to know exactly what is going to to work or reason out why it does or doesn't work.

Anyway, there are many variations of the idea to test, and it's very possible that what works best for Komodo is not what works best for Jazz, Stockfish or DiscoCheck. For now I'll try things one at a time:
- use it as a third killer for move ordering
- use it as an LMR veto
We use it LIMIT the reductions, a very similar idea but not quite the same.
- 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 think what happens is that usually the killer move is the right move assuming the hash table move doesn't do the job. But your opponent might make a move which makes the killer move inappropriate. For example if the killer is Nf3 and the opponent pushes a pawn to g4, you don't want to play Nf3. Instead you will record that there is a better answer to Pg4. If the opponent plays Bg4 however Nf3 is probably still a valid move.

But it should be tried - no harm done and it might turn out that you can get away with a little bit more generalization here.

We shall see :D
As you say, it can easily be different with different programs. In fact it would probably be quite odd if it wasn't because all sorts of things interact here.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

Post Reply