Author |
Topic: Repetition fights (Read 1881 times) |
|
clyring
Forum Guru
Arimaa player #6218
Gender: 
Posts: 362
|
 |
Repetition fights
« on: Jul 1st, 2015, 7:50am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
harvestsnow
Forum Guru
Gender: 
Posts: 88
|
|
Re: Repetition fights
« Reply #1 on: Jul 1st, 2015, 4:33pm » |
Quote Modify
|
I had to brute-force it. If my code 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...
|
| « Last Edit: Jul 1st, 2015, 7:18pm by harvestsnow » |
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Repetition fights
« Reply #2 on: Jul 11th, 2015, 5:35am » |
Quote Modify
|
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? 
|
|
IP Logged |
|
|
|
clyring
Forum Guru
Arimaa player #6218
Gender:
Posts: 362
|
|
Re: Repetition fights
« Reply #3 on: Jul 11th, 2015, 7:24am » |
Quote Modify
|
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?
|
|
IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Repetition fights
« Reply #4 on: Jul 11th, 2015, 8:52am » |
Quote Modify
|
oh, I see it.
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Repetition fights
« Reply #5 on: Jul 15th, 2015, 3:38am » |
Quote Modify
|
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.
|
| « Last Edit: Jul 15th, 2015, 4:45am by chessandgo » |
IP Logged |
|
|
|
clyring
Forum Guru
Arimaa player #6218
Gender:
Posts: 362
|
|
Re: Repetition fights
« Reply #6 on: Jul 15th, 2015, 4:40am » |
Quote Modify
|
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.
|
|
IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Repetition fights
« Reply #7 on: Jul 15th, 2015, 4:55am » |
Quote Modify
|
sorry, I messed it up, edited.
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Repetition fights
« Reply #8 on: Jul 15th, 2015, 5:04am » |
Quote Modify
|
on Jul 15th, 2015, 4:40am, 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.
|
| « Last Edit: Jul 15th, 2015, 5:04am by chessandgo » |
IP Logged |
|
|
|
clyring
Forum Guru
Arimaa player #6218
Gender:
Posts: 362
|
|
Re: Repetition fights
« Reply #9 on: Jul 15th, 2015, 5:26am » |
Quote Modify
|
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.
|
|
IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Repetition fights
« Reply #10 on: Jul 15th, 2015, 5:37am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
clyring
Forum Guru
Arimaa player #6218
Gender:
Posts: 362
|
|
Re: Repetition fights
« Reply #11 on: Jul 15th, 2015, 5:50am » |
Quote Modify
|
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!
|
|
IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print