Arimaa Forum - Print Page


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

        Arimaa >> General Discussion >> Importance of repetition rule
        
(Message started by: Fritzlein on May 26^th, 2010, 3:26pm)

Title: Importance of repetition rule
Post by Fritzlein on May 26^th, 2010, 3:26pm

I'm a big fan of decisive games. I can tolerate draws in small amounts, but I don't like them to be frequent. Part of my enjoyment of Arimaa is that it is not naturally drawish. As pieces are captured, the position becomes increasingly unstable, until eventually even a tiny advantage becomes enough to win. This tendency to rumble towards a win for one player or the other seems to be naturally emergent from the basic mechanics of Arimaa. Even if only one player is trying for a win while the other one hunkers down on defense, drawing out a rabbit eventually leads to a hostage, which leads to a loss of elephant mobility, which leads to captures, which leads to goal.

Outside observers, however, may be unfamiliar with the internal strategic pressures of Arimaa, and may justly wonder from the bare rules whether Arimaa is made "artificially" drawless by the repetition rule. There are two levels of "naturalness" that gamers may demand. Some find it tolerable to forbid undoing the opponent's immediately previous move, but consider it too much of a logistical headache to ban larger cycles. In the parlance of Go, they don't mind a "ko rule", but balk at a "superko rule". Others demand an even greater purity, saying that it is already too ugly to ban the opponent from undoing the directly previous move, and if there is no other way for the player who is winning to bring the game to conclusion, then the game should be called a draw, since that is the "natural" outcome. These people (including user unic, programmer of bot_fairy) would rather have neither a ko rule nor a superko rule.

Out of curiosity, I examined the fifty-six games of the 2010 Arimaa World Championship to get some sense of what would happen if Arimaa were played with only a ko rule and no superko rule, or were played with neither a ko rule nor a superko rule. The short answer is that none of the fifty-six games would have had a different outcome, i.e. Arimaa's repetition rules were not necessary to prevent draws in the 2010 World Championship.

To be more specific, in thirty of the games, I couldn't find a single reversible move. The ko rule is not even applicable to these games. This is in stark contrast to Go, where ko situations arise in almost every game.

Of the twenty-six games which featured a reversible move, fourteen had only the losing player making a reversible move. The player in the lead has no incentive to reverse such a move and play for a draw, and indeed in every case had a stronger move than reversal available. So, while the ko rule was applicable, it was not relevant.

In the twelve remaining games, the player in the lead made a move which the trailing player would presumably have liked to reverse, in order to play for a draw rather than seeing his position deteriorate further. Thus the ko rule was relevant and made it easier for the attacker to make progress. However, in each case there were other moves available to press the attacker's advantage, so the absence of a repetition rule would not have created any draws. To put it another way, the leading player always had an advantage greater than the margin of needing to play a reversible move.

The closest to an outcome-changing situation was game 134177 (http://arimaa.com/arimaa/gameroom/comments.cgi?gid=134177), where the ko rule made The_Jeh unable to undo chessandgo's move 38s. Freeing the framed horse is large, but not quite as large as chessandgo's material advantage. Even had The_Jeh managed to force chessandgo to, say, sacrifice this framed horse for a rabbit later on, chessandgo would still have been winning.

In summary, the breakdown of the 56 games was:

30 ko rule not applicable
14 ko rule applicable but irrelevant
12 ko rule relevant but not outcome-changing
0 ko rule outcome-changing

I also kept an eye out for superko situations and found:

55 superko rule not applicable
1 superko rule applicable but irrelevant
0 superko rule relevant but not outcome-changing
0 superko rule outcome-changing

At our current strategic understanding of Arimaa, I estimate that entirely removing the repetition rule would result in approximately 1% draws, while retaining the ko rule and ditching the superko rule would result in 0.01% draws, i.e. perhaps one in ten thousand. Indeed, in Beginning Arimaa I recommend the simple ko rule instead of the official Arimaa rule, because it is so much easier and covers almost every case. (Note I am speaking of human players, not brain-dead computers that aimlessly shuffle pieces simply because they have no long-term strategy.)

Of course, any forecast like mine must be tempered by admitting that we don't know what future games of Arimaa will look like. At one point in 2004, it looked possible (albeit unlikely) that optimal play could prevent all rabbit pulls, and thus result in a no-capture stalemate. Games have become far more aggressive since then. Now we understand that someone who plays to prevent rabbit pulls can be crushed under a swarm.

In 2010, the more plausible threat of a no-capture stalemate would be a swarming player sharing control of both opposing traps, but getting so tied up in the process that he has no mobility left to make captures in his home traps. So far, both sides of the equation have never happened at the same time, i.e. the swarming player has either been not quite strong enough to share control of both opposing traps (and thus eventually lost pieces), or he was strong enough to avoid losing pieces in either opposing trap and retained the mobility necessary to make captures in home traps. Also, whenever the defender gets at least one strong piece out in front of the swarm, it prevents stalemate.

Arimaa is not naturally drawish at present, and doesn't rely on the repetition rule to be playable. If unic had his way and abolished the repetition rule, there would be a few draws, but not too many. It is a theoretical possibility that Arimaa will become naturally drawish in the future, at which point the ko rule and superko rule would take on greater significance than they have now, but based on present top-level games, that danger seems remote.

Title: Re: Importance of repetition rule
Post by FireBorn on May 26^th, 2010, 6:23pm

Sans ko rule:

What if the winning player was low on time and it was critical for the losing player to reverse a certain move? This would give the winning player an incentive to continually play the reversible move in order to refill his reserve.

Title: Re: Importance of repetition rule
Post by Fritzlein on May 26^th, 2010, 7:02pm

Without a ko rule there would of course have to be some way to declare a repeating position to be a draw, perhaps by the chess rule of allowing a draw claim by either player after three-fold repetition. Chess players do routinely gain time with a second repetition even when they intend to deviate and play for the win before allowing a third repetition.

Title: Re: Importance of repetition rule
Post by omar on May 26^th, 2010, 9:45pm

Thanks for looking into this Karl.

Like you said Arimaa is not inherently drawish because as the game progresses the goal of the game becomes more achievable and results in a win for one player or the other. Chess tends to be inherently drawish because as the game progresses and there are less pieces on the board the goal of the game becomes harder to achieve.

I was also pondering what would happen if 3rd time repetition meant the game is a draw instead of being an illegal move. Even if that were the case I think it would often turn out that one of the players would feel they have an advantage and would choose to deviate rather than allowing a draw. A game would only draw if both players were pretty much equal and thought that any other move would cause them to lose. This type of draw might be the ultimate result for Arimaa, but if we get to a point where most of the games end this way we are probably playing close to perfect.

Title: Re: Importance of repetition rule
Post by FireBorn on Jun 28^th, 2010, 10:25pm

This game seems drawish: http://arimaa.com/arimaa/games/jsShowGame.cgi?gid=147644&s=b I resigned cuz I couldn't figure out any way to make progress.

Title: Re: Importance of repetition rule
Post by Fritzlein on Jun 28^th, 2010, 11:15pm

Interesting game, Fireborn. Thanks for the link. I'm impressed at how much progress you made from a very bad position. From move 35, Bomb could have put his camel on f2, flipped your dog to f1, and won lots of material in short order. Bomb's double-frame position was not initially drawish, i.e. your swarm failed to share control of both opposing traps, resulting in a large advantage to the defense.

I think you were correct to despair of making progress from the final position. The only way I see for you to win is to run the game out of time and win due to possessing greater material. Due to the silly time control with 30 seconds per move and 8 hours for the game, that would have taken approximately 480 moves. It is clear that the time cutoff seldom comes into play, or we would know better than to set it as such a high number of moves.

The reason I wouldn't call the position drawish is that as late as 84g you are offering Bomb a chance to make progress by flipping your f3-dog to g2. That would have won Bomb at least a dog and a rabbit, nearly equalizing the material with a nice position as well. That is to say, I think Bomb was winning after your 83s, even though Bomb wasn't clever enough to see the winning plan.

I guess that it is an open question for debate whether an Arimaa position can be called drawish based on one incompetent player refusing to execute an advantageous plan, as opposed to each player's objectively best move being to maintain the stalemate. But you are certainly right that this is the type of position that raises the possibility of Arimaa devolving into a draw.

Title: Re: Importance of repetition rule
Post by FireBorn on Jun 29^th, 2010, 8:58am

Thanks for the analysis, Fritzlein.

Title: Re: Importance of repetition rule
Post by Fritzlein on Jun 29^th, 2010, 8:13pm

on 06/29/10 at 08:58:32, FireBorn wrote:

Thanks for the analysis, Fritzlein.

You're welcome; thanks for the link. I hope other people post similar games to this thread. If Arimaa is ever going to suffer from a draw problem, these are the early warning signs that will allow us not only to recognize the problem rather than denying it, but also to formulate patches to the rules that might fix it before all of our events bog down unacceptably. My intuition is that Arimaa's superko rule does not fix the potential problem in any practical sense, so we can't be smug about saying draws in Arimaa are impossible. Draws never happen (yet) but that is no excuse to ignore the possibility.

Title: Re: Importance of repetition rule
Post by rozencrantz on Jun 29^th, 2010, 8:49pm

My understanding was that there was no provision in the rules for a draw. Is there a 50-move rule similar to chess?

Title: Re: Importance of repetition rule
Post by Fritzlein on Jun 29^th, 2010, 9:33pm

on 06/29/10 at 20:49:53, rozencrantz wrote:

My understanding was that there was no provision in the rules for a draw. Is there a 50-move rule similar to chess?

No, there is no 50-move rule in Arimaa. Therefore every game continues until some condition is met: goal, elimination, or immobilization. Repetition is illegal, so if nothing else, one of the players will eventually exhaust all of his options and lose by immobilization when the only otherwise-legal move would be a repetition.

It is possible that none of the conditions would be met within a reasonable time frame, say within 150 moves. No game between two humans has ever drawn out indefinitely, but in case it would happen, Omar has put a maximum game time into the time control. If the maximum game time were ever reached, the player with more pieces would win. If the number of pieces were tied, the player who knocked his opponent down to that number of pieces first would win. If there were no captures in the game, Silver would win.

The time cutoff rule makes draws impossible, but it is only a reasonable rule because it never happens. I'm glad the situation is covered in case it unexpectedly occurs in a World Championship or something, but my belief is that if it starts to become necessary to invoke a time cutoff to decide games, the Arimaa community will quickly reject the time cutoff rule and replace it with something more acceptable.

To be clear, this makes TWO rules that Arimaa has to make it theoretically drawless, one based on repetition (a.k.a. superko) and one based on game time. Both rules are ugly hacks in my opinion, but neither is ever invoked, so it doesn't matter. Yet. Arimaa is not drawish by nature, so it doesn't need these patches to make it drawless, but if it ever needed them, the patches would be deemed inadequate and quickly discarded, IHMO.

Title: Re: Importance of repetition rule
Post by omar on Jun 30^th, 2010, 7:07pm

Quote:

To be clear, this makes TWO rules that Arimaa has to make it theoretically drawless, one based on repetition (a.k.a. superko) and one based on game time. Both rules are ugly hacks in my opinion, but neither is ever invoked, so it doesn't matter. Yet. Arimaa is not drawish by nature, so it doesn't need these patches to make it drawless, but if it ever needed them, the patches would be deemed inadequate and quickly discarded, IHMO.

Maybe with no game time limit and perfect play Arimaa is ultimately a draw. That would be awesome.

Title: Re: Importance of repetition rule
Post by Fritzlein on Jun 30^th, 2010, 11:48pm

on 06/30/10 at 19:07:46, omar wrote:

Maybe with no game time limit and perfect play Arimaa is ultimately a draw. That would be awesome.

The result of perfect play in Arimaa could be a Gold win, a Silver win, or a draw, but I don't care which it is as long as our imperfect play never gets good enough that the "perfect result" starts to dominate. In practice we can deal with a small number of draws or a small Gold/Silver imbalance, but not very much of either. Fortunately we are quite deep in the exploration of Arimaa without any draws or any imbalance. The longer it stays that way, i.e. the longer perfect play is an irrelevant theoretical construct, the happier I will be.