One branch of mathematics, called Combinatorial Game Theory, was developed around 30 years ago specifically to deal with the analysis of games. It prescribes a way of breaking games down into smaller parts that are easier to examine, and then using a special kind of algebra to add up the values of the individual subgames. And if there's one thing that mathematicians are good at it's counting.

Combinatorial Game Theory

"The Chess Players", by Thomas Eakins

Despite its power, Combinatorial Game Theory, or CGT, is only valid for games satisfying certain conditions. The most important are that there are two players, both players have complete knowledge about the state of the game, there is no chance element (such as a dice roll or card shuffle), and both players take turns to make a move (skipping turns is not allowed) so that the first player unable to move loses the game. So Backgammon, Poker, Battleships, Monopoly, and Solitaire, among others, cannot be considered by CGT as they fail various combinations of these criteria.

The games that CGT can be applied to all have the same basic essence: you win by ensuring that you can always make at least one more move than your opponent. The classic example of this type of game is one we all played as children, namely...

Twenty-one

In case you've forgotten, Twenty-one is played with a heap of 21 coins (or matchsticks, or whatever) placed between the two contestants. The players take it in turn to remove one, two or three coins from the heap, each aiming to pick up the last one, so that the other player is unable to move and therefore loses.

It turns out that Twenty-one is a first-person-win game - no matter how well the second person plays, the starter has a strategy that is unbeatable. If you begin it is possible to ensure that there are exactly four coins left for your opponent's turn. Your opponent can take at most three of these, and you are able to swipe whatever is left to win.

CGT mathematicians have spent a lot of time analysing a game very similar to Twenty-one called Nim. Nim is played with any number of piles of coins, and the two competitors are allowed to take either a whole pile or any number of coins within the same pile. Again, the winner is the one to take the last pile or single coin, leaving the other player with no coins left. Twenty-one is in fact a special case of Nim, where there are seven piles, each with only 3 coins.

Nim

Nim, it turns out, responds very well to analysis by CGT. The aim of Nim is to guarantee that you can always make another move and your opponent runs out of moves before you do. What CGT does, then, is count up the maximum number of moves both players are able to make, and so work out who has extra "spare moves". Nim is a so-called impartial game, because both players use the same pieces and so have identical moves available to them - unlike, for example, chess, which is a partisan game, meaning that the players each have their own pieces which only they are allowed to move.

A possible starting setup for Nim

So in Nim the players have the same number of spare moves, and the only thing that matters is whose go it is next. For example, in the situation where there is only one coin left, whoever gets to move next will win. After the first player takes the last coin there are none left for the second player, who therefore loses. CGT has its own special way of describing situations like this, and its own algebra for working out the value of a game. The scenario where there is only one coin left is written as

{ 0 | 0 } = *.

Since CGT does not know whose turn it is next, it gives the number of moves remaining after either player moves. The numbers in the curly brackets signify that after taking the last coin the left-hand player will have no spare moves left, and likewise for the right-hand player. Because Nim is an impartial game, the numbers to the left and right of the central bar will always be the same. The value of the game is written after the equals sign. The star signifies that whoever moves next wins, which is known as a fuzzy position. The game of Twenty-one is a fuzzy position from the very start, since whoever begins is able to force a win.

If, however, there are two single coins left, then whoever has to move next will lose. This is because whichever of Left or Right moves next will have to leave exactly one coin. The other player takes this coin, thereby winning the game. This case is written as

{ 1 | 1 } = 0.

Again, the left- and right-hand numbers tell us the number of moves remaining after either player's next turn, which is one in this example. The value here is 0, since whoever has to move next will lose the game, and so a "first-player-loss" scenario is also known as a zero position. All first-player-losses can be simplified to the last position of the game where there are no coins left:

{   |   } = 0.

A fuzzy position in Nim

A slightly more complicated scenario is where there are three coins left, arranged as a pile of two next to a single coin. The first player takes the top coin off the pile of two, the second player removes either of the two single ones remaining, and the first player then wins by taking the last coin. So whichever of Left or Right moves first can win - another fuzzy position:

{ 2 | 2 } = *.

Of course, the first player could have started by taking either the single coin or the entire pile of two. This choice, between leaving one or two spare moves, would be written as

{ 1 , 2 | 1 , 2 }.

But unnecessarily leaving only one spare move at the start of your opponent's turn would be completely irrational, since your opponent would be able to take whatever was left and win the game. Such foolish options are ignored by CGT as both players are assumed to be playing intelligently and trying to win. And so:

{ 1 , 2 | 1 , 2 } = { 2 | 2 } = *.

Just as in the first example, this scenario simplifies to { 0 | 0 } = *, which is the position after the second player's move.

A partisan game - chess

In partisan games the two players have different options for their moves. Now the left and right numbers in the curly brackets don't have to be the same. If Left has four available moves and Right has only three then Left has one spare and will win no matter who starts. This is written as

{ 4 | 3 } = 1,

which simplifies to { 0 |   } = 1. This is known as a "positive position" since Left wins regardless of who has the first move. If the tables are turned and Right has one spare move then the game is a "negative position" (by convention, game values are always given from Left's point of view).

"Retrato de dos jugadores de ajadrez", by Honori Daumier

Chess is one such partisan game, and now that we understand how CGT works we can use it to look at board positions. In fact, chess as a whole is technically not eligible to be analysed by CGT. Although both players have complete knowledge about the pieces on the board and there is no random element, there are more subtle requirements for applying CGT. In general the winner of a chess game is not the player with the most spare moves, but the one to checkmate the other, and CGT works best with games where having to make a move is normally a disadvantage. In chess, however, it is almost always a great advantage to be next to move. In fact, one way of handicapping a stronger player in the hope of producing a more even game is to remove the pawn in front of one of the stronger player's knights and let the other player move twice at the start (known as a "pawn and two moves" handicap).

Chess is also much more complex than games like Nim, and simply having more spare moves than your opponent is unlikely to win you the game - you can still be checkmated. Furthermore, chess has many pieces at the start, and, crucially, very powerful ones that can exert their influence across large areas of the board; the queen, for example, can attack up to 18 squares. The result is that for most of the game the board cannot be broken down into independent components like the separate piles of coins in Nim. In the later stages, however, when most of the long-range pieces have been exchanged off, the board can be decomposed into several subgames. Now, being next to move may no longer be an advantage, and CGT becomes a perfect tool for examining the scenario.

CGT in the endgame

A Trébuchet position

For certain positions in the endgame the player who must move next will lose. This is identical to the zero positions in Nim, and in chess these special cases are called mutual Zugzwangs. "Zugzwang" is a German word meaning "compulsion to move". The Trébuchet position shown to the right is one such example of a mutual Zugzwang:

{   |   } = 0.

The pawns are blocking each other's advance, and so it is a king that must move next. However, White cannot move to f4, nor Black to d5, as the king would be putting himself into check from the enemy pawn. The first king to move must therefore step back from his pawn, leaving him no longer able to protect it (the rules of chess forbid the kings moving within one square of each other). The opponent is now able to capture this pawn and force his or her own pawn onto the back row. The rules allow such a pawn to be promoted to a queen, an advantage that is known to be decisive, ensuring an inevitable win for the second player to move.

A fuzzy position in the endgame

If some extra pieces are added to the board it is possible to convert this into a fuzzy position - first-to-move wins:

{ 0 | 0 } = *.

Here, the first person to move can push his or her pawn on the a-file forward one square. The other player's pawn is now blocked, leaving no option but to move the king. In this case there are two components to the game: the value of the a-pawns = *, and the value of the Trébuchet = 0. The value of the game as a whole is therefore = *.

A positive position in the endgame

If, however, the White pawn were placed on a2 rather than a3, the value of the position would become positive: { 0 |   } = 1. The White pawn has not moved yet in the game, and so is allowed to advance either one or two squares for its first move. It is this choice that gives White a spare move. If Black moves first then the White pawn advances a single square and blocks as before. But if it is White's turn first then the pawn can leap forward both squares to barricade, and again Black is forced to break the Trébuchet and so lose. Thus White wins regardless of who has to move first.

Schweda vs Sika, 1929

The position above is still fairly simple, though. CGT really comes into its own when there are more pawns on the board and the position becomes too complicated to analyse easily by just looking at it. For example, the position to the left arose in a game between Schweda and Sika in 1929. Schweda, playing as White, correctly evaluated it as a winning position for him. In 1960 Euwe demonstrated that Black could also have forced a win if it had been his move. But he was unable to define clearly why this position is a first person win, even though he was world chess champion for two years and had a PhD in mathematics! However, now that Combinatorial Game Theory has been developed the analysis is easy.

The trick is to decompose the game into independent components and compute the value of each. The kings and pawns on the e- and f-files are locked in a different kind of Trébuchet, which as we know = 0, and so the other two subgames constitute a last-mover-wins scenario.

The pawns on the a- and b-files are actually in quite a complicated position: three of them have the double-move option, and in a few moves there will be the opportunity for captures. If the numbers are added up, though, it turns out that the value of this a- and b-file subgame = . This is a new symbol, but all it means is that the position is infinitesimally positive - White has a very slight advantage.

"The Chess Players", by Thomas Eakins

The value of the second component - the two pawns on the h-file - is easier to compute. Here Black has the double-move option but White does not. If it is Black's turn, the Black pawn advances two squares and blocks the White pawn's advance on the next turn. If White moves first then Black only advances one square and again soon blocks White. Black can therefore use this spare move to guarantee that it is White's turn after the resolution of the subgame. The value of this is = *, which just indicates a slightly negative number.

The algebra of CGT can be used to add up the numbers and *, and it turns out that these two components sum to a fuzzy value. Whoever moves first on the board can orchestrate matters so that after the resolution of the pawn subgames it is the other player's turn. This player has no option but to move his or her king and so lose the Trébuchet and soon the game.

Combinatorial Game Theory is therefore a very powerful tool for analysing certain types of games. The simple game of Nim is a good demonstration of how this technique works, but its strength only really becomes clear when it is applied to much more complicated scenarios like chess endgames. It can even solve a 75-year-old puzzle that has already defeated a chess master with a doctorate in maths.

Further Reading:

• Winning Ways For Your Mathematical Plays, Volume 1, 2nd edition, Berlekamp, Conway, Guy
• Games of No Chance, Richard Nowakowski (ed.)

About the author

Lewis Dartnell read Biological Sciences at Queen's College, Oxford. He took a year off to travel, but has now just started a four-year MRes/PhD program in Bioinformatics at University College London's Centre for multidisciplinary science, CoMPLEX. You can contact Lewis about this article on l.dartnell@ucl.ac.uk.

Lewis came second in the 2003 THES/OUP science writing competition with an article on the parallels between language and the structure of proteins. Although he does enjoy the odd game of chess, his understanding of Combinatorial Game Theory can't seem to break an embarrassing losing streak...