Draw by repetition when mate is possible

mathmoi · Post by **mathmoi** » Tue Dec 30, 2008 4:33 am

Hi,

I've run into a problem that I suppose is common and I'd like to know how others are solving it. In some end-game position, when my engine finds a mate, say a mate in 10, the next time it search he will quickly find a mate in 13 that is simply equivalent to going back to the position in wich it found a mate in 10 in the previous search. Of course there is a faster mate in this position, since two ply ago there was a mate in 10 there is now at least a mate in 8. The problem is a search at a really low depth like d=3 might find the mate in 13 in the transposition table and the search will not go further. My engine is then simply reversing it's moves and the opponents is usually glad to accept a draw by repetition.

The first thing I tried to prevent this was to move the draw check before the transposition table probe. My engine stopped accepting the draws, but I'm not sure this really solve the problem. Moreover this slow down my engine significantly.

An other solution I haven't tries yet would be to keep searching deeper even if the search returns a mate score. However it seems most programs don't do this since they usually stop searching rapidly when a mate is found.

How do you solve this issue in your programs?

michiguel · Post by **michiguel** » Tue Dec 30, 2008 5:52 am

mathmoi wrote:Hi,

I've run into a problem that I suppose is common and I'd like to know how others are solving it. In some end-game position, when my engine finds a mate, say a mate in 10, the next time it search he will quickly find a mate in 13 that is simply equivalent to going back to the position in wich it found a mate in 10 in the previous search. Of course there is a faster mate in this position, since two ply ago there was a mate in 10 there is now at least a mate in 8. The problem is a search at a really low depth like d=3 might find the mate in 13 in the transposition table and the search will not go further. My engine is then simply reversing it's moves and the opponents is usually glad to accept a draw by repetition.

The first thing I tried to prevent this was to move the draw check before the transposition table probe. My engine stopped accepting the draws, but I'm not sure this really solve the problem. Moreover this slow down my engine significantly.

An other solution I haven't tries yet would be to keep searching deeper even if the search returns a mate score. However it seems most programs don't do this since they usually stop searching rapidly when a mate is found.

How do you solve this issue in your programs?

When you find "mate in 10 plies" after searching 3 plies, you actually found an equivalent of "mate in 13 plies" at the root. When I find mate in 10, I return mate in 11 etc. At the root, it will be mate in 13. However, when you enter search(), you have to adjust alpha and beta if they are in the "mate" range. If mate in 10 is alpha at the root, beta should be mate in 9 at ply one, alpha mate in 8 at ply 2, beta mate in 7 at ply 3. That is to make sure that a mate in 10 at ply 3 won't cut if off. I think HG Muller does something like this too.

Almost everybody else make a correction with the plies and how to store it in the hashtable. It would be better if you search it or something else explain it because it has been always awkward to understand for me.

A third option, proposed by Bruce Moreland is a quick fix that apparently worked for him well in practice: Do not store mate in 10 in the hashtable. Store "Mate in less than 200" (i.e. do not store an exact score). This will be ok to cut most of the lines, and it you are faced with a mate you already saw, you research it and find it again. I would start with this because it is the easiest and less prone to forget something and generate a bug. You can try later any of the other two more accurate procedures later.

Miguel

What I do can be summarized by this:

Code: Select all


static eval_t
adjust_in &#40;eval_t x&#41;
&#123;
	if &#40;MATE100_VALUE < x ) 
		return x + 1;
	if &#40;x < -MATE100_VALUE&#41; 
		return x - 1;
	return x;
&#125;

static eval_t
adjust_out &#40;eval_t x&#41;
&#123;
	if &#40;MATE100_VALUE < x&#41; 
		return x - 1;
	if &#40;x < -MATE100_VALUE&#41; 
		return x + 1;
	return x;
&#125;


search ()
&#123;
    alpha = adjust_in &#40;alpha&#41;;
    beta  = adjust_in &#40;beta&#41;;

    /* Check hashtables here */

    /* Do your search stuff here... */

    /* Whenever you return&#58; */

    return adjust_out&#40;best&#41;;		/* adjust to drive the checkmates */
&#125;

hgm · Post by **hgm** » Tue Dec 30, 2008 9:55 am

You should not stop deepening as long as you have not reached a depth enough to see the mate. I.e. if a mate-in-13 is found, you should only stop deepening after 25 ply is reached. Otherwise you run the risk of missing a faster mate, which can have the disastrous consequences you see.

In micro-Max I deepcould not bother to check that, and I deepen to 98 ply (its default value for the WinBoard sd command). This is still extremely fast if the mate is close, say mate-in-2, as no branch will extend deeper than 3 ply. So in fact the limit of 98 is really important, or it would quickly deepen to a million plies or so, with a crash due to stack overflow as a result. So you will still see uMax speed up when it approaches the mate.

mathmoi · Post by **mathmoi** » Tue Dec 30, 2008 2:22 pm

hgm wrote:You should not stop deepening as long as you have not reached a depth enough to see the mate. I.e. if a mate-in-13 is found, you should only stop deepening after 25 ply is reached. Otherwise you run the risk of missing a faster mate, which can have the disastrous consequences you see.

In micro-Max I deepcould not bother to check that, and I deepen to 98 ply (its default value for the WinBoard sd command). This is still extremely fast if the mate is close, say mate-in-2, as no branch will extend deeper than 3 ply. So in fact the limit of 98 is really important, or it would quickly deepen to a million plies or so, with a crash due to stack overflow as a result. So you will still see uMax speed up when it approaches the mate.

Hi H.G.

It seemed the right thing to do, but I was under the impression that everyone stopped searching as soon as they got a mate score back. I'll just keep searching and I'm sure this problem will go away. Thanks.

pedrox · Post by **pedrox** » Tue Dec 30, 2008 9:13 pm

michiguel wrote:
mathmoi wrote:Hi,

I've run into a problem that I suppose is common and I'd like to know how others are solving it. In some end-game position, when my engine finds a mate, say a mate in 10, the next time it search he will quickly find a mate in 13 that is simply equivalent to going back to the position in wich it found a mate in 10 in the previous search. Of course there is a faster mate in this position, since two ply ago there was a mate in 10 there is now at least a mate in 8. The problem is a search at a really low depth like d=3 might find the mate in 13 in the transposition table and the search will not go further. My engine is then simply reversing it's moves and the opponents is usually glad to accept a draw by repetition.

The first thing I tried to prevent this was to move the draw check before the transposition table probe. My engine stopped accepting the draws, but I'm not sure this really solve the problem. Moreover this slow down my engine significantly.

An other solution I haven't tries yet would be to keep searching deeper even if the search returns a mate score. However it seems most programs don't do this since they usually stop searching rapidly when a mate is found.

How do you solve this issue in your programs?
When you find "mate in 10 plies" after searching 3 plies, you actually found an equivalent of "mate in 13 plies" at the root. When I find mate in 10, I return mate in 11 etc. At the root, it will be mate in 13. However, when you enter search(), you have to adjust alpha and beta if they are in the "mate" range. If mate in 10 is alpha at the root, beta should be mate in 9 at ply one, alpha mate in 8 at ply 2, beta mate in 7 at ply 3. That is to make sure that a mate in 10 at ply 3 won't cut if off. I think HG Muller does something like this too.

Almost everybody else make a correction with the plies and how to store it in the hashtable. It would be better if you search it or something else explain it because it has been always awkward to understand for me.

A third option, proposed by Bruce Moreland is a quick fix that apparently worked for him well in practice: Do not store mate in 10 in the hashtable. Store "Mate in less than 200" (i.e. do not store an exact score). This will be ok to cut most of the lines, and it you are faced with a mate you already saw, you research it and find it again. I would start with this because it is the easiest and less prone to forget something and generate a bug. You can try later any of the other two more accurate procedures later.

Miguel

What I do can be summarized by this:
Code: Select all
static eval_t
adjust_in &#40;eval_t x&#41;
&#123;
	if &#40;MATE100_VALUE < x ) 
		return x + 1;
	if &#40;x < -MATE100_VALUE&#41; 
		return x - 1;
	return x;
&#125;

static eval_t
adjust_out &#40;eval_t x&#41;
&#123;
	if &#40;MATE100_VALUE < x&#41; 
		return x - 1;
	if &#40;x < -MATE100_VALUE&#41; 
		return x + 1;
	return x;
&#125;


search ()
&#123;
    alpha = adjust_in &#40;alpha&#41;;
    beta  = adjust_in &#40;beta&#41;;

    /* Check hashtables here */

    /* Do your search stuff here... */

    /* Whenever you return&#58; */

    return adjust_out&#40;best&#41;;		/* adjust to drive the checkmates */
&#125; 

This is known as mate distance pruning?

Is this correct?

Code: Select all

    // Mate distance pruning
	if (!pv_node&#41; &#123;
		if&#40;-MATE+ply >= beta&#41;
			return beta;
		if&#40;MATE-ply-1 < beta&#41;
			return beta-1;
	&#125;
	else &#123;
		alpha = MAX&#40;-MATE+ply, alpha&#41;;
		beta = MIN&#40;MATE-ply-1, beta&#41;;
		if&#40;alpha >= beta&#41;
			return alpha;
	&#125;

Pedro

bob · Post by **bob** » Tue Dec 30, 2008 11:54 pm

mathmoi wrote:Hi,

I've run into a problem that I suppose is common and I'd like to know how others are solving it. In some end-game position, when my engine finds a mate, say a mate in 10, the next time it search he will quickly find a mate in 13 that is simply equivalent to going back to the position in wich it found a mate in 10 in the previous search. Of course there is a faster mate in this position, since two ply ago there was a mate in 10 there is now at least a mate in 8. The problem is a search at a really low depth like d=3 might find the mate in 13 in the transposition table and the search will not go further. My engine is then simply reversing it's moves and the opponents is usually glad to accept a draw by repetition.

The first thing I tried to prevent this was to move the draw check before the transposition table probe. My engine stopped accepting the draws, but I'm not sure this really solve the problem. Moreover this slow down my engine significantly.

An other solution I haven't tries yet would be to keep searching deeper even if the search returns a mate score. However it seems most programs don't do this since they usually stop searching rapidly when a mate is found.

How do you solve this issue in your programs?

Never stop the search until you find mate in N-1, unless you run out of time. This solves this problem...

michiguel · Post by **michiguel** » Wed Dec 31, 2008 12:08 am

pedrox wrote:
michiguel wrote:
mathmoi wrote:Hi,

I've run into a problem that I suppose is common and I'd like to know how others are solving it. In some end-game position, when my engine finds a mate, say a mate in 10, the next time it search he will quickly find a mate in 13 that is simply equivalent to going back to the position in wich it found a mate in 10 in the previous search. Of course there is a faster mate in this position, since two ply ago there was a mate in 10 there is now at least a mate in 8. The problem is a search at a really low depth like d=3 might find the mate in 13 in the transposition table and the search will not go further. My engine is then simply reversing it's moves and the opponents is usually glad to accept a draw by repetition.

The first thing I tried to prevent this was to move the draw check before the transposition table probe. My engine stopped accepting the draws, but I'm not sure this really solve the problem. Moreover this slow down my engine significantly.

An other solution I haven't tries yet would be to keep searching deeper even if the search returns a mate score. However it seems most programs don't do this since they usually stop searching rapidly when a mate is found.

How do you solve this issue in your programs?
When you find "mate in 10 plies" after searching 3 plies, you actually found an equivalent of "mate in 13 plies" at the root. When I find mate in 10, I return mate in 11 etc. At the root, it will be mate in 13. However, when you enter search(), you have to adjust alpha and beta if they are in the "mate" range. If mate in 10 is alpha at the root, beta should be mate in 9 at ply one, alpha mate in 8 at ply 2, beta mate in 7 at ply 3. That is to make sure that a mate in 10 at ply 3 won't cut if off. I think HG Muller does something like this too.

Almost everybody else make a correction with the plies and how to store it in the hashtable. It would be better if you search it or something else explain it because it has been always awkward to understand for me.

A third option, proposed by Bruce Moreland is a quick fix that apparently worked for him well in practice: Do not store mate in 10 in the hashtable. Store "Mate in less than 200" (i.e. do not store an exact score). This will be ok to cut most of the lines, and it you are faced with a mate you already saw, you research it and find it again. I would start with this because it is the easiest and less prone to forget something and generate a bug. You can try later any of the other two more accurate procedures later.

Miguel

What I do can be summarized by this:
Code: Select all
static eval_t
adjust_in &#40;eval_t x&#41;
&#123;
	if &#40;MATE100_VALUE < x ) 
		return x + 1;
	if &#40;x < -MATE100_VALUE&#41; 
		return x - 1;
	return x;
&#125;

static eval_t
adjust_out &#40;eval_t x&#41;
&#123;
	if &#40;MATE100_VALUE < x&#41; 
		return x - 1;
	if &#40;x < -MATE100_VALUE&#41; 
		return x + 1;
	return x;
&#125;


search ()
&#123;
    alpha = adjust_in &#40;alpha&#41;;
    beta  = adjust_in &#40;beta&#41;;

    /* Check hashtables here */

    /* Do your search stuff here... */

    /* Whenever you return&#58; */

    return adjust_out&#40;best&#41;;		/* adjust to drive the checkmates */
&#125; 
This is known as mate distance pruning?

Is this correct?
Code: Select all
    // Mate distance pruning
	if (!pv_node&#41; &#123;
		if&#40;-MATE+ply >= beta&#41;
			return beta;
		if&#40;MATE-ply-1 < beta&#41;
			return beta-1;
	&#125;
	else &#123;
		alpha = MAX&#40;-MATE+ply, alpha&#41;;
		beta = MIN&#40;MATE-ply-1, beta&#41;;
		if&#40;alpha >= beta&#41;
			return alpha;
	&#125;
Pedro

Hola Pedro,

I think it is a different thing. I did not know what mate distance pruning is until know.... From the name, and the code you show, it looks like I am doing exactly that in a different place of the code (I have many wheels reinvented in my program

.

This go at the top of search() and it its what you call mate distance pruning (I annotated it as "unreachable mates". I think it is the same.

Code: Select all

	/*---------------------------*
	  Unreachable Check Mates
	 *---------------------------*/

	if &#40;alpha >= &#40;MATE_VALUE-1&#41;) &#123;
		return adjust_out &#40;alpha&#41;;
	&#125;

	/* cut off, I cannot be mated on time faster than beta */	
	if &#40;beta <= (-MATE_VALUE + 2&#41; && !position_isincheck&#40;po&#41;) &#123;
		return adjust_out &#40;beta&#41;;	
	&#125;

Note that the code looks different because what you show adjusts the mate score with ply. The second method I mentioned in my first post and the almost universal one to adjust mate scores. Bob Hyatt explained it many times long time ago and must have influenced several programmers. By the time I read this explanation, I already came with my own.

Saludos,
Miguel

Zach Wegner · Post by **Zach Wegner** » Wed Dec 31, 2008 12:17 am

mathmoi wrote:The first thing I tried to prevent this was to move the draw check before the transposition table probe. My engine stopped accepting the draws, but I'm not sure this really solve the problem. Moreover this slow down my engine significantly.

You should _always_ do the repetition check before the hash probe. The hash table doesn't take the move path into account, so you will walk into very many repetitions this way, not just from mates.

hgm · Post by **hgm** » Wed Dec 31, 2008 11:51 am

To see how some top engines "solve" this problem, look at the game below, from the Duch Open Championship 2008 (Leiden):

Code: Select all

&#91;Event "Computer Chess Game"&#93;
&#91;Site "SCHAAK_PC"&#93;
&#91;Date "2008.11.15"&#93;
&#91;Round "-"&#93;
&#91;White "Ktulu"&#93;
&#91;Black "joker_P2.exe"&#93;
&#91;Result "1-0"&#93;
&#91;TimeControl "3840"&#93;
&#91;Annotator "6... -0.01"&#93;

1. d4 Nf6 2. c4 e6 3. Nf3 Be7 4. e3 O-O 5. Nc3 d5 6. Bd3 dxc4 7. Bxc4 c5 8.
O-O cxd4 9. exd4 Nc6 10. Be3 Qa5 11. Rc1 Rd8 12. h3 Bd7 13. Re1 Be8 14. a3
Rac8 15. Bd3 Qh5 16. Qb3 Na5 17. Qa2 Bc6 18. Ne5 Nd5 19. Be2 Nxc3 20. Rxc3
Qh4 21. Nxc6 Nxc6 22. Bg4 Rb8 23. Qc4 h5 24. g3 Qf6 25. Bxh5 Nxd4 26. Rd1
Nc6 27. Qe4 Rd6 28. Be2 Rbd8 29. Rxd6 Rxd6 30. Bb5 a5 31. Bxc6 bxc6 32. Kg2
Bf8 33. Qf3 Qd8 34. Rxc6 Rxc6 35. Qxc6 Qb8 36. Bb6 a4 37. Bd4 Qb3 38. Bc3
Qd5+ 39. Qxd5 exd5 40. Bb4 Bxb4 41. axb4 Kf8 42. g4 Ke7 43. h4 Kd6 44. Kf1
f6 45. f4 d4 46. Ke2 Kd5 47. Kd3 Kc6 48. Kxd4 Kb5 49. g5 fxg5 50. hxg5 Kc6
51. f5 Kd6 52. b5 g6 53. f6 Ke6 54. b6 a3 55. bxa3 Kf5 56. b7 Kxg5 57. f7
Kh5 58. f8=Q Kg4 59. b8=Q g5 60. Qbd8 Kh4 61. Qh6+ Kg3 62. Qdxg5+ Kf2 63.
Qhf6+ Ke2 64. Qe3+ Kd1 65. Qf1+ Kc2 66. Qed3+ Kb2 67. Qg2+ Ka1 68. Qc3+ Kb1
69. Qb7+ Ka2 70. Qc2+ Kxa3 71. Qcb2+ Ka4 72. Q2b3+ Ka5 73. Qc7+ Ka6 74.
Qe6+ Kb5 75. Qec6+ Kb4 76. Qb8+ Ka3 77. Qc3+ Ka2 78. Qcb3+ Ka1 79. Qd1+ Ka2
80. Qe1 Ka3 81. Qeb4+ Ka2 82. Qb1+ Ka3 83. Qg3+ Ka4 84. Qgb3+ Ka5 85. Qg8
Ka6 86. Qb2 Ka7 87. Qd5 Ka6 88. Qdb7+ Ka5 89. Qb1 Ka4 90. Q1b5+ Ka3 91. Qb1
Ka4 92. Q7b5+ Ka3 93. Qe4 Ka2 94. Qg2+ Ka1 95. Qg1+ Ka2 96. Qb8 Ka3 97. Qb5
Ka2 98. Kc5 Ka3 99. Qc1+ Ka2 100. Qe2+ Kb3 101. Qcc2+ Ka3 102. Qcd3+ Ka4
103. Qb5+ Ka3 104. Qd1 Ka2 105. Qdf1 Ka3 106. Qf3+ Ka2 107. Qg2+ Ka3 108.
Qd3+ Ka4 109. Qge4+ Ka5 110. Qd8+ Ka6 111. Qa4+ Kb7 112. Qc6+ Ka7 113.
Qcc7+ Ka6 114. Qe5 Kb7 115. Qed5+ Ka7 116. Qc7+ Ka6 117. Qcc6+ Ka7 118.
Qcd7+ Kb8 119. Qb3+ Ka8 120. Qa7+ Kxa7 121. Kd5 Ka8 122. Qb2 Ka7 123. Kc5
Ka8 124. Qb5 Ka7 125. Kd4 Ka8 126. Qa6+ Kb8 127. Qc6 Ka7 128. Kc4 Kb8 129.
Kc5 Ka7 130. Kd5 Kb8 131. Qd7 Ka8 132. Kd4 Kb8 133. Kc4 Ka8 134. Qb5 Ka7
135. Kd4 Ka8 136. Qb4 Ka7 137. Qb2 Ka6 138. Kc4 Ka7 139. Kc3 Ka8 140. Kd3
Ka7 141. Kc4 Ka8 142. Kc5 Ka7 143. Qb1 Ka8 144. Kc6 Ka7 145. Qb2 Ka6 146.
Kc5 Ka7 147. Qb4 Ka8 148. Kc6 Ka7 149. Qb1 Ka6 150. Qb5+ Ka7 151. Qb6+ Ka8
152. Qd8+ Ka7 153. Kb5 Kb7 154. Qd7+ Kb8 155. Kc5 Ka8 156. Kc6 Kb8 157.
Qb7#
&#123;White mates&#125; 1-0

Sven · Post by **Sven** » Wed Dec 31, 2008 8:48 pm

As an example, Fruit 2.1 checks for draw by repetition (and also for some trivial draws that are mainly based on present material) *before* probing the transposition hash table. I think you get in trouble if you don't, since you usually don't know about repetitions within your hash entry.

I also think the problem is not only related to mate scores from the hash table. Assume you are somewhere in the tree at node P and store a value V in the TT hash table that means "the moving side is losing". Later on, maybe in a later search or another iteration, you search P again deeper than before, and in one line you arrive at node Q, with same side to move as in P, where you find a forced way to repeat P. What you would like to get returned from searching Q is indeed a draw value, therefore you also need to get a draw value returned from P based on the repetition, not the hash table value V - provided you stick with the usual way of scoring already the first repetition as a draw when being within the tree. So you do not need a mate score to get into trouble when not checking for repetition first.

This is at least how I understand it. There might also be some other solutions around.

EDIT: I only noticed Zach's post, with the same advice "rep check before hash probe", after having sent mine.

Sven

Draw by repetition when mate is possible

Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible

Re: Draw by repetition when mate is possible