Arimaa Forum - Print Page


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

        Arimaa >> General Discussion >> Repetition fights
        
(Message started by: clyring on Jul 1^st, 2015, 7:50am)

Title: Repetition fights
Post by clyring on Jul 1^st, 2015, 7:50am

Consider the following generalized repetition fight on a bipartite directed graph with seven vertices:
G1; from which gold may move to S2.
S2; from which silver may move to either G3.
G3a, G3b; from which gold may move only to the corresponding S4.
S4a, S4b; from which silver may move to G1 or G5.
G5; from which gold may move to either S4.

Assuming silver has just moved for the first time from outside the repetition fight to G1 and all moves leaving the repetition fight are losses, who wins, and why is this interesting?

Title: Re: Repetition fights
Post by harvestsnow on Jul 1^st, 2015, 4:33pm

I had to brute-force it. If my code (http://pastebin.com/hcWZtnS9) is correct,

Quote:

Silver wins for any depth of the repetition rule (at least up to 10), except 1 where Gold trivially wins.

I suppose the next step is to find a position where this happens...

Title: Re: Repetition fights
Post by chessandgo on Jul 11^th, 2015, 5:35am

I don't see it. As I understand, the arcs of your graph are:
(g1,s2),
(s2,g3a), (g3a, s4a), (s4a, g5), (s4a, g1), (g5,s4a)
(s2,g3b), (g3b, s4b), (s4b, g5), (s4b, g1), (g5,s4b)

And it seems to me that all reasonable routes will lead to silver to play on s4x with all nodes but g3a and g3b (once each) having been visited twice. For example:

g1,s2,g3a,s4a,g5,s4b,g1,s2,g3b,s4b,g5,s4a.

What am I missing? And what are the answers to the questions you raise clyring? :)

Title: Re: Repetition fights
Post by clyring on Jul 11^th, 2015, 7:24am

You are correct in your reading of the available arcs but incorrect in your analysis. I really don't want to be the one to explain how, though. Obviously harvestsnow's script will spit out the right winner, but it fails to satisfactorily explain what's going on to produce said winner. It's beautiful and simple and you will know it as soon as you find it. :)

Maybe a helpful preliminary exercise: What prerequisites must each player meet in order to win the repetition fight?

Title: Re: Repetition fights
Post by chessandgo on Jul 11^th, 2015, 8:52am

oh, I see it.

Title: Re: Repetition fights
Post by chessandgo on Jul 15^th, 2015, 3:38am

In order to win, one has to put the opponent in a state where all out-arcs point towards a node visited twice. Thus silver's strategy is (edited) to move to g5 until one of s4a and s4b has been visited twice (say s4a). Then, moving through g1, silver proceeds through the 'a' branch to g3a, on which gold will be unable to play.

This is very intersting because gold wins the game with the more natural "no (second) repeat position allowed" rule, but silver wins with arimaa's "no third repeat". The only remaining question is: is there an arimaa position examplifying clyring's abstract problem? If so, it will prove that the number of repetitions allowed changes the sets of positions from which gold/silver has a win. Presumaly clyring's gadget can be iterated to prove that changing "no third repeat" to "no 4th repeat" has an impact as well and so forth.

Title: Re: Repetition fights
Post by clyring on Jul 15^th, 2015, 4:40am

Close, but not quite: Silver must take the 'a' path the second time around in your example because G5 has already been visited twice. Note that gold can never run out of moves except at the G3x nodes regardless of the maximum allowed repetitons, and this was the point of my preliminary exercise.

The fact that there exist even bipartite directed graphs with this property is supremely annoying for the purpose of exactly solving potentially arbitrarily structured and lengthy repetition fights such as those that are revealed by the endgame tablebases, especially since the underlying computational problem, the game of generalized geography, is actually PSPACE-complete. I came up with this gem after struggling to prove the nonexistence of such for a couple of days on the expectation that if the conjecture was false, any counterexamples would be too complex to find and solve by hand. But my partial results narrowed the search considerably. :)

...and yes, no two repetition rules with constant but different maximum allowed repetitions produce the same winner on all bipartite directed graphs, though this is seen more simply by increasing the number of branches G3x and S4x than by trying to create some iterated abomination. :)

Title: Re: Repetition fights
Post by chessandgo on Jul 15^th, 2015, 4:55am

sorry, I messed it up, edited.

Title: Re: Repetition fights
Post by chessandgo on Jul 15^th, 2015, 5:04am

on 07/15/15 at 04:40:56, clyring wrote:

...and yes, no two repetition rules with constant but different maximum allowed repetitions produce the same winner on all bipartite directed graphs, though this is seen more simply by increasing the number of branches G3x and S4x than by trying to create some iterated abomination. :)

It seems to me that we got lucky with 2 branches, I don't see what more branches will do. With n>2 branches, Gold will be able to split his g5 moves into n/3 moves towards each s4x, and the extra single hit we got from the original traverse of the graph won't place any s4x above n-1, the way it does with n=2.

Title: Re: Repetition fights
Post by clyring on Jul 15^th, 2015, 5:26am

As soon as one of the S4x nodes has been visited more times than the G1 node, silver can win by cycling through (G1, S2, G3x, S4x) and gold has no say in the matter. Silver is winning iff the maximum allowed number of repetitions is >= the number of branches.

Title: Re: Repetition fights
Post by chessandgo on Jul 15^th, 2015, 5:37am

Oh you're right. Great!

Any idea about finding an arimaa position matching your 2-branch graph? I've toyed a bit with it this morning but can't get there.

Title: Re: Repetition fights
Post by clyring on Jul 15^th, 2015, 5:50am

I haven't come up with anything promising, but haven't done terribly much search on that front, either. Please tell me if you fare better! :)