avoidrep-pruning
Moderator: Ras
-
- Posts: 2251
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
avoidrep-pruning
If alfa >= DRAW_SCORE and both previous moves (each of either side) were reversible (move50 >= 2), is it safe to avoid repetition draws by pruning the move which reverses or unmakes the own previous one two ply before?
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: avoidrep-pruning
No, because only one move is undone, so there's a potentially different position. If both moves are undone, the position from four ply earlier reappears and this is easily detected as a repetition.
-
- Posts: 2251
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: avoidrep-pruning
Lets take a look from the other, weaker side.
Assume you enter a node with beta <= 0, so that a repetition with score zero would fail high. Further assume Move50 counter is >= 3 and distance to root at least 3 as well. And the two previous reversible moves of the "better" side were in fact make and unmake, thus a null-move - so that the "weaker" side to move may undo it own previous move as well (which was reversible due to move50 >= 3 condition) - forcing at least a two-fold repetition to immediate return a failing high zero-score. Since the position to repeat was legal before, it is safe to assume that unmaking last reversable move is legal as well, despite eventually in check - thus without generating and trying this move.
I was surprised how often the above cheap conditions were true in my search, also because it catches repetitions at the horizon which would otherwise not be found in qsearch. It significantly reduces the number of the tradionial repetition detections by comparing hashkeys as well. In fact it seems that most repetitions occur in that strupid way in my program.
The probably better implementation would be to prune reversible moves which unmake the previous one, if alfa >= 0 and Move50 >= 2.
Assume you enter a node with beta <= 0, so that a repetition with score zero would fail high. Further assume Move50 counter is >= 3 and distance to root at least 3 as well. And the two previous reversible moves of the "better" side were in fact make and unmake, thus a null-move - so that the "weaker" side to move may undo it own previous move as well (which was reversible due to move50 >= 3 condition) - forcing at least a two-fold repetition to immediate return a failing high zero-score. Since the position to repeat was legal before, it is safe to assume that unmaking last reversable move is legal as well, despite eventually in check - thus without generating and trying this move.
I was surprised how often the above cheap conditions were true in my search, also because it catches repetitions at the horizon which would otherwise not be found in qsearch. It significantly reduces the number of the tradionial repetition detections by comparing hashkeys as well. In fact it seems that most repetitions occur in that strupid way in my program.
The probably better implementation would be to prune reversible moves which unmake the previous one, if alfa >= 0 and Move50 >= 2.
Re: avoidrep-pruning
Same experience here, same solution as well.Gerd Isenberg wrote:Lets take a look from the other, weaker side.
Assume you enter a node with beta <= 0, so that a repetition with score zero would fail high. Further assume Move50 counter is >= 3 and distance to root at least 3 as well. And the two previous reversible moves of the "better" side were in fact make and unmake, thus a null-move - so that the "weaker" side to move may undo it own previous move as well (which was reversible due to move50 >= 3 condition) - forcing at least a two-fold repetition to immediate return a failing high zero-score. Since the position to repeat was legal before, it is safe to assume that unmaking last reversable move is legal as well, despite eventually in check - thus without generating and trying this move.
I was surprised how often the above cheap conditions were true in my search, also because it catches repetitions at the horizon which would otherwise not be found in qsearch. It significantly reduces the number of the tradionial repetition detections by comparing hashkeys as well. In fact it seems that most repetitions occur in that strupid way in my program.
The probably better implementation would be to prune reversible moves which unmake the previous one, if alfa >= 0 and Move50 >= 2.
Cheers,
Tony
-
- Posts: 2251
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: avoidrep-pruning
Great, you already tried it before without telling us? I hoped I could encourage my ict7 competitors to introcude some last minute bugsTony wrote: Same experience here, same solution as well.
Cheers,
Tony

See you,
Gerd
-
- Posts: 10696
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: avoidrep-pruning
NoGerd Isenberg wrote:If alfa >= DRAW_SCORE and both previous moves (each of either side) were reversible (move50 >= 2), is it safe to avoid repetition draws by pruning the move which reverses or unmakes the own previous one two ply before?
imagine Queen at d1 and Rook at b3
black rook b3-b2
white queen d1-a4
black rook b2-b3
the queen cannot go back to d1.
Note that Junior had repetition bug by assuming that white has at least a draw after the black rook goes b2-b3 (I am not sure if this was exactly the case but I am sure that it evaluated some non drawing line as a draw)and I am not sure if Amir corrected it.
In order to test if programs have this bug you need to compose a position when the only way for black to win is by b3-b2 d1-a4 b2-b3 or something similiar and there are not many cases when it happens.
Uri
-
- Posts: 2251
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: avoidrep-pruning
Thanks Uri,Uri Blass wrote:NoGerd Isenberg wrote:If alfa >= DRAW_SCORE and both previous moves (each of either side) were reversible (move50 >= 2), is it safe to avoid repetition draws by pruning the move which reverses or unmakes the own previous one two ply before?
imagine Queen at d1 and Rook at b3
black rook b3-b2
white queen d1-a4
black rook b2-b3
the queen cannot go back to d1.
Note that Junior had repetition bug by assuming that white has at least a draw after the black rook goes b2-b3 (I am not sure if this was exactly the case but I am sure that it evaluated some non drawing line as a draw)and I am not sure if Amir corrected it.
In order to test if programs have this bug you need to compose a position when the only way for black to win is by b3-b2 d1-a4 b2-b3 or something similiar and there are not many cases when it happens.
Uri
i had the vague feeling that there was something wrong. So it seems one additional condition is appropriate to fix it ...
e.g. from the loser's point of view
Code: Select all
if ( beta < 0 && move50 >= 3 && ply >= 3
&& move[ply-3].from == move[ply-1].to
&& move[ply-3].to == move[ply-1].from
&& move[ply-1].to isNotElement (inbetween(move[ply-2].from, move[ply-2].to) )
return 0;
Gerd
Re: avoidrep-pruning
You have to check if the returning move is legal off course. ie also for checks etc.Uri Blass wrote:NoGerd Isenberg wrote:If alfa >= DRAW_SCORE and both previous moves (each of either side) were reversible (move50 >= 2), is it safe to avoid repetition draws by pruning the move which reverses or unmakes the own previous one two ply before?
imagine Queen at d1 and Rook at b3
black rook b3-b2
white queen d1-a4
black rook b2-b3
the queen cannot go back to d1.
Note that Junior had repetition bug by assuming that white has at least a draw after the black rook goes b2-b3 (I am not sure if this was exactly the case but I am sure that it evaluated some non drawing line as a draw)and I am not sure if Amir corrected it.
In order to test if programs have this bug you need to compose a position when the only way for black to win is by b3-b2 d1-a4 b2-b3 or something similiar and there are not many cases when it happens.
Uri
Tony
-
- Posts: 10696
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: avoidrep-pruning
NoTony wrote:You have to check if the returning move is legal off course. ie also for checks etc.Uri Blass wrote:NoGerd Isenberg wrote:If alfa >= DRAW_SCORE and both previous moves (each of either side) were reversible (move50 >= 2), is it safe to avoid repetition draws by pruning the move which reverses or unmakes the own previous one two ply before?
imagine Queen at d1 and Rook at b3
black rook b3-b2
white queen d1-a4
black rook b2-b3
the queen cannot go back to d1.
Note that Junior had repetition bug by assuming that white has at least a draw after the black rook goes b2-b3 (I am not sure if this was exactly the case but I am sure that it evaluated some non drawing line as a draw)and I am not sure if Amir corrected it.
In order to test if programs have this bug you need to compose a position when the only way for black to win is by b3-b2 d1-a4 b2-b3 or something similiar and there are not many cases when it happens.
Uri
Tony
I do not have to do it in case that I implement it for the following reasons:
1)I have a legal move generator so illegal move is not generated in the first place
2)Even if I had illegal move generator then I see no difference between returning a draw after the illegal move and returning a win for the side to move after it.
If white is happy with a draw and you have
black rook b3-b2
white queen d1-a4+
black rook b2-b3 illegal then returning win for white and returning draw will give the same practical result that b2-b3 is not good for black.
Uri
-
- Posts: 2251
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: avoidrep-pruning
Tony wrote: You have to check if the returning move is legal off course. ie also for checks etc.
Tony
Code: Select all
pos[0] white to move
legal reversible white move[0], from[0]->to[0],
pos[1] black to move
legal reversible black move[1], from[1]->to[1],
pos[2] white to move
legal white move[2], from[2]->to[2], where to[2] == from[0] && from[2] == to[0]
pos[3] black to move
is black move[3] legal to repeat the position?
pos[4] == pos[0] again
If black's move[1] was a distant move of a sliding piece, but the way back to from[1] is now interrupted, because to[2] is occupied again, thus to[2] (or from[0]) is member of the inbetween set of from[1]->to[1]. That is true for checks as well.