One-dimensional noughts and crosses

The ordinary game of Noughts and Crosses, also known as Tic-tac-toe, features a 3 \times 3 board on which two players alternate placing symbols (O for the first player, and X for the second player) in unoccupied squares, attempting to form a line of three collinear squares containing their symbol. It has been known since time immemorial that, assuming perfect play, the game results in a draw. Randall Munroe provided a beautiful illustration of the optimal strategy for each player.

There have been extensions to higher dimensions. For example, a popular variant involves a 4 \times 4 \times 4 board, where the first player to obtain four collinear cubes of their symbol wins. Apparently, this one is a victory for the first player (assuming perfect play), although humans play sufficiently suboptimally that this has no impact.

After receiving a particular text message ending with an alternating string of ‘X’s and ‘O’s, I was inspired to go in the opposite direction and consider variants of Noughts and Crosses on a one-dimensional board. One particularly interesting example is a game mentioned on the Advanced Mentoring Scheme:

Two players (Alice and Bob) alternate placing either an ‘X’ or an ‘O’ on an unoccupied square of a 1 \times n board. As soon as three adjacent squares form the string ‘XOX’, the player who has just placed that symbol wins. If the board fills up without this happening, the game is declared a draw.

It’s relatively easy to show that the only losing positions are those where the unoccupied squares form the string ‘X__X’, where placing either of the symbols in one of the empty spaces enables the opponent to secure an immediate win. Since losing positions must have an even number of empty spaces, we can prove that Alice can force at least a draw for odd n, and Bob can force at least a draw for even n.

To force a win, the favoured player must therefore simply attempt to form the string ‘X__X’ and then play naturally, knowing that parity will eventually reward him or her with a victory. If the board is sufficiently large, it is easy to see that a win is guaranteed. The thresholds for forcing a win are n = 7 for Alice and n = 18 for Bob, far below the n = 2010 in the AMS question.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to One-dimensional noughts and crosses

  1. wojowu says:

    I heard about 1D noughts and crosses where we construct arithmetic progression of given length. No matter how many colors there are or how long progression needs to be, for suffiscently large grids it must be win for either side.

    • apgoucher says:

      Yes, by van der Waerden’s theorem.

      Hales-Jewett is even more relevant, since a corollary is that for fixed n and k, a k-player game on a n*n*…*n board of sufficiently high dimension (where n collinear points results in a victory) cannot result in a draw.

      I discussed some of these theorems in my unofficial Ramsey theory talk at the olympiad training camp.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s