The anti-pattern game

Here is a small game I though of when taking a course on modal logic. It is a bit too tedious to be played by humans, but I had great fun finding a winning stategy for it – and there are still simple questions about this game I cannot answer.

The rules

The anti-pattern game is a two-player game. It is played using black and white pebbles (like Go). These pebbles are placed in sequence on a line. On their turn the player has a simple choice: to continue the sequence with a white or a black pebble.

A player looses if they put down a pebble such that the sequence contains a pattern. A pattern is a sequence of pebbles repeated three times in a row.

A player wins if the other player looses.

Example

Here is a simlpe game won by player 1:

● ● ○ ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ○ ● ● ○ ○ ● ● ○ ○ ●
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

Player two lost because after their final turn, the sequence ended with the pattern: ● ○ ○ ● repeated trice.

Player two could have chosen to play ○ instead on the final turn, but that would also be a loosing move since then ○ would have been repeated trice. So if player two could have won, it must have changed its course several moves ago.

A winning strategy – READY PLAYER 1

The obvious question about any such two-player game is weather any player has a winning strategy. Often this can be determined by a finiteness condition, but here we could at least imagine that the game could go on to generate an infinitely long sequence.

To solve this question I wrote a short Haskell program which does a brute force search to find a winning strategy. Actually, the Haskell program wasn’t that short – because I wanted to apply modal logic to formulate the winning strategy condition and had to make appropriate definitions.

As it turns out, there is a winning strategy for player 1, and they can win the game inn less than twenty-two moves. The Haskell program finds the solution represented as a finite tree, which decides the moves of player 1 given any possible move of player 2.

Generalisations

Even though the game is solved, there are more questions we could pose if we make small adjustments to the game. Some of these questions I do not yet know the answer to.

Cooperating players

This question is simple to formulate: If the palyers were cooperating, could the game go on for ever? Put more precisely:

Is there an infinite binary sequence where no contigous subsequence is of the form σσσ for some sequence σ of non-zero length?

First off, it is clear that this game can continue for a long time. Here is a game with a thousand played moves:

● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ●
○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ○ ○ ● ● ○ ● ● ○
● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ●
● ○ ● ● ○ ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○
○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ○
● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ●
○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○
● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○
● ● ○ ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ●
● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ○ ● ●
○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ●
○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○
● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ○ ● ● ○ ● ● ○
● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ●
● ○ ● ● ○ ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ●
○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ○
● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ●
○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○
● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○
● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ●
● ○ ● ○ ● ● ○ ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○
● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ●
○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○
● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ○ ● ● ○ ● ● ○ ● ○ ●
● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ●
● ○ ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ●
○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ○ ● ● ○
● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ●
○ ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○
● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ○ ● ● ○ ●
● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ●
○ ● ● ○ ● ● ○ ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ●
○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○
● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ●
● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ○ ● ● ○ ● ● ○
○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ●
● ○ ● ● ○ ○ ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ●
○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○
○ ● ● ○ ● ● ○ ● ○ ● ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ●
● ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ● ● ○ ○ ● ● ○ ● ● ○ ●

At first sight this might seem disorderly, but there is a lot of repetition here:

• The sequence of the first three pebbles ● ● ○ covers most of the game:
  • Image
• The entire first line (25 pebbles) occurs several times (even at the 25 character line offset):
  • Image

The fact that ● ● ○ is so prominent in this example, suggest a way to generate an infinite game sequence:

data Colour = Black | White
 deriving (Eq, Ord, Show)

instance Show Colour where
  show Black = "●"
  show White = "○"

generate :: [Colour] -> [Colour]
generate p = [Black,Black,White]
  ++ (case p of
       (Black : cs) -> White : generate cs
       (White : cs) -> [Black,White] ++ generate cs )

stream :: [Colour]
stream = generate stream

This makes stream an inductively defined stream of pebbles, which makes up an infinitely long game. An interesting question is then: Can player 1 force the game to go on idefinitely (assuming player 2 will not loose if avoidable)?

As an aside: This stream, while devoid of direct repetition is very compressible. It is also an example of data which responds well to being compressed several times. Here are the first 1 million moves of the stream compressed twice. The file is a mere 512 bytes, and unpacks to a 26kb file, which again unpacks to 3Mb. That’s a compression factor of almost 6000!¹

More colours

What if the game had more colours? What if there were three colours of pebbles, not just two?

More repetition allowed

The choice that three repetitions form a pattern is arbitrary. What if we allowed three repetitions, but prohibited four? Clearly the games would be longer, but would it make an essential difference to wether a player has a winning strategy?

More players

What if there are more players? This could influence the dynamics, and I do not know of a winning strategy for the three player variant. Since the game could go on for ever, it is not obvious that there is a winning strategy for any player when he controls only a third of the moves.

There is also a question of who winns in a three player game. Below is a record of one, where player 1 places the loosing pebble. But did player 2 or player 3 win?

● ○ ● ○ ● ● ○ ● ○ ● ○ ○ ● ○ ● ○ ○ ● ○ ● ○ ○
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1

Different winning conditions would give different incentives. Here are two possible winning conditions:

• Cooperative victory: If a player looses the other two win.
• Exclusive victory: If player n looses, then player n + 1 (mod 3) wins.

In the cooperative variant it is clear that any two players could cooperate to win – basically because they out-number the third. But in a neurtal setting, who could cooperate? Player 1’s first move has no effect, but player 2 could play the same colour as Player 1, in order to open up for a cooperation with player 1. Then player 3 has a forced move, and when Player 1 is ready to make his move again, the board looks as follows:

● ● ○ ?
1 2 3 1

If player 1 plays ● now, he and player 2 can force player 3 to loose:

● ● ○ ● ● ○ ● ● ○ 
1 2 3 1 2 3 1 2 3

If player 1 instead plays ○ the playing field is more open, and player 3 gets to chose his move:

● ● ○ ○ ● ?
1 2 3 1 2 3

But even though player 2 and player 3 can cooperate to force player 1’s moves in this setup, player 3 would loose the sequence:

● ● ○ ○ ● ● ○ ● ● ○ ● ●
1 2 3 1 2 3 1 2 3 1 2 3

Thus, for the cooperative variant, the question is: Can either player 1 or player 2 choose to cooperate with player 3 instead? The answer remains elusive for the time being.

In the exclusive variant the player 2 does not want to help player 1 win, so

● ● ○ ● ● ○ ● ● ○ 
1 2 3 1 2 3 1 2 3

is not acceptable to player 2. However, it now unclear if any player has a winning strategy, or if given perfect play from each player the game would go on idefinitely.