Improving History Tables

[voyagerOne]

So today history table scores which piece to position creates a cutoff.
an array like this history[piece][toPos]

What if we create another level so the history table also considers the opponent's prior move.

So something like this history[opPiece][opToPos][piece][toPos];

I wonder if this will improve move ordering better than just a piece-to history table.

(Yes I know this will be expensive...)

[Evert]

Sounds like a hybrid between history and counter move heuristics. Interesting idea, but I suspect that the hit-rate on the table is too low to offer much of an improvement.

[AlvaroBegue]

I used that idea in my checkers program 20 years ago. It also worked well in connect 4, but I didn't try it in chess, because at the time the amount of memory required for this was considered large.

The precise way I implemented this in checkers and connect 4 is by keeping the usual single-move table and an additional two-move table. When ordering moves, I query both tables and add the entries, with a large weight for the two-move entry (I can't remember exactly, but something like 40).

I wouldn't be surprised if it works for chess, but the gains will probably be small, because the important ordering happens earlier (hash move, good captures, killers). In checkers and connect 4 it doesn't make sense to try captures first, so the history heuristic plays a more vital role, and any improvement is important.

[cdani]

In Discocheck, and latter I put in Andscacs, there is:

Code: Select all

* Double Move Refutation Hash Table:
* - used for quiet move ordering, and as an LMR guard.
* - move pair (m1, m2) -> move m3 that refuted the sequence (m1, m2) last time it was visited by the
* search.
* - dm_key is the zobrist key of the last 2 moves (see board::Board::get_dm_key(), in particular floor at
* root sp0).
* - always overwrite: fancy ageing schemes, or seveal slots per move pair did not work in testing.

And it's worth at least 15 elo.

Latter I added to Andscacs, in my current developing version that is not published, guess what, Triple move refutation table, and Quadruple move refutation table
They win something less, but something.

Is not the same, but gives the idea that there is room to win something with those ideas.

[Evert]

In Discocheck, and latter I put in Andscacs, there is:

Code: Select all

* Double Move Refutation Hash Table:
* - used for quiet move ordering, and as an LMR guard.
* - move pair (m1, m2) -> move m3 that refuted the sequence (m1, m2) last time it was visited by the
* search.
* - dm_key is the zobrist key of the last 2 moves (see board::Board::get_dm_key(), in particular floor at
* root sp0).
* - always overwrite: fancy ageing schemes, or seveal slots per move pair did not work in testing.

And it's worth at least 15 elo.

Latter I added to Andscacs, in my current developing version that is not published, guess what, Triple move refutation table, and Quadruple move refutation table
They win something less, but something.

Is not the same, but gives the idea that there is room to win something with those ideas.

Hmm… see also http://www.talkchess.com/forum/viewtopic.php?t=55438
(I haven't tried it yet)