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

History pruning / move ordering question

Post by jd1 » Fri May 10, 2013 5:39 am

Hi,

I have a question: should History Pruning use the same table as History for move ordering?

Toga has two history tables:

1. depth*depth increment on the best move which improves alpha. This governs the move ordering. Toga does not decrement failed moves.

I tried a depth*depth decrement but this was slightly worse (even after fixing bugs like: use signed integers, don't allow quiet moves with bad history to come after bad captures, 2048 limit for history to give aging - IIRC Stockfish is 2000, etc.). (Note: above test done without History Pruning).

2. Table recording the historical probability of a move to cause a fail high (value >= beta). Depth is not considered here.

I removed History Pruning from the current development version and tried:
- Use the History Probability (HistHit * 16384 / HistTot) table for move ordering also. This failed badly (around -30 elo or so).
- Use the depth*depth History table for History Pruning as well (i.e. pruning quiet moves based on quiet move count rather than by the history_prob table. I also tried using the played move count, but this was even worse). Of course a lot of tuning is necessary here in order to compare, but after _much_ tuning I haven't even got to within 20 elo of the old History Pruning.
- I also tried, for an experiment, to use Stockfish's algorithm (depth*depth bonus for good moves / penalty for bad moves, aging, move count based pruning with the current formula instead of history pruning). The result was -70 elo or so.

Intuitively I feel that history pruning and move ordering should use the same table, but I haven't been successful so far.

I wonder whether anyone has suggestions/comments. Does anyone else maintain two tables, one for ordering and one for pruning and/or reductions?

Thanks a lot!
Jerry

PK
Posts: 824
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: History pruning / move ordering question

Post by PK » Fri May 10, 2013 10:05 am

I admit using two separate history tables and do not agree with Your intuition :)

roughly, there are three cathegories of moves: those that fail high often, those that tend to fail low and those that are volatile. obviously, You want to sort the first category as high as possible, and reduce the second one as much as possible. But You don't want to reduce a volatile move, as it causes tactical risks, and You might want to sort it high, gambling on getting either a cutoff or a quick, cost-effective refutation.

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

Re: History pruning / move ordering question

Post by Don » Fri May 10, 2013 12:05 pm

jd1 wrote:Hi,

I have a question: should History Pruning use the same table as History for move ordering?

Toga has two history tables:

1. depth*depth increment on the best move which improves alpha. This governs the move ordering. Toga does not decrement failed moves.

I tried a depth*depth decrement but this was slightly worse (even after fixing bugs like: use signed integers, don't allow quiet moves with bad history to come after bad captures, 2048 limit for history to give aging - IIRC Stockfish is 2000, etc.). (Note: above test done without History Pruning).

2. Table recording the historical probability of a move to cause a fail high (value >= beta). Depth is not considered here.

I removed History Pruning from the current development version and tried:
- Use the History Probability (HistHit * 16384 / HistTot) table for move ordering also. This failed badly (around -30 elo or so).
- Use the depth*depth History table for History Pruning as well (i.e. pruning quiet moves based on quiet move count rather than by the history_prob table. I also tried using the played move count, but this was even worse). Of course a lot of tuning is necessary here in order to compare, but after _much_ tuning I haven't even got to within 20 elo of the old History Pruning.
- I also tried, for an experiment, to use Stockfish's algorithm (depth*depth bonus for good moves / penalty for bad moves, aging, move count based pruning with the current formula instead of history pruning). The result was -70 elo or so.

Intuitively I feel that history pruning and move ordering should use the same table, but I haven't been successful so far.

I wonder whether anyone has suggestions/comments. Does anyone else maintain two tables, one for ordering and one for pruning and/or reductions?

Thanks a lot!
Jerry
I use a table for move ordering and reductions are based on the move number in the move list as well as other tactical criteria.

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

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: History pruning / move ordering question

Post by jdart » Fri May 10, 2013 1:43 pm

I use 1. for ordering and 2. for pruning as Toga does. It is actually in one table but the table contains structs and different fields are used.

But I have other kinds of pruning besides history pruning, including Late Move Pruning, which ignores history. So the history pruning is not acting alone.

I have not experimented with variants of this lately. I am kind of surprised you'd get -70 ELO from using the Stockfish method.

--Jon

jd1
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: History pruning / move ordering question

Post by jd1 » Fri May 10, 2013 10:45 pm

Thanks to everyone for all the helpful replies!
jdart wrote: But I have other kinds of pruning besides history pruning, including Late Move Pruning, which ignores history. So the history pruning is not acting alone.
I will try to use Late Move Pruning as well then, thanks for the input. I like the idea as at the moment sometimes, at low depth, I prune quiet move no. 5 while searching quiet move no. 20 due to the differences between the two history tables.
jdart wrote: I have not experimented with variants of this lately. I am kind of surprised you'd get -70 ELO from using the Stockfish method.

--Jon
Well, maybe I still had a bug :) But on the other hand, it was self-play, a quick time control and too few games to know the actual elo difference (~2000). I also think Stockfish's move count pruning formula is too aggressive to work in Toga. By making the formula less aggressive, I got to within 20 elo or so.

Jerry

jd1
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: History pruning / move ordering question

Post by jd1 » Fri May 10, 2013 10:49 pm

Don wrote: I use a table for move ordering and reductions are based on the move number in the move list as well as other tactical criteria.

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.
That's an interesting idea, although I have heard of this before. I'll put a refutation table on my TODO list. May I ask how you index the table? Maybe RefutationTable[piece][to] stores the move which has been known to be a refutation?

Thanks!
Jerry

jd1
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: History pruning / move ordering question

Post by jd1 » Fri May 10, 2013 10:51 pm

PK wrote:I admit using two separate history tables and do not agree with Your intuition :)

roughly, there are three cathegories of moves: those that fail high often, those that tend to fail low and those that are volatile. obviously, You want to sort the first category as high as possible, and reduce the second one as much as possible. But You don't want to reduce a volatile move, as it causes tactical risks, and You might want to sort it high, gambling on getting either a cutoff or a quick, cost-effective refutation.
Thank you!

I'm not sure I understand you completely. Are there certain kinds of moves that we want to sort late but not reduce/prune or vice versa?

Jerry

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

Re: History pruning / move ordering question

Post by Don » Fri May 10, 2013 10:55 pm

jd1 wrote:
Don wrote: I use a table for move ordering and reductions are based on the move number in the move list as well as other tactical criteria.

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.
That's an interesting idea, although I have heard of this before. I'll put a refutation table on my TODO list. May I ask how you index the table? Maybe RefutationTable[piece][to] stores the move which has been known to be a refutation?

Thanks!
Jerry
I believe it is piece/from/to - and the contents is the actual move that was last seen to refute the indexed move. It is cleared between moves and always overwrite. Not particularly fancy.

It is used primarily in forward pruning decisions and I believe I achieved a slight gain by reducing LESS if the move was a refutation move - especially when the reduction is significant. Refutation moves are a very old idea and have been around a long time, but I think primarily as a move ordering gizmo.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

jd1
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: History pruning / move ordering question

Post by jd1 » Fri May 10, 2013 11:11 pm

Thank you, that makes sense.

Jerry

PK
Posts: 824
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: History pruning / move ordering question

Post by PK » Sun May 12, 2013 1:37 pm

my explanation was a little messy, but You are right: there might be moves that are unlikely to win, but for tactical reasons it's inadvisable to reduce them. they shouldn't be sorted too high, though.

Post Reply