Four-dimensional naughts and crosses: what is it and how to play it
This is already the twentieth draw in a row - Marat said tiredly. That was true, every game we played went by the same scenario, as if everything was planned in advance. I paused for a second. Well, I said...
Out[]=
X
X
O
X
O
O
X
X
·
·
·
·
·
O
·
·
·
·
·
O
X
O
X
X
X
X
O
O
O
X
O
X
O
·
X
O
O
·
X
O
O
X
X
O
X
·
·
X
·
O
O
O
·
·
·
·
X
·
O
·
X
·
·
·
·
·
X
·
·
·
·
·
·
O
X
O
O
O
X
X

Introduction

What is the difference between 2D and 4D?

The game is practically the same in four dimensions: the players still need to construct rows of three tiles to win. The main difference is that the game happens not on a two-dimensional square but on a four-dimensional generalization of cube called tesseract. It isn’t that scary as it sounds, though - rows are still counted in much the same way. Because the 4D game gives more opportunities for constructing tiles, in order to win one must construct not just one row but nine - that’s the second difference. Lastly, since the central tile gives the player who takes it too much of a lead, I decided to disable it to make the game more balanced.

Why is 4D better?

◼
  • It is cooler - I mean, when was the last time you played in four dimensions?
    • ◼
  • It is harder to find the optimal strategy. While in 2D naughts and crosses it doesn’t take long to figure out the undefeatable tactic, in the four-dimensional case there are too many possible scenarios to do this.
    • ◼
  • It requires more thinking. While in the 2D tic-tac-toe there are 8 possible rows, in 4D there are 232. What this means is that the players need to think several turns in advance to choose the tile that’s going to let them construct more rows.
    • ◼
  • It gives an intuition for four-dimensional space.
    • ◼
  • Because there is more space in the game, the 4D version can accommodate more players.
    • ◼
  • The chance of draw is smaller in the four-dimensional version.

    • How do you construct the rules?

    It might not be immediately clear how we can extend the aughts and crosses game if no human (excluding mental asylum patients) has ever experienced 4D space and thus can’t tell us what it is like. However, it turns out that this is not a problem, as we have math at our disposal. If we first develop a mathematical formalism for the 2D tic-tac-toe, it is very easy to generalize to any higher number of dimensions.

    Formalizing the “normal” 2-dimensional naughts and crosses

    Playing grid

    We can view the playing grid as an array, which is basically a table that stores the information about each tile; let’s call it g. We denote the value of the n’th tile in the m’th row as
    g
    mn
    , and m and n are called the indexes of g . Here is a picture showing which entries of g correspond to which tiles:
    In[]:=
    Grid[Table[Subscript["g",StringJoin[ToString/@{i,j}]],{i,3},{j,3}],FrameAll,Spacings{1,1}]
    Out[]=
    g
    11
    g
    12
    g
    13
    g
    21
    g
    22
    g
    23
    g
    31
    g
    32
    g
    33
    If, for example, the playing grid looks like this:
    In[]:=
    example2Dgrid = Array[RandomChoice[{"·", "X", "O"}]&, {3, 3}];
    In[]:=
    Grid[example2Dgrid, Frame All, Spacings  {1, 1}]
    Out[]=
    O
    ·
    X
    X
    ·
    ·
    X
    ·
    ·
    Then this is what the entries of g are:
    In[]:=
    Column @ Flatten @ Table[Row[{Subscript["g", StringJoin[ToString /@ {i, j}]], " = ", ToString @ example2Dgrid[[i, j]]}], {i, 3}, {j, 3}]
    Out[]=
    g
    11
    = O
    g
    12
    = ·
    g
    13
    = X
    g
    21
    = X
    g
    22
    = ·
    g
    23
    = ·
    g
    31
    = X
    g
    32
    = ·
    g
    33
    = ·

    Representing grid entries with numbers

    This idea is rather straightforward. Instead of using “·” to represent empty spaces, we can store the number 0 in the playing grid. Also, instead of representing player 1’s marks as “X”, we can use the number 1. When displaying the grid, we can substitute the proper icons for the numbers, so that the user sees the familiar picture.
    This would allow us to change the users’ icons during the game, and this would also let two users playing on different computers with different icon settings to compare their playing grids.

    The notion of a line

    The key feature of the tic-tac-toe game is that a player needs to place three marks in a line to win. For instance, if
    g
    12
    =
    g
    22
    =
    g
    32
    =1
    , then these three entries form a line. Let’s try to formalize this notion.
    If three marks are placed in a line, there is such mark that lies exactly in-between the other two. We can formalize this statement with the help of vectors. We can view the indexes of g not only as indexes but also as coordinates on a two-dimensional plane if we imagine an actual physical tic-tac-toe playing grid. Then, the statement that a point
    P
    2
    lies in-between the points
    P
    1
    and
    P
    3
    can be written as
    P
    2x
    =
    P
    1x
    +
    P
    3x
    2
    ​​
    P
    2y
    =
    P
    1y
    +
    P
    3y
    2
    where
    P
    1x
    is the x-coordinate of point 1. This can also be written in vector notation as
    P
    2
    =
    P
    1
    +
    P
    3
    2
    , where
    P
    1
    is the position vector of the first point.
    We can re-write these equations as
    P
    3
    -
    P
    2
    =
    P
    2
    -
    P
    1
    =v
    Where v is some vector. There are some limitations for v. First of all, it cannot be zero, because that would mean that the three tiles are actually one same tile, which does not make a lot of sense. Second, since the tiles must be adjacent to each other, the components of v must be either 0, -1, or 1. Think of this like this: if you are standing on a tile and you jump to a neighboring one, then you are only going to move by either -1, 0, or 1 length units along each direction of space.

    Counting rows

    This is not essential for playing but just quite curious. If you just want to play, you can safely skip this part.
    Let’s try to find an algorithm for counting rows. To do that, we just have to iterate over all possible lines and count those that match the criterion.
    We can characterize a line by giving its starting point (e.g. the tile that is on one of the line’s ends) and the vector v. The other two points can be found by simply moving by the displacement v from the starting point.
    We can first find all possible vectors v for the two - dimensional grid by enumeration and selection :
    In[]:=
    possible2Dv = Select[​​ Flatten[Table[{vx, vy}, {vx, {-1, 0, 1}}, {vy, {-1, 0, 1}}], 1],​​ # ≠ {0, 0}&​​];
    Here is what we get:
    In[]:=
    Column @ possible2Dv
    Out[]=
    {-1,-1}
    {-1,0}
    {-1,1}
    {0,-1}
    {0,1}
    {1,-1}
    {1,0}
    {1,1}
    Basically, if we draw all the possible vectors, we get a hedgehog:
    In[]:=
    Graphics[Arrow[{{0, 0}, #}]& /@ possible2Dv]
    Out[]=
    Knowing v, we can compute the set of possible starting points for it. The only criterion that we have to satisfy is that all tiles of the line must lie inside the grid.Mathematically, this can be written as
    1≤
    s
    x
    +2
    v
    x
    ≤3
    and
    1≤
    s
    y
    +2
    v
    y
    ≤3
    , or simply
    1≤
    s
    i
    +2
    v
    i
    ≤3
    , where s is the radius vector of the starting point and i goes through all coordinates (in this case: x and y). From here, we get an inequality that we can use to find possible s:
    1-2
    v
    i
    ≤
    s
    i
    ≤3-2
    v
    i
    . Since s also lies inside the grid,
    1≤
    s
    i
    ≤3
    . Since both of these must hold, we get that
    Max[1-2
    v
    i
    ,1]≤
    s
    i
    ≤Min[3-2
    v
    i
    ,3]
    . Now, since the components
    s
    i
    of s must be integers and the components
    v
    i
    of v is either -1, 0, or 1, we can simply go through all possible
    v
    i
    ’s and compute the set of possible values of
    s
    i
    :
    s
    i
    ∈{3}
    v
    i
    =-1​​
    s
    i
    ∈{1,2,3}
    v
    i
    =0​​
    s
    i
    ∈{1}
    v
    i
    =1
    This is how the normal vector N looks like in two dimensions:
    This is how we filter the set of possible v’s (the “hedgehog”).
    We are left with half of the original hedgehog.
    So finally, we have the algorithm for counting rows:

    Generalizing to four dimensions

    In four dimensions, everything is basically the same as in the two-dimensional case. As before, we can represent the playing grid as an array, except that now it has not two but four indexes. It can be drawn as a 33 grid of 33 grids, like this:
    Here is a picture showing which entries of g correspond to which tiles:
    Here is an example of a row:
    In the four-dimensional case, it’s far easier to make a line, so I decided to set the winning threshold to 9. In other words, one needs to score nine lines in order to win.

    How to play

    Below is how you play the game using the WL functions presented in this essay. You can still play the game even if you don’t have access to Wolfram Language, though, if you understand how the game works - you just need a piece of paper and a pen. There is nothing you can’t do that the computer can (at least in this case). The algorithm for counting rows is described here.

    0. Start a new game

    Here is how you create a new game:
    There are the options for this function:
    ◼
  • "NPlayers" is the number of players in the game. By default, it’s set to 2.
    • ◼
  • “PlayerIcons” is the list of the characters that represent players on the grid. by default it’s set to {0 → “·“, 1 → “X”, 2 → “O”, 3 → “Y”, 4 → “Z”}. What it means that blank spaces (0) will be represented as “·“, player 1 will be represented by “X”, player 2 - by “O”, and so on. There must be at least as many icons as there are players.
    • ◼
  • “Threshold” is the score that a player needs to get to win. By default it’s set to 9.

    • 1. Launch the game

    (You have to run this line on your computer, as Cloud does not display the results properly) Players’ lines are shown in blue. The “Turn” part of the panel indicates whose turn it is, and “Scores” shows what scores the players have. “History” shows the three latest changes that happened in the game in the form tileId → player, player is the player who was the last to act, and tileId is the id of the tile that they chose. The “Back” button cancels the latest change that happened; use it when you accidentally pressed at a wrong place in the grid.
    Here is what the playing grid may look like:

    2. Tap at some place on the grid

    If you and your opponent(s) are in the same room

    This will put your mark at that place. Press “Back” if you accidentally pressed a wrong tile.

    If you are playing online

    Bonus: see where the scores came from

    It can often be quite difficult to see where the players’ scores came from. In this case, you can use the NC4showLines function, that gives an animation that illustrates it. Below, you can see the result of NC4howLines[1], which shows player 1’s lines.
    Similarly, of you want to see a similar visual for the second player (O), use NC4showLines[2].

    3. Enter the opponent’s turn

    If you and your opponents are in the same room

    Simply get your opponents to the computer and get them to repeat point 2.

    If you are playing online

    At this step, your opponent should have sent you the id of the tile that they chose to place their mark at.
    ​
    Enter the tile id that you received into the text input field on top of the panel. Then place the “Go” button; if everything went correctly, one of the tiles in the playing grid will be marked, and the turn will go to the next person. If the number you entered was invalid for some reason, nothing will happen.

    4. If any of the players won, proceed to step 5. Otherwise, return to step 3

    Basically, keep playing until someone wins.

    5. Rejoice your victory (maybe)

    6. Return to step 0 or quit playing

    Export / load game

    You can export the game in the form of a string:
    The string contains all information about the game: the number of players, the game’s history (e.g. the record of what turns were made by each player), the winning threshold, and even the players’ icons are included.
    You can store this string in a .txt (or your favorite file format) file and later upload them using NC4loadGame:
    You can also use this function to compare two games. If you and your friend are playing remotely and you want to make sure that you are playing the same game, you can compare the last part of the strings (the “rubbish” part). This is where the game’s history is stored; the computer also uses this data to determine what the playing grid looks like.

    Code

    Setup

    newGame

    play

    showGoSection

    showBackButton

    showScores

    showPlayingPaneStatic

    This function was only used to get the Cloud to display the playing pane properly; it’s not utilized in the primary code.

    showLines

    countLines

    showGrid

    exportGame

    exportGrid

    loadGame

    loadHistory

    Auxiliary functions

    gridWrite

    getGridCoords

    getTileId

    getTile