Cubefree! Oh, that’s a good keyword to find more results about this.

From your link it seems it is a conjecture that this is the lexicographically earliest one. Very interesting!

That's a neat thought!

One could interpret the outcome of the game as a number by ○ being the digit 0 and ● being 1. For fun we could also say that if there is a repeating subsequence at the end (someone lost), then that is repeated infinitely. I suggest this because any won game has a sub-string repeated three times at the end, so we might as well repeat it to infinity!

Say the example game, ● ● ○ ○ ● ● ○ ○ ● ● ○ ● ● ○ ● ○ ○ ● ● ○ ○ ● ● ○ ○ ●, would be 0.11001100110110100110011001, or perhaps 0.11001100110110(1001) where the parenthesis express infinite repetition. If we choose the first, it is 768160/959951 and the second would be 65553/81920.

In any case, a won game would be a rational number, while a game which goes on forever would be an irrational! One could then wonder which irrational numbers are represented by such games.

Great explanation!

I guess it also hints at why the sequences keep getting smaller when you compress it several times (as mentioned in a footnote). Each compression peels away layers in this expansion. That’s my intuition at least.

Cool! I haven’t thought about varying the number of stones one could put. It’s definitely a variation to look into!

Would your intuition be that this makes it so that neither player has a winning strategy? That perfect play would yield an infinite sequence?

The game could use a better definition of what constitutes a pattern.

>> A pattern is a sequence of pebbles repeated three times in a row.

By that logic, player 2 would have lost at their fifth turn. ... And 'in a row' is open to interpretation since it is additional information to 'repeated three times'.

If it was a file filled entirely with one character, the compression could simply be to write a file saying "this character copied 3 million times", which is less than 512 bytes.

This is not exactly what happens here, but many compression algorithms work by recognising that certain substrings are very common, and give them a "shorter code". In this game, there are some quite long such strings, giving a good compression rate. Furthermore, because of the recursive nature, it can find such patterns again after the common substrings are replaced by shorter codes, because these codes again form patterns with repeated substrings. This goes on until there is almost just a bit of meta data and an "ur-pattern".

Compression is fascinating in many ways. For instance, since there are a fixed number of files of a certain size and some bigger files are made smaller, some smaller files must be made bigger by the compression! Of course, this could be as simple as attaching a header or flag which says "I could not compress this. Here is the old file verbatim." But that is still a bit longer than the original!

In some sense, the program itself is a ~512 byte compression of an infinite stream of bytes.

You can think about the compressed size of some file as approximating the amount of information (in the Shannon sense[1]) there is in the file. A perfect compression would reduce the file to exactly the size of the amount of information it contains.

[1] https://arxiv.org/pdf/1612.09316

> I wonder how the situation changes if 2 times repetitions would count as pattern

I might be misunderstanding, but do you mean that you cannot even have two of the same colour in a row? This is a very simple win for first player:

W B W ?

  0 1 0 2 0 1 2 0 1 0 2 0 2 1

Yes, sorry for just teasing its existence. I shall see if I can find a good way to present it when I have some time!

Ah, I hadn't tested this on mobile. I could try find some way of preventing the line break.

Neat!

The AI game seems to go on forever. It hasn’t found the winning strategy. Which is fine. The infinite sequences seem to be getting the most juice in the discussion here.

Yes, but the connection is not clear from what I wrote. I keep intending to make a little post about the connection, but I want it to highlight some Haskell code I wrote, but I haven't polished it yet. I want to make an update to it, using my applicative logic library[0][1].

The short version: By representing the game coalgebraically, one can use modal logic to solve it (find a winning strategy for player 1) by brute force.

The old code looks like:

    -- Modal operators
    e = modal any' (Coalg possible)
    a = modal all' (Coalg possible)

    -- Test for winning strategy within a limited number of moves.
    winning :: Integer -> Player -> State -> Bool
    winning 0 _ _ = False
    winning n p s = wonAlready || e (a (winning (n-1) p)) s where
           wonAlready = (winner s == Just p)

We can translate this into more standard modal logic: Letting ◇ be "There is a move a player could make", and □ be any move a player makes. We define the existence of a winnning strategy for player 1 inductively:

    S(0) = ⊥
    S(n+1) = W(p₁) ∨ ◇ □ S(n)

Intuitively, you have a winning strategy if you won already, or if there is a move you make, such that whatever move the opponent makes you, you still have a winning strategy.

[0]: https://hakon.gylterud.net/programming/applicative-logic.htm...

[1]: https://github.com/typeterrorist/applicative-logic/blob/moda... – this is a branch with the modal logic operators defined.

     -- Game data
     data Player = P1 | P2
            deriving (Eq, Show)

     data Color = Red | Blue
            deriving (Eq, Show)

     data State = S [Color]
            deriving (Eq, Show)

     data Strategy = Won
                   | Force Color Strategy
                   | Choice (Color -> Strategy)



    -- Modal operators
    e' = modal sany' (Coalg possible')
    a' = modal sall' (Coalg possible')

     -- Test for winning strategy within a limited number of moves.
     winning' :: Integer -> Player -> State -> Maybe Strategy
     winning' 0 _ _ = Nothing
     winning' n p s = wonAlready <|> (e' (a' (winning' (n-1) p)) s) where
            wonAlready = if (winner s == Just p) then Just Won else Nothing