7
$\begingroup$

I'd like to know if infinitely repeating sequences of moves (i.e. cycles) are possible in the following game:

Reneo is a game for two players (Black and White) that is played on an initially empty square board. The top and bottom edges of the board are colored black; the left and right edges are colored white.

A crosscut is a 2x2 area containing two diagonally adjacent black stones and two diagonally adjacent white stones.

Black plays first, then turns alternate. On your turn, place a stone of your color on an empty point. If this stone is part of a crosscut, swap it with an enemy stone that is also part of the crosscut. As a result, the swapped friendly stone must not be part of a crosscut any more. If the swapped enemy stone is still part of a crosscut, remove that stone.

You win if, after a full move by either player, there is a chain of orthogonally connected stones of your color touching the two opposite board edges of your color. Passing is not allowed, but, if you have no legal moves available, your turn is skipped.

Note that you will never remove more than one stone on a single turn, and you can only remove a stone by placing in the center of this pattern:

o x 
x · o
  o x

("x" are black stones, "o" are white stones and "·" is an empty point.)

$\endgroup$

2 Answers 2

5
$\begingroup$

It turns out

This is not possible

To prove this

For any game state S define the following score
SINGLES: $\alpha$ is the number of black or white stones
PAIRS: $\beta$ is the number of pairs of orthogonally adjacent stones of the same colour
CHECKERBOARDS: $\gamma$ is the number of 2x2 checkerboard containing two stones of the same colour and two empty spaces
Define $f(S) = \alpha X^2 + \beta X + \gamma$ to be a polynomial of degree 2. Polynomials are compared by letting $X \to \infty$. For instance $5X^2 > 4X^2 + 40X$ because the LHS has larger $X^2$ coefficient.

We then claim

Any legal move must increase the score of the game state. Suppose this is not true. WLOG assume we have a game state S with Black to play. To avoid incrementing $\alpha$ we must replace a White stone with a Black one, according to the following template (up to rotation or reflection)
enter image description here

Clearly, cell C must be empty. Now let us enumerate possible states for A/B:
B is white: Black just executed an illegal move
B is black: $\beta$ increases by at least 1
B is empty and A is white: $\beta$ is unchanged but $\gamma$ increases by 1
B is empty and A is not white: $\beta$ increases by at least 1
Therefore, every legal move increases the score.

Finally,

No game state can ever appear more than once, otherwise the score would not be monotonically increasing. But a finite-size board implies a finite number of possible states. QED.

$\endgroup$
10
  • $\begingroup$ "swap it with an enemy stone that is also part of a crosscut": It does not say the same crosscut, so your state change when taking a stone is not the only one possible $\endgroup$
    – Retudin
    Commented Aug 7, 2023 at 12:55
  • $\begingroup$ @Retudin, it must be the same crosscut because there cannot be a crosscut on the board before your placement. I might edit that for clarity, though. Thanks. $\endgroup$
    – Luis
    Commented Aug 7, 2023 at 13:06
  • $\begingroup$ of course .. I did not consider that $\endgroup$
    – Retudin
    Commented Aug 7, 2023 at 13:09
  • $\begingroup$ Huh, I saw some previous answer (is it deleted?) claiming it was possible. If this answer is correct, what was wrong with the previous answer? I'm curious to know, because at that time I felt it was correct. EDIT: oh, answered in the comments above. $\endgroup$
    – justhalf
    Commented Aug 9, 2023 at 3:07
  • $\begingroup$ @Luis Didn't Retudin previous answer have no existing crosscut on the board before placement, it was just that the new token creates two crosscut? (or probably I misremembered Retudin's answer. Retudin, can you post a link to the image you posted there?) $\endgroup$
    – justhalf
    Commented Aug 9, 2023 at 3:10
3
$\begingroup$

Another solution:

A move can either increase the total number of pieces or leave it unchanged. On a finite board, an infinite loop can only happen after a certain point if all the moves after that remove the opponent's pieces. Such a configuration should exist:

BWO
WXB
OBW

BWO
WWB
OBW

BWO
WBB
OWW (the O here is empty or W)

BWO
WXB
OWW

For an infinite loop to be possible, there must be multiple configurations like the first board (to be called "clamps" from now on), and with each move, there must be ways to prevent these from running out. Let's see if there's one:

BWO
WXB
OBW (the O here is empty or W)
1 2 3
4 5 6

becomes this:

BWO
WXB
OWW (the O here is empty or W)
1 2 3
4 5 6

One of the clamps is clearly lost. If the small change can gain us another clamp, this would be possible, but there's no way the W can be part of a valid clamp here, so there are no infinite loops.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.