When I lecture on the mathematical theory behind board games, Quarto is one of my favourite examples. It’s a commercially available board game for two players: you can see an example board to the right.
Each game piece has four attributes taking one of two values. Each piece is: tall or short; black or white; round or square; and flat-topped or dimpled.
A Quarto board has sixteen spaces arranged in a $ 4 \times 4 $ grid. Players take turns placing pieces on the board and the aim is to be the player who places the fourth in a row, column or diagonal which all match in any one attribute (eg four square pieces or four dimpled pieces).
But there’s a twist! Players don’t choose which piece to play. Instead, they are handed a piece by their opponent. So in fact the aim is to get your opponent to hand you a piece you can use to win.
This is helped by the fact that there are a limited number of pieces. In fact, each combination of attributes is used once. Since there are two possibilities for each attribute and four attributes, that means there are $2^4=16$ pieces.
Having 16 pieces is handy, because a $ 4 \times 4 $ board has $4^2=16$ spaces, meaning that the pieces all fit on the board. I think it wouldn’t be as satisfying for a game that ended in a draw to be left with empty spaces on the board.
Once I was chatting with a student about the similarities between Quarto and noughts and crosses. As he was working on a project about $ 3 \times 3 $ noughts and crosses, it seemed natural to try to modify Quarto to make a $ 3 \times 3 $ version.
To downsize the 16 game pieces, we can ignore one of the attributes—perhaps ‘dimpled or flat-topped’. The three remaining attributes generate $2^3=8$ pieces.
We have a problem! Our $3 \times 3 $ board has $3^2 = 9$ positions, meaning that there is a gap on the board when the game ends in a draw.
Bigger boards
What size boards are possible, if we say that there must be the same number of spaces on the board as there are pieces, and all our pieces are different?
Rather than think about the number of pieces directly, it’s helpful to think about the number of different attributes.
In general, if we have $m$ attributes then we have $2^m$ pieces.
We want this to be the same as the number of spaces on an $n \times n$ board, for some values of $m$ and $n$. For a game we can actually play, we need $m$ and $n$ to be integers.
That is, we require
\[ 2^m=n^2. \]
We can rearrange this to give
\[ m = 2\log_2(n)\text{.}\]
Since the right hand side is multiplied by 2, this tells us that $m$ must be even. To make $m$ an integer, we need $\log_2(n)$ to be an integer, which will only happen if $n$ is a power of 2.
The regular game uses four attributes on a $ 4 \times 4 $ board. Using six attributes would generate 64 pieces and this means using an $ 8 \times 8 $ board. We know this will work as
\[ 2^6 = 8^2 = 64.\]
Of course, we don’t have to stop there. To give another example, fourteen attributes would use a $ 128 \times 128 $ board since
\[ 2^{14} = 128^2 = \text{16,384}\text{.}\]
Keeping track of the pieces
With six attributes, we might imagine adding stripes to half the pieces, and perhaps putting bumps on the side of half. But you might reasonably be wondering how on earth you’d keep track of the 16,384 pieces with fourteen different attributes (weight? smell? attractiveness to cats?).
Rather than try to dream up ever more elaborate ways to distinguish the pieces, a simple system is simply to label each attribute either 0 or 1.
For the standard Quarto set, I choose arbitrarily to label the attributes as follows:
- white (0), black (1);
- short (0), tall (1);
- round (0), square (1);
- dimpled (0), flat (1).
I can then label the pieces using numbers in this order:
- colour,
- height,
- shape,
- dimpledness.
This means each piece in the standard set can be represented by a four-digit binary number.
For example, $0100$ would be white, tall, round and dimpled, while $1001$ would be black, short, round and flat-topped.
Now instead of worrying about whether two pieces are the same height, colour or temperature, I can just say the winning condition is met if all pieces in a line share one digit in common. For example, $0100$ and $1001$ are both round, and so both have a third digit $0$.
The standard Quarto pieces are labelled with their binary digits here:
Non-binary thinking
So far we have changed the size of the board, but there is more we can generalise if we wish. Can you imagine three different heights? Three different colours? A ternary number taking values 0, 1 or 2? Then we can design games where attributes take three values.
Since there are now three options for each of our $m$ attributes, we require that
\[ 3^m = n^2\text{,} \]
that is,
\[ m = 2 \log_3(n)\text{.}\]
We still need $m$ to be even, but now we are looking for $n$ to be a power of three.
Good news! We can now design a $ 3 \times 3 $ game of Quarto! This would use $m=2$ attributes and generate nine pieces since $3^m=n^2=9$.
The next viable board would be $ 9 \times 9 $, using four attributes and $ 3^4 = 9^2 = 81 $ pieces.
In general, if each attribute could take $k$ values (each piece is one of $k$ different heights, plays one of $k$ different jingles, etc), then we would be looking for
\[ k^m = n^2,\]
or
\[ m = 2 \log_k(n).\]
That is, we want even $m$ and for $n$ to be a power of $k$.
Higher dimensions
You may have noticed there’s still a pesky number in our equation: the 2, reflecting the fact we are on a two-dimensional game board.
It’s certainly possible to imagine playing on a three-dimensional board. You might have seen a 3D noughts and crosses puzzle, or be imagining Star Trek’s 3D chess.
It’s probably best to think about a $4 \times 4 \times 4 $ Quarto cube as four Quarto boards stacked on top of each other. Before you get your hammer and nails out, you could of course just draw four boards next to each other on a piece of paper. It’s important to remember which board is on top of which other board, though—because diagonal lines moving up the board in the third dimension can get a bit complicated.
A $ 4 \times 4 \times 4 $ cube could be used with 64 pieces having six binary attributes, since
\[ 2^6 = 4^3 = 64.\]
As a human, you might be surprised to learn we don’t have to stop in three dimensions either. Mathematically, it’s perfectly possible to design games in any of $d$ dimensions. Then we would need
\[ k^m = n^d,\]
or
\[ m = d \log_k(n).\]
So we can generate games provided $m$ is divisible by $d$ and $n$ is a power of $k$.
For example, four binary attributes on a $ 2 \times 2 \times 2 \times 2 $ 4-cube (or hypercube) would use $ 2^4 = 2^4 = 16 $ pieces, which is handy because those are the same pieces as standard Quarto.
How do you play on a four-dimensional cube? Start with a $2 \times 2 $ grid, like below. Now draw a second grid next to it and remember this is above the first in 3D space. At this point, we have two small boards that are really layers of a cube:
So far it’s not too scary, right? Now draw a second ‘cube’ next to your first (as below). OK, now—squinting a little—just imagine that your new cube is next to the first one in the fourth dimension!
Actually, it doesn’t matter if, like me, you can’t visualise this 4D cube! Just like with the 3D cube above we remembered that one square was on top of the other, so we remember the relationships between the squares here. To make it easy, I’ve labelled the top and bottom of the layers in the third dimension using top and bottom and the top and bottom of the layers in the fourth dimension using Top and Bottom.
So the space labelled A in the last diagram is the bottom layer of a 3D cube, and the space labelled B is above it in the third dimension. But also that cube is the bottom layer of a four-dimensional hypercube, and the space labelled C is above A if we move in the fourth dimension. Keeping track of the relationships between the layers avoids the need to think too hard about the fourth dimension, and if you do this you may notice that there are loads of ways to make two-in-a-row.
Game design
Putting all this together, we can come up with a game where pieces have $m$ different attributes, which can each take $k$ different values, on a board in $d$ dimensions, and each side of the board is $ n$ spaces long.
A combination of $m, k, d, $ and $n$ will work if $n = k^p$ for some positive integer $ p$, and if $ m = dp$. For example, choosing $p=7$ when $k=2$ and $d=2$, we get $m=14$ and $n=128$: our Quarto set with 16,384 pieces we discussed earlier.
So I invite you to choose a dimension and number of attributes and generate yourself a game. It may be more complicated and less fun to play than the original set, though!
More from Chalkdust
In conversation with Martin Hairer
We talk to the Fields medallist about his life, his work and his advice to his younger self.
I don’t like science fiction
Peach Semolina admits her true feelings about science fiction, and delves into the maths of quantum teleportation.
A canal runs through it
Colin Beveridge barges in and admires some curious railway bridges
2022 Fields medal winners
Albert Wood returns to introduce the work that has won mathematics’ most famous award this year.
Spam calls and number blocking
Michael Wendl really wants those spammers to stop calling him
Formal sums
Nik Alexandrakis explains what they are and what they can tell us