History Gravity Formula

[gflohr]

I currently have a very basic implementation of the history heuristic. I give a bonus of depth * depth for quiet moves that case a beta cutoff.

In an older post (viewtopic.php?p=821798&hilit=history+gravity#p821798), the "history gravity formula" was mentioned. I've found this description of it: https://www.chessprogramming.org/Histor ... tic#Update

The example code there contains constants -MAX_HISTORY and MAX_HISTORY that clamp the bonus to a certain range. Should these constant be found by experiment? What are good starting values for them?

A little bit below, in the section about maluses, the bonus is now calculated as 300 x depth - 250 (instead of depth x depth) and also applied as a negative malus to the previously searched quiet moves. Why is the depth no longer squared when applying both bonuses and maluses? And are 300 and 250 again constants that have to be found by experiment?

[chrisw]

I currently have a very basic implementation of the history heuristic. I give a bonus of depth * depth for quiet moves that case a beta cutoff.

In an older post (viewtopic.php?p=821798&hilit=history+gravity#p821798), the "history gravity formula" was mentioned. I've found this description of it: https://www.chessprogramming.org/Histor ... tic#Update

The example code there contains constants -MAX_HISTORY and MAX_HISTORY that clamp the bonus to a certain range. Should these constant be found by experiment? What are good starting values for them?

A little bit below, in the section about maluses, the bonus is now calculated as 300 x depth - 250 (instead of depth x depth) and also applied as a negative malus to the previously searched quiet moves. Why is the depth no longer squared when applying both bonuses and maluses? And are 300 and 250 again constants that have to be found by experiment?

The clamping needs to be tight because (if SF) they are only using 16 bits for each value.

You don’t want the history value to blow up, so the bonus addition algorithm decays the prior and adds in the new in such a way as to limit the value.

You need to handle quite large values within the range because depth squared can get a bit large.

The constants act as limit definers and decay definers, iirc.

The absolute range can be whatever you want, you’ll be dividing it down (normalising) to “compare” it with other parameters from search. All a bit hit and miss and left to optimisation, trial and error. I doubt anyone call tell you why any values are as they are, because Elo.

[gflohr]

Okay, so the constants are only the result of trial and error, right?

But I have a problem, measuring progress. My initial move ordering was PV first, possible TT hit second, and for all other moves, I've used the static exchange evaluation SEE. And I do no pruning at all for the time being.

Then I've implemented the killer heuristic. I try to use two killer moves from the current ply, and one more from ply-2. That reduced the search time to depth 8 from the starting position from about 230 seconds to about 70 seconds. Yes, slow, because the engine is written in Perl as an experiment to see how much performance I can squeeze out of that language. But the effect is pretty obvious.

However, my SPRTs still seem to converge very slowly. In fact, so slowly that I wasn't able to run one of them to the end. I'm using fast-chess with a time control of 0/0:30+0.05. I expected that the new version of the engine would be able to look at more nodes and must always be a lot stronger than the old version, which has fewer cutoffs. But this is not the case. Does that suggest a bug in the search? Or should I change the time control?

Just a minimal implementation of the history heuristic reduces the search time to depth 8 even more, from 70 seconds to 40 seconds, but I'm reluctant to merge that code when I still don't have a reliable proof for the effect of the killer heuristic. I wonder if it is better to use a fixed search time in the SPRT to rule out idiosyncrasies of my time management, and a TT size of 0 to rule out bugs in the implementation of the transposition table?

[jdart]

You need to not use Perl. Perl is not the language you want for runtime performance.

Also, before worrying about tuning history, you need to make sure your engine is bug-free and has a reasonable search implementation. I don't know if your very slow speeds are from using Perl or from something wrong with the search (could be both).

Here is a simple test you could try: ECM position 1600: 2r2r2/p2qppkp/3p2p1/3P1P2/2n2R2/7R/P5PP/1B1Q2K1 w - - .

"go depth 8" with my engine visits 9645 nodes. That with null move pruning, history pruning, static eval pruning, etc. If your node count is way higher than this, either you do not have enough pruning, or you have a search bug, or both. (static eval pruning, aka reverse futility pruning, is actually one of the most effective pruning methods, followed by null move).

[Robert Pope]

You need to not use Perl. Perl is not the language you want for runtime performance.

Also, before worrying about tuning history, you need to make sure your engine is bug-free and has a reasonable search implementation. I don't know if your very slow speeds are from using Perl or from something wrong with the search (could be both).

Here is a simple test you could try: ECM position 1600: 2r2r2/p2qppkp/3p2p1/3P1P2/2n2R2/7R/P5PP/1B1Q2K1 w - - .

"go depth 8" with my engine visits 9645 nodes. That with null move pruning, history pruning, static eval pruning, etc. If your node count is way higher than this, either you do not have enough pruning, or you have a search bug, or both. (static eval pruning, aka reverse futility pruning, is actually one of the most effective pruning methods, followed by null move).

I just ran this through my engine and had over 2M nodes to depth 8. Any suggestions on how to troubleshoot why it's not pruning more?
1 -84 0 358 f4g4
2 -63 0 2361 f4g4 d7c7
3 -54 1 13668 f4h4 h7h5 d1d4 e7e5
4 -31 2 39930 f4h4 f8h8 d1g4 d7c7
5 -1 5 131268 f4h4 h7h5 h3g3 d7c7 d1h5
6 -31 12 351707 f4h4 h7h5 h3g3 d7b5 f5g6 b5c5
7 -28 29 934279 f4h4 h7h5 h3g3 d7b5 f5g6 b5b6 g1h1 f7g6
8 -20 63 2127297 f4h4 h7h5 h3g3 c4e5 h4h5 d7b5 g1h1 b5c5
9 5 178 6126232 f4h4 f8h8 d1c1 d7b5 h3c3 c4b6 c1h6 g7f6 c3c8 h8c8
10 24 426 14589842 f5f6 e7f6 b1f5 d7b5 f5c8 f8c8 f4f2 c4e5 h3b3 b5c5 b3b7
11 29 789 26788273 f5f6 e7f6 b1f5 d7b5 f5c8 f8c8 f4f2 c4e5 h3b3 b5a4 d1e2 c8c1 f2f1

[jdart]

A really basic thing is - are you correctly using alpha-beta (negamax), with a zero-width search window for moves past the pv? (https://www.chessprogramming.org/Alpha- ... ementation).

Then, do you have the standard pruning such as reverse futility and null move, and are they working as intended?

I have built in a trace function to the program that, if enabled, prints out an indented list of each node, including pruning decisions, etc. Very useful for debugging: For example:

Code: Select all

trying 0. f5xg6 (0/44)
window [-32000, 32000]
 window [-32000,32000]
 stand pat score = -539
 trying 1. d7xh3
 pruned (SEE)
 trying 1. f7xg6
  window [-32000,539]
  stand pat score = 142
  trying 2. f4xf8
   window [-539,-142]
   stand pat score = -787
   trying 3. c8xf8
    window [142,539]
    stand pat score = -114
    trying 4. b1xg6
    pruned (SEE)
    trying 4. h3xh7
    pruned (SEE)
   3. c8xf8 -142
   **CUTOFF**

[abulmo2]

Here is a simple test you could try: ECM position 1600: 2r2r2/p2qppkp/3p2p1/3P1P2/2n2R2/7R/P5PP/1B1Q2K1 w - - .

"go depth 8" with my engine visits 9645 nodes.

I just ran this through my engine and had over 2M nodes to depth 8. Any suggestions on how to troubleshoot why it's not pruning more?
8 -20 63 2127297 f4h4 h7h5 h3g3 c4e5 h4h5 d7b5 g1h1 b5c5

Fruit 2.1 also searches about 2 MNodes. My simple engine Dumb prunes more and gets about 13 KNodes. Stockfish 17 prunes even more and visits only 4.9 KNodes. If you want to search less nodes, you should prune more, verify you move ordering quality and of course the accuracy of your evaluation function also plays a role.

[lithander]

Leorik 1 does not implement pruning or reductions (e.g. never fails to find a mate in X at exactly that search depth) and searches 12M nodes:

Code: Select all

info depth 8 score cp -12 nodes 12434457 nps 5228955 time 2378 pv f4h4 f8h8 d1c1 d7b5 c1h6 g7g8 b1e4 b5c5

...so 2M already has some prunings/reductions going, just not as much as modern engines.