Best move changes with hash table size

[brianr]

I am wondering why this should matter.
Perhaps it is related to LMR or other pruning methods?
Thanks.

[tpetzke]

The hash table influences move ordering, if in a small hash the entry is overwritten it can't supply a hash move to be tried first anymore. Maybe the otherwise hash move is now late in the list and reduced, so the trees will start to differ

Thomas...

[hgm]

Indeed, there is no guarantee that using a TT will not alter the search results. When you would only accept hits that have exactly the requested depth, then you could guarantee this. But that is rather detrimental to playing strength.

[xmas79]

I found myself that TT is one of the biggest causes of search instability. The size of TT matters. Playing with different TT sizes gives you different search trees, hence different search results. If you disable LMR and other pruning methods you will see the same effect. The problem is that TT entries gets overwritten during search. The best move you find during the early stage of an iteration will be stored in TT, but that entry will be likely overwritten if hash size is not "big enough" for the search tree you are searching. See my post to understand that.
http://www.talkchess.com/forum/viewtopic.php?t=48274
Here I faced a strange behaviour in a simpl KNBk endgame. The tree space is small (compared to midgames). If you set TT size to say 8Mb you will get a lot of overwrites, making best moves and PV difficult to retrieve. If you set to a big value (say 512Mb) you will get a lot less of overwrites, raising the chanches of getting the best move stored during search.

Natale.

[bob]

I am wondering why this should matter.
Perhaps it is related to LMR or other pruning methods?
Thanks.

Been the case for as long as I can remember, dating back to when I first added a hash table to my program (somewhere in later 70's...)

Fine 70 is a cute test. Most find it faster than the nominal 26 ply + capture search required to see winning the pawn. But if you fiddle with hash size, the depth where you find it can change.

very small hash:

18 0.02/18.00 1.06 1. Kb2 Ka8 2. Kc3 Kb7 3. Kd2 Kc8 4.
Ke3 Kd7 5. Kd3 Kc7 6. Kc4 Kb6 7. Kb3
Kb7 8. Kc2 Kb8 9. Kd3 Kb7 10. Ke3 Kb8
11. Kf3 Kc7 12. Kg3 Kd7
18 0.02/18.00 ++ 1. Kb1! (>+1.07)
18 0.02/18.00 ++ 1. Kb1! (>+1.36)
18 0.02/18.00 ++ 1. Kb1! (>+1.52)
18 0.02/18.00 ++ 1. Kb1! (>+1.84)
18 0.02/18.00 ++ 1. Kb1! (>+2.48)
18 0.02/18.00 3.17 1. Kb1 Kb7 2. Kc1 Kb8 3. Kc2 Kc7 4.
Kd3 Kc8 5. Kc4 Kd7 6. Kb5 Kc7 7. Kxa5
Kb7 8. Kb5 Kc7 9. a5 Kb7

bigger hash:

24 0.02/27.00 ++ 1. Kb1! (>+1.36)
24 0.02/27.00 ++ 1. Kb1! (>+1.52)
24 0.02/27.00 ++ 1. Kb1! (>+1.84)
24 0.03/27.00 ++ 1. Kb1! (>+2.48)
24 0.03/27.00 3.22 1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
Kc2 Kc8 5. Kd2 Kc7 6. Kd3 Kb7 7. Ke3
Kc7 8. Kf3 Kd7 9. Kg3 Ke7 10. Kh4 Kf6
11. Kh5 Ke7 12. Kg5 Kd7 13. Kxf5

It's all about the luck of overwriting the right/wrong entry...

[brianr]

I should have mentioned that I was specifically looking at different moves from a fixed depth search.
I suppose the extended depths will vary and thus the backed up scores to the full-width fixed depth will also be different.
My initial thinking was that there should only be one best move for a fixed depth, regardless of what the move ordering is, and that the single best move should still be found (which was not considering extensions).

[bob]

I should have mentioned that I was specifically looking at different moves from a fixed depth search.
I suppose the extended depths will vary and thus the backed up scores to the full-width fixed depth will also be different.
My initial thinking was that there should only be one best move for a fixed depth, regardless of what the move ordering is, and that the single best move should still be found (which was not considering extensions).

Notice that if you search to depth-18, you get two different moves and two different scores for the above...

It is not an ultra-frequent issue, but it is not exactly rare either.

Example, search to depth=18 with hash=64K and hash=128K:


18 0.01/18.00 1.06 1. Kb2 Ka8 2. Kc3 Kb7 3. Kd2 Kc8 4.
Ke3 Kd7 5. Kd3 Kc7 6. Kc4 Kb6 7. Kb3
Kb7 8. Kc2 Kb8 9. Kd3 Kb7 10. Ke3 Kb8
11. Kf3 Kc7 12. Kg3 Kd7
18 0.01/18.00 ++ 1. Kb1! (>+1.07)
18 0.01/18.00 ++ 1. Kb1! (>+1.36)
18 0.01/18.00 ++ 1. Kb1! (>+1.52)
18 0.01/18.00 ++ 1. Kb1! (>+1.84)
18 0.01/18.00 ++ 1. Kb1! (>+2.48)
18 0.01/18.00 3.17 1. Kb1 Kb7 2. Kc1 Kb8 3. Kc2 Kc7 4.
Kd3 Kc8 5. Kc4 Kd7 6. Kb5 Kc7 7. Kxa5
Kb7 8. Kb5 Kc7 9. a5 Kb7
18-> 0.01/42.00 3.17 1. Kb1 Kb7 2. Kc1 Kb8 3. Kc2 Kc7 4.
Kd3 Kc8 5. Kc4 Kd7 6. Kb5 Kc7 7. Kxa5
Kb7 8. Kb5 Kc7 9. a5 Kb7


then hash=128K:

18 0.01/18.00 1.06 1. Kb2 Ka8 2. Kc3 Kb7 3. Kd2 Kc8 4.
Ke3 Kd7 5. Kd3 Kc7 6. Kc4 Kb6 7. Kb3
Kb7 8. Kc2 Kb8 9. Kd3 Kb7 10. Ke3 Kb8
11. Kf3 Kc7 12. Kg3 Kd7
18-> 0.01/18.00 1.06 1. Kb2 Ka8 2. Kc3 Kb7 3. Kd2 Kc8 4.
Ke3 Kd7 5. Kd3 Kc7 6. Kc4 Kb6 7. Kb3
Kb7 8. Kc2 Kb8 9. Kd3 Kb7 10. Ke3 Kb8
11. Kf3 Kc7 12. Kg3 Kd7

This has always been the best hash test position I've seen because it goes so deep so fast.

example:

47-> 10.06/18.00 10.06 1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
Kc2 Kc8 5. Kd2 Kb8 6. Ke2 Kc8 7. Kf3
Kd7 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kf7
11. Kg5 Kg7 12. Kxf5 Kf7 13. Ke4 Kf6
14. Kd3 Kf5 15. Kc4 Kxf4 16. Kb5 Ke4
17. Kc6 Kxd4 18. Kxd6 Kc4 19. Kc6 Kb4
20. d6 Kxa4 21. d7 Kb4 22. d8=Q a4
23. Qb6+ Kc3 24. Qc5+ Kb3 25. Qb5+
Ka3
48 10.98/18.00 ++ 1. Kb1! (>+10.22)
48 11.73/18.00 ++ 1. Kb1! (>+10.38)
48 12.65/18.00 ++ 1. Kb1! (>+10.70)
48 13.23/18.00 ++ 1. Kb1! (>+11.34)
48 15.19/18.00 ++ 1. Kb1! (>+12.62)