about hash tables and illogical behaviour of chess programs

[Uri Blass]

I find that stockfish is using the following code

Code: Select all

bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply, bool allowNullmove) {

    Value v = value_from_tt(tte->value(), ply);

    return   (allowNullmove || !(tte->type() & VALUE_TYPE_NULL) || !ZugDetection)

          && (   tte->depth() >= depth
              || v >= Max(value_mate_in(PLY_MAX), beta)
              || v < Min&#40;value_mated_in&#40;PLY_MAX&#41;, beta&#41;)

          && (   &#40;is_lower_bound&#40;tte->type&#40;)) && v >= beta&#41;
              || &#40;is_upper_bound&#40;tte->type&#40;)) && v < beta&#41;);

 
  &#125;

I think that this behaviour is illogical.

What is illogical is that you never prune when the depth is not enough and the score is not relevant.

Imagine that
depth=9
tte->depth()=8

beta=0
v=900(queen value)
(is_lower_bound(tte->type()) is true

The hash tables know that you win at least a queen based on search to depth 8

common sense tell me that it is a waste of time to make a search to depth 9 and it is better to return some score from the hash but stockfish like other chess programs do not do it.

Note that I tried to change the code but based on testing it seems that stockfish made strange blunders with the new code(blunders that I cannot reproduce from clear hash)

Here is my code that probably does not work at the bottom of this post(maybe 50 is too low but looking at games I simply found blunders by stockfish in good position and the main problem is that I could not reproduce the blunders from clear hash).

Here is one of the games(I admit that I did not play many games to get conclusions and for some reason stockfish1.7.1b with the relevant code played 30.Rf1 that I cannot reproduce)

Maybe you need not to return the score but to return score that is closer to beta v-50*depth_diff in case that v>beta or v+50*depth_diff when v<beta and maybe 50 is too small but common sense tell me that the idea must be good with the right implementation.

[Event "URI-AMD, Blitz:4'+4""]
[Site "URI-AMD"]
[Date "2010.04.18"]
[Round "2"]
[White "Stockfish 1.7.1b"]
[Black "Stockfish 1.7.1 JA"]
[Result "0-1"]
[ECO "A30"]
[Annotator "0.16;0.16"]
[PlyCount "146"]
[TimeControl "240+4"]

{W=16.8 ply; 562kN/s B=15.8 ply; 595kN/s} 1. c4 c5 2. Nf3 Nf6 3. Nc3 e6 4. g3
b6 5. Bg2 Bb7 6. O-O Be7 7. d4 cxd4 8. Qxd4 d6 9. Rd1 a6 10. b3 Nbd7 11. e4 {
Both last book move} Qc8 {0.16/17 14} 12. Qe3 {(Bc1-a3) 0.16/16 18} O-O {
0.20/17 11} 13. Nd4 {(Bc1-a3) 0.16/17 10} Qc5 {(Qc8-c7) 0.12/16 13} 14. f3 {
0.16/16 14} Rad8 {(Rf8-e8) 0.16/15 8} 15. Na4 {0.32/17 12} Qc7 {0.20/15 9} 16.
Ba3 {(Bg2-h3) 0.32/16 14} Nc5 {0.32/17 27} 17. Nc3 {0.32/17 12} Rfe8 {
(Rd8-c8) 0.32/17 15} 18. Bh3 {0.36/17 8} h6 {(Be7-f8) 0.20/16 15} 19. Rac1 {
(Bh3-g2) 0.36/16 8} Rc8 {0.44/15 7} 20. Rc2 {0.40/16 10} Bf8 {
(Qc7-b8) 0.36/17 50} 21. Qe2 {(Bh3-g2) 0.40/15 14} Nh7 {(Bf8-e7) 0.32/15 15}
22. Qf2 {(Ba3xc5) 0.32/16 10} Be7 {0.44/15 7} 23. Re2 {(Qf2-e3) 0.40/16 10} b5
{(Nh7-g5) -0.24/15 12} 24. cxb5 {0.08/15 8} Qa5 {0.00/15 7} 25. Nb1 {
(Ba3-b2) 0.00/16 10} axb5 {0.00/14 6} 26. b4 {0.16/15 6} Qa4 {-0.16/15 7} 27.
Ree1 {0.08/16 7} Nd7 {(Nc5-a6) 0.00/15 13} 28. Nxe6 {(Bh3-f1) -0.08/15 7} Rc2 {
-0.40/15 7} 29. Re2 {-0.40/15 7} Rc4 {-0.08/15 12} 30. Rf1 {
(Rd1-d2) -0.44/16 15} Bf6 {(Nd7-e5) -2.54/15 5} 31. Nxg7 {-2.74/16 6} Bxg7 {
-2.62/15 5} 32. Bxd7 {-2.74/17 9} Re7 {(Bg7-d4) -2.30/16 6} 33. Bb2 {
-2.30/15 12} Rxd7 {-2.34/15 5} 34. h4 {(Bb2xg7) -2.38/16 9} Bxb2 {-2.86/15 7}
35. Rxb2 {-2.54/14 3} d5 {-2.70/16 5} 36. Qd2 {(e4xd5) -2.62/16 8} Rdc7 {
(Qa4-a6) -3.07/15 7} 37. Qxh6 {(Qd2-e3) -2.78/16 10} Rc2 {-3.35/16 6} 38. Rxc2
{-3.03/17 6} Rxc2 {-3.51/16 7} 39. Rf2 {-3.47/16 11} dxe4 {-3.47/17 7} 40. fxe4
{-3.59/17 10} Bxe4 {-3.63/17 7} 41. Rxc2 {-3.59/17 5} Qxc2 {-4.00/18 5} 42. Nd2
{-3.43/16 1} Qd1+ {-4.24/18 5} 43. Kf2 {-3.71/19 9} Nf6 {-4.24/19 6} 44. Qg5+ {
-3.91/18 6} Kh7 {-4.00/18 4} 45. Ke3 {-4.60/20 8} Qe1+ {-4.60/18 6} 46. Kd4 {
-3.67/14 0} Qg1+ {(Qe1-a1+) -4.80/16 5} 47. Qe3 {-4.08/15 7} Qa1+ {-4.84/15 6}
48. Qc3 {-5.09/18 8} Qxa2 {-5.05/18 6} 49. Nxe4 {-5.41/18 6} Qd5+ {-4.92/11 1}
50. Ke3 {-3.71/6 0} Qxe4+ {-5.13/16 6} 51. Kd2 {-6.02/19 24} Qg2+ {
(Nf6-d5) -5.17/16 5} 52. Kc1 {-5.05/16 17} Ne4 {-5.33/17 4} 53. Qd3 {-5.05/16 6
} Kg6 {-5.37/15 5} 54. Qd4 {(Qd3-d8) -5.37/15 6} f5 {(Ne4xg3) -5.89/14 4} 55.
Qd7 {(h4-h5+) -5.57/16 9} Qxg3 {(Qg2-f1+) -6.26/15 5} 56. Qe8+ {-6.22/15 16}
Kf6 {-6.42/15 5} 57. Qc6+ {-6.30/16 10} Nd6 {-6.70/15 5} 58. Qc5 {-6.34/16 5}
Qe1+ {-7.23/14 4} 59. Kc2 {-6.42/16 5} Ke6 {-7.35/15 6} 60. h5 {-6.58/15 4}
Qe2+ {-8.80/14 6} 61. Kc1 {-6.94/15 5} f4 {(Qe2xh5) -10.06/16 6} 62. Qg5 {
(Qc5-c2) -6.46/14 5} f3 {(Qe2-c4+) -90.44/14 5} 63. Qg8+ {(Qg5-d2) -8.64/15 6}
Kd7 {(Ke6-e5) -93.37/21 6} 64. Qg7+ {-23.87/15 10} Kc6 {-#41/19 6} 65. Qc3+ {
-89.14/29 5} Qc4 {-93.47/19 6} 66. Qxc4+ {-89.09/20 0} bxc4 {-93.42/17 6} 67.
Kd2 {-89.29/27 5} Ne4+ {(c4-c3+) -#12/13 3} 68. Kc1 {(Kd2-e3) -93.42/23 5} f2 {
-#7/8 0} 69. h6 {(Kc1-c2) -106.20/26 5} f1=Q+ {-#6/7 0} 70. Kc2 {
(Kc1-b2) -#8/11 0} Qd3+ {(Qf1-g2+) -#4/6 0} 71. Kb2 {-#3/6 0} Qd2+ {-#3/6 0}
72. Ka3 {-#2/6 0} Qc1+ {-#2/6 0} 73. Ka2 {(Ka3-a4) -#1/6 0} Nc3# {-#1/6 0} 0-1

11042: Stockfish 1.7.1b - Stockfish 1.7.1 JA, URI-AMD, Blitz:4'+4"
4r1k1/1b1nbppn/3pN2p/1p6/qPr1P3/B4PPB/P3RQ1P/1N1R2K1 w - - 0 1

Analysis by Stockfish 1.7.1b:

30.Re2-d2
± (1.01) Depth: 1 00:00:00
30.Re2-d2 Nd7-e5
± (0.84) Depth: 2 00:00:00
30.Re2-d2 Nd7-e5 31.Ne6-f4
± (0.72) Depth: 3 00:00:00
30.Re2-d2 Nd7-e5 31.Ne6-f4 Nh7-g5
² (0.52) Depth: 4 00:00:00
30.Re2-d2 Nd7-e5 31.Ne6-f4 Nh7-g5 32.Bh3-g2
= (0.12) Depth: 5 00:00:00
30.Rd1-d4 Nh7-f6 31.Rd4xc4 b5xc4 32.Ne6-c7 Re8-c8
² (0.44) Depth: 5 00:00:00
30.Rd1-d4 Nh7-f6 31.Rd4xc4 b5xc4 32.Ne6-c7 Re8-c8
= (0.24) Depth: 6 00:00:00 24kN
30.Rd1-d4 Nh7-f6 31.Rd4xc4 b5xc4 32.Ne6-c7 Re8-c8
= (0.04) Depth: 6 00:00:00 29kN
30.Rd1-d4 Nh7-f6 31.Qf2-e3 Nd7-e5 32.Nb1-d2 Qa4-d1+ 33.Re2-e1
² (0.44) Depth: 6 00:00:00 34kN
30.Rd1-d4 Nh7-f6 31.Qf2-e3 Nd7-e5 32.Nb1-d2 Qa4-d1+ 33.Re2-e1 Rc4-c3
² (0.36) Depth: 7 00:00:00 38kN
30.Rd1-d4 Nh7-f6 31.Qf2-e3 Nd7-e5 32.Nb1-d2 Rc4-c2
² (0.28) Depth: 7 00:00:00 40kN
30.Rd1-d4 Nh7-f6 31.Qf2-e3 Nd7-e5 32.Nb1-d2 Rc4-c2
= (0.12) Depth: 7 00:00:00 41kN
30.Rd1-d4 Nh7-f6 31.Ne6-f4 Nd7-e5 32.Rd4-d2 g7-g5 33.Nf4-d3 g5-g4
= (0.20) Depth: 7 00:00:00 48kN
30.Rd1-d4 Nh7-f6 31.Re2-d2 Nd7-e5 32.Ne6-f4 g7-g5
= (-0.04) Depth: 8 00:00:01 55kN
30.Rd1-d4 Nh7-f6 31.Ne6-f4 Nd7-e5 32.Rd4-d2 g7-g5 33.Nf4-d3 g5-g4
³ (-0.28) Depth: 8 00:00:01 69kN
30.Rd1-d2 Nd7-e5 31.Ne6-f4 Nh7-g5 32.Bh3-g2 f7-f5 33.Nf4-d5 Bb7xd5 34.Rd2xd5 f5xe4 35.f3xe4
= (-0.08) Depth: 8 00:00:01 71kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Qf2-b6 Qa4-a8 34.e4-e5 Rc4-c6 35.Be6xf7+ Kg8xf7 36.e5-e6+ Kf7-g8 37.Qb6xb5
³ (-0.28) Depth: 9 00:00:01 96kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Qf2-b6 Qa4-a8 34.e4-e5 Rc4-c6 35.Qb6xb5 d6xe5 36.Qb5xe5 Qa8-a7+ 37.Qe5-d4 Qa7xd4+ 38.Rd2xd4
= (-0.12) Depth: 10 00:00:01 187kN
30.Rd1-d2 Nd7-e5 31.Ne6-d4 Nh7-g5 32.Bh3-g2 Ne5xf3+ 33.Nd4xf3 Ng5xe4
³ (-0.40) Depth: 11 00:00:01 293kN
30.Re2-d2 Nd7-e5 31.Ne6-f4 Nh7-g5 32.Bh3-g2 f7-f5 33.h2-h4 f5xe4 34.h4xg5 e4xf3 35.Bg2-h3
= (0.16) Depth: 11 00:00:01 379kN
30.Re2-d2 Nd7-e5 31.Ne6-f4 Nh7-g5 32.Bh3-g2 f7-f5 33.h2-h4 f5xe4 34.h4xg5 e4xf3 35.Qf2-b6 Bb7-e4 36.Bg2-f1 Be4xb1 37.Rd1xb1 Qa4xa3 38.Bf1xc4+ b5xc4 39.g5xh6 g7xh6
= (-0.20) Depth: 11 00:00:01 401kN
30.Re2-d2 Nd7-e5 31.Ne6-f4 Nh7-f6 32.Bh3-g2 g7-g5 33.Nf4-d3 Ne5xd3 34.Rd2xd3 g5-g4 35.Qf2-e3 g4xf3 36.Bg2xf3 Bb7xe4 37.Bf3xe4 Nf6xe4 38.Qe3xh6
= (-0.20) Depth: 12 00:00:02 626kN
30.Re2-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4
³ (-0.28) Depth: 13 00:00:04 826kN
30.Re2-d2 Nd7-e5 31.Ne6-f4 f7-f5 32.Bh3xf5 Nh7-g5 33.Bf5-e6+ Kg8-h7 34.Be6xc4 Ng5xf3+ 35.Kg1-h1 Nf3xd2
³ (-0.36) Depth: 13 00:00:05 1322kN
30.Re2-d2 Nd7-e5 31.Ne6-f4 f7-f5 32.Bh3xf5 Nh7-g5 33.Bf5-e6+ Kg8-h7 34.Be6xc4 Ng5xf3+ 35.Kg1-h1 Nf3xd2
³ (-0.52) Depth: 13 00:00:06 1660kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-d4 Bb7-a6 35.Qd4-b2
= (-0.12) Depth: 13 00:00:07 1987kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-d4 Re8-c8 35.Ba3-b2 Be7-f6 36.Qd4-b6 Qa4xa2 37.Qb6xb7 Qa2xb1+ 38.Kg1-f2 Rc8-e8 39.Re2-e1
³ (-0.40) Depth: 13 00:00:07 2005kN
30.Rd1-d2 Nd7-e5 31.Ne6-d4 Nh7-g5 32.Bh3-g2 d6-d5 33.e4xd5 Be7xb4 34.Ba3xb4 Rc4-c1+
³ (-0.60) Depth: 14 00:00:08 2420kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Be7-d8 36.Qa5xa8 Bd8-b6+ 37.Kg1-g2 Re8xa8 38.Ba3-b2 Ra8xa2 39.Nb1-c3 Ra2-a8 40.Nc3-b5
= (-0.20) Depth: 14 00:00:10 3041kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Nh7-f6 36.Nb1-c3 Nf6xe4 37.Nc3xe4 Bb7xe4 38.Qa5xa8 Be4xa8 39.b4-b5 Ba8-f3 40.Re2-e1
³ (-0.48) Depth: 14 00:00:10 3062kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Nh7-f6 36.Nb1-c3 Nf6xe4 37.Nc3xe4 Bb7xe4 38.Qa5xa8 Be4xa8 39.b4-b5 Ba8-f3 40.Re2-e1
³ (-0.28) Depth: 15 00:00:11 3343kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Be7-f6 36.Qa5xa8 Bb7xa8 37.b4-b5 Ba8xe4 38.Ba3-b4 Kg8-f8 39.Nb1-c3 Be4-d3 40.Re2xe8+ Kf8xe8 41.a2-a4 Bf6-d4+ 42.Kg1-g2
³ (-0.48) Depth: 15 00:00:11 3391kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Be7-f6 36.Qa5xa8 Bb7xa8 37.b4-b5 Ba8xe4 38.Ba3-b4 Kg8-f8 39.Nb1-c3 Be4-d3 40.Re2xe8+ Kf8xe8 41.a2-a4 Bf6-d4+ 42.Kg1-g2
³ (-0.40) Depth: 16 00:00:13 4613kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Be7-f6 36.Qa5xa8 Bb7xa8 37.b4-b5 Ba8xe4 38.Ba3-b4 Kg8-f8 39.Nb1-c3 Be4-d3 40.Re2xe8+ Kf8xe8 41.a2-a4 Bf6-d4+ 42.Kg1-g2
³ (-0.32) Depth: 16 00:00:13 4697kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Be7-f6 36.Qa5xa8 Bb7xa8 37.b4-b5 Ba8xe4 38.Ba3-b4 Kg8-f8 39.Nb1-c3 Be4-d3 40.Re2xe8+ Kf8xe8 41.a2-a4 Bf6-d4+ 42.Kg1-g2
= (-0.16) Depth: 16 00:00:13 4931kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Be7-f6 36.Qa5xa8 Bb7xa8 37.b4-b5 Ba8xe4 38.Ba3-b4 Kg8-f8 39.Nb1-c3 Be4-d3 40.Re2xe8+ Kf8xe8 41.a2-a4 Bf6-d4+ 42.Kg1-g2 Nh7-f6 43.a4-a5 Ke8-d7 44.Kg2-f3
= (-0.16) Depth: 16 00:00:13 4985kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Be7-f6 36.Qa5xa8 Bb7xa8 37.b4-b5 Ba8xe4 38.Ba3-b4 Kg8-f8 39.Nb1-c3 Be4-d3 40.Re2xe8+ Kf8xe8 41.a2-a4 Bf6-d4+ 42.Kg1-g2 Nh7-f6 43.a4-a5 Ke8-d7 44.Kg2-f3 Kd7-c7 45.Rd2-d1 g7-g5
³ (-0.40) Depth: 17 00:00:17 7767kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Re8-b8 35.Qb6-a5 Qa4-d7 36.Ba3-b2 Bb7-c6 37.a2-a3 Be7-d8 38.Qa5-f5 Qd7xf5 39.e4xf5 Nh7-f6 40.Nb1-c3 Bc6-f3 41.Re2-e6 Bf3-g4 42.Nc3-d5 Bg4xf5 43.Nd5-e7+ Bd8xe7 44.Re6xe7 Nf6-e4
³ (-0.44) Depth: 18 00:00:38 17059kN
30.Rd1-d2 Nd7-e5 31.Ba3-b2 f7xe6 32.Bh3xe6+ Kg8-h8 33.f3-f4 Re8-f8 34.Be6xc4 Ne5xc4 35.Nb1-c3 Qa4xb4 36.Nc3-d5 Bb7xd5 37.Rd2xd5 Nh7-f6
³ (-0.60) Depth: 19 00:00:52 23392kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Qa8-c8 36.Qa5-f5 Qc8-c6 37.Qf5-d5 Nh7-f6 38.Qd5xc6 Bb7xc6 39.Nb1-c3 Be7-d8 40.e4-e5 Bd8-b6+ 41.Kg1-f1 d6xe5 42.b4-b5 Bc6-f3
µ (-0.76) Depth: 19 00:01:17 34897kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Qa8-c8 36.Qa5-f5 Qc8-c6 37.Qf5-d5 Qc6-c7 38.Qd5-b5 Re8-b8 39.Qb5-a5 Qc7-d7 40.Ba3-b2 Bb7-c6 41.a2-a3 Be7-d8 42.Qa5-f5 Qd7xf5 43.e4xf5 Nh7-f6 44.Bb2-d4 Bc6-f3 45.Re2-e6 Bf3-g4
³ (-0.44) Depth: 19 00:01:30 40491kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Qa8-c8 36.Qa5-f5 Qc8-c6 37.Qf5-d5 Qc6-b6+ 38.Qd5-d4 Be7-d8 39.Kg1-f1 Qb6-a6 40.Rd2-c2 Nh7-f6 41.Rc2xc4 Re8xe4 42.Re2xe4 Nf6xe4
³ (-0.52) Depth: 20 00:01:48 48779kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Re8-b8 35.Qb6-a5 Qa4-e8 36.b4-b5 Bb7-c6 37.Nb1-c3 Bc6xb5 38.e4-e5 Be7-d8
³ (-0.60) Depth: 20 00:02:15 61194kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Re8-b8 35.Qb6-a5 Qa4-e8 36.b4-b5 Bb7-c6 37.Nb1-c3 Bc6xb5 38.Nc3xb5 Rb8xb5 39.Qa5-c3 Qe8-c6 40.Rd2-d4
³ (-0.36) Depth: 20 00:02:34 69608kN
30.Rd1-d2 Nd7-e5 31.f3-f4 f7xe6 32.Bh3xe6+ Ne5-f7 33.Be6xc4 b5xc4 34.Qf2-b6 Qa4-a8 35.Qb6-a5 Qa8-c8 36.Nb1-c3 Be7-d8 37.Qa5-f5 Qc8-a8 38.Qf5-b5 Nh7-f6 39.Ba3-b2 Bb7-a6 40.Qb5-f5 Qa8-a7+ 41.Kg1-f1 Qa7-b8 42.b4-b5 Ba6-c8 43.Qf5-g6 Bd8-b6
³ (-0.36) Depth: 20 00:02:38 71487kN

(, 18.04.2010)

Code: Select all

int pruning_value(int depth_diff)
{
	return 50*depth_diff;
}
bool additional_pruning_lower(Value beta,int depth_diff,Value v)
{
	//we have lower bound and if v is high enough we prune 
	if &#40;v<beta&#41;
		return false;
	if &#40;v >= Min&#40;value_mate_in&#40;PLY_MAX&#41;, beta+pruning_value&#40;depth_diff&#41;)) 
		return true;
	return false;
&#125;
bool additional_pruning_higher&#40;Value beta,int depth_diff,Value v&#41;
&#123;
	if &#40;v>=beta&#41;
		return false;
	if &#40;v<Max&#40;value_mated_in&#40;PLY_MAX&#41;,beta-pruning_value&#40;depth_diff&#41;))
		return true;
	return false;
&#125;
bool ok_to_use_TT&#40;const TTEntry* tte, Depth depth, Value beta, int ply, bool allowNullmove&#41; 
&#123;
	 Value v = value_from_tt&#40;tte->value&#40;), ply&#41;;
	 int depth_diff= Max&#40;depth-tte->depth&#40;),0&#41;;
	  
	 return   &#40;allowNullmove || !&#40;tte->type&#40;) & VALUE_TYPE_NULL&#41; || !ZugDetection&#41;
		 && (   &#40;is_lower_bound&#40;tte->type&#40;))&&additional_pruning_lower&#40;beta,depth_diff,v&#41;)
		 ||     &#40;is_upper_bound&#40;tte->type&#40;)) &&additional_pruning_higher&#40;beta,depth_diff,v&#41;) );


&#125;

[hgm]

You could be checkmated at 9 ply, in reply to capturing the Queen, not? You cannot be sure the at ply of a 9-ply search was your own move; there could have been a check extension.

[Uri Blass]

You could be checkmated at 9 ply, in reply to capturing the Queen, not? You cannot be sure the at ply of a 9-ply search was your own move; there could have been a check extension.

Yes

I cannot be sure but many pruning ideas are based on things that you are almost sure about them when the idea is that you lose strength at fixed depth but earn strength at fixed time.

Uri

[Ralph Stoesser]

I find that stockfish is using the following code
...

I think that this behaviour is illogical.

What is illogical is that you never prune when the depth is not enough and the score is not relevant.

...

Actually Stockfish uses the TT score from a shallower search for null move pruning and for razoring decisions at actual depth.

But there is no depth_diff term. It could be usefull to try to use this term to better the quality of those pruning/razoring decisions.

For example in step 6: razoring of search(), the razor_margin could depend not only on actual depth, but also on depth_diff regarding refinedValue.
There should be a big difference whether the estimated score for the actual node come from the static evaluation or come from a search with depth near to actual depth. But the search code is not yet aware of this difference.

[jwes]

This is all assuming you use failsoft. With failhard you almost never get such large values in the TT.

[mcostalba]

For example in step 6: razoring of search(), the razor_margin could depend not only on actual depth, but also on depth_diff regarding refinedValue.
There should be a big difference whether the estimated score for the actual node come from the static evaluation or come from a search with depth near to actual depth. But the search code is not yet aware of this difference.

Actually the refined value _could_ belong from TT, but is not sure. If TT value is not found or is not usable then refined value equals the static evaluation.

[Ralph Stoesser]

I don't meant to get large difference in value, but in reliability of the value, depending on where refinedValue belong from, search or static evaluation.

Marco,

Sure. But what is your point?

Below I don't bear on the razoring especially. Depth 9 is far beyond the max razor depth.

Assume we are at depth 9. We could compute something like this:

1. refined value belong from static evaluation: depth_diff = 9 - (-1)
2. refined value belong from qsearch: depth_diff = 9 - 0
3. refined value belong from search at depth 1: depth_diff = 9 - 1,
...
10. refined value belong from search at depth 8: depth_diff = 9 - 8

reliability_of_refined_value = depth - depth_diff + 1.

My point is the following:

In case the refined value belong from static evaluation, the value is rather unreliable. In case the refined value belong from search with depth near to actual depth it is much more reliable. So we could use this information for pruning decisions, couldn't we?

[PK]

it seems that You propose some kind of (multi)ProbCut, based on hash table rather than on actual search to shallower depth.

[mcostalba]

In case the refined value belong from static evaluation, the value is rather unreliable. In case the refined value belong from search with depth near to actual depth it is much more reliable. So we could use this information for pruning decisions, couldn't we?

Regarding qsearch called from razoring I would think that if the position is already in TT with proper depth then you have an immediate return, so skipping the qsearch when you have the refined value doesn't should improve things a lot.

In general terms I agree there is more info in a refined value from a TT then from static evaluation, but is not so trivial. We have made some experiment in the past using refined instead of eval, for instance in futility pruning, but results were mixed.

So I would think you are right, but I also think is not easy to exploit this potential with a working patch that is proven to increase ELO.

[Ralph Stoesser]

it seems that You propose some kind of (multi)ProbCut, based on hash table rather than on actual search to shallower depth.

Not exactly. I meant nothing special yet about how to use this information. I just think Uri's idea is tempting to try, *somehow*. It's tempting because we can have it for free, and because it seems intuitively right to exploit the information.

On the other hand I'm aware of the situation in chess programming, that often intuitively good looking ideas are in fact worth nothing (no ELO gain). Especially when there are already several selective schemes, and on top of that, in case they already work very good as it's the case with Stockfish.

in razoring we have (among others) this condition:
refinedValue < beta - razor_margin(depth)

In static null move pruning we have this condition:
refinedValue >= beta + futility_margin(depth, 0))

Both conditions depend on refinedValue, the estimated value for the current position. But this estimate sometimes is rather accurate, and othertimes it's rather unaccurate. The above conditions nonetheless rely on this value with the same condition.
That's what's eye-catching to me.