Chapter 8
Can Chess Be Solved?
Chess is a unique cognitive nexus, a place where art and science come together in the human mind and are then refined and improved by experience.
– Garry Kasparov
Imagine an incredibly powerful computer that could always figure out the best move in any given possible chess position. ‘Best move’ means the one that leads most quickly to winning or, at the very least, not losing – in other words, the optimal outcome for the player. Now, suppose that this computer played against another that was identical to it in every respect. Which computer would win, or would it always be a draw? We’ve solved so many monumental problems in maths, you’d think an old game like chess, with easy-to-learn rules, would hold no challenges to theoreticians armed with the latest computing technology. But nothing could be further from the truth.
The first chess-playing machine, known as The Turk, was actually a fake – although it managed to fool a lot of people between 1770, when it was first unveiled by its Hungarian inventor, Wolfgang von Kempelen, and its destruction by fire in 1854. Among those who saw it in action were Napoleon Bonaparte (no mean mathematician himself), Benjamin Franklin, and one of the pioneers of modern computation, Charles Babbage. Behind a large wooden cabinet was the head and upper body of a life-sized mannequin dressed in impressive Ottoman robes and a turban. Three doors at the front of the cabinet could be opened to reveal an intricate mechanism and other components, while three doors at the back could also be opened, one at a time, to let spectators see through to the other side. What they didn’t see, however, was the expert human chess player who sat on a seat that could be slid from one side of the cabinet to the other as the doors were successively opened and closed. The concealed occupant determined the moves made in reply to whoever was challenging the machine, and then operated The Turk’s arm and hand to move chess pieces on a board visible to the audience via linkages connected to a pegboard chess board inside the cabinet. Ingenious and exquisitely made though von Kempelen’s automaton was, it relied wholly on human brainpower to overcome its opponents.
No mechanical wizardry – no symphony of cogs and gears, levers and linkages – could work fast enough to play even a modest game of chess, such is the complexity of the game. Hopes for a true chess-playing machine had to await the development of the electronic computer after World War II. Pioneers of computation, such as Alan Turing, John von Neumann, and Claude Shannon, were interested in chess as a means of testing out early ideas in artificial intelligence. In a seminal paper on the subject, in 1950, Shannon wrote: ‘Although of no practical importance, the question is of theoretical interest, and it is hoped that … this problem will act as a wedge in attacking other problems – of greater significance.’ A couple of years later, Dietrich Prinz, a colleague of Turing’s, ran the first chess-playing program on the new Ferranti Mark I computer at Manchester University. Memory and processing limitations meant that it could solve only ‘mate-in-two’ problems, in other words, finding the best move when checkmate is two moves away. A reduced version of chess, using a 6 by 6 board without bishops, was programmed to run on the MANIAC I computer at Los Alamos Laboratory in 1956. The computer played three of these ‘anti-clerical’ games: the first against itself, the second against a strong human player handicapped by not having a queen, which the computer lost, and the third against a novice who’d only just learned the rules. In this final game the computer won, albeit against a feeble opponent, thus marking the first victory of machine over human.
In 1958, a researcher at IBM, Alex Bernstein, wrote the first program that could play games of standard chess on the firm’s 704 mainframe – the computer on which both FORTRAN and LISP were developed and on which speech synthesis was first achieved. The scene in the film 2001: A Space Odyssey in which the HAL 9000 computer’s awareness gradually degrades as Dave Bowman disconnects its cognitive circuits, was inspired by Arthur C. Clarke having seen the 704’s efforts at speech synthesis a few years before. Earlier in the movie, HAL easily beats astronaut Frank Poole at chess. Director Stanley Kubrick was a passionate chess player so, not surprisingly, the moves shown in the HAL–Poole encounter are from an actual game: that between A. Roesch and W. Schlage in Hamburg in 1910.
The challenge facing all chess-playing machines is the immense complexity of the game, in terms of strategy and possible moves. All told, there are about 1046 possible positions and at least 10120 unique games of chess, the latter known as Shannon’s number, after Claude Shannon, who stated it in his 1950 article ‘Programming a Computer for Playing Chess’. At the start, things are fairly simple with just twenty possible moves for White – sixteen involving pawns, only three of which are common, and four involving knights, only one of which is common. But the number of possibilities rapidly grows as the game progresses and other pieces, including bishops, rooks, queen, and king, join in the action. After each player has made one move there are 400 different possible positions, after two moves 72,084 positions, after three moves more than 9 million positions, and after the fourth move, more than 288 billion different possible positions. This is roughly one for every star in our galaxy, while the total number of chess games is far, far greater than the number of fundamental particles in the universe.
In the early days of computer chess, the relatively primitive hardware available was a serious handicap. But the basic programming approach to playing a strong game had already been figured out in the 1950s by the Hungarian-American mathematician John von Neumann. The MiniMax algorithm is so called because it strives to minimise the opponent’s score while maximising its own score. By the end of the decade it had been combined with another approach known as alpha-beta pruning, which uses rules of thumb, or heuristics, distilled from the playing strategy of top human players, to weed out bad moves early on so that the computer doesn’t waste time going down fruitless branches of its search tree. This is not the same as a computer learning from its mistakes – that came later – but rather an attempt to program in some good tips and move combinations used by grandmasters in the past.
Agnijo’s chessboard at home. The position shown occurred between Deep Blue (white) and Garry Kasparov (black) in 1996 in the game in which, for the first time, a computer defeated the human world champion.
As computers became more powerful, in the 1970s and 1980s, they were able to run programs that searched both deeper and smarter. In 1978, a computer won a game against a human master for the first time. The same decade saw the start of the World Computer Chess Championships. One of the authors (David), while employed as applications software manager at the supercomputer maker Cray Research in Minneapolis, worked with Robert Hyatt of the University of Alabama at Birmingham to optimise Hyatt’s chess program, Blitz, to run on the Cray-1 – then the fastest computer on Earth. In 1981 Cray Blitz became the first computer to achieve a master rating after it won the Mississippi State Championship 5–0, and in 1983 it beat its arch-rival, Bell Labs’ Belle, to become the world computer chess champion.
Since that time, progress in computer chess has been dramatic. In 1997, the human world chess champion, Garry Kasparov, lost in a five-game tournament to IBM’s Deep Blue, and the last time a human beat the strongest computer on the planet was in 2005. The top computers are now so far beyond the rating ever achieved by a human that it’s safe to say that no one will ever defeat the best computer chess players again. At the time of writing the highest rating (based mainly on tournament wins or losses against other strong players) ever achieved by a carbon-based life-form is 2882, in May 2014, by the current human champion, the Norwegian Magnus Carlsen. This is presently outstripped by at least 50 of the best computer programs, including Stockfish, which has the highest rating ever achieved, by human or machine, of 3394.
Still, for all the prowess of today’s high-speed chess-playing systems, the question remains: is chess solvable? Put another way, can the outcome be known even before play starts? There are many simpler games where the answer to this is ‘yes’. One of the simplest and best known is tic-tac-toe or noughts and crosses. Analysing tic-tac-toe is quite easy because the game has to end in at most nine turns, and much of the time a player is forced to play a certain square to stop their opponent from winning. Any games between players who’ve figured out the strategy will always end in a draw. The fact that tic-tac-toe involves just a 3 by 3 grid helps make solving it easy. But games don’t need a big board in order to be complex. Many people, at one time or another, have played the game of dots and boxes, where you start with a square grid of points and each player in turn draws a line between any two of them. The person who joins up the fourth side of a box wins the box, puts their initial in it, and then connects another pair of dots as part of the same turn. If that results in completing a second box they join another pair of dots and so on. The smallest board size on which the game is interesting is 3 by 3. Although this is the same board size as tic-tac-toe, the amount of strategy involved is already far greater. It’s known that in a 3 by 3 dots and boxes game the second player can force a win but most people don’t know the winning strategy, which turns out to be surprisingly complex. The majority of us essentially play at random, trying not to give away any boxes, then taking as many boxes as we can before giving the opponent as few boxes as possible. For boards that are much bigger than 3 by 3, theoreticians have no clue as to who will win at the start. They can also find positions, which turn up frequently in high-level play, where it’s guaranteed that every move by a player will cause them to lose the game, but after any such move it’s not known how the other player can win, even though it’s known that they can. This is an example of what’s called a non-constructive proof, in other words a proof that shows that something – such as a winning strategy – exists, without giving any hint as to how to achieve that end. These kinds of proof may seem counterintuitive. After all, how can we know for sure that something exists without being able to give an example? Yet, they turn up frequently in games such as this. The bottom line is it may be a simple matter to prove that a certain player can win, but be completely unfeasible to know in detail exactly how this win is to be achieved.
With dots and boxes, like tic-tac-toe, all the possible moves are available at the start of the game and the number of possibilities always goes down as the game progresses. Chess is a much more complex game than dots and boxes, which itself already has huge potential for high-level and grandmaster play. In chess, many more moves are available at each turn, the number of possible moves expands rapidly, and games can go on for much longer. In terms of knowing who is going to win, the best we can do at present is solve this problem in the case of some endgames where a small number of pieces are left on the board. Solving chess in its entirety – finding an optimal strategy by which one of the players can always force a win or both can force a draw – seems like a distant pipedream. Having said this, computers have made spectacular progress in being able to look many moves ahead and select powerful sequences of moves from among billions that are available.
Perhaps even more surprising is the rapid progress that computers have made in another ancient and even more strategically complex game, Go. Played mainly in China, Japan, and South Korea, on a 19 by 19 board, it has roots that extend back two and a half thousand years and is the oldest board game still enjoyed today. In antiquity, it was one of the four arts of the Chinese scholar, along with painting, calligraphy, and playing the qin, a stringed instrument. The antagonists in Go, Black and White, take turns, but unlike in chess, Black plays first. Each player in turn places a stone of their colour on the board and can capture groups of opposing stones, removing them, by surrounding them (the name Go comes from the Chinese for ‘encircling game’) with their own stones. As well as these basic rules there are many others, but more than anything the tactics and strategy involved in Go are fiendishly intricate. Tactics refers to what’s happening in a local part of the board where groups of stones vie over life, death, rescue, and capture, whereas strategy takes in the global situation of the game. Compared to chess, Go involves a larger board, many more alternatives to consider per move, and generally longer games. The brute-force methods that give chess computers the edge would take far too long to be applied to Go. They would invariably prove useless against a grandmaster, who can decide from among the many move options available using higher-level skills, such as pattern recognition, built up from long experience and at which the human brain is particularly adept. Recognising certain types of pattern, which may superficially look quite different in different situations, is a much harder challenge for computers than simply calculating at lightning speed. In fact, after computers started beating the strongest human players at chess, Go experts remained confident that it would be a long, long time until computers reached even a modest amateur level at their own game.
A game of Go.
Then, in 2016, Google’s program AlphaGo defeated one of the world’s best Go players, Lee Sedol, by 4 games to 1. Relying not so much on brute-force methods of looking at many game situations ahead, AlphaGo was designed to play in a more human-like way. It’s based around a neural network that simulates how an organic brain tackles problems. Starting out with a huge database of expert games, it was made to play a very large number of games against itself, with the aim of eventually learning how to recognise winning patterns. It uses the smart, heuristic approach of a human player combined with the speed of silicon circuitry to achieve what hadn’t been thought possible any time soon, to become a world-class Go superstar. In 2017 AlphaGo went one better, winning three out of three games against the top-ranked human player, China’s Ke Jie.
There seems little doubt that, before long, Go-playing computers will be as unbeatable by their flesh-and-blood creators as chess computers are today. But the question remains: are games like chess and Go ultimately solvable? In chess, because White always goes first, Black can only react to the threats that White poses. So if ever chess were to be solved, in other words the best sequence of moves found that White could play in response to whatever the opponent did, it is almost certain that the only possible outcomes would be a win for White or a draw. With Go it is less clear because, unlike in chess, Black goes first and White receives a number of points (6.5 under Japanese rules, 7.5 under Chinese rules) as compensation. It may be that this is enough for White to win, or perhaps the first-move advantage for Black is so great that Black still wins. No one knows and, perhaps, no one will.
A sure-fire way to solve chess would be to draw a tree for all possible positions and then, starting from any position, evaluate every branch by looking at where it ended and then choosing the one that led to the optimal outcome. That’s fine, in theory. But, given that there are roughly 1,200 trillion trillion trillion trillion trillion trillion trillion trillion possible chess games, the resulting tree would be colossal. Building a computer to hold so much data would be a challenge given that there are probably fewer than 1080 atoms in the entire visible universe, which is 40 powers of ten smaller. In practice a lot of the branches could be pruned at an early stage because many of the possible positions are ridiculous and would never crop up in a real game, even one between beginners. But after all the clever trimming back had been done, the tree of possible, realistic moves would still be extraordinarily daunting. It would be even more so in the case of Go. This massive complexity has led some to conclude that although mathematics doesn’t stand in the way of solving such games, matters of practicality do. When there aren’t enough subatomic particles in existence to store the tree of moves, even after extensive pruning, how can a solution be achieved? Perhaps advanced artificial intelligence will come to the rescue, enabling vastly more pruning so that the tree size becomes manageable. Quantum computers, able to search huge numbers of branches simultaneously, might be another option, although unlike with Shor’s algorithm for factoring large numbers, we currently don’t have an algorithm for solving these types of problems or even know whether one exists. Some hope for a possible future solution comes from the fact that the game of draughts or chequers was solved, in 2007, after hundreds of computers, working over a period of nearly 20 years, searched through all the combinations of moves that could be played. A game of draughts, it transpires, will always end in a draw if neither player makes a mistake. Whether, with advances in technology and programming, chess will eventually follow, and perhaps Go too, remains to be seen.
What we do know is that games like chess and Go, and simpler ones including tic-tac-toe and dots and boxes, are ‘games of perfect information’. This means that before a player makes a move, he or she has all the information they need to determine which moves are good or bad. Nothing is hidden from view or uncertain. This means that, in principle, given an unlimited amount of memory and time, they could be solved. But there are other games, such as poker, that lack perfect information. When deciding what to do next, a poker player doesn’t know what cards anyone else is holding, even though that’s a crucial factor in deciding who wins. In a poker tournament that contains a beginner and an expert, the beginner may get lucky, draw a royal flush, and win a hand. However, on average, the expert’s superior knowledge of when to bet or fold will see them win more often and win more money than the beginner over the course of a large number of hands.
Before we could ever say that a game like poker had been solved, we’d need to be clear what ‘solved’ actually means when it comes to games without perfect information. No computer could guarantee a 100 percent win rate in poker – without cheating – as the possibility of a human drawing a royal flush would always exist. What could class as solving poker is for a computer to play by a strategy that will, on average, result in the maximum winnings.
Poker is further complicated by the possibility of bluffing and the fact that, in most tournaments, considerably more than two people are playing. In a situation with multiple humans and one computer, it’s possible – perhaps even likely – that the human players would gang up in such a way as to put the computer at a disadvantage. If they did, each person might win less than if they played entirely selfishly, but the humans as a whole would win more.
All this said, a program has been developed that can’t be beaten, over long periods of play, at a type of poker called heads-up limit Texas Hold ’Em (a two-player game). The new software, announced in 2014, marks the first time an algorithm has been found that effectively solves a complex game in which some information is hidden from the player. This hidden information, together with the luck of the draw, ensures that the program can’t win every hand. But on average, and over many hands, there’s virtually no chance that a human could ever beat it (just as, for example, a human could practically never beat Stockfish at chess), so that effectively this version has been solved. Not only can the program help human players improve their game, but it’s also been suggested that the approach it takes could prove useful in health care and security applications.
It may seem, from the poker example, that all games with imperfect information involve some sort of chance that’s outside the control of the players. But that isn’t the case. In the familiar game of rock-paper-scissors, all that matters is what each person plays: there’s no chance involved that is outside the control of the players. Yet, in spite of this, the game has imperfect information. The usual way of playing the game, by two people making hand gestures simultaneously, is effectively no different than if the players were in separate rooms and wrote down their decisions, each unaware of the other player’s choice.
Now, in a game with perfect information there’s always some ‘pure’ strategy – some move or series of moves that results in the most favourable outcome. For example, in chess there’s always a best move (or often multiple winning moves), which, if played consistently in the same situation is the optimal thing to do. In the case of rock-paper-scissors, the exact opposite is true. Adopting a pure strategy by playing, say, rock every time, or a regular pattern of rock, paper, scissors, would be easily beaten. Instead, the best approach is what’s known as a mixed strategy, which means that in any position different actions are taken with different probabilities. Solving a game like rock-paper-scissors or two-player poker is about finding an optimal mixed strategy that guarantees the highest probability of winning. The strategy of ‘always play rock’ would have a 100 percent winning probability if the opponent were foolish enough to always play scissors. On the other hand, given the more likely case that the opponent would quickly respond by always playing paper the winning probability of ‘always play rock’ would fall to 0 percent. It comes as no surprise that rock-paper-scissors has been solved and the solution is quite trivial. The optimal strategy is to play rock ⅓ of the time, paper ⅓ of the time, and scissors ⅓ of the time. Counting a draw as half a win, this gives the player a 50 percent minimum win rate, which is the best of all possible strategies. While there’s some scope for high-level play, it relies on psychology instead of game theory, exploiting the fact that humans are generally bad at being truly random, as we saw in Chapter 3. In general, in games without perfect information the optimal strategy is always mixed.
In such games, too, there’s a concept known as the Nash equilibrium, named after the American mathematician and economist John Nash, who made important contributions to game theory and was the subject of the novel (and subsequent film) A Beautiful Mind. In a strong Nash equilibrium, all players have a strategy, which if they deviate from in any way (assuming no one else does so simultaneously) they’ll be worse off than before. There’s also another concept, a weak Nash equilibrium, where a player can deviate from the strategy and be neither worse nor better off than before, but it’s impossible to deviate from the strategy and end up better off than before. Nash equilibria play a pivotal role in game theory.
In a game with perfect information, a Nash equilibrium occurs if both sides play the optimal strategy. This can be strong or weak, depending on whether there are multiple optimal strategies. In a game with imperfect information, this is also true. However, it’s entirely possible for there to be multiple Nash equilibria. To determine whether we’ve found them all, another concept is needed, known as a zero-sum game or constant-sum game.
In a zero-sum game one person’s gains exactly equal the other person’s losses. More general is a constant-sum game, in which the total gains made by the players never change. Chess is an example. The players could both draw, earning half a point each, or one could win, with the winner earning one point and the loser earning nothing. By contrast, a game such as football isn’t a constant-sum game, because if the teams draw each gains one point, but if one team wins they gain three points and the loser gains nothing. The sum of points can be 2 or 3. Constant-sum games can all be converted into zero-sum games by adding or subtracting points. For example, if half a point were deducted from each player of a chess game, the game would be zero-sum. For this reason, results which apply to zero-sum games generally also apply to constant-sum games.
In any zero- or constant-sum game, the only Nash equilibria occur when both players play an optimal strategy. However, this result doesn’t apply to games that are not constant-sum, which may have many other Nash equilibria. In games that aren’t constant-sum, another issue becomes relevant – that of Pareto efficiency. Any set of strategies is Pareto efficient if it’s impossible to change all strategies to make someone better off without making someone else worse off. In a zero-sum game any set of strategies is Pareto efficient. But in general this isn’t the case. Even Nash equilibria may not be Pareto efficient as a puzzle known as the Prisoner’s Dilemma makes clear.
Two prisoners have both been convicted separately of a crime that carries a sentence of one year. In addition, however, some witness statements have linked the pair to having jointly taken part in a more serious crime carrying a sentence of six years. The prisoners are given a choice. They can both either remain silent or privately betray their partner. Neither will be told what the other has done until they receive their sentence. If both betray each other, both will receive four years in prison in total (three years each for the major crime and one year each for the minor crime). If only one betrays the other, the betrayer goes away free and the other prisoner receives a full seven years for both crimes. If both stay silent, both can only be convicted of the minor crime and both serve one year. Surprisingly, it turns out that no matter what the other person does, betraying them is always better than staying silent. The only Nash equilibrium is therefore when both prisoners betray each other and both serve four years. However, this isn’t Pareto efficient, as it’s better for both of them to stay silent and serve only one year each. The Prisoner’s Dilemma can be repeated any number of times, with strategies that depend on what happens in the past – a problem known as the iterated Prisoner’s Dilemma, which can become very complicated indeed. The best strategies for the iterated version tend to be those that involve generally staying silent, provided the other player also does so, but punishes players for betraying them by also betraying. These strategies thereby reap the benefits of the Pareto efficient outcome against each other, while trying to avoid the worst outcome by opting for the Nash equilibrium if it’s clear that the other strategy is betraying it.
Most people prefer that the games they play end in a reasonable amount of time, say an hour or two, before fatigue, hunger, or boredom set in. The World Chess Federation puts a time limit, for all its major events, of 90 minutes for the first 40 moves, and 30 minutes for the rest of the game. However, the longest game on record, between Ivan Nikolic and Goran Arsovic in Belgrade in 1989, lasted over 20 hours before ending in a draw after 269 moves due to the ‘50-move’ rule. This states: ‘The game may be drawn if each player has made at least the last 50 consecutive moves without the movement of any pawn and without any capture.’ A draw can also be claimed, again by the player whose turn it is, if the same position has occurred three times. Assuming that such a claim is made under the 50-move rule, the longest a game can possibly go on is just under 6,000 moves.
Much longer, potentially billions of times longer than the Sun will shine, are games that could be played on a chessboard that stretched forever in all directions. So-called infinite chess has the same rules and number of pieces as the common or garden finite variety, but uses a board that has no end or edges. Playing it could involve some spectacular moves – a rook might shoot off a trillion places in one direction, a bishop might hurtle in from the equivalent distance of intergalactic space to capture a pawn the next. This is not a socially acceptable game for limited beings like ourselves. Yet, through the power of maths we can know something about it even if we can never participate. Most importantly, we can be sure of one very important fact about infinite chess: like its finite cousin there is a strategy, which if adopted, would guarantee a win for one of the players. What is that strategy? Unless we had a computer of infinite speed and memory capacity there’s no way of knowing. But the fact that all forms of chess, and other games of perfect information, finite or infinite, can be solved in theory provides at least some measure of satisfaction.
Back in the pioneering days of artificial intelligence, in the 1960s, mathematicians and computer scientists such as Claude Shannon used chess as an application to test ways of making computers think more like human beings. Today, complex games of strategy are still used for this purpose. In themselves, of course, the games have no great importance, unless they’re how you make a living. But the ways in which machines are constructed or taught, or learn for themselves, to become stronger players can be transferred to other tasks that do matter. What’s more, the effort to solve chess and similar complex games sheds some light on the limits of what we can ultimately hope to know.