Logic and Geometry Problem #5: does Savage Go have cycles?

Question

My question is whether or not a cycle can occur in the game of Savage Go. That is, you kill some of mine, I kill some of yours, you kill some of mine... Endless cycle of turns. Game never finishes.

No level of player skill is assumed. In fact, assume the players are cooperating in trying to create a cycle.

If you can't find a cycle, a proof that cycles can't occur would be most helpful. Otherwise, please just describe your experience with this. It's helpful to know if people made a serious effort but couldn't find a cycle.

To summarize, I need proof that cycles can occur or proof that cycles can't occur.

Savage Go

Answer 1

I don't have a rigorous proof, but here's my take on it:

1. Every turn, the board ends up with one more stone on it unless a player is unable to play every stone.

2. If each player can play all of their stones every turn, the board will eventually be full. If that happens, then the player who plays last will win, because playing a stone that completely fills the board will necessarily surround all the opponent's groups, removing them from the board.

3. The only way to prevent (2) is to repeatedly have a scenario where a player cannot play all of their stones on their turn.

4. The only things that can prevent a player from having to play all their stones on a turn are:

   • There are no empty spaces available on the board => this results in a win for the current player, per (2), and an end to the game.
   • The only spaces available to play would result in a stone being self-bounded without allowing for removal of any of the stones bounding it.

5. From (3) and (4), the only way to possibly have a cycle is for each player to be continually prevented from playing all their pieces because of a self-bounding situation.

6. If there is a configuration of stones that prevents Black from playing a piece because it will be self-bounded, then that space is a valid move for White (since it is surrounded by white pieces or the board edges). Thus White will eventually need to play a stone there (since the number of pieces on the board will always increase, barring illegal moves), at which point it will no longer be an issue for Black.

7. From (5), (6), and (3), since no board space can be an illegal move (self-bounded) for both Black and White, and thus will eventually be filled, the board will eventually be completely filled, always resulting in a win for one player or the other.

This seems intuitive to me, but it's possible I missed something. If so, I'm sure someone will point it out.

Answer 2

A cycle on a degenerate case is possible:

On 1x2 board.

White is X, Black is O.
1. ..
2. X.
3. XO -> .O Black captures 1 White.
4. XO -> X. White needs to place 2, but can only place 1. Captures 1 Black.
5. XO -> .O Black needs to place 2, but can only place 1. Captures 1 White.
6. Back to step 4.

Similar idea can probably be done on larger boards, but need to show the build up until the cycle steady state.