Iain Duncan

Games have been a part of human civilization from the very beginning, with the oldest known board game originating in Egypt 5000 years ago. In the modern world, esports is a billion-dollar industry and even games like chess have millions of players every day. However, when games are played in a competitive context a simple question presents itself: what will happen if my opponent and I both play perfectly?

Games which have a definite (but not necessarily known) answer to that question are referred to as solvable. For a game to certainly be solvable it must be a turn-based, perfect-knowledge game with a limited number of possible moves per turn. One of those terms may need defining… A perfect knowledge game is one where all players know the total present state of the game, what the other players want, and what will happen if they make a certain move. Notable games which meet these criteria are Noughts and Crosses (Tic-Tac-Toe), Connect-4, Checkers, Chess, and Go. However, not all of these games have been solved, even though it’s theoretically possible. What gets in the way of ‘solving’ a game? 

Solvable has been defined, in this article, to mean that a game has what is known as a weak solution, whether we know what that solution is or not. A weak solution is one which shows that the outcome of a game is determined from its starting point when both players play optimally and produces an algorithm (computer program) which generates this move sequence. The reason all games of the type described are theoretically solvable is because they can be written as a game tree. 

A game tree is a diagram where the current position of a game is connected to all positions which can be reached from it. For a weak solution, the top of the game tree will be its starting position, the second row will be every position which can be reached after two moves, etc. 

These diagrams give us clues, both on how to solve such games and what might get in the way of the solution. 

To illustrate how we can find solutions, imagine two people steering a car down a branching road in complete disregard for health and safety. The first player (Blue) wishes to reach one of the blue destinations and the second player (Red) one of the reds. They take turns choosing which road to go down and both know where the roads will lead. Blue is to go first. The road map is: 

where the blue rectangle means it is Blue’s choice and the red box means it is Red’s choice. 

We analyse the game by considering which choice the players will make at each decision point, called a game-state or node. We work from the end of the game to the start to determine the optimal strategy. For the blue box farthest to the right, as we move vertically down the different game states Blue will make the following choices: blue, red (as there is no other option), blue, blue. In the red box, Red will choose branch 2 if she is in the upper game state and either branch if she is in the bottom state. Her choice doesn’t matter for the lower branch because she knows that Blue will choose blue for either of the lower two branches and she will lose. She chooses bottom in the upper state because Blue will have to choose red afterwards, so Red will win. However, since Blue knows what red will choose if she picks path a, Blue will pick path b. This is the essence of what makes the game solvable. Both players played as well as they could. Both players analysed the full game tree before making a decision and Blue knew that, if she made the right choice, she would win no matter what. Red didn’t stand a chance. 

To see the problem with this approach, let’s look at the game tree for Noughts and Crosses again. In the first row (labelled ‘starting position’), there is one game possible, in the next (labelled ‘one move’) there are three, and in the third (labelled ‘two moves’) there are 12. If we were to write down the entire game tree for Noughts and Crosses there would be 255,168 possible games: a massive number which would of course need a lot more space than just this page! And it gets worse, because Noughts and Crosses is a relatively simple game. You probably found that it was very likely to be a draw before you turned ten. For a game with m possible moves every turn, the n^th level of the game tree will contain mⁿ  possible games – a number which can get very large very quickly. In chess, there are about 16 legal moves per turn and games last around 40 moves. This means we can estimate the number of possible chess games by looking on the 80^th level of the game tree (40 moves per player). Our crude estimate is 16⁸⁰ ~ 10⁹⁶ – a very large number. For reference, the upper estimate for the number of atoms in the observable universe is 10⁸², which means there are TEN THOUSAND BILLION possible chess games for every atom in the universe.  

If we set a computer to figure out every possible game of chess and then sort through the games to find the best one, we would have our weak solution. As I said, chess is a solvable game. However, doing this would take a computer bigger than the solar system, and timescales far longer than any human lifetime. If we want a solution, the brute force approach is simply not an option. Fortunately, humans are very good at games. For almost as long as computers have existed, humans have been finding ways of making them think smarter, as well as faster. Modern game-solving is a process of optimisation and knowing which possibilities can be neglected as much as it is a process of raw computational might. 

One such way of making the computer smarter is to introduce an intermediate value function (IVF). This allows the computer to judge how good a game state is, even though the game has not reached a conclusion yet. If a computer can do that, it does not need to analyse the entire game tree to make a move. Instead it can only look, say, 20 moves ahead, thus saving a lot of computation time. This is exactly what humans do when playing games. It is very rare we work out the entirety of a game tree. Instead, we work out what positions look good and work towards attaining them. Only when we have a good position do we look for a way to win. 

Chess computers, colloquially referred to as engines, are primarily differentiated by their IVFs. The first computer to beat the human World Champion, Gary Kasparov, used an IVF which was built around human experience playing chess. For example, humans realised that some pieces were more valuable than others and that some squares were safer for the king. This information can then be turned into an IVF. The result is a program which has a similar understanding of the game to a human, but can always see 20 moves ahead and never makes mistakes. 

The next step is to build an IVF which goes beyond human experience. The most famous example of this again comes from chess – a computer called AlphaZero. AlphaZero’s IVF was built by feeding as many chess games as possible into a machine learning algorithm. This algorithm then constructed its own concepts of what made a good position based on how frequently certain patterns appeared to the outcomes of those games. The result was a program which dominated its peers and revolutionized human chess. 

Of course, the use of IVFs does not necessarily produce a solution to the game. Nor are they the only tool that we use to look for solutions. Search functions exist to make sorting through the game tree faster and the speed at which computers can perform calculations is still increasing. We are now able to produce solutions for games, such as Checkers and Three Musketeers, which were once considered practically impossible. Chess and Go elude us for now, but it is possible that with time even these massively complex games will be solved.  

So to come back to our original question: if you and your opponent play a game perfectly, will you win, lose or draw? A simple question, with a complicated answer, involving supercomputers, game trees and more calculations than there are atoms in the universe. However, if the game you’re playing meets the criteria needed, you can be pretty sure the answer’s out there. You just need to find it – good luck!

In the next article in this series we will move on from solvable games to consider ‘Game Theory’ – COMING SOON.