Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> General Discussion >> Please help me verify the 3-repeat rule
        
(Message started by: chimaera on Nov 12th, 2009, 8:24pm)
Title: Please help me verify the 3-repeat rule
Post by chimaera on Nov 12th, 2009, 8:24pm
Could someone please give this a quick scan and validate my logic here? I'm trying to make sure that I fully understand the "3-move repeat rule" in the Arimaa rules.

I've marked up each board position like so:
// board layout $WhoseTurn-$Pattern #$OccurenceNumber


Code:
2g
+-----------------+ // board layout Gold-A #1
8| d c r h r r c d |
7| r r m h r r r e |
6|   . x .   x   . |
5| .   .   .   .   |
4|   .   .   .   . |
3| .   x   . x .   |
2| D C D H R H E M |
1| C R R R R R R R |
+-----------------+
  a b c d e f g h

2s
+-----------------+ // board layout Silver-A #1
8| d c r h r r c d |
7| r r m h r r r e |
6|   . x .   x   . |
5| .   .   .   .   |
4|   .   .   .   . |
3| .   x   . x E   |
2| D C D H R H   M |
1| C R R R R R R R |
+-----------------+
  a b c d e f g h

3g
+-----------------+ // board layout Gold-B #1
8| d c r h r r c d |
7| r r m h r r r   |
6|   . x .   x   e |
5| .   .   .   .   |
4|   .   .   .   . |
3| .   x   . x E   |
2| D C D H R H   M |
1| C R R R R R R R |
+-----------------+
  a b c d e f g h

3s
+-----------------+ // board layout Silver-B #1
8| d c r h r r c d |
7| r r m h r r r   |
6|   . x .   x   e |
5| .   .   .   .   |
4|   .   .   .   . |
3| .   x   . x .   |
2| D C D H R H E M |
1| C R R R R R R R |
+-----------------+
  a b c d e f g h

4g
+-----------------+ // board layout Gold-A #2
8| d c r h r r c d |
7| r r m h r r r e |
6|   . x .   x   . |
5| .   .   .   .   |
4|   .   .   .   . |
3| .   x   . x .   |
2| D C D H R H E M |
1| C R R R R R R R |
+-----------------+
  a b c d e f g h

4s
+-----------------+ // board layout Silver-A #2
8| d c r h r r c d |
7| r r m h r r r e |
6|   . x .   x   . |
5| .   .   .   .   |
4|   .   .   .   . |
3| .   x   . x E   |
2| D C D H R H   M |
1| C R R R R R R R |
+-----------------+
  a b c d e f g h

5g
+-----------------+ // board layout Gold-B #2
8| d c r h r r c d |
7| r r m h r r r   |
6|   . x .   x   e |
5| .   .   .   .   |
4|   .   .   .   . |
3| .   x   . x E   |
2| D C D H R H   M |
1| C R R R R R R R |
+-----------------+
  a b c d e f g h

5s
+-----------------+ // board layout Silver-B #2
8| d c r h r r c d |
7| r r m h r r r   |
6|   . x .   x   e |
5| .   .   .   .   |
4|   .   .   .   . |
3| .   x   . x .   |
2| D C D H R H E M |
1| C R R R R R R R |
+-----------------+
  a b c d e f g h


The move eh6n and then a pass would be illegal, correct? It would cause the board layout "Gold-A" to occur a third time. Therefore, if silver makes the move eh6n, then she must make 1+ more moves before she is allowed to end her turn.
Title: Re: Please help me verify the 3-repeat rule
Post by chimaera on Nov 12th, 2009, 8:38pm
Also, I should note that I did search and find threads discussing this, but I want to make absolutely sure that I understand this rule. The rule "If after a turn the same board position and side to move would be repeated three times..." is a little ambiguous because it implies a fourth occurrence would be illegal (an initial pattern plus three repeats of the pattern).
Title: Re: Please help me verify the 3-repeat rule
Post by Fritzlein on Nov 12th, 2009, 8:45pm

on 11/12/09 at 20:24:05, chimaera wrote:
The move eh6n and then a pass would be illegal, correct? It would cause the board layout "Gold-A" to occur a third time. Therefore, if silver makes the move eh6n, then she must make 1+ more moves before she is allowed to end her turn.

Correct.

It gets a little tricky to be talking about which steps are forbidden, because the repetition rule deals with which full turns are forbidden.
Title: Re: Please help me verify the 3-repeat rule
Post by chimaera on Nov 12th, 2009, 8:53pm
Thank you. I didn't want to clutter up the forum with a repeat (;D) of a topic, but the previous posts I found were just people saying "So if I repeat it X times that's bad?"; "Yes, repeating it X times is bad", etc.
Title: Re: Please help me verify the 3-repeat rule
Post by chimaera on Nov 12th, 2009, 8:56pm

on 11/12/09 at 20:45:21, Fritzlein wrote:
It gets a little tricky to be talking about which steps are forbidden, because the repetition rule deals with which full turns are forbidden.


And yes, it is very tricky to do this. The approach I've taken in my program is to allow the user to back herself into a corner and thus lose, but not to allow a turn to be ended early if it would be illegal, or to move at the last step of a turn if it would be illegal, or to begin a push on the second-last step if the only way to follow through on the push would be illegal. Implementing this check was very annoying!
Title: Re: Please help me verify the 3-repeat rule
Post by ocmiente on Apr 19th, 2010, 1:13pm
I wonder if misunderstanding the 3-repeat rule is very common.  I didn't grasp it until game 141408 (http://arimaa.com/arimaa/games/jsShowGame.cgi?gid=141408&s=b), bot_marwin vs. Adanac in the 2010 Arimaa challenge, move 42s.  I was wondering why marwin didn't just repeat the position and force Adanac to choose something else.  

I read the rule to mean that basically you couldn't make the same move three times, provided your opponent repeated his moves also.  It didn't occur to me that the repeated board position doesn't occur 3 times until both players repeat their moves 3 times.  I think Adanac put it well in the chat room:
Quote:
Defending by reversing is cheap so I'm glad the attacker wins the repitition rule.


The way the works out still seems counterintuitive to me - but I think that the logic of it works out brilliantly.  

Of course, I could still be misinterpreting the rule and need some deeper understanding... please correct this if it's wrong.  

<EDIT> Should have written "...the repeated board position doesn't occur 3 times until both players repeat their moves 2 times, which would take 4 turns each.  The 4th turn of the second player would be illegal.  
Title: Re: Please help me verify the 3-repeat rule
Post by Eltripas on Apr 19th, 2010, 5:15pm

on 04/19/10 at 13:13:15, ocmiente wrote:
I wonder if misunderstanding the 3-repeat rule is very common.  I didn't grasp it until game 141408 (http://arimaa.com/arimaa/games/jsShowGame.cgi?gid=141408&s=b), bot_marwin vs. Adanac in the 2010 Arimaa challenge, move 42s.  I was wondering why marwin didn't just repeat the position and force Adanac to choose something else.  

I read the rule to mean that basically you couldn't make the same move three times, provided your opponent repeated his moves also.  It didn't occur to me that the repeated board position doesn't occur 3 times until both players repeat their moves 3 times.  I think Adanac put it well in the chat room:

The way the works out still seems counterintuitive to me - but I think that the logic of it works out brilliantly.  

Of course, I could still be misinterpreting the rule and need some deeper understanding... please correct this if it's wrong.  


You are misinterpreting the rule, the rule is designed in a way that it always helps the development of the game, for example if the game is in a position A and the attacker makes a move so the game is no in position B, the defender moves back to position A, and then the attacker moves again to get the position B, the defender can't return to the position A for a third time so the game makes development.
Title: Re: Please help me verify the 3-repeat rule
Post by ocmiente on Apr 19th, 2010, 6:23pm
umm... well... I think what I wrote earlier agrees with what you wrote - so I think you might have meant 'were' misinterpreting, rather than 'are' misinterpreting?  

Sorry that my writing was not as clear as it could have been.  In short, I think I understand why marwin did what it did - and that its behavior was due to the 3-repeat rule.   The 3-repeat rule does not have do to so much with repeating a move three times as it does with repeating a board position (combined with whose move it is), which seems pretty simple on paper - but I expect that many people don't get that the first time they read it... and if they don't, its likely that it won't sink in until they witness a game like the one I watched.

Title: Re: Please help me verify the 3-repeat rule
Post by Hippo on Apr 20th, 2010, 7:31am
Out of topic ... I have checked no change rule as well ... for example rotating two dogs does not change the board state.
Title: Re: Please help me verify the 3-repeat rule
Post by rbarreira on Apr 20th, 2010, 7:37am
The problem is that people keep talking about "repeating" and "returning to" positions (which is actually how the rule is written). The problem is that the first time the position happens, it's not "repeating" itself strictly speaking.

If I understand it correctly, the rule actually means that you can't "have" the same (position/side to move) three times. By using "have" instead of other ambiguous verbs there should be no room left for confusion.
Title: Re: Please help me verify the 3-repeat rule
Post by lightvector on Apr 20th, 2010, 11:20am
I agree. From the game rules:


Quote:
If after a turn the same board position and side to move would be repeated three times, then that move is considered illegal and the player must select a different move.


I think it would be clearer to say something like:

If after a turn the same board position and side to move would occur for the third time, then that move is illegal and the player must select a different move.
Title: Re: Please help me verify the 3-repeat rule
Post by ocmiente on Apr 20th, 2010, 2:23pm

Quote:
I think it would be clearer to say something like:

If after a turn the same board position and side to move would occur for the third time, then that move is illegal and the player must select a different move.


Yes, I agree with that.  


Quote:
Out of topic ... I have checked no change rule as well ... for example rotating two dogs does not change the board state.


Hippo, I hadn't even thought about that - but it's an interesting point.  Rotating two pieces isn't a legal move, right? Since the board state doesn't actually change?


I went ahead and looked into the threefold repetition rule for Chess: http://en.wikipedia.org/wiki/Threefold_repetition.  

From that, it appears that the initial rule did have to do with repeating moves, and not with repeating positions.  I think that that is the more natural and intuitive way for people to think about something like this, especially when playing on a board with no computer assistance.  

Quote:
The first use of such a rule was in a tournament was in London in 1883, but was stated vaguely:

... if a series of moves be repeated three times the opponent can claim a draw.


It was soon changed to be that the position had to be repeated, along with the side to move, and ability to castle.  I think that this is better for the game, but not as intuitive.
Title: Re: Please help me verify the 3-repeat rule
Post by Fritzlein on Apr 20th, 2010, 2:32pm

on 04/20/10 at 14:23:05, ocmiente wrote:
Rotating two pieces isn't a legal move, right? Since the board state doesn't actually change?

Correct.  Swapping your dogs doesn't change the position, so it is not a legal move.  Also for repeated positions the dogs are interchangeable, not distinct.


Quote:
From that, it appears that the initial rule did have to do with repeating moves, and not with repeating positions.  I think that that is the more natural and intuitive way for people to think about something like this, especially when playing on a board with no computer assistance.

Yes, for Arimaa too, when there is no computer assistance I would replace the repetition rule with the simpler rule: Your move may not undo your opponent's previous move.   That isn't identical to the actual rule, but it is vastly simpler and covers most of the cases.  Indeed, bot_bomb uses the "no undo" rule instead of the true repeat rule, and that was good enough to win five Computer Championships.
Title: Re: Please help me verify the 3-repeat rule
Post by Arimabuff on Apr 21st, 2010, 2:30am
I wonder how people can even play a fair game without computer assistance especially people who are new to the game. It must be easy to forget a freezing "en passant" or a disappearing piece on the trap because it has been abandoned for one step. The repeat rule is just icing on an already hard to digest cake.
Title: Re: Please help me verify the 3-repeat rule
Post by Fritzlein on Apr 21st, 2010, 6:25am

on 04/21/10 at 02:30:08, Arimabuff wrote:
I wonder how people can even play a fair game without computer assistance especially people who are new to the game. It must be easy to forget a freezing "en passant" or a disappearing piece on the trap because it has been abandoned for one step. The repeat rule is just icing on an already hard to digest cake.

Yes, I expect beginners make illegal moves all the time in Arimaa.  On the other hand, that's just how it was for chess when I was learning.  I would leave my king in check for several moves, and not know what to do when I discovered it later.  I didn't understand when I could or couldn't castle.  I thought that pawns could use their opening double-move to capture two squares diagonally as well as advance two squares forward.  Admittedly, Arimaa isn't easy to play at first without a rule-checker keeping watch, but it is in good company on that score.
Title: Re: Please help me verify the 3-repeat rule
Post by SpeedRazor on Apr 21st, 2010, 9:08am

on 04/21/10 at 06:25:50, Fritzlein wrote:
Yes, I expect beginners make illegal moves all the time in Arimaa.


If it helps, Victor Korchnoi made it all the way to the Soviet Union Chess Championship before he realized that you could still castle if your castling rook was en prise, and Gary Kasparov considers him to be the best player to never become world champion.  Good company indeed...
Title: Re: Please help me verify the 3-repeat rule
Post by Hippo on Apr 21st, 2010, 10:25am
I have wrote that eariler, but theoretically you would prefere dog and horse to two horses as the first one allows you to rotate them in zugzwang :). I have to find a position proving that :)
Title: Re: Please help me verify the 3-repeat rule
Post by Adanac on Apr 21st, 2010, 1:21pm

on 04/21/10 at 09:08:44, SpeedRazor wrote:
If it helps, Victor Korchnoi made it all the way to the Soviet Union Chess Championship before he realized that you could still castle if your castling rook was en prise, and Gary Kasparov considers him to be the best player to never become world champion.  Good company indeed...


Another Grandmaster (I have forgotten which one) was surprised to learn that a queenside castle was legal (K to c1, Rook to d1) even with a black rook on b2.  You can't castle out of, into, or through check but that only applies to the king.  I remember being amazed that a Grandmaster hadn't bothered to learn the rules of castling!

Admittedly, I didn't bother to really learn the repitition rules in Arimaa until a couple of years ago.   :-[ And then I was pleasantly surprsied to learn that it generally favours the attacker  :)

As an aside, I remember hearing a debate between 2 chess players about whether a white king on e1 can castle to e3 with a white rook jumping from e8 to e2 -- the important point is that the rook has just been promoted from a pawn.  It hasn't moved yet since changing from a pawn to a rook so one guy was arguing that it satisfied the "castling with a rook that hasn't moved yet" rule.  It's obviously not in the spirit of the castling and yet some people are such rules lawyers that they'll try to argue any ridiculous scenarios on technicalities!
Title: Re: Please help me verify the 3-repeat rule
Post by omar on Apr 21st, 2010, 7:58pm

on 04/20/10 at 11:20:13, lightvector wrote:
I agree. From the game rules:


I think it would be clearer to say something like:

If after a turn the same board position and side to move would occur for the third time, then that move is illegal and the player must select a different move.


Thanks for the clearer wording. I've updated the rules page.
Title: Re: Please help me verify the 3-repeat rule
Post by omar on Apr 21st, 2010, 8:09pm

on 11/12/09 at 20:56:02, chimaera wrote:
And yes, it is very tricky to do this. The approach I've taken in my program is to allow the user to back herself into a corner and thus lose, but not to allow a turn to be ended early if it would be illegal, or to move at the last step of a turn if it would be illegal, or to begin a push on the second-last step if the only way to follow through on the push would be illegal. Implementing this check was very annoying!


What I do to implement this is keep an array of strings representing the positions that have occurred in the history of the game. Like this:

Code:
................................................RHDEMDHRRCRRRRCRb
rrrccrrrrhhdedmr................................RHDEMDHRRCRRRRCRw
rrrccrrrrhhdedmr...................E.....H..M...R.D..DHRRCRRRRCRb
rrrccrrrr.hd.d.r.h....m.....e......E.....H..M...R.D..DHRRCRRRRCRw
rrrccrrrr.hd.d.r.h....m.....e.......E....HM...H.R.D..D.RRCRRRRCRb
rrrccrrrr.hd.d...h....mr..........e.E....HM...H.R.D..D.RRCRRRRCRw


After the 4 steps are taken check to see if the resulting position string occurs two times in the array. If so then the move is not allowed.
Title: Re: Please help me verify the 3-repeat rule
Post by RonWeasley on Apr 22nd, 2010, 4:50am

on 04/21/10 at 13:21:38, Adanac wrote:
As an aside, I remember hearing a debate between 2 chess players about whether a white king on e1 can castle to e3 with a white rook jumping from e8 to e2 -- the important point is that the rook has just been promoted from a pawn.  It hasn't moved yet since changing from a pawn to a rook so one guy was arguing that it satisfied the "castling with a rook that hasn't moved yet" rule.  It's obviously not in the spirit of the castling and yet some people are such rules lawyers that they'll try to argue any ridiculous scenarios on technicalities!

As a tournament director, I've been waiting to summarily dismiss such foolishness.  I'm very surprised it hasn't happened in any of our tournaments.
Title: Re: Please help me verify the 3-repeat rule
Post by rbarreira on Apr 22nd, 2010, 5:07am

on 11/12/09 at 20:56:02, chimaera wrote:
And yes, it is very tricky to do this. The approach I've taken in my program is to allow the user to back herself into a corner and thus lose, but not to allow a turn to be ended early if it would be illegal, or to move at the last step of a turn if it would be illegal, or to begin a push on the second-last step if the only way to follow through on the push would be illegal. Implementing this check was very annoying!


Another reason why step-based search should at most be used only for deepening/move ordering, not for the regular search tree stuff like checking end of game or legality of moves.

With a regular minimax (move-based) the 3-repetition rule is very easy to implement in a bot (basically what omar just said but implemented more efficiently, probably by using the history of past board hashes).


Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.