Seeing a promotion, but not playing it...

[hgm]

We had aproblem with Jabba refusing to promote a Pawn, in a game in a tourney I played. As I think this is a problem of more general interest, I move this discussion to the programmers section, so we can continue it here:

Jabba still seems to have some problems:

Code: Select all

[Event "Computer Chess Game"]
[Site "SCHAAK_PC"]
[Date "2010.01.20"]
[Round "1.9"]
[White "Jabba 1.0KM / 4"]
[Black "Faile KM 1.4.4 / 5"]
[Result "1/2-1/2"]
[TimeControl "40/1440"]
[Variant "knightmate"]
[Number "18"]
[Annotator "1. +0.00   1... +0.02"]

1. f4 {+0.00/10} d6 {+0.02/11} 2. Mf2 {+0.05/11} e5 {+0.04/11} 3. fxe5
{+0.13/11} dxe5 {+0.00/11} 4. c4 {+0.05/10} Bd6 {+0.16/9} 5. e3 {+0.03/10}
Qf6 {+0.13/11} 6. Mf3 {+0.03/10} e4 {+0.88/11} 7. Mf4 {+0.03/10} Bxf4
{+0.90/11} 8. exf4 {+0.05/12} Qxf4 {+0.87/11} 9. g3 {+0.13/10} Qf2+
{+1.18/10} 10. Kc2 {+0.10/10} Mf8 {+1.10/10} 11. Qe1 {+0.12/9} Qxe1
{+1.30/12} 12. Kxe1 {+0.02/12} Me7 {+1.36/12} 13. Bg2 {+0.02/12} Bf5
{+1.44/12} 14. Mc2 {+0.00/12} Kg8 {+1.56/11} 15. b3 {+0.00/11} Re8
{+1.63/11} 16. Rf1 {+0.01/11} Mf6 {+1.62/11} 17. Rf2 {+0.04/10} a5
{+1.62/10} 18. Mc3 {+0.01/10} a4 {+1.65/10} 19. b4 {+0.01/10} Me5
{+1.61/10} 20. Md4 {+0.03/11} Mxd4 {+1.51/11} 21. Rxf5 {+0.52/12} Re7
{+1.52/11} 22. c5 {+0.69/10} a3 {+1.45/10} 23. Rg5 {+0.67/10} f6 {+1.55/11}
24. Rf5 {+0.64/10} c6 {+1.52/11} 25. Bf1 {+0.61/10} Mc7 {+1.49/10} 26. Rb1
{+0.61/10} b6 {+1.35/11} 27. Rb3 {+0.72/11} bxc5 {+1.58/11} 28. bxc5
{+0.63/11} g6 {+1.53/11} 29. Rf2 {+0.70/10} Mxc5 {+1.47/10} 30. Bxa3
{+0.83/9} Re5 {+1.47/10} 31. Bb2 {+0.77/9} Re6 {+1.35/12} 32. a3 {+0.72/10}
Rd8 {+1.42/11} 33. a4 {+0.76/9} f5 {+1.54/10} 34. a5 {+0.78/9} Ra8
{+1.47/10} 35. Bc3 {+0.87/9} Md5 {+1.48/11} 36. Ra3 {+0.78/9} Mcd6
{+1.49/10} 37. Bb2 {+0.85/9} M6c5 {+1.80/11} 38. a6 {+0.37/10} Mb6
{+1.74/11} 39. g4 {+0.53/9} fxg4 {+1.91/11} 40. Rf7 {+0.35/11 0.1} Re7
{+1.98/11 0.1} 41. Rxe7 {+0.13/11} Kxe7 {+2.14/11} 42. Be2 {+0.08/10} h5
{+2.03/11} 43. Bf6+ {+0.12/8} Kf5 {+2.03/10} 44. Ra4 {+0.17/9} g3
{+2.24/11} 45. h4 {+0.17/10} Mb5 {+2.19/10} 46. Ra3 {+0.23/11} Me6
{+1.93/10} 47. Bg5 {+0.25/11} Me5 {+1.87/11} 48. Bf1 {+0.02/10} Kg7
{+1.79/11} 49. a7 {+0.00/11} Mb4 {+1.92/11} 50. Ra6 {+0.00/11} Mc5
{+1.88/11} 51. Be3 {+0.00/11} Mcd6 {+1.26/11} 52. Bh3 {+0.04/11} Ke8
{+1.01/12} 53. Kg2 {+0.05/11} Mc7 {+1.09/11} 54. Ra5 {+0.90/11} Md5
{+0.95/11} 55. Kf4 {+1.16/12} Mcd6 {+0.68/10} 56. Ke2 {+1.21/10} Kf6
{+0.49/11} 57. Kxg3 {+1.57/10} Ke8 {+0.34/10} 58. Ke2 {+1.55/10} c5
{+0.34/10} 59. Bf4 {+1.58/10} M6c6 {+0.30/11} 60. Ra6 {+1.76/11} c4
{+0.52/12} 61. Bb8 {+2.61/12} c3 {+0.88/11} 62. dxc3 {+3.44/13} Kf6
{-1.78/11} 63. Ra1 {+3.81/11} Mdd6 {-2.97/11} 64. Rg1 {+4.38/11} Kd5
{-3.67/11} 65. Rxg6 {+4.50/13} Mdc7 {-4.19/11} 66. Bg2 {+4.51/12} Mxb8
{-4.14/11} 67. axb8=Q {+4.59/14} Rxb8 {-4.21/11} 68. Bxe4+ {+4.66/13} Ke3
{-4.21/9} 69. Bxc6 {+4.66/13} Rb2+ {-4.22/10} 70. Kf4 {+4.66/11} Kd1
{-4.22/10} 71. Kxh5 {+4.78/12} Rh2 {-4.23/10} 72. Rg4 {+4.78/11} Kxc3
{-4.19/10} 73. Bg2 {+4.78/10} Kd1 {-4.22/11} 74. Kf4 {+4.80/13} Ke3
{-4.23/10} 75. Rg3+ {+4.80/11} Kf5 {-4.28/10} 76. Rf3 {+5.00/12} Kd6
{-4.38/10} 77. Rh3 {+4.92/11} Rxh3 {-12.28/17} 78. Bxh3 {+5.59/28} Kf7
{-12.35/18} 79. Bg2 {+12.04/27} Kd6 {-12.43/17} 80. Kd5 {+12.04/16 0.1} Kf5
{-9999.71/18 0.1} 81. h5 {+12.04/15} Kh6 {-9999.77/17} 82. Bf3 {+12.04/22}
Kf7 {-9999.75/17} 83. Bh1 {+12.04/15} Kh6 {-9999.79/18} 84. Bg2 {+12.04/18}
Kg4 {-9999.77/16} 85. Be4 {+12.04/14} Kh6 {-9999.79/18} 86. Bh1 {+12.04/14}
Kf5 {-9999.77/18} 87. Bf3 {+12.04/12} Kh6 {-9999.79/18} 88. Be4 {+12.04/19}
Kf7 {-9999.79/18} 89. Bc2 {+12.04/14} Kh6 {-9999.79/17} 90. Bd3 {+12.04/26}
Kf7 {-9999.79/18} 91. Bc4 {+12.04/15} Kh6 {-9999.79/17} 92. Bb3 {+12.04/19}
Kf5 {-9999.77/17} 93. Ba2 {+12.04/21} Kh6 {-9999.79/17} 94. Bc4 {+12.04/19}
Kf7 {-9999.77/17} 95. Bb3 {+12.04/15} Ke5 {-9999.79/16} 96. h6 {+15.19/13}
Kg6 {-9999.81/14} 97. h7 {+15.19/12} Kh8 {-9999.83/14} 98. Bc4 {+15.19/17}
Kf7 {-9999.85/12} 99. Bd3 {+15.19/13} Kh8 {-9999.87/12} 100. Be4
{+15.19/15} Kf7 {-9999.85/14} 101. Bf3 {+15.30/14} Kh8 {-9999.85/14} 102.
Bg2 {+15.25/15} Kg6 {-9999.85/14} 103. Bh1 {+15.25/14} Kh8 {-9999.87/14}
104. Bf3 {+15.25/16} Kf7 {-9999.85/13} 105. Bg2 {+15.25/14} Kh8
{-9999.87/13} 106. Bh1 {+15.25/17} Kg6 {-9999.85/14} 107. Be4+ {+15.25/15}
Kh8 {-9999.85/13} 108. Bc2 {+15.25/21} Kf7 {-9999.85/14} 109. Bg6+
{+15.25/13} Kh8 {-9999.83/14} 110. Bf5 {+15.25/15} Kf7 {-9999.85/13} 111.
Bc2 {+15.25/14} Kh8 {-9999.87/14} 112. Bd3 {+15.25/21} Kf7 {-9999.85/14}
113. Bb1 {+15.25/14} Kh8 {-9999.87/13} 114. Ba2 {+15.25/18} Kg6
{-9999.85/13} 115. Ke3 {+15.25/14} Kh8 {-9999.83/14} 116. Bd5 {+15.25/18}
Kg6 {-9999.85/14} 117. Be4+ {+15.25/15} Kh8 {-9999.83/13} 118. Bc6
{+15.25/20} Kf7 {-9999.85/13} 119. Kd5 {+15.25/15} Kh8 {-9999.87/13} 120.
Bb7 {+15.25/21 0.1} Kg6 {-9999.85/14 0.1} 121. Ba8 {+15.30/14} Kh8
{-9999.87/14} 122. Bc6 {+127.93/15} Kf7 {-9999.85/14} 123. Bb7 {+127.93/14}
Kh8 {-9999.87/14} 124. Ba8 {+15.25/15} Kf7 {-9999.85/14} 125. Ke3
{+15.25/14} Kh8 {-9999.83/15} 126. Be4 {+15.25/21} Kf7 {-9999.83/14} 127.
Bf3 {+15.25/14} Kh8 {-9999.83/14} 128. Bb7 {+15.25/17} Kg6 {-9999.85/14}
129. Bg2 {+15.25/18} Kh8 {-9999.83/15} 130. Ba8 {+15.25/18} Kf7
{-9999.85/14} 131. Bh1 {+15.25/17} Kh8 {-9999.83/15} 132. Bf3 {+15.25/16}
Kg6 {-9999.85/14} 133. Kf5 {+15.25/21} Kh8 {-9999.87/12} 134. Kd4
{+15.25/22} Kf7 {-9999.85/13} 135. Ba8 {+15.25/13} Kh8 {-9999.83/14} 136.
Bb7 {+15.25/15} Kg6 {-9999.85/13} 137. Bd5 {+15.25/13} Kh8 {-9999.83/14}
138. Bc6 {+15.25/18} Kf7 {-9999.85/13} 139. Be4 {+15.25/12} Kh8
{-9999.83/15} 140. Bd5 {+15.25/20} Kg6 {-9999.85/14} 141. Bf3 {+15.25/18}
Kh8 {-9999.83/15} 142. Be4 {+15.25/16} Kf7 {-9999.83/15} 143. Bg2
{+15.25/22} Kh8 {-9999.83/15} 144. Ba8 {+15.25/23} Kg6 {-9999.85/15} 145.
Bh1 {+15.25/14} Kh8 {-9999.83/15} 146. Bg2 {+15.25/16} Kf7 {-9999.81/14}
147. Bb7 {+15.25/14}
{Xboard adjudication: 50-move rule} 1/2-1/2

Faile sees it is going to be checkmated already for a long time, but Jabba's scor never exceeds +15, so that it apparently does see it can force promotion. But it fails to execute the plan, and keeps aimlessly moving its Bishop until the 50-move axe chops it.

From the position where the Pawn reaches the 7th rank (until there, no problems) the game is easiy won

[d] 7n/7P/8/3N4/8/1B6/8/8 w - - 1 98

98.Bc2 Kf7 {only move} 99.Bd3 Kh8 {or promotes} 100.Kf4 Kf7 {only move} 101.Kg6 Kg5 {say} 102.h8=Q Kf7 103.Qh5 Kd6 (103... Kd8 104.Qd5#) 104.Kh4 Kb7 105.Qd5# (104... Kc8 105.Qc5#) {checkmate} 1-0

[d] 8/1n6/8/3Q4/7N/3B4/8/8 b - - 6 8

Jabba did not see the mate, but what is worse, it did not acheive the promotion that it did see!

Hmm.

I've played through the game with Jabba here... it sees the promotion, but keeps pushing the promotion down the pv... as the game progresses, the promotion is always six moves or so into the pv, with hash tables on and off.

Any ideas what this might be?

The evaluation of the position is the same here regardless of the bishop position - could this be a factor?

Richard

Pure minimax does not care if you promote on the first move, or on the 6th. As long as you have the Queen in the end-leaf, you get the score for it. I guess here there is some funny kind of horizon effect in operation: If you promote early, the opponent's Royal Knight has more time to flee towards the center, which presumably increases black's score. If you promote late, he will be close to the corner in the end-leaf, as he must stay in the corner to defend against promotion.

So of all lines of equal depth that do not have the checkmate within the horizon, the ones where you postponed driving the opponent's Royal Knight out of the corner, and promote, until the last possible moment probably gets a better score. The (transient) price of promotion is that you let the Royal Knight escape to the center, and it tries to push that price over the horizon.

In my engines behavior like hat is discouraged through the delayed-loss bonus. I am not sure how others solve it.

Yes, I see what you mean. I think this is the case, because after reading your post, I spent most of last night digging up hash table threads on this forum, and playing through test positions to check that all was ok with the hash!!



Can I ask how you apply this score? A bonus for seeing it earlier (depth based?)


Regards

Richard

PS It would be nice if you ran another tournament

[hgm]

What I do is this:

Code: Select all

Search(alpha, beta)
{
  if&#40;apha < eval&#41; alpha--;
  if&#40;beta <= eval&#41; beta--;

  // usual Search implementation

  if&#40;bestScore < eval&#41; bestScore++; // add bonus of 1 cP
  return bestScore;
&#125;

This is for a bonus of only 1 point (centi-Pawn), which is perfect for picking the fastest mate, but might not be enough in this case, where ' positional noise' causes scores to be much less uniform than mate scores. And it would only suppress the effect we see here when the bonus for not delaying the promotion, so that the losing side has more moves where bestSore (including the unavoidable promotion) < eval (not including a Queen yet), and thus gets the bonus added more often.

With a larger bonus, however, you have to be a little bit more careful of how to treat scores close to the threshold, to avoid that adding the bonus would cause the corrected score to become a non-monotonous function of the uncorrected score. The correction on the window limits would always have to be the inverse of that on the final score, and you woud have to make absolutely sure that rounding is done such that the correction cannot make the window too small. E.g.

Code: Select all

Search(alpha, beta)
{
  if&#40;apha < eval&#41; floor&#40;eval + &#40;alpha - eval&#41;/0.97&#41;;
  if&#40;beta < eval&#41; ceiling&#40;eval + &#40;beta - eval&#41;/0.97&#41;;

  // usual Search implementation

  if&#40;bestScore < eval&#41; bestScore = eval + &#40;bestScore - eval&#41;*0.97; // add bonus of 3%
  return bestScore;
&#125;

[metax]

I don't like this delayed-loss bonus very much. I think it is very inelegant especially combined with a transposition table (there are way to solve that, but my opinion is that, apart from mate scores, the evaluation of a position should always be independent of search variables like depth).

[hgm]

I think on the contrary that this is a very elementary part of evaluation. Yet-to-be-realized gains tend to evaporate more easily in Chess than realized gains. So postponing a gain will reduce the average score you can expect on deeper search, and to make a good choice between moves you will have to factor in that expectation. It repairs one of the major basic flaws in minimax.

I don't see what it has to do with transposition tables.

[metax]

I think on the contrary that this is a very elementary part of evaluation. Yet-to-be-realized gains tend to evaporate more easily in Chess than realized gains. So postponing a gain will reduce the average score you can expect on deeper search, and to make a good choice between moves you will have to factor in that expectation. It repairs one of the major basic flaws in minimax.

I don't see what it has to do with transposition tables.

If the score for a position is not always the same depending on the depth, there can of course occur problems with the transposition tables because they store a fixed score of a position. If that score is changed based on the depth, transposition tables cannot be used easily for pruning.

[hgm]

Scores always change with the depth. Searching one ply deeper almost always gives a tiny correction on the score. And sometimes a large one, and even changing the move can not always prevent that. Yet hardly any engine only accepts 'exact-depth' hits for hash cutoffs. The usual method (because it is the best, Elo wise) is to accept any result from a search with a depth >= what you want to do now. And if that has another score (which it usually has), than you simply assume that the earlier score was in error, because it did not search deep enough.

I still don't see what that has to do with the delayed-loss bonus. The latter does not make the score dependent on the depth, but on the moves you play (in particular, in which order you play them). It is very usual that playing a different line produces a different score, and it never stopped anyone from hashing...

[jwes]

I think the problem is with the evaluations after the promotion. If the evaluations kept increasing the closer the position is to mate, the problem would not occur.

[hgm]

Indeed. But it doesn't. As is quite usual after cashing a material gain; nothing comes entirely for free, and there will be some back-lash.

So the moral lesson is that a very shallow search of the position where you promote, gives you a large error margin on the (search) evaluation of that position, and that you should expect the score on a more accurate, somewhat deeper search to be lower.

So postponing the promotion to reap the higher, but less accurate score from a shallower search of it is a bad idea, and should somehow be penalized. Which is exactly what the delayed-loss bonus does.

[michiguel]

I think on the contrary that this is a very elementary part of evaluation. Yet-to-be-realized gains tend to evaporate more easily in Chess than realized gains. So postponing a gain will reduce the average score you can expect on deeper search, and to make a good choice between moves you will have to factor in that expectation. It repairs one of the major basic flaws in minimax.

I don't see what it has to do with transposition tables.

If the score for a position is not always the same depending on the depth, there can of course occur problems with the transposition tables because they store a fixed score of a position. If that score is changed based on the depth, transposition tables cannot be used easily for pruning.

I think it is the opposite! It is better to be in a position in which you know you win a knight in three moves than a position that you know you win a knight in four moves. With mates it is easier to see. I do something almost identical in Gaviota, but only for mates.

At the top of search I alpha = adjust_in(alpha) and beta= adjust_in(beta). Before return, I do score = adjust_out(score). The beauty of it is that you do not have to touch the mate scores in the transposition table at all. They are all taken care by itself.

Miguel

Code: Select all

static eval_t
adjust_in (eval_t x)
{
	ASSERT (-INFINITY_VALUE <= x && x <= INFINITY_VALUE&#41;;

	if &#40;MATE100_VALUE < x && x < MATE_VALUE&#41; 
		return x + 1;
	if (-MATE_VALUE < x && x < -MATE100_VALUE&#41; 
		return x - 1;
	return x;
&#125;

static eval_t
adjust_out &#40;eval_t x&#41;
&#123;
	ASSERT (-INFINITY_VALUE <= x && x <= INFINITY_VALUE&#41;;

	if &#40;MATE100_VALUE < x && x <= MATE_VALUE&#41; 
		return x - 1;
	if (-MATE_VALUE  <= x && x < -MATE100_VALUE&#41; 
		return x + 1;
	return x;
&#125;

[jwes]

Indeed. But it doesn't. As is quite usual after cashing a material gain; nothing comes entirely for free, and there will be some back-lash.

So the moral lesson is that a very shallow search of the position where you promote, gives you a large error margin on the (search) evaluation of that position, and that you should expect the score on a more accurate, somewhat deeper search to be lower.

So postponing the promotion to reap the higher, but less accurate score from a shallower search of it is a bad idea, and should somehow be penalized. Which is exactly what the delayed-loss bonus does.

I have seen this effect, but it means that the evaluation is flawed, particularly in the position above which is totally won. Those regrouping moves that appear to cause the evaluation to drop, are actually improving the position, at least is the sense of bringing checkmate closer (which is really what is important), and so should have higher scores. Putting in a delayed loss bonus is hiding the problem rather than fixing it.