Message Boards

GROUPS:

Staff Picks Computer Science Game Development Mathematics Recreation Algebra Discrete Mathematics Dynamic Interactivity Wolfram Language

Rauan Kaldybaev

Naughts and crosses on a tesseract, or the four-dimensional tic-tac-toe

Rauan Kaldybaev

Posted 13 days ago

339 Views

2 Replies

5 Total Likes

Follow this post

enter image description here

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

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

Out[]=

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

, and m and n are called the indexes of g . Here is a picture showing which entries of g correspond to which tiles:

Grid[Table[Subscript["g",StringJoin[ToString/@{i,j}]],{i,3},{j,3}],FrameAll,Spacings{1,1}]

In[]:=

g 11	g 12	g 13
g 21	g 22	g 23
g 31	g 32	g 33

Out[]=

If, for example, the playing grid looks like this:

example2Dgrid = Array[RandomChoice[{"·", "X", "O"}]&, {3, 3}];

In[]:=

Grid[example2Dgrid, Frame All, Spacings  {1, 1}]

In[]:=

O	·	X
X	·	·
X	·	·

Out[]=

Then this is what the entries of g are:

Column @ Flatten @ Table[Row[{Subscript["g", StringJoin[ToString /@ {i, j}]], " = ", ToString @ example2Dgrid[[i, j]]}], {i, 3}, {j, 3}]

In[]:=

= O

= ·

= X

= ·

= X

= ·

Out[]=

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

, 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

lies in-between the points

and

can be written as

where

is the x-coordinate of point 1. This can also be written in vector notation as

, where

is the

position vector

of the first point.

We can re-write these equations as

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 :

possible2Dv = Select[ Flatten[Table[{vx, vy}, {vx, {-1, 0, 1}}, {vy, {-1, 0, 1}}], 1], # ≠ {0, 0}&];

In[]:=

Here is what we get:

Column @ possible2Dv

In[]:=

{-1,-1}

{-1,0}

{-1,1}

{0,-1}

{0,1}

{1,-1}

{1,0}

{1,1}

Out[]=

Basically, if we draw all the possible vectors, we get a hedgehog:

Graphics[Arrow[{{0, 0}, #}]& /@ possible2Dv]

In[]:=

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≤

≤3

and

1≤

≤3

, or simply

1≤

≤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

≤

≤3-2

. Since s also lies inside the grid,

1≤

≤3

. Since both of these must hold, we get that

Max[1-2

,1]≤

≤Min[3-2

,3]

. Now, since the components

of s must be integers and the components

of v is either -1, 0, or 1, we can simply go through all possible

’s and compute the set of possible values of

∈{3}

=-1

∈{1,2,3}

∈{1}

Given v, we can calculate the set of possible values for each of the

. We can then iterate through all possible combinations of

, and this will give us the set of possible values of s. For instance, if

v=<-1,0>

, then

∈{3}

and

∈{1,2,3}

, then this basically means that the first component of s is 3 and the second component is either 1, 2, or 3. Then, s can be either

{3,1}

{3,2}

, or

{3,3}

. We can automatize this process using Wolfram Language.

get2DstartingPoints[v_] := Tuples[Table[Which[q  -1, {3}, q  0, {1, 2, 3}, q  1, {1}], {q, v}]];

In[]:=

get2DstartingPoints[{-1, 0}]

In[]:=

{{3,1},{3,2},{3,3}}

Out[]=

Now, you would think (at least I thought) that, to find the number of lines a particular player has scored, we simply have to iterate through all possible v’s and their corresponding sets of possible starting points, and then count the number of lines using the algorithm given above. However, if you actually did that, you would get twice the actual number of lines, because each line would be counted twice, as there are two combinations of s and v that yield the same starting point. Mathematically, if we construct a line

{s,s+v,s+2v}

, we can also construct a line

{s',s'+v',s'+2v'}

, where

v=-v'

s'=s-2v

. If we substitute the definitions of v’ and s’, we would get the line

{s+2v,s+v,s}

, which is basically the old one written in reverse.
To prevent this situation from happening, we can remove half of the v’s, such that there was no v and -v pairs. For that, let us draw a plane B, such that it passes through the origin and none of the possible vectors v lies inside this plain. You can prove that if we only leave such v’s that lie on one side of the plane, there will be no v and -v pairs. This is the solution to the problem.
We can characterize the plane B by a normal vector N. If

v·N>0

, the lector lies on one side of the plain, and if

v·N

is negative, then the vector lies on the other side. We can use this property to remove the “extra” vectors v. Now, the choice of N is arbitrary, we just have to make sure that no vector v lies in the plane, e.g. v · N ≠ 0. One of the ways in which it can be done is when

i-1

, so that none of the N’s components can be obtained by adding or subtracting the other ones. Because the components of v are either -1, 0, or 1, the dot product of v and N will have the form

+...

, so it cannot be zero.

This is how the normal vector N looks like in two dimensions:

normalVector2D = Array[2^(#-1)&, 2]

In[]:=

{1,2}

Out[]=

This is how we filter the set of possible v’s (the “hedgehog”).

vToConsider = Select[possible2Dv, Total[# * normalVector2D] > 0&]

In[]:=

{{-1,1},{0,1},{1,0},{1,1}}

Out[]=

We are left with half of the original hedgehog.

Graphics[Arrow[{{0, 0}, #}]& /@ vToConsider]

In[]:=

Out[]=

So finally, we have the algorithm for counting rows:

countRows2D[g_, playerId_] := Block[{score = 0}, Table[ Table[ If[AllTrue[g[[#[[1]], #[[2]]]]& /@ {s, s + v, s + 2 v}, #  playerId&], score++], {s, get2DstartingPoints[v]} ], {v, vToConsider}]; score];

In[]:=

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:

·	O	·
·	O	·
·	O	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	X
·	·	·

·	·	X
·		X
·	·	O

Y	·	·
Y	Y	X
Y	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

Out[]=

Here is a picture showing which entries of g correspond to which tiles:

g 1111	g 1211	g 1311
g 2111	g 2211	g 2311
g 3111	g 3211	g 3311

g 1112	g 1212	g 1312
g 2112	g 2212	g 2312
g 3112	g 3212	g 3312

g 1113	g 1213	g 1313
g 2113	g 2213	g 2313
g 3113	g 3213	g 3313

g 1121	g 1221	g 1321
g 2121	g 2221	g 2321
g 3121	g 3221	g 3321

g 1122	g 1222	g 1322
g 2122		g 2322
g 3122	g 3222	g 3322

g 1123	g 1223	g 1323
g 2123	g 2223	g 2323
g 3123	g 3223	g 3323

g 1131	g 1231	g 1331
g 2131	g 2231	g 2331
g 3131	g 3231	g 3331

g 1132	g 1232	g 1332
g 2132	g 2232	g 2332
g 3132	g 3232	g 3332

g 1133	g 1233	g 1333
g 2133	g 2233	g 2333
g 3133	g 3233	g 3333

Out[]=

Here is an example of a row:

X	·	·
·	·	·
·	·	·

·	X	·
·	·	·
·	·	·

·	·	X
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·		·
·	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

Out[]=

In this case,

1111,

1212

1313

form a line in which every tile is taken by the player 1 and marked as X.

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:

NC4newGame[NPlayers3]

In[]:=

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

NC4play[]

In[]:=

(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:

·	O	·
·	O	·
·	O	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	X
·	·	·

·	·	X
·		X
·	·	O

Y	·	·
Y	Y	X
Y	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

·	·	·
·	·	·
·	·	·

Out[]=

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

This will put your mark at that place. Now, to let your opponent(s) know where you chose to place your mark, copy the tile id from the “History” part of the panel. The section will have the following form: History: 23 → X 45 → O 9 → XThe bottom pair shows the last turn that was made. The general “formula” is tileId → icon. Anyway, you should copy the left part of the bottom pair (in this case, it would be 9).Now, send it to your opponent(s) via, for example, a Telegram chat. Upon receiving this information, your opponents should proceed to step 3.

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.

·	·	·
·	·	·
·	·	·

·	·	·
·	O	·
·	·	·

O	O	O
·	X	·
X	X	X

·	X	·
·	·	·
·	·	·

·	X	·
·		·
·	X	·

·	X	·
O	O	O
·	O	·

·	·	X
·	X	·
X	X	O

·	·	·
·	O	·
·	·	·

·	·	·
·	O	·
·	·	·

Out[]=

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)

Out[]=

6. Return to step 0 or quit playing

Export / load game

You can export the game in the form of a string:

NC4exportGame[]

In[]:=

{3, {0 -> "·", 1 -> "X", 2 -> "O", 3 -> "Y", 4 -> "Z"}, 9, "MAwGGFIaAjmZ1E9sy7ADB3uvc4zhXODRYEBgKuHvv7M3rHY2PRj"}

Out[]=

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:

NC4loadGame["{3, {0 -> \"·\", 1 -> \"X\", 2 -> \"O\", 3 -> \"Y\", 4 -> \"Z\"}, 9, \"MAwGGFIaAjmZ1E9sy7ADB3uvc4zhXODRYEBgKuHvv7M3rHY2PRj\"}"]

In[]:=

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

ClearAll[ NC4newGame, NC4play, NC4showLines, NC4showGrid, NC4exportGame, NC4exportGrid, NC4loadGame, NC4gridWrite, NC4getGridCoords, NC4getTileId, NC4getTile, NC4countLines, NC4gridWrite, NC4showCongratulations, NC4gridFullQ, NC4showPlayingPane, NC4showPlayingPaneStatic, NC4showGoSection, NC4showBackButton, NC4showScores, NC4partyParrot, NC4tie]NC4tileId = 0;NC4gameEncodingCharacters = StringJoin[Join[{"0123456789"}, Alphabet[], ToUpperCase @ Alphabet[]]];NC4gECpositionsReplacementList = Table[StringPart[NC4gameEncodingCharacters, i]  i - 1, {i, StringLength[NC4gameEncodingCharacters]}];

In[]:=

NC4partyParrot =

;

In[]:=

NC4tie =

;

In[]:=

NC4newGame[];

In[]:=

newGame

Options[NC4newGame] =  "NPlayers"  2, "PlayerIcons"   0  "·", 1  "X", 2  "O", 3  "Y", 4  "Z" , "Threshold"  9;NC4newGame[OptionsPattern[]] :=  NC4nPlayers = OptionValue["NPlayers"]; NC4playerIcons = OptionValue["PlayerIcons"]; NC4threshold = OptionValue["Threshold"]; NC4grid = Table[If[i  j  k  l  2, Null, 0], {i, 3}, {j, 3}, {k, 3}, {l, 3}]; NC4turn = 1; NC4history = {};;

In[]:=

play

NC4play[] := Dynamic[ Block[  lines = NC4countLines[#, OutputForm  List]& /@ Range[NC4nPlayers], winners, maxscore , If[NC4gridFullQ[], maxscore = Max[Length /@ lines]; winners = Select[Ordering[Leng