Arimaa Forum - Print Page


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

        Arimaa >> General Discussion >> Some Arimaa variant puzzles
        
(Message started by: half_integer on Jan 4^th, 2018, 2:13pm)

Title: Some Arimaa variant puzzles
Post by half_integer on Jan 4^th, 2018, 2:13pm

I have been amusing myself thinking about some simple endgame tablebases and this has led to considering a few "artificial" win conditions. I am curious if others would find it interesting to analyze or play these variants.

First: rabbit vs. rabbits. One side has a single rabbit, the other has 'N' rabbits but cannot win by goaling; they must immobilize the opponent rabbit or force it to suicide. (All rabbits start in their own home row.)

What is the minimum number of rabbits needed to be able to win against optimal play? Does it matter who moves first? Is the setup critical (for either side)? I think that three is not enough; four is tricky and I think five is enough to win fairly easily.

Second: Elephant vs. cats. The goal is to immobilize or eliminate the cats. Can the cats survive indefinitely? It seems clear that one cat will always be hunted down. What about two? I think that the cats lose but that the E has to capture one of them first and then hunt the other one down; it might not be possible to immobilize both simultaneously against careful play. What is the minimum number of pieces needed to survive indefinitely against a single E? What if the E can't capture, but the traps are still there as obstacles?

Those that have built tablebases before would probably find these problem sizes manageable if they choose to modify the code to analyze them. What does the community think before complete analysis?

Title: Re: Some Arimaa variant puzzles
Post by clyring on Jan 5^th, 2018, 1:16am

I've had some good fun mulling these over. Here's what I've come up with so far:

In rabbit vs rabbits, the lone rabbit's strength comes from its flexibility. If it advances too soon, it can be stopped by as few as two enemies, but its lateral movement is much faster than that of a large group. After imagining a few lines of play to try to convince myself of your claims about n=3 and n=5, I grew hopeful for the possibility of a clean defensive strategy for n=4. But while there is a simple way to defend indefinitely on the seventh rank (modulo some repetition fights that don't currently seem trivial to me), encroaching on the attacking rabbit with the goal of immobilizing it seems hard unless it willingly advances into danger.

A fortress for the defender with n=4 has with the silver pieces, rb7 rd6 re7 rg7 (image (http://arimaa.com/arimaa/notconv/old/boardimg.php?orient=n&size=300&imgtype=png&ranks=/1r2r1r/3r/////)), when silver can at any time effectively pass with re7w rd6e, creating the mirror image of the fortress. If the gold rabbit moves to c5 or f5, it can immediately be trapped by silver rabbits one square east and west. If gold otherwise threatens to move into a7, silver can place rabbits on a7, b7, and d6. (Since the mirror image of the resulting position is reachable by silver for threats to enter h7 despite the asymmetry of the fortress itself, no generality is lost by only considering threats on a7.) The only available squares for the gold rabbit to move to next which prevent silver from simply moving back to the fortress configuration are a4, b4, c5, f5, and the squares north and/or west of c5. Moving the gold rabbit next to c5 or f5 allows the same trick as before, and the squares north and/or west of c5 fall victim to a similar idea with ra7 rb7 rd5, leaving only a4 and b4 for gold to try. However, since d7 is not within range of these squares, the d6 silver rabbit can slide to e6 and back for as long as the gold rabbit stays on a4 and b4 without breaking any of the other refutations.

With two-row setups, the lone rabbit cannot prevent the formation of this fortress from setup.* This should be very clear if the defender has the gold pieces, and if the attacker sets up with the lone rabbit in the west, silver can reach one of the fortress positions within one move from the setup rb7 rc7 re7 rg7. It follows that a forced win from setup by one attacking rabbit against four defending rabbits must involve repetition.

*With the one-row setups I later realized you specified, this isn't so clear, and I haven't yet investigated.

As mentioned earlier, I'm also not optimistic about a non-repetition win for the defending four rabbits. Advancing any of the defending rabbits past the third rank seems to make defending at all against a non-advanced attacking rabbit very hard, and defending in a way that allows the free steps necessary for progress without repetition seems very hard. I think I can prove that the position Rd2 rb7 rd7 re7 rg5 (plan window (http://arimaa.com/arimaa/games/planGame.cgi?movelist=1w%20Rd2%0A1b%20rb7%20rd7%20re7%20rg5)) has a forced win for gold by leveraging Hippo's theorem on the position after 2g Rd2nnww ~~2s rb7www re7e~~ 2s rb7w rd7ww re7e 3g Rb4eeee 3s rb7eee ra7s, but I fear it will be the ugliest thing I ever do.

For the elephant vs cats problem I have stronger intuitions but have put in less thought. Unlike with the rabbit vs rabbits problem, I think the proper thing to do is to treat any repetition of positions as a cats win, since there is clearly no way for the cats to force immobilization without an entirely unreasonable number of units.

The elephant can easily hunt down and capture two cats by taking one hostage. The other can try to defend, but it's pretty hopeless. The elephant needs neither zugzwang nor a second trap to finish the job. However, capture is necessary for the elephant to win: The cats simply stay far apart, and the elephant while dragging one cat is too slow to catch up to the other.

My intuition suggests that three pieces should also be a fairly easy win for the elephant since with a hostage it should be possible to switch gears and force capture of one of the defending pieces in another trap. With four well-positioned small pieces on the board this might be tricky, but I think it is still probably an elephant win. Five is unclear, and while I expect six to be enough, this confidence is far from unshakeable. But fortunately, due to the large number of symmetries, an elephant versus six cats tablebase should be quite tractable.

Title: Re: Some Arimaa variant puzzles
Post by half_integer on Jan 5^th, 2018, 6:49pm

Without actually proving anything, my analysis of the rabbits game is consistent with yours, including the possibility of a repetition fight. The single rabbit needs to stay off the trap rows, while advancing past the traps is also problematic for the defending side.

However, I was unable to decipher your moves below as they seem to go off the board, so maybe there are some typos:
2g Rd2nnww 2s rb7www re7e 3g Rb4eeee 3s rb7eee ra7s

I don't understand when you say that the E vs. cc doesn't need to use two traps. I'm thinking the easiest strategy is something like an Eg3:Ch3 hostage - the second cat must be at e3 to avoid instant capture, and the E can then go freeze it and push it into c3 next turn.

Three cats seems similar, in that a second defending cat at f2 or f4 can be 3-step frozen to g2/g4. Maybe it works better to position at b3 but I'm guessing then the f6 trap can be used instead.

(I agree that "survive indefinitely" is not a good criteria for actually playing this game, but is natural for an analysis problem.)

From a programming standpoint these are interesting to consider how to take advantage of the symmetries. For the rabbits, the "goal" is any row even with the last defending rabbit (except rows 2 and 5 directly in front of a trap for Gold) since win follows easily from there. So positions with the same span between Silver and Gold and the same relative positioning of the trap squares are equivalent, e.g. a rows 2-4 position and the same rows 5-7 position.

The E vs. c's game can take advantage of four-fold board symmetry instead of just two-fold, since there is no "goaling direction". In fact, that can be extended to eight-fold symmetry along the diagonal of one quadrant - thus, the E has only 9 unique squares to occupy after discounting the trap square.

Title: Re: Some Arimaa variant puzzles
Post by clyring on Jan 6^th, 2018, 10:44am

I've corrected the ill-transcribed movelist. Insufficient proofreading for the odd hours of the morning, I suppose. Regarding E vs cc at one trap, here (http://arimaa.com/arimaa/games/planGame.cgi?movelist=1w%20Eg3%0A1b%20cb3%20ce3%20ch3%20cf7%0A2w%20Eg3n%20Eg4w%20Ef4w%0A2b%20ch3w%20cf7e%0A3w%20Ee4e%20ce3n%20Ef4e%20ce4e%0A3b%20cg7w%20cb3s%20cb2e%0A4w%20Eg4n%20cg3n%20Eg5w%20cg4n%0A4b%20cc2e%20cd2e%20ce2e%0A5w%20cf4w%20Ef5s%20ce4s%20Ef4w%0A5b%20cf2w%20ce3w%20cd3s%20cd2s%0A6w%20Ee4s%20Ee3n%20ce2n%0A6b%20cd1w%20cc1n%20cg5s%20cg4s%0A7w%20ce3s%20Ee4s%20Ee3w%20Ed3s) is a demonstration of the technique and how four cats can quickly become overwhelmed when it is applied. I'm now leaning toward the minimum number of cats for long-term survival against a roving elephant being 5 or 6.

Regarding the symmetries of the E vs c's problem, in addition to the eightfold dihedral symmetry of the board, there is also a symmetry under permutation of the cats which reduces the state space of the six cats problem by a factor of 720 compared to a seven-piece scenario with greater diversity of pieces.

The fourth rank-seventh rank equivalence you mention for rabbit versus rabbits is interesting, but seems to apply only in the small minority of positions where there are no pieces past the fourth rank. (And due to the absence of a trap on the nonexistent ninth rank, the equivalence does not extend to the fifth and eighth ranks.) It is almost possible to ignore any defending rabbit that the attacking rabbit has already passed as being captured- only almost, though, as the passed defender can still be used by the defender to waste a turn or influence a repetition fight. Still, the former is fairly easily modeled and managed and repetition fights where one side gets free steps are already often pretty hard to resolve, whether or not all non-repetition wins are known.