The Mathematics of Games: Can You Solve a Game Before Playing It?

Think about the last time you played a game. Perhaps you were trying to force a win in Uno, planning your next move in chess, or desperately looking for a way to avoid losing at a board game. Usually, we think of a game as a process that unfolds one move at a time. We make a decision, our opponent responds, and we react again. But what if you could determine the outcome of a game before playing it? Not by guessing, and not by being particularly good at the game, but by proving mathematically that a position is winning or losing. This is the idea behind combinatorial game theory, where games become mathematical objects that can be analysed using logic, algorithms and even seemingly unrelated ideas such as binary arithmetic.

A beautiful place to start is Nim, a game that looks almost too simple to contain much mathematics. There are several piles of objects, and players take turns removing any positive number of objects from exactly one pile. Whoever takes the last object wins. For example, imagine three piles containing 3, 4 and 5 objects. There is, remarkably, a simple mathematical test for whether the position is winning: take the bitwise XOR of the pile sizes. Writing the numbers in binary,

3 = 011

4 = 100

5 = 101

The symbol for the XOR operation is ⊕. XOR compares the corresponding binary digits: two equal digits give 0, while different digits give 1. For example:

3 ⊕ 4 ⊕ 5

= 011 ⊕ 100 ⊕ 101

= 010

= 2.

Since this is equal to 2 and not 0, the position is therefore winning for the player whose turn it is. More importantly, there is always a move that changes the XOR to zero. Here, reducing the pile of 5 to 3 gives

3 ⊕ 4 ⊕ 3 = 0

That apparently strange operation is actually a perfect strategy. Once the XOR is zero, any move your opponent makes changes exactly one pile, so the XOR becomes non-zero. You can then respond by making another move that restores it to zero. Eventually, your opponent is left with no move at all. Intriguingly, Nim provides a striking example of how a game can be completely understood through mathematics rather than trial and error.

Nim also hints at a much bigger idea: combinatorial game theory asks what the optimal outcome of a game is when both players play perfectly. A game can be represented as a huge tree. Each node represents a position, and each branch represents a possible move. From a particular position, we can ask: “Can I move to a position from which I can force a win?” If the answer is yes, the position is winning; if every possible move gives the opponent a winning position, it is losing. For certain classes of games, the mathematics can go much further. The Sprague-Grundy theorem, for example, shows that every position in a finite impartial game can be assigned a number called its Grundy value, effectively allowing complicated games to be treated mathematically like Nim. In this way, game theory turns an enormous collection of possible moves into something that can be analysed systematically.

A much more familiar example is Connect Four. It is easy to assume that such a game must depend on intuition: perhaps controlling the centre is good, or perhaps creating two threats at once is useful. But Connect Four has actually been solved. On the standard 7×6 board, the first player has a forced win if both players play perfectly, provided the first player begins in the central column. This was solved by James D. Allen and Victor Allis in 1988. Allis's work used a program called VICTOR, which combined search with mathematically proven strategic rules.

Why does going first matter so much? At first, it might seem that the advantage should be tiny: after all, both players get almost the same number of moves. But in a game with no randomness, having the first opportunity to create a threat can fundamentally change the structure of the game. In Connect Four, the central columns are particularly powerful because they participate in many possible horizontal and diagonal winning lines. Starting in the centre allows the first player to build threats that the second player cannot simultaneously neutralise. The important point is that “the first player wins” does not mean that anyone who moves first will automatically win. It means that there exists a strategy which guarantees victory against every possible response.

But Connect Four also demonstrates a problem that appears again and again in mathematical games: the number of possibilities grows incredibly quickly. A standard Connect Four board has trillions of possible positions. It is therefore impossible to simply sit down and manually examine every possible game. Instead, mathematicians and computer scientists use techniques such as minimax search, where a program assumes that both players will always choose the move best for themselves, alongside methods such as alpha-beta pruning and strategic position analysis. Solving a game therefore becomes a combination of mathematics and computation: we need to understand what makes a position winning, while also finding efficient ways to search through the enormous number of possibilities.

This brings us to Hex, a game that makes Connect Four look surprisingly small. Hex is played on a rhombus-shaped board made of hexagonal cells. Two players take turns placing stones, attempting to connect their two opposite sides of the board. The remarkable feature is that draws are impossible: eventually one player must create a connected path. Even more remarkably, mathematicians already know something about the outcome. John Nash's famous strategy-stealing argument proves that the first player must have a winning strategy on an n × n Hex board. The catch is enormous: the proof tells us that a winning strategy exists, but does not tell us what that strategy actually is.

This is where Hex becomes particularly interesting from a research perspective. Although the general game has not been completely solved in the practical sense of finding an explicit optimal strategy for every possible board position, researchers have solved increasingly large boards and openings using sophisticated combinations of game theory and computer science. One important idea is the virtual connection: rather than simply looking for an immediate path, algorithms can prove that certain groups of stones are effectively connected because no matter how the opponent responds, a connection can eventually be established. Researchers have also developed ideas such as domination, inferior-cell analysis, and game-state reduction, allowing huge sections of the game tree to be discarded without examining every move. These techniques have led to complete solutions for all openings on smaller boards, including 7×7 and 8×8, while substantial progress has also been made on 9×9 boards.

The contrast between Nim, Connect Four and Hex reveals something fascinating about what it means to “solve” a game. Nim has a compact mathematical rule: calculate an XOR. Connect Four has a provable winning strategy, discovered through a combination of strategic reasoning and computational search. Hex goes one step further: mathematics proves that the first player can win, but finding an explicit strategy remains extraordinarily difficult as the board grows. In each case, the challenge is not simply to find a good move. It is to understand all possible responses and prove what happens regardless of what the opponent does.

Perhaps that is what makes mathematical games so compelling. A game that feels like a collection of decisions can actually contain an enormous mathematical structure beneath the surface. Every move changes the future possibilities, and every possible response creates another branch in the tree. Mathematics gives us a language for navigating that structure, while algorithms give us a way of exploring it. And there is something wonderfully paradoxical about the subject: the better we become at solving games, the more clearly we see how much remains unsolved. Perhaps the next time you sit down to play a game, ask yourself a different question. What if the winner of the game was decided long before the first move was ever made?

Bibliography

Bouton, Charles L. “Nim, A Game with a Complete Mathematical Theory.” Annals of Mathematics, vol. 3, no. 1/4, 1901, pp. 35–39. JSTOR, 1901. Accessed 5 Oct. 2026.

Smith, Samuel Bruce. “The Sprague–Grundy Theorem.” Chance, Strategy, and Choice: An Introduction to the Mathematics of Games and Elections, Cambridge University Press, 2015, pp. 335–348. Cambridge University Press, 11 May 2018. Accessed 5 Oct. 2026.

Allis, Victor. “A Knowledge-Based Approach of Connect-Four: The Game Is Solved: White Wins.” ICGA Journal, vol. 11, no. 4, 1988, p. 165. SAGE Journals, 1 Dec. 1988. Accessed 5 Oct. 2026.

Allen, James Dow. The Complete Book of Connect 4: History, Strategy, Puzzles. Puzzle Wright Press, 2010. Open Library, 3 Feb. 2023. Accessed 5 Oct. 2026.

University of California, Berkeley. “3.2 Minimax.” CS 188: Introduction to Artificial Intelligence. n.d. Accessed 5 Oct. 2026.

Hayward, Ryan B. “A Puzzling Hex Primer.” Games of No Chance 3, edited by Michael H. Albert and Richard J. Nowakowski, Cambridge University Press, 2009, pp. 151–162. Cambridge University Press, 28 Feb. 2011. Accessed 5 Oct. 2026.

Nash, John. “Some Games and Machines for Playing Them.” RAND Corporation Technical Report D-1164, 1952. RAND Corporation, 2 Feb. 1952. Accessed 5 Oct. 2026.

Hayward, Ryan B., Yngvi Björnsson, Michael Johanson, Morgan Kan, Nathan Po, and Jack van Rijswijck. “Solving 7×7 Hex: Virtual Connections and Game-State Reduction.” Advances in Computer Games 10, 2004, pp. 261–278. Michael Johanson, 2004. Accessed 5 Oct. 2026.

Henderson, Philip, Broderick Arneson, and Ryan B. Hayward. “Solving 8×8 Hex.” Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, 2009, pp. 505–510. IJCAI, 2009. Accessed 5 Oct. 2026.