On history and piece square tables

[lucasart]

In Jazz I've never managed to make history (for move ordering) work. Every time I try it it's a regression. Move ordering in Jazz (without history tables) is the reasonably standard hash move/winning captures/killer moves/losing captures/quiet moves. Quiet moves are sorted according to the change in score from the piece square tables.

History tables are very important in DiscoCheck. The reason why it's a superior technique to piece/square table is that it is dynamic. Piece/square table fo ordering quiet moves will probably work well at low depth, but eventually history (if done right) is better.

Regarding move ordering, what you describe sounds ok-ish, but it can be improved. Here's what I do in DiscoCheck to give an idea (for search not qsearch):
* hash move
* good captures/promotions, by descending SEE
* quiet moves: 2 killers, counter move, other quiet moves by descending history score
* bad captures/promotions by descending SEE

History table works as follows:
* history[color][piece][tsq] (reset to zero before each search)
* when a (quiet) move fails high, mark it as good by adding depth^2
* all moves that were search previously to the move that failed high are marked as bad, by susbreacting depth^2
* overflow
- cap the depth^2 bonus/malus with a constant value HistoryMax
- whenever a value exceeds, in absolute value the bound HistoryMax, divide the whole table by 2

It works very well, and the effect of having a good history table mechanism is amplified by search move count dependant (ie. history score dependant) search reductions (a.k.a. LMR).

This history method is by Tord Romstad, and was pionereed by Glaurung. It has changed a little bit in Stockfish (handling of overflows is different in SF, though the original Glaurung method worked best for me), but it's mostly the same.

I suggest you throw away all your complicated code and try that instead. Simple and general methods are always superior to hacky/complex techniques IMO.

PS: Yes, I use SEE and not MVV/LVA. I have found it works better in DiscoCheck, although MVV/LVA works better for the qsearch. As a speed optimization, I revert to MVV/LVA for ordering search captures in predicted All nodes. I'm not sure such an optimization is a good idea though: typically a compromise speed/accuracy which works well at super fast tc that I use for testing, but can backfire at long tc (i cannot measure).

[Evert]

History tables are very important in DiscoCheck. The reason why it's a superior technique to piece/square table is that it is dynamic. Piece/square table fo ordering quiet moves will probably work well at low depth, but eventually history (if done right) is better.

Quite. That's why I want to get rid of it (the scaling is probably even worse for Jazz because the PSQ used is specifically for the root position).

Regarding move ordering, what you describe sounds ok-ish, but it can be improved. Here's what I do in DiscoCheck to give an idea (for search not qsearch):
* hash move
* good captures/promotions, by descending SEE
* quiet moves: 2 killers, counter move, other quiet moves by descending history score
* bad captures/promotions by descending SEE

Looks pretty much the same as mine; I said I do losing captures ahead of quiet moves, in fact I don't: losing captures are scored according to their SEE value and so have negative scores, meaning they are below quiet moves.

History table works as follows:
* history[color][piece][tsq] (reset to zero before each search)
* when a (quiet) move fails high, mark it as good by adding depth^2
* all moves that were search previously to the move that failed high are marked as bad, by susbreacting depth^2
* overflow
- cap the depth^2 bonus/malus with a constant value HistoryMax
- whenever a value exceeds, in absolute value the bound HistoryMax, divide the whole table by 2

Ok, so that is the same as what I do, except that my scheme also adjusts the history table in ALL nodes. Looks like that may be the problem then.

I suggest you throw away all your complicated code and try that instead.

What complicated code?

Yes, I use SEE and not MVV/LVA. I have found it works better in DiscoCheck,

Same, although my SEE is lazy: if the first capture is an up-capture I return a guestimate of the expected gain instead of the full SEE.

[Mincho Georgiev]

Do PV nodes really have such a strong impact here

At least in my case.

[jd1]

Having said that, there is a difference in implementation between what I do and what an engine like Stockfish does. I penalise moves that don't improve alpha immediately after they're searched, while Stockfish penalises them by going through the move list again after all moves have been searched. This seemed, to me, to be a bit clumsy in that the move list has to be run through twice. It's possible that I missed the point here though, which may be not to penalise quiet moves at all in ALL nodes, where move ordering is meaningless and we can learn nothing from it.

Something to try...

IMHO this is likely the problem.

I think penalizing all moves in ALL nodes will add too much randomness, especially since ALL node moves are going to account for the majority of your history updates (at CUT nodes most likely we don't try most of the moves).

You could also try only adding a bonus (depth*depth), without subtracting depth*depth from moves which fail low.

For Toga, what works best is:
- All moves that improves alpha are incremented by depth*depth (This is significantly better than only incrementing moves which fail high only for me).
- All moves tried before the move which failed high are decremented by depth. (not depth*depth as in Stockfish).

Actually this "uneven" increment/decrement scheme makes sense to me as I would think that a fail high is more important than a fail low. I think a move which has failed high 10 times and failed low 20 times is better than another move which has failed high once and failed low 10 times (assuming identical depths).

An "even" scheme like Stockfish's will place the second move ahead - and this is clearly worse for Toga.

Jerry

[lucasart]

History table works as follows:
* history[color][piece][tsq] (reset to zero before each search)
* when a (quiet) move fails high, mark it as good by adding depth^2
* all moves that were search previously to the move that failed high are marked as bad, by susbreacting depth^2
* overflow
- cap the depth^2 bonus/malus with a constant value HistoryMax
- whenever a value exceeds, in absolute value the bound HistoryMax, divide the whole table by 2

Ok, so that is the same as what I do, except that my scheme also adjusts the history table in ALL nodes. Looks like that may be the problem then.

By ALL nodes, do you mean *actual* ALL nodes ? (ie. a non PV node that does indeed fail low). Or predicted ALL nodes ?

Just to clarify, I update the history table whenever I get a fail high, regardless of the predicted node type. But I do not score negative history bonus when all moves fail low, as that would pollute the table significantly.

[Evert]

By ALL nodes, do you mean *actual* ALL nodes ? (ie. a non PV node that does indeed fail low). Or predicted ALL nodes ?

Actual. I don't do any node-type prediction.

Just to clarify, I update the history table whenever I get a fail high, regardless of the predicted node type. But I do not score negative history bonus when all moves fail low, as that would pollute the table significantly.

Ok, that's what I thought. It's different from what I do (or rather, don't, since history is disabled) at the moment and may well be why it doesn't work.

Hopefully I can start a test with this change tonight...

[Evert]

Having said that, there is a difference in implementation between what I do and what an engine like Stockfish does. I penalise moves that don't improve alpha immediately after they're searched, while Stockfish penalises them by going through the move list again after all moves have been searched. This seemed, to me, to be a bit clumsy in that the move list has to be run through twice. It's possible that I missed the point here though, which may be not to penalise quiet moves at all in ALL nodes, where move ordering is meaningless and we can learn nothing from it.

Something to try...

Ok, excluding moves at ALL nodes from the penalty list seems to have tipped the scales. It's not a huge plus over using the piece square tables, no more than +4 at self play and probably smaller, but it's a starting point. I'm sure there are things that can be refined/tuned here (rate of aging for instance).

[Don]

The key insight here I learned from glaurung, I don't know the origins but you need to "age" the history tables. In other words the most recent events for one of these records is more important. I think in Glaurung they would go in every once in a while and cut the entries in half. In Komodo we use a more dynamic anytime method but it's not an important distinction. You are basically keeping the success ratio of the moves (and you don't worry about move that have not been played.)

I don't sort these by see() by the way as was stated here, I think that was a misunderstanding. In fact to our surprise the history entries seem to over-ride see(), in other words it hurts to change the ordering based on SEE().

Hello Evert,

It seems you're going the way of 'complexity'. At times, the best way may be the way of simplicity. And the 'experience' of the top engines should tell us the way to go. There is usually no perfect way to do a thing and, in such cases, simplicity may be best.

Don gave good pointers on how move ordering is done in komodo. He uses history[color][type][to] as you do. Quite moves are ordered by calling SEE and sorted back if they are losing. If you use PST, then you cannot use history - so there is a choice to be made.

It may be enough to just increase the history counter for good moves (beta cutoff). Reducing history may not help very much - a low history count, in itself, indicates 'badness' without the need to add history reduction. It is like what Bob use to say - when a move is extended, it is like a reduction for moves that are not extended, killing two birds with one stone.

I've got hints about simplifying things from this forum. After I actually made the simplification, I come to realize that it is better. An example is not to have a separate quiescent search routine, but just to merge it with a single search routine.

Best Regards,
Rasjid.

[Evert]

Ok, excluding moves at ALL nodes from the penalty list seems to have tipped the scales. It's not a huge plus over using the piece square tables, no more than +4 at self play and probably smaller, but it's a starting point. I'm sure there are things that can be refined/tuned here (rate of aging for instance).

Aaaaand with the test completed we're at a whopping -2 elo.

As I said though, there are more things I can tweak to try to make this work.

[Evert]

Slight update:

Test is still running, but it looks like I found a formulation that gives a (considerable) improvement. I can't say for certain yet because the currently running version has some non-history related changes as well and it's possible that those are actually responsible for the improvement. More on that when I know it.

What I actually wanted to bring up was what I did to select the test version. Rather than try one tweak and wait several (many) hours for the test to run I output some statistics from my benchmark test, particularly the distribution of cutoff move numbers (and the average move that caused a cutoff). I then optimised this average directly instead of playing games. Ultimately I'm playing games to confirm whether it's any good (and it seems to be), but I was quite pleasantly surprised that this simple idea seems to work as well as it does.