The Anti-Pattern Game

Summary

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 ...