History heuristic and fixed depth search

[petero2]

In texel the history heuristic is very important for ordering of quiet moves. As an experiment I removed the history heuristic and played fixed depth matches against the unmodified version. Here is the result:

Code: Select all

depth  elo change
2       -5
4      -34
5      -52
6      -85
8      -90

The value of the history heuristic for fixed depth searches is a lot larger than I would have guessed.

As expected if I also remove LMR/LMP the history heuristic no longer improves the strength in fixed depth matches:

Code: Select all

depth  elo change
4       -1
5      +11
6       +7
7      -20
8       +7

I can not explain the differences for different depths, but on average the change is around 0. Each elo estimate is based on approximately 4000 games so these results have a pretty high statistical significance.

Has this effect been measured in other engines, and if so, what was the result?

[hgm]

I don't understand this. Without LMR/LMP, history is just a move-ordering heuristic, not? So with or without it, you should get exactly the same moves, although the time it takes to fond them can be different.

[petero2]

I don't understand this. Without LMR/LMP, history is just a move-ordering heuristic, not? So with or without it, you should get exactly the same moves, although the time it takes to fond them can be different.

I can think of a few reasons why I don't get exactly the same moves:
1. Hash table grafting. What you find in the hash table depends on what you have already searched.
2. Root moves are ordered by the size of the subtree used to search them.
3. If two moves have the same score, the search will prefer the first move it found.
4. Futility pruning is only applied when at least one legal move has already been searched.

There may be more reasons, but the above is enough to explain why I don't get exactly the same (but reordered) search tree with and without the history heuristic.

[jordanbray]

In texel the history heuristic is very important for ordering of quiet moves. As an experiment I removed the history heuristic and played fixed depth matches against the unmodified version. Here is the result:

Code: Select all

depth  elo change
2       -5
4      -34
5      -52
6      -85
8      -90

The value of the history heuristic for fixed depth searches is a lot larger than I would have guessed.

As expected if I also remove LMR/LMP the history heuristic no longer improves the strength in fixed depth matches:

Code: Select all

depth  elo change
4       -1
5      +11
6       +7
7      -20
8       +7

I can not explain the differences for different depths, but on average the change is around 0. Each elo estimate is based on approximately 4000 games so these results have a pretty high statistical significance.

Has this effect been measured in other engines, and if so, what was the result?

Shouldn't you get a higer elo with LMR/LMP disabled on a fixed depth search? These numbers make sense to me, because you're not searching the nodes as much with LMR/LMP turned on.

[petero2]

In texel the history heuristic is very important for ordering of quiet moves. As an experiment I removed the history heuristic and played fixed depth matches against the unmodified version. Here is the result:

Code: Select all

depth  elo change
2       -5
4      -34
5      -52
6      -85
8      -90

The value of the history heuristic for fixed depth searches is a lot larger than I would have guessed.

As expected if I also remove LMR/LMP the history heuristic no longer improves the strength in fixed depth matches:

Code: Select all

depth  elo change
4       -1
5      +11
6       +7
7      -20
8       +7

I can not explain the differences for different depths, but on average the change is around 0. Each elo estimate is based on approximately 4000 games so these results have a pretty high statistical significance.

Has this effect been measured in other engines, and if so, what was the result?

Shouldn't you get a higer elo with LMR/LMP disabled on a fixed depth search? These numbers make sense to me, because you're not searching the nodes as much with LMR/LMP turned on.

I do get higher elo with LMR/LMP diisabled for fixed depth search, but I did not report that above. The second table compares "texel-no-history-no-lmr/lmp" vs "texel-no-lmr/lmp".

For "texel-no-lmr/lmp" vs "texel" I get:

Code: Select all

depth  elo change
4      +106
5      +136
6      +104
7      +116