Repetition detection question

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.
bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Repetition detection question

Post by bob » Mon Jan 28, 2008 9:55 pm

Here is something I have not seen asked or discussed previously. I found a serious repetition bug in Crafty that has been around for a couple of years. But in fixing it I looked carefully at how/when/where it was called, and came across the following issue.....

Do you still do repetition checks below a null-move? I have not yet concluded whether the answer should be yes or no. For me, I have been doing so, but it appears that it is wasted and might even break a null-move search here and there, because obviously there can be no repetition below a null-move that repeats a position prior to the null move. Actually there can be, but do we want it to terminate the null-move search? I am thinking "no" since the purpose of the null-move is to determine whether my current position is so good that even if I "pass" I am still winning, and a repetition might cause the answer to be "no" erroneously...

Has anyone given this any kind of thought??? If so, did you actually reach any kind of useful conclusion as a result? :)

Bob

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

Re: Repetition detection question

Post by Gerd Isenberg » Mon Jan 28, 2008 10:00 pm

bob wrote:Here is something I have not seen asked or discussed previously. I found a serious repetition bug in Crafty that has been around for a couple of years. But in fixing it I looked carefully at how/when/where it was called, and came across the following issue.....

Do you still do repetition checks below a null-move? I have not yet concluded whether the answer should be yes or no. For me, I have been doing so, but it appears that it is wasted and might even break a null-move search here and there, because obviously there can be no repetition below a null-move that repeats a position prior to the null move. Actually there can be, but do we want it to terminate the null-move search? I am thinking "no" since the purpose of the null-move is to determine whether my current position is so good that even if I "pass" I am still winning, and a repetition might cause the answer to be "no" erroneously...

Has anyone given this any kind of thought??? If so, did you actually reach any kind of useful conclusion as a result? :)

Bob
Why not treat null-move as irreversible?

rjgibert
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Repetition detection question

Post by rjgibert » Mon Jan 28, 2008 10:36 pm

I'm very far from an expert on nullmove, but here is my take on this issue.

If you repeat a position from before the null move, that is a demonstration that for at least that one line after the null move, the null move was of no benefit to the other side i.e. the position is still good for the null moving side, so the repetition should be counted, but not as a draw, but as a fail high position for the null moving side.

I may be way off base, but that is what seems to make sense to me.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Repetition detection question

Post by Zach Wegner » Mon Jan 28, 2008 11:17 pm

bob wrote:Here is something I have not seen asked or discussed previously. I found a serious repetition bug in Crafty that has been around for a couple of years. But in fixing it I looked carefully at how/when/where it was called, and came across the following issue.....

Do you still do repetition checks below a null-move? I have not yet concluded whether the answer should be yes or no. For me, I have been doing so, but it appears that it is wasted and might even break a null-move search here and there, because obviously there can be no repetition below a null-move that repeats a position prior to the null move. Actually there can be, but do we want it to terminate the null-move search? I am thinking "no" since the purpose of the null-move is to determine whether my current position is so good that even if I "pass" I am still winning, and a repetition might cause the answer to be "no" erroneously...

Has anyone given this any kind of thought??? If so, did you actually reach any kind of useful conclusion as a result? :)

Bob
I check(ed) for null moves in the history, because I use infinitely recursive null move and it could immediately return a draw. I didn't really think it through, I just needed to not return reps after null moves. Now I realize the Gerd's suggestion is a much better way of handling it.

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Repetition detection question

Post by bob » Mon Jan 28, 2008 11:18 pm

Gerd Isenberg wrote:
bob wrote:Here is something I have not seen asked or discussed previously. I found a serious repetition bug in Crafty that has been around for a couple of years. But in fixing it I looked carefully at how/when/where it was called, and came across the following issue.....

Do you still do repetition checks below a null-move? I have not yet concluded whether the answer should be yes or no. For me, I have been doing so, but it appears that it is wasted and might even break a null-move search here and there, because obviously there can be no repetition below a null-move that repeats a position prior to the null move. Actually there can be, but do we want it to terminate the null-move search? I am thinking "no" since the purpose of the null-move is to determine whether my current position is so good that even if I "pass" I am still winning, and a repetition might cause the answer to be "no" erroneously...

Has anyone given this any kind of thought??? If so, did you actually reach any kind of useful conclusion as a result? :)

Bob
Why not treat null-move as irreversible?
That is what I have been doing, but I thought I would ask to see if there were any different opinions...

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Repetition detection question

Post by bob » Mon Jan 28, 2008 11:19 pm

rjgibert wrote:I'm very far from an expert on nullmove, but here is my take on this issue.

If you repeat a position from before the null move, that is a demonstration that for at least that one line after the null move, the null move was of no benefit to the other side i.e. the position is still good for the null moving side, so the repetition should be counted, but not as a draw, but as a fail high position for the null moving side.

I may be way off base, but that is what seems to make sense to me.
My question would be, why is that good? Suppose I am winning handily before trying a null-move. How does repeating a position after the null that was played before the null prove that this position is good for me???

rjgibert
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Repetition detection question

Post by rjgibert » Mon Jan 28, 2008 11:27 pm

bob wrote:
rjgibert wrote:I'm very far from an expert on nullmove, but here is my take on this issue.

If you repeat a position from before the null move, that is a demonstration that for at least that one line after the null move, the null move was of no benefit to the other side i.e. the position is still good for the null moving side, so the repetition should be counted, but not as a draw, but as a fail high position for the null moving side.

I may be way off base, but that is what seems to make sense to me.
My question would be, why is that good? Suppose I am winning handily before trying a null-move. How does repeating a position after the null that was played before the null prove that this position is good for me???
It's just as good as the position before the the null move that got repeated. You gave up a tempo with the nullmove and wrested the tempo back. What could be more convincing (besides mate)?

rjgibert
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Repetition detection question

Post by rjgibert » Tue Jan 29, 2008 12:15 am

bob wrote:
rjgibert wrote:I'm very far from an expert on nullmove, but here is my take on this issue.

If you repeat a position from before the null move, that is a demonstration that for at least that one line after the null move, the null move was of no benefit to the other side i.e. the position is still good for the null moving side, so the repetition should be counted, but not as a draw, but as a fail high position for the null moving side.

I may be way off base, but that is what seems to make sense to me.
My question would be, why is that good? Suppose I am winning handily before trying a null-move. How does repeating a position after the null that was played before the null prove that this position is good for me???
Here is another way of looking at it if you prefer.

If you answer "no" as you suggested to the original question you posed, then what will happen is that your program will then look up the position in the hash table and get a hit if the entry has not been overwritten.

Naturally, the entry will have more than enough depth to it and your program will use the entry for a cutoff producing essentially the same result.

Karlo Bala
Posts: 301
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Repetition detection question

Post by Karlo Bala » Tue Jan 29, 2008 12:36 am

bob wrote:
Gerd Isenberg wrote:
bob wrote:Here is something I have not seen asked or discussed previously. I found a serious repetition bug in Crafty that has been around for a couple of years. But in fixing it I looked carefully at how/when/where it was called, and came across the following issue.....

Do you still do repetition checks below a null-move? I have not yet concluded whether the answer should be yes or no. For me, I have been doing so, but it appears that it is wasted and might even break a null-move search here and there, because obviously there can be no repetition below a null-move that repeats a position prior to the null move. Actually there can be, but do we want it to terminate the null-move search? I am thinking "no" since the purpose of the null-move is to determine whether my current position is so good that even if I "pass" I am still winning, and a repetition might cause the answer to be "no" erroneously...

Has anyone given this any kind of thought??? If so, did you actually reach any kind of useful conclusion as a result? :)

Bob
Why not treat null-move as irreversible?
That is what I have been doing, but I thought I would ask to see if there were any different opinions...
I treat NULL move just like pawn push somewhere out of board.
(every NULL is different pawn push). With that approach even double NULL work fine in pawn endgames 8-)
Best Regards,
Karlo Balla Jr.

BubbaTough
Posts: 1154
Joined: Fri Jun 23, 2006 3:18 am

Re: Repetition detection question

Post by BubbaTough » Tue Jan 29, 2008 12:39 am

This is an interesting question. Has anyone actually collected any data as to which way works best in games?

-Sam

Post Reply