History pruning / move ordering question

[Don]

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.

[jdart]

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]

Thanks to everyone for all the helpful replies!

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.

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]

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]

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

[Don]

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.

[jd1]

Thank you, that makes sense.

Jerry

[PK]

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.

[zamar]

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

[Don]

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.