avoidrep-pruning

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

avoidrep-pruning

Post by Gerd Isenberg » Tue May 15, 2007 7:14 pm

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?

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: avoidrep-pruning

Post by sje » Wed May 16, 2007 1:01 am

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.

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: avoidrep-pruning

Post by Gerd Isenberg » Wed May 16, 2007 5:58 am

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.

Tony

Re: avoidrep-pruning

Post by Tony » Wed May 16, 2007 6:15 am

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.
Same experience here, same solution as well.

Cheers,

Tony

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: avoidrep-pruning

Post by Gerd Isenberg » Wed May 16, 2007 6:40 am

Tony wrote: Same experience here, same solution as well.

Cheers,

Tony
Great, you already tried it before without telling us? I hoped I could encourage my ict7 competitors to introcude some last minute bugs ;-)

See you,
Gerd

Uri Blass
Posts: 8605
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: avoidrep-pruning

Post by Uri Blass » Wed May 16, 2007 7:21 am

Gerd 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?
No

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

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: avoidrep-pruning

Post by Gerd Isenberg » Wed May 16, 2007 8:55 am

Uri Blass wrote:
Gerd 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?
No

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
Thanks 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&#91;ply-3&#93;.from == move&#91;ply-1&#93;.to
     && move&#91;ply-3&#93;.to == move&#91;ply-1&#93;.from
     && move&#91;ply-1&#93;.to isNotElement &#40;inbetween&#40;move&#91;ply-2&#93;.from, move&#91;ply-2&#93;.to&#41; )
        return 0;
Regards,
Gerd

Tony

Re: avoidrep-pruning

Post by Tony » Wed May 16, 2007 12:15 pm

Uri Blass wrote:
Gerd 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?
No

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
You have to check if the returning move is legal off course. ie also for checks etc.

Tony

Uri Blass
Posts: 8605
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: avoidrep-pruning

Post by Uri Blass » Wed May 16, 2007 12:32 pm

Tony wrote:
Uri Blass wrote:
Gerd 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?
No

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
You have to check if the returning move is legal off course. ie also for checks etc.

Tony
No

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

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: avoidrep-pruning

Post by Gerd Isenberg » Wed May 16, 2007 1:19 pm

Tony wrote: You have to check if the returning move is legal off course. ie also for checks etc.
Tony

Code: Select all

pos&#91;0&#93; white to move
  legal reversible white move&#91;0&#93;, from&#91;0&#93;->to&#91;0&#93;, 
pos&#91;1&#93; black to move
  legal reversible black move&#91;1&#93;, from&#91;1&#93;->to&#91;1&#93;, 
pos&#91;2&#93; white to move
  legal white move&#91;2&#93;, from&#91;2&#93;->to&#91;2&#93;, where to&#91;2&#93; == from&#91;0&#93; && from&#91;2&#93; == to&#91;0&#93;
pos&#91;3&#93; black to move
  is black move&#91;3&#93; legal to repeat the position?
pos&#91;4&#93; == pos&#91;0&#93; again 
I think the only legality check needed for undoing black's move[1] are such cases Uri mentioned.
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.

Post Reply