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.
User avatar
hgm
Posts: 23790
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: History pruning / move ordering question

Post by hgm » Mon May 13, 2013 3:15 pm

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
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: History pruning / move ordering question

Post by jd1 » Tue May 14, 2013 6:04 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
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
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: History pruning / move ordering question

Post by zamar » Tue May 14, 2013 8:00 am

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

dchoman
Posts: 171
Joined: Wed Dec 28, 2011 7:44 pm
Location: United States

Re: History pruning / move ordering question

Post by dchoman » Tue May 14, 2013 10:53 am

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
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: History pruning / move ordering question

Post by zamar » Tue May 14, 2013 12:43 pm

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

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

Re: History pruning / move ordering question

Post by Don » Tue May 14, 2013 1:03 pm

zamar wrote:
dchoman wrote: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.
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 » Tue May 14, 2013 1:12 pm

Don wrote:
lucasart wrote: - 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 ;-)
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 » Tue May 14, 2013 1:28 pm

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

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: History pruning / move ordering question

Post by tpetzke » Tue May 14, 2013 2:13 pm

Hi,

how do you calculate the hash signature of two moves ?

key = boardkey XOR boardkey_two_moves ago ?

Thomas...

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 » Tue May 14, 2013 2:32 pm

tpetzke wrote: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
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Post Reply