Different behavior with different hash sizes. (Stockfish 1.9

[bob]

It is perfectly normal for a particular program to produce the same scores using different hash sizes for some positions

Hi Bob,

I am extremely surprised at that, at least when you look at PVs (and nodes) obtained after some time elapsed, when the hash table has been overly "filled" - don't pick at me for the word!

Of course, if you have Gigabyte large hashtables, and you look at PVs/nodes after 1 second (or less), you may have the same for 1 or 2 GB hash size...

Notice the "some" in "some positions". For some positions, hashing just doesn't help. For the average case, it certainly helps...

[Arsha Mahdavi]

I hope this would be my last question.

In fact, some times hashing _increases_ the size of the tree, because of this grafting issue. But in doing so, you actually get a better search result than if you didn't have hashing at all.
Hash hits can do two things. (1) reduce the size of the tree by saving the effort of searching beyond the hash hit. (2) possibly increase the size of the tree because it introduces deeper searches than expected, which provides more accurate information.

In short, you can save time, or possibly gain increased accuracy. And sometimes even both.

Please look carefully at two different analyses by Stockfish 1.9. It seems that in this particular position, smaller hash table has increased the size of the tree but provided more accurate information. Especially it’s apparent at depth 17 (in bold case).
We also could conclude that “It has reduced the size of tree (regarding 256 MB hash table)” (save time!) but again it has not provided the accurate information.

Can you explain what was happened in these two circumstances?

Position:

• 6k1/3qr1p1/1pn1pr2/p5Np/1nPPQP2/2B3P1/1R4K1/4R3 b - - 0 59

Stockfish 1.9 128 MB hash:

• 1...Rh6 2.Rh1 Qb7 3.Ra1 Qc8 4.Re2 h4 5.gxh4 Qf8 6.Bxb4 Nxb4 7.d5 Rxh4 8.d6
  +/- (1.13) Depth: 14 00:00:07 2007kN
  1...Rh6 2.Rh1 Qb7 3.Ra1 Qc8 4.Re2 h4 5.gxh4 Qf8 6.Bxb4 Nxb4 7.d5 Rxh4 8.d6
  +/- (1.21) Depth: 15 00:00:08 2384kN
  1...Rh6 2.Rh1 Kh8 3.Re2 Qe8 4.Ree1 Na2 5.Bb2 a4 6.Ra1
  +/- (1.29) Depth: 15 00:00:10 3042kN
  1...Rh6 2.Rbe2 h4 3.Rh1 hxg3 4.Rxh6 gxh6 5.Nxe6
  +- (1.45) Depth: 15 00:00:14 4276kN
  1...Rh6 2.Rbe2 Kf8 3.Rh1 Nd8 4.Rb1 Ndc6 5.Ra1 Qe8 6.Rh1 Kg8 7.Ree1 Qd7 8.Re2 Kh8 9.Re3 Na2 10.Bb2 Nab4 11.Ra1 Qd6 12.Nf3 Qd7
  +/- (1.33) Depth: 15 00:00:20 6547kN
  1...Rh6 2.Rbe2 Kf8 3.Qf3 Kg8 4.f5 exf5 5.d5 h4 6.dxc6 Rxe2+ 7.Rxe2 h3+ 8.Nxh3 Qxc6 9.Qxc6 Nxc6 10.Ng5
  +- (1.53) Depth: 16 00:00:27 8877kN
  1...Rh6 2.Rbe2 Qc8 3.d5 exd5 4.Qxe7 Nxe7 5.Rxe7 Qf8 6.Re8 dxc4 7.Rxf8+ Kxf8 8.Ne6+ Kf7 9.Nxg7 Nd5 10.Be5 Rh7 11.Nf5 Kg6 12.Nh4+ Kf7 13.Kf3 Rh6
  +- (1.65) Depth: 16 00:00:33 10959kN
  1...Rh6 2.Rbe2 Qc8 3.d5 exd5 4.Qxe7 Nxe7 5.Rxe7 Qf8 6.Re8 dxc4 7.Rxf8+ Kxf8 8.Ne6+ Kf7 9.f5 Nd3 10.Rb1 Nb4 11.Bxb4 axb4 12.Rxb4 Rf6 13.Rxc4 Rxf5 14.Nd4 Rc5 15.Rb4 Rd5 16.Kf3 g6 17.Ke4
  +- (1.85) Depth: 17 00:00:44 15400kN
  1...Rh6 2.Rbe2 Qd6 3.f5 h4 4.gxh4 exf5 5.Qxf5 Qf6 6.Rxe7 Qxf5 7.Re8+ Qf8 8.Rxf8+ Kxf8 9.Re4 Nd8 10.d5 Nd3 11.Kf3 a4 12.Ke3 Nc5 13.Rf4+ Kg8 14.Ne4 a3 15.Nxc5
  +- (1.97) Depth: 18 00:01:11 25983kN
  1...Rh6 2.Rbe2 Qd6 3.f5 h4 4.gxh4 exf5 5.Qxf5 Qf6 6.Qh3 Rxe2+ 7.Rxe2 Qf8 8.d5 Nd8 9.Qg3
  +- (2.22) Depth: 19 00:01:58 43869kN
  1...Rh6 2.Rbe2 Qd6 3.f5 h4 4.gxh4 exf5 5.Qxf5 Qf6 6.Qh3 Rxe2+ 7.Rxe2 Qf8 8.d5 Nd8 9.Qg3
  +- (2.46) Depth: 19 00:03:10 70280kN
  1...Rh6 2.Rbe2 Nd8 3.d5 h4 4.gxh4 Nb7 5.Qd4 Nc5 6.Bxb4 axb4 7.f5 e5 8.Rxe5 Rxe5 9.Qxe5 Rf6 10.Ne6 Qb7 11.Rg1 Rf7 12.Kh2 b3 13.Qd6
  +- (2.22) Depth: 19 00:04:39 103mN

Stockfish 1.9 256 MB hash:

• 1...Rh6 2.Rh1 Qb7 3.Ra1 Qc8 4.Re2 h4 5.gxh4 Qf8 6.Bxb4 Nxb4 7.d5 Rxh4 8.d6
  +/- (1.13) Depth: 14 00:00:09 2007kN
  1...Rh6 2.Rh1 Qb7 3.Ra1 Qc8 4.Re2 h4 5.gxh4 Qf8 6.Bxb4 Nxb4 7.d5 Rxh4 8.d6
  +/- (1.21) Depth: 15 00:00:10 2384kN
  1...Rh6 2.Rh1 Kh8 3.Re2 Qe8 4.Ree1 Na2 5.Bb2 a4 6.Ra1
  +/- (1.29) Depth: 15 00:00:12 3042kN
  1...Rh6 2.Rh1 Kh8 3.Re2 Qe8 4.Ree1 Na2 5.Bb2 Nab4 6.g4 h4 7.Nf3 Kg8 8.Nxh4 a4 9.Nf3 Rf7 10.Rxh6 gxh6
  +/- (1.33) Depth: 15 00:00:14 3649kN
  1...Rh6 2.Rh1 Re8 3.Re2 Re7 4.Kg1 Qc8 5.Reh2 g6 6.Rb2 Qa6 7.Qe2 Qc8 8.Kg2 h4 9.gxh4 Qd7 10.Qe4
  +/- (1.21) Depth: 16 00:00:21 6218kN
  1...Rh6 2.Rh1 Re8 3.Re2 Re7 4.Re3 Qe8 5.Bxb4 axb4 6.d5 exd5 7.Qxd5+ Kf8
  +/- (1.25) Depth: 17 00:00:36 11692kN
  1...Rh6 2.Rh1 Re8 3.Re2 Re7 4.Re3 Qe8 5.Ree1 Kh8 6.Ra1 Qd7 7.Rhe1 Qb7 8.d5 exd5 9.Qf5
  +/- (1.29) Depth: 18 00:00:55 18448kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 Na6 5.f5 e5 6.Ne6 h4 7.Rh1 hxg3 8.Rxh6 gxh6 9.Kxg3
  +/- (1.37) Depth: 19 00:01:15 25582kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 Na6 5.f5 e5 6.Ne6 Nc5 7.Qh4 Qb7 8.Nxc5 bxc5 9.Rxe5 Rxe5 10.Rxe5 Qb2+
  +/- (1.21) Depth: 19 00:01:36 33518kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 Na6 5.Qf3 Nc5 6.f5 e5 7.Rxe5 Rxe5 8.Rxe5 a4 9.d6 Rxd6 10.Qxh5 Rd2+ 11.Kh3
  +- (1.45) Depth: 19 00:01:41 35535kN
  1...Rh6 2.Rbe2 h4 3.Rh1 hxg3 4.Rxh6 gxh6 5.Nxe6
  +- (1.61) Depth: 19 00:02:09 46260kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 h4 5.gxh4 Qe8 6.Qd4 Rxh4 7.d6 Rg4+ 8.Kf1 e5 9.Qe4 Rxg5 10.fxg5 Re6 11.Rd1 Qd7 12.Qa8+ Re8 13.Qe4
  +- (1.69) Depth: 19 00:02:42 58878kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 Re8 5.Nxe6 b5 6.cxb5 Qd7 7.f5 Qxd5 8.Qxd5 Nxd5 9.Rd2 Nb6 10.Rd6 Rb8 11.Rc1 Rf6 12.Rcc6 Na4 13.Rc7 Rxf5 14.Rd4
  +- (1.81) Depth: 20 00:04:46 107mN

[Dann Corbit]

With bigger hash it has the right move four seconds faster to the same depth.

What's to explain?

I think it is folly to try to fully understand hash table behavior by analyzing the output for a single position.

Better to do a code review and then to trace the code if you want to understand it.

[bob]

I hope this would be my last question.

In fact, some times hashing _increases_ the size of the tree, because of this grafting issue. But in doing so, you actually get a better search result than if you didn't have hashing at all.
Hash hits can do two things. (1) reduce the size of the tree by saving the effort of searching beyond the hash hit. (2) possibly increase the size of the tree because it introduces deeper searches than expected, which provides more accurate information.

In short, you can save time, or possibly gain increased accuracy. And sometimes even both.

Please look carefully at two different analyses by Stockfish 1.9. It seems that in this particular position, smaller hash table has increased the size of the tree but provided more accurate information. Especially it’s apparent at depth 17 (in bold case).
We also could conclude that “It has reduced the size of tree (regarding 256 MB hash table)” (save time!) but again it has not provided the accurate information.

Can you explain what was happened in these two circumstances?

Position:

• 6k1/3qr1p1/1pn1pr2/p5Np/1nPPQP2/2B3P1/1R4K1/4R3 b - - 0 59

Stockfish 1.9 128 MB hash:

• 1...Rh6 2.Rh1 Qb7 3.Ra1 Qc8 4.Re2 h4 5.gxh4 Qf8 6.Bxb4 Nxb4 7.d5 Rxh4 8.d6
  +/- (1.13) Depth: 14 00:00:07 2007kN
  1...Rh6 2.Rh1 Qb7 3.Ra1 Qc8 4.Re2 h4 5.gxh4 Qf8 6.Bxb4 Nxb4 7.d5 Rxh4 8.d6
  +/- (1.21) Depth: 15 00:00:08 2384kN
  1...Rh6 2.Rh1 Kh8 3.Re2 Qe8 4.Ree1 Na2 5.Bb2 a4 6.Ra1
  +/- (1.29) Depth: 15 00:00:10 3042kN
  1...Rh6 2.Rbe2 h4 3.Rh1 hxg3 4.Rxh6 gxh6 5.Nxe6
  +- (1.45) Depth: 15 00:00:14 4276kN
  1...Rh6 2.Rbe2 Kf8 3.Rh1 Nd8 4.Rb1 Ndc6 5.Ra1 Qe8 6.Rh1 Kg8 7.Ree1 Qd7 8.Re2 Kh8 9.Re3 Na2 10.Bb2 Nab4 11.Ra1 Qd6 12.Nf3 Qd7
  +/- (1.33) Depth: 15 00:00:20 6547kN
  1...Rh6 2.Rbe2 Kf8 3.Qf3 Kg8 4.f5 exf5 5.d5 h4 6.dxc6 Rxe2+ 7.Rxe2 h3+ 8.Nxh3 Qxc6 9.Qxc6 Nxc6 10.Ng5
  +- (1.53) Depth: 16 00:00:27 8877kN
  1...Rh6 2.Rbe2 Qc8 3.d5 exd5 4.Qxe7 Nxe7 5.Rxe7 Qf8 6.Re8 dxc4 7.Rxf8+ Kxf8 8.Ne6+ Kf7 9.Nxg7 Nd5 10.Be5 Rh7 11.Nf5 Kg6 12.Nh4+ Kf7 13.Kf3 Rh6
  +- (1.65) Depth: 16 00:00:33 10959kN
  1...Rh6 2.Rbe2 Qc8 3.d5 exd5 4.Qxe7 Nxe7 5.Rxe7 Qf8 6.Re8 dxc4 7.Rxf8+ Kxf8 8.Ne6+ Kf7 9.f5 Nd3 10.Rb1 Nb4 11.Bxb4 axb4 12.Rxb4 Rf6 13.Rxc4 Rxf5 14.Nd4 Rc5 15.Rb4 Rd5 16.Kf3 g6 17.Ke4
  +- (1.85) Depth: 17 00:00:44 15400kN
  1...Rh6 2.Rbe2 Qd6 3.f5 h4 4.gxh4 exf5 5.Qxf5 Qf6 6.Rxe7 Qxf5 7.Re8+ Qf8 8.Rxf8+ Kxf8 9.Re4 Nd8 10.d5 Nd3 11.Kf3 a4 12.Ke3 Nc5 13.Rf4+ Kg8 14.Ne4 a3 15.Nxc5
  +- (1.97) Depth: 18 00:01:11 25983kN
  1...Rh6 2.Rbe2 Qd6 3.f5 h4 4.gxh4 exf5 5.Qxf5 Qf6 6.Qh3 Rxe2+ 7.Rxe2 Qf8 8.d5 Nd8 9.Qg3
  +- (2.22) Depth: 19 00:01:58 43869kN
  1...Rh6 2.Rbe2 Qd6 3.f5 h4 4.gxh4 exf5 5.Qxf5 Qf6 6.Qh3 Rxe2+ 7.Rxe2 Qf8 8.d5 Nd8 9.Qg3
  +- (2.46) Depth: 19 00:03:10 70280kN
  1...Rh6 2.Rbe2 Nd8 3.d5 h4 4.gxh4 Nb7 5.Qd4 Nc5 6.Bxb4 axb4 7.f5 e5 8.Rxe5 Rxe5 9.Qxe5 Rf6 10.Ne6 Qb7 11.Rg1 Rf7 12.Kh2 b3 13.Qd6
  +- (2.22) Depth: 19 00:04:39 103mN

Stockfish 1.9 256 MB hash:

• 1...Rh6 2.Rh1 Qb7 3.Ra1 Qc8 4.Re2 h4 5.gxh4 Qf8 6.Bxb4 Nxb4 7.d5 Rxh4 8.d6
  +/- (1.13) Depth: 14 00:00:09 2007kN
  1...Rh6 2.Rh1 Qb7 3.Ra1 Qc8 4.Re2 h4 5.gxh4 Qf8 6.Bxb4 Nxb4 7.d5 Rxh4 8.d6
  +/- (1.21) Depth: 15 00:00:10 2384kN
  1...Rh6 2.Rh1 Kh8 3.Re2 Qe8 4.Ree1 Na2 5.Bb2 a4 6.Ra1
  +/- (1.29) Depth: 15 00:00:12 3042kN
  1...Rh6 2.Rh1 Kh8 3.Re2 Qe8 4.Ree1 Na2 5.Bb2 Nab4 6.g4 h4 7.Nf3 Kg8 8.Nxh4 a4 9.Nf3 Rf7 10.Rxh6 gxh6
  +/- (1.33) Depth: 15 00:00:14 3649kN
  1...Rh6 2.Rh1 Re8 3.Re2 Re7 4.Kg1 Qc8 5.Reh2 g6 6.Rb2 Qa6 7.Qe2 Qc8 8.Kg2 h4 9.gxh4 Qd7 10.Qe4
  +/- (1.21) Depth: 16 00:00:21 6218kN
  1...Rh6 2.Rh1 Re8 3.Re2 Re7 4.Re3 Qe8 5.Bxb4 axb4 6.d5 exd5 7.Qxd5+ Kf8
  +/- (1.25) Depth: 17 00:00:36 11692kN
  1...Rh6 2.Rh1 Re8 3.Re2 Re7 4.Re3 Qe8 5.Ree1 Kh8 6.Ra1 Qd7 7.Rhe1 Qb7 8.d5 exd5 9.Qf5
  +/- (1.29) Depth: 18 00:00:55 18448kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 Na6 5.f5 e5 6.Ne6 h4 7.Rh1 hxg3 8.Rxh6 gxh6 9.Kxg3
  +/- (1.37) Depth: 19 00:01:15 25582kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 Na6 5.f5 e5 6.Ne6 Nc5 7.Qh4 Qb7 8.Nxc5 bxc5 9.Rxe5 Rxe5 10.Rxe5 Qb2+
  +/- (1.21) Depth: 19 00:01:36 33518kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 Na6 5.Qf3 Nc5 6.f5 e5 7.Rxe5 Rxe5 8.Rxe5 a4 9.d6 Rxd6 10.Qxh5 Rd2+ 11.Kh3
  +- (1.45) Depth: 19 00:01:41 35535kN
  1...Rh6 2.Rbe2 h4 3.Rh1 hxg3 4.Rxh6 gxh6 5.Nxe6
  +- (1.61) Depth: 19 00:02:09 46260kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 h4 5.gxh4 Qe8 6.Qd4 Rxh4 7.d6 Rg4+ 8.Kf1 e5 9.Qe4 Rxg5 10.fxg5 Re6 11.Rd1 Qd7 12.Qa8+ Re8 13.Qe4
  +- (1.69) Depth: 19 00:02:42 58878kN
  1...Rh6 2.Rbe2 Qc8 3.Bxb4 Nxb4 4.d5 Re8 5.Nxe6 b5 6.cxb5 Qd7 7.f5 Qxd5 8.Qxd5 Nxd5 9.Rd2 Nb6 10.Rd6 Rb8 11.Rc1 Rf6 12.Rcc6 Na4 13.Rc7 Rxf5 14.Rd4
  +- (1.81) Depth: 20 00:04:46 107mN

As I explained, there are two possible effects from hashing, with respect to the size of the tree.

(1) reduce the size of the tree due to saving effort when you encounter the same position a second time.

(2) increase the size of the tree because of the grafting between nodes, which "can" set an N-ply search see deeper than N plies. Sometimes this will increase the size of the tree. Sometimes this will actually reduce the size of the tree.

(2) above is both unpredictable and inconsistent. If you make the table big enough, you should get the same result each and every time. If the table has any overwrites at all, these could be to inconsequential positions, or they could cause you to lose critical positions that would either provide a more accurate score or a smaller (sometimes larger) tree.

The effect is quite random, overall, but on average, it improves the strength of the program significantly. In general, bigger hash lets you search deeper, until you reach a point where the hash is large enough that no information is lost due to replacement policy choices. For a single position, you can get almost any result you might dream of...

[ernest]

[For some positions, hashing just doesn't help.

Any example (trivial or not)?

[Dann Corbit]

[For some positions, hashing just doesn't help.

Any example (trivial or not)?

Here is one from gedankenexperiment:

A long series of single reply moves. There are no transpositions to benefit from. A hash table will decrease performance, because of also performing the work of computing the hash, storing the hash table entries and looking for them.

[ernest]

A long series of single reply moves.

OKOK Dann...
I mean a position with no game background, you just perform infinite analysis after clearing the hashtable.

[bob]

[For some positions, hashing just doesn't help.

Any example (trivial or not)?

Not that I have saved. The obvious example where it helps is fine 70 where you can't see the win until somewhere beyond depth=26 without hashing, yet you see it at between 18 and 24 plies with hashing (24 is a normal range due to search reductions and pruning).

[ernest]

The obvious example where it helps is fine 70

Indeed I just did infinite analysis on Fine #70 with Rybka 4 (1-cpu for reproducibility) with 512 MB hash, then 256 MB hash.
Of course, the PVs and nodes were different.
I have yet to see a position where, in infinite analysis, PVs and nodes are the same for different hash sizes!

[bob]

The obvious example where it helps is fine 70

Indeed I just did infinite analysis on Fine #70 with Rybka 4 (1-cpu for reproducibility) with 512 MB hash, then 256 MB hash.
Of course, the PVs and nodes were different.
I have yet to see a position where, in infinite analysis, PVs and nodes are the same for different hash sizes!

Nodes may well always change for deep searches and different hash sizes. But I have encountered many positions where the score or PV doesn't change at all. The obvious trivial case is a forced mate, of course, or a forced tactical win. But even in many normal positions the score doesn't change, although the node count almost always does (and I can not recall a case where changing the hash size did not change the node count, unless you double the hash size when it was already large enough that no overwrites were happening). However, such a case might well exist, so I would not discount it.