Stockfish and endgame K-KBN

[Werner]

Here is a game which Stockfish did not win even when showing a mate score. Is this a general problem or a little bug?

Werner

[Event "Thinker54D"]
[Site "SPEEDSTER"]
[Date "2009.03.17"]
[Round "1"]
[White "Thinker 5.4Di x64 4CPU"]
[Black "Stockfish 1.2def x64 4CPU"]
[Result "1/2-1/2"]
[BlackElo "2200"]
[ECO "A38"]
[Opening "Englisch"]
[Time "22:14:14"]
[Variation "Symmetrisch, Hauptvariante, 7.d3 d6 8.a3 a6"]
[WhiteElo "2200"]
[TimeControl "40/600:40/600:40/600"]
[Termination "normal"]
[PlyCount "294"]
[WhiteType "human"]
[BlackType "human"]

1. Nf3 Nf6 2. c4 c5 3. Nc3 Nc6 4. g3 g6 5. Bg2 Bg7 6. O-O O-O 7. d3 a6 8.
a3 Rb8 9. Rb1 b5 {-0.13/18 19} 10. cxb5 axb5 {0.00/18 18} 11. b4 cxb4
{0.00/19 33} 12. axb4 d6 {-0.11/17 24} 13. Bf4 Bg4 {0.00/17 37} 14. Qd2 Qd7
{-0.05/18 27} 15. Rfc1 e5 {+0.01/18 32} 16. Bg5 Rfc8 {0.00/18 14} 17. Bh4
Ne8 {+0.33/18 46} 18. Nd5 f6 {+0.39/18 18} 19. Qe3 Ne7 {+0.33/17 26} 20.
Rxc8 Nxc8 {+0.29/17 17} 21. d4 Be6 {+0.41/17 11} 22. Nc3 Qa7 {+0.54/17 18}
23. Ne4 Bf5 {+0.70/17 28} 24. Rc1 h6 {+0.86/17 13} 25. g4 Bxg4 {+0.98/16 9}
26. Bg3 Be6 {+1.01/17 14} 27. Qd2 Nb6 {+1.21/17 10} 28. dxe5 dxe5 {+1.15/17
9} 29. Nc5 Bf7 {+1.23/18 9} 30. Rd1 Na4 {+1.56/17 13} 31. Ra1 Qe7 {+1.76/18
14} 32. Nxa4 bxa4 {+1.74/17 3} 33. Rxa4 Bf8 {+1.90/18 11} 34. Ne1 Rxb4
{+1.96/19 15} 35. Rxb4 Qxb4 {+2.01/21 12} 36. Qxb4 Bxb4 {+2.01/20 1} 37.
Nd3 Bd6 {+2.05/21 20} 38. Bc6 Kf8 {+2.05/21 14} 39. f3 Ng7 {+2.07/21 16}
40. Be1 Bc4 {+2.00/20 10} 41. Kf2 Ke7 {+1.98/20 31} 42. Nb2 Ba6 {+2.00/20
26} 43. Bd2 g5 {+1.96/21 35} 44. Na4 Ne6 {+2.00/20 18} 45. Nc3 Bc5+
{+2.01/21 25} 46. e3 f5 {+2.01/21 24} 47. Na4 Bd6 {+2.00/20 39} 48. Kg2 Ba3
{+2.01/20 17} 49. Nc3 Bc4 {+1.96/20 19} 50. Nb5 Bc5 {+2.07/21 15} 51. Nc3
Kd6 {+2.13/20 12} 52. Ba4 Bd3 {+2.05/19 15} 53. Bd1 f4 {+2.13/19 11} 54.
exf4 exf4 {+2.15/21 11} 55. Ne4+ Bxe4 {+2.21/22 13} 56. fxe4 Ke5 {+2.21/23
15} 57. Bf3 Kd4 {+2.31/22 11} 58. Bg4 Nd8 {+2.21/23 11} 59. Ba5 Nf7
{+2.19/23 8} 60. Bh5 Nd6 {+2.19/22 9} 61. e5 Nf5 {+2.15/22 11} 62. Bc7 Ke3
{+2.11/21 9} 63. Kf1 Bd4 {+2.12/21 16} 64. e6 Bf6 {+2.19/21 8} 65. Bg6 Ng7
{+2.17/24 12} 66. Bf7 Be7 {+1.90/23 12} 67. Be5 Nf5 {+1.92/24 12} 68. Bb8
Kf3 {+2.25/20 8} 69. Bh5+ g4 {+2.29/22 8} 70. Be8 Bc5 {+2.27/22 13} 71. Ke1
Ng7 {+2.27/21 11} 72. Bd7 h5 {+2.17/22 12} 73. Be5 Nf5 {+2.31/20 13} 74.
Bc6+ Ke3 {+2.74/6} 75. Bb2 f3 {+3.12/20 13} 76. Bc1+ Kd3 {+3.11/19 12} 77.
e7 Nxe7 {+3.21/21 13} 78. Be8 Be3 {+3.14/22 11} 79. Bb2 Ke4 {+3.56/22 13}
80. Bxh5 Kf4 {+4.62/22 9} 81. Bc3 Nf5 {+6.96/24 22} 82. Be8 Bg1 {+5.78/25
29} 83. Bd2+ Ke5 {+6.64/26 28} 84. Bc6 Bxh2 {+7.60/25 22} 85. Ba5 Kd6
{+7.86/25 25} 86. Be4 Bg3+ {+9.72/23 16} 87. Kd2 Bf4+ {+9.72/17 2} 88. Ke1
Be3 {+16.39/23 25} 89. Kd1 Bd4 {+18.17/23 22} 90. Bd8 f2 {+74.70/24 21} 91.
Bd3 Ne3+ {+74.90/24 20} 92. Kd2 g3 {+74.95/24 19} 93. Bh4 Nf5 {+74.95/23
32} 94. Bxg3+ Nxg3 {+74.95/22 1} 95. Ba6 Kc5 {+75.00/24 16} 96. Kd1 f1=Q+
{+M25/10} 97. Bxf1 Nxf1 {+M24/6} 98. Ke2 Nh2 {+M23/6} 99. Kd3 Kd5 {+M22/6}
100. Kc2 Kc4 {+M21/8} 101. Kd2 Bc5 {+M20/6} 102. Ke2 Kc3 {+M21/9} 103. Ke1
Kd3 {+M21/6} 104. Kd1 Bg1 {+M20/6} 105. Ke1 Bd4 {+M13/6} 106. Kd1 Nf1
{+M12/6} 107. Ke1 Ng3 {+M11/6} 108. Kd1 Be3 {+M19/6} 109. Ke1 Bc5 {+M23/10}
110. Kd1 Bb4 {+M14/8} 111. Kc1 Kc4 {+M13/6} 112. Kc2 Nf1 {+M15/6} 113. Kd1
Kd3 {+M10/8} 114. Kc1 Bc3 {+M9/6} 115. Kd1 Ne3+ {+M10/6} 116. Kc1 Kc4
{+M9/6} 117. Kb1 Nf1 {+M8/6} 118. Kc2 Ng3 {+M18/10} 119. Kb1 Kb4 {+M21/12}
120. Kc2 Bd4 {+M21/14} 121. Kd3 Kc5 {+M20/6} 122. Kc2 Kc4 {+M19/6} 123. Kd2
Bb6 {+M18/6} 124. Kd1 Kc3 {+M17/6} 125. Kc1 Bg1 {+M19/8} 126. Kd1 Kc4
{+M18/6} 127. Kd2 Bd4 {+M19/6} 128. Kc2 Nh5 {+M24/7} 129. Kd2 Nf4 {+M36/26
20} 130. Ke1 Kd3 {+M39/6} 131. Kf1 Ke4 {+M38/6} 132. Ke1 Ne6 {+M47/6} 133.
Kd2 Be5 {+M43/10} 134. Ke2 Nf4+ {+M42/6} 135. Kf2 Nd3+ {+M43/8} 136. Kg2
Kf4 {+M42/10} 137. Kf1 Kf3 {+M40/6} 138. Kg1 Bd6 {+M42/6} 139. Kf1 Bf4
{+M41/6} 140. Kg1 Be3+ {+M41/8} 141. Kh2 Nf4 {+M40/10} 142. Kh1 Ke4
{+M39/6} 143. Kh2 Bf2 {+M38/6} 144. Kh1 Bd4 {+M37/6} 145. Kh2 Kf3 {0.00/100
4} 146. Kh1 Nd3 {0.00/100 1} 147. Kh2 Ne1 {0.00/100 5 50-Züge-Regel}
1/2-1/2

[mcostalba]

Thanks Werner for the report.

I will try to understund what's happened...I suspect a bug somewhere.

Thanks
Marco

[zamar]

The cause of the bug might lie anywhere, but this thing came into my mind:
(this is really just a wild guess!!)

// Stop search early when the last two iterations returned a mate score
if ( Iteration >= 6
&& abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100
&& abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100)
stopSearch = true;

Could these lines be the cause of the problem? I've tried to understand these lines, but just don't get it how they could be safe? I mean that of course they work well in ideal case when no move is extended/reduced/pruned. But in special endgames like KBNK, these standard search tree balancing methods can form quite bizarre search trees where longer mate is found much more quicker than shorter.

BTW, what's wrong with the simple "two moves ago we had mate in 25, don't stop until we found mate in 23 or (move time limit + some extra time) expires"? (Okay, it's a bit ugly )

[mcostalba]

Well I didn't notice that!

I was arguing around a diffrent idea: Stockfish shows this bug while Glaurung doesn't (so it seems) so I was looking for notable differences that could have introduced this.

One very very random idea was in the qsearch. Glaurung does not store qsearch results in TT while Stockfish does. Perhaps could be that when the value is a mate one we cannot store as is in qsearch...just a wild guess.

Point is that if bug is not reproducible it becames really a wild guess job...I don't like this kind of approach

[zamar]

Oh... Did I read the source correctly that you are doing TT lookup in qsearch when it's called from search_pv? If so, it must be very wrong... Did I miss something?

[mcostalba]

Oh... Did I read the source correctly that you are doing TT lookup in qsearch when it's called from search_pv? If so, it must be very wrong... Did I miss something?

Good catch !!!

Here is a possible patch:

Code: Select all

From: Marco Costalba <mcostalba@gmail.com>
Date: Sat, 21 Mar 2009 14:51:31 +0100
Subject: [PATCH] Fix: In qsearch do not use TT value when in a PV node

We already do like this in search_pv(), so extend
also in qsearch().

Bug spotted by Joona Kiiski.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
---
 src/search.cpp |   13 ++++++++-----
 1 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/src/search.cpp b/src/search.cpp
index 03c566e..64acc3a 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1417,10 +1417,14 @@ namespace {
     if (pos.is_draw())
         return VALUE_DRAW;
 
-    // Transposition table lookup
-    const TTEntry* tte = TT.retrieve(pos);
-    if (tte && ok_to_use_TT(tte, depth, beta, ply))
-        return value_from_tt(tte->value(), ply);
+    // Transposition table lookup, only when not in PV
+    bool pvNode = (beta - alpha != 1);
+    if (!pvNode)
+    {
+        const TTEntry* tte = TT.retrieve(pos);
+        if (tte && ok_to_use_TT(tte, depth, beta, ply))
+            return value_from_tt(tte->value(), ply);
+    }
 
     // Evaluate the position statically
     EvalInfo ei;
@@ -1443,7 +1447,6 @@ namespace {
     // Initialize a MovePicker object for the current position, and prepare
     // to search the moves.  Because the depth is <= 0 here, only captures,
     // queen promotions and checks (only if depth == 0) will be generated.
-    bool pvNode = (beta - alpha != 1);
     MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth, isCheck ? NULL : &ei);
     Move move;
     int moveCount = 0;
-- 
1.6.1.9.g97c34

[zamar]

Are you sure that this condition is always true:

bool pvNode = (beta - alpha != 1);

"Zero window pv searches" are of course extremely rear, but they can happen. Can't they? (I'm not absolutely sure about this ). If you disagree, then just go ahead.

Why not to simply add "bool pvnode" in the argument list of qsearch-function instead?

[mcostalba]

I have tested this condition in real games and never found a pv node where beta - alpha == 1

I have asked myself the same question some months ago because I found the condition used also in original Glaurung, in qsearch() futility pruning

Code: Select all

// Futility pruning
if(UseQSearchFutilityPruning && !isCheck && !moveIsCheck && 
    !move_promotion(move) && !moveIsPassedPawnPush && 
    beta - alpha == 1 &&
    pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame) {

But it seems Tord made it right


P.S.: Use of TT value in qsearch is a controversial subject, many authors confirm for them is unuseful, but I have made tests in Stockfish and it seems that it helps...probably I will do again another 1000 games 1+0 test on this subject before to release...just to be really sure.

[zamar]

I have tested this condition in real games and never found a pv node where beta - alpha == 1

Okay, so they are very rare However there are only a handful of PV-Nodes/game, so this condition is true 99.999% of time. 0.001% cases won't lead to crash, so it's okay

[mcostalba]

I would even say that they are impossible.

If you see in evaluate values are rounded up according to a grain size

Code: Select all

return Value(int(result) & ~(GrainSize - 1));

Where

Code: Select all

// Evaluation grain size, must be a power of 2.
const int GrainSize = 4;

So the minumum difference between alpha and beta should be at least 4.

But I have not proven this...just a my idea.