This is just a thought, but I wonder if there is a mathematical connection between this game and something like the binary representation of irrational (or maybe transcendental) numbers.
The article is also notable for its consistency in spelling "lose" as "loose".
> The file is a mere 512 bytes, and unpacks to a 26kb file, which again unpacks to 3Mb.
My brain hurts when thinking about that. How could 512 bytes be enough to store ~3 million bytes? I know that compression is basically about finding patterns and this sequences should be very compressible.
very interesting, once I realized that the longer sequences were wrapping on my mobile. At first, it appeared that the “top” line was player 1 in the “bottom” line was player 2
This reminds me of primitive words [1]: A primitive word is a word that is not the (2+ times) repetition of any other word.
This is slightly different than a non-pattern word from the article, which is a word that is not a 3+ times repetition of any other word.
The anti-pattern game is about extending words such that they do not contain a pattern word.
I wonder how the situation changes if 2 times repetitions would count as pattern (i.e. non-primitive words).
For primitive words, it is an open problem if the language of primitive words (over any non-trivial finite alphabet) is context free.
I wonder if the language of words that don't contain patterns (or non-primitive words) is context free.
This reminds me of the movie "The Oxford Murders" with Elijah Wood, where a maths professor and their student argue if any pattern can be predicted by logic. Well worth a watch.
It's not intuitively clear to me how the game can go on forever -- I would expect that, eventually, you would hit upon some valid pattern. The explanation in the text didn't really make sense to me. Could anyone help with this?
These sequences are also known as "cubefree," so you might want to continue researching along those lines.
In particular, the game discussed is trying to find cubefree words over a two-letter alphabet. The sample infinite game seems to agree with the listed sequence on OEIS for the lexicographically earliest infinite cubefree word, though your method of generation appears to be different from the one in the comments. (I haven't analyzed it in detail.)
One relatively common way to remove first player advantage is to have the first player place one stone, and then after that each person places two stones on their turn. So
After player 1s first move there is one stone in the sequence.
After player 2s first move there are three stones.
After player 1s next move there are five stones.
After player 2s next move there are seven stones.
Etc. Usually this completely removes first player advantage. It’s obvious that this removes player 1s potential advantage since black or white, his move is symmetrical without loss of generality.
Player 2 actually has the first consequential move, with three possible options — again, taking player 1s move as a given color, player 2 can play
DD
DS
SD
where S means “same” and D means “different”. Technically player 2 has four options: he could also play SS and lose immediately :-)
There is a simple intuitive explanation for how an "infinite" game is possible:
We can define two different sequences of three characters that start with 0 and end with 1: 001 and 011. Because they each start and end with a different character, we can never create a series of three characters by chaining two of these sequences.
Now we can go one step deeper and encode the "001" sequence as 0, and the "011" sequence as 1. We can generate our 001 and 011 pattern again, but with our encoded versions of 0 and 1, giving us these sequences: 001001011 and 001011011. These sequences again have the same characteristics, they start and end with different sub-sequences (001 and 011) so they can be chained without creating a series of three sub-sequences.
We can now use these larger sequences and encode these as 0 and 1, and so forth ad infinitum.
But what is the winning strategy? It would be interesting to know whether the decision tree has a compact algorithmic, since that would serve as an explanation of the strategy. Even if not, I'd be curious if there is some other simple proof of its existence. And failing that, it would be interesting to see an optimal game: a game in which player 2, though doomed, makes the game take as long as possible (presumably 21 moves).
16 comments
[ 3747 ms ] story [ 2079 ms ] thread(For the initiated, I should mention that it is related to Thue–Morse sequences.)
The article is also notable for its consistency in spelling "lose" as "loose".
My brain hurts when thinking about that. How could 512 bytes be enough to store ~3 million bytes? I know that compression is basically about finding patterns and this sequences should be very compressible.
https://gowers.wordpress.com/2013/08/23/determinacy-of-borel...
The anti-pattern game is about extending words such that they do not contain a pattern word.
I wonder how the situation changes if 2 times repetitions would count as pattern (i.e. non-primitive words).
For primitive words, it is an open problem if the language of primitive words (over any non-trivial finite alphabet) is context free.
I wonder if the language of words that don't contain patterns (or non-primitive words) is context free.
[1] https://arxiv.org/abs/1104.4427
Could you tell us more about this? I am curious how this problem was formulated using modal logic. Seems fascinating
In particular, the game discussed is trying to find cubefree words over a two-letter alphabet. The sample infinite game seems to agree with the listed sequence on OEIS for the lexicographically earliest infinite cubefree word, though your method of generation appears to be different from the one in the comments. (I haven't analyzed it in detail.)
https://oeis.org/A282317
After player 1s first move there is one stone in the sequence.
After player 2s first move there are three stones.
After player 1s next move there are five stones.
After player 2s next move there are seven stones.
Etc. Usually this completely removes first player advantage. It’s obvious that this removes player 1s potential advantage since black or white, his move is symmetrical without loss of generality.
Player 2 actually has the first consequential move, with three possible options — again, taking player 1s move as a given color, player 2 can play
DD DS SD
where S means “same” and D means “different”. Technically player 2 has four options: he could also play SS and lose immediately :-)
We can define two different sequences of three characters that start with 0 and end with 1: 001 and 011. Because they each start and end with a different character, we can never create a series of three characters by chaining two of these sequences.
Now we can go one step deeper and encode the "001" sequence as 0, and the "011" sequence as 1. We can generate our 001 and 011 pattern again, but with our encoded versions of 0 and 1, giving us these sequences: 001001011 and 001011011. These sequences again have the same characteristics, they start and end with different sub-sequences (001 and 011) so they can be chained without creating a series of three sub-sequences.
We can now use these larger sequences and encode these as 0 and 1, and so forth ad infinitum.
runnable version