The Maths of Board Games

Why are there chess Grandmasters, but not Grandmasters of noughts and crosses (otherwise known as tic-tac-toe)? It is because chess is “harder” – but what do we really mean by that? 

Answering that question leads us to develop the idea of mathematical complexity, which is a measure of how ‘big’ a game is. 

We’ll look at the complexity of popular games, and ask: what is the hardest game of all time?

A lecture by Sarah Hart recorded on 10 October 2023 at Barnard's Inn Hall, London

The transcript and downloadable versions of the lecture are available from the Gresham College website: https://www.gresham.ac.uk/watch-now/maths-games

Gresham College has offered free public lectures for over 400 years, thanks to the generosity of our supporters. There are currently over 2,500 lectures free to access. We believe that everyone should have the opportunity to learn from some of the greatest minds. To support Gresham's mission, please consider making a donation: https://gresham.ac.uk/support/

Website:  https://gresham.ac.uk
Twitter:  https://twitter.com/greshamcollege
Facebook: https://facebook.com/greshamcollege
Instagram: https://instagram.com/greshamcollege

Transcript

0:04

So today we're gonna talk about the mathematics of board games. Now, play is part of being human and archeological evidence of games dates back many millennia across all civilizations. Some games though, endure and they continue to hold our interest no matter how many times we play them. And I'm gonna make the case that there are good mathematical reasons why this is so. Part of our exploration can be encapsulated in the question, why are their grandma of chess but not grandma of naughts and crosses? And the answer to that leads us to develop the ideas of mathematical complexity, which, uh, is kind of a way to measure how big a game is in some sense. And along the way, we're gonna meet the machine that played chess with both Benjamin Franklin and Napoleon Bonaparte. And we are going to find out what is the hardest board game of all time. So I've said board games have been played for thousands of years. Uh, we have some evidence for this, um, archeologically. So we, we find these beautiful gaming boards. This one, uh, originates from the ancient Mesopotamian city of Ur, and it's called the Royal Game of Ur. It's a game that perhaps we don't play so much nowadays, however, it's got several things and characteristics in common with some of our modern games. So it's, it's a game, it's a race. You have to get your seven counters, um, from safe initial point all the way along down the central row, and then round to, to home, and then they're safe. But meanwhile, your opponent is doing the same thing with their counters on their side of the board. And you both are having to traverse this, uh, risky middle, uh, row where if your opponent lands on one of your counters, then that counter gets sent home. So we've played all played games that are similar to this. Um, you don't have free choice entirely, so there is some chance involved as well as skill because, um, you have these four, that kind of tetrahedral dice that you roll, and that determines, uh, how many steps you can move, how many squares you can move. So it's a mixture of chance and skill, like many games, very entertaining. The rules for this were lost for a long time, thousands of years, but were rediscovered by, uh, a brilliant, uh, researcher at the British Museum, Irving Finkle. Um, and you can, you can look up, he plays a game of this on YouTube and it's very, very entertaining. He found out what the rules were and now we can play this game again. Uh, it's a brilliant game, but do not think that, you know, this beautiful gaming board that we see here means that these games were the preserve of the wealthy only anyone can make. And this is an example of, of, uh, a board that was just scratched onto the base of a large statue. So, so you can just scratch your board and play a game of, uh, get a few pebbles you don't need very much. So everyone's playing these games, and that continues to today. We don't need to buy an expensive set. We can scratch out a par cheesy board and play, um, a game again, find a few pebbles, play a game. So we don't need equipment. These games can be played by anyone anywhere. So that's brilliant that they're so universal. Another thing we should notice is that games are not just played for entertainment. There are different reasons that we have for playing these games. Of course, we want to be entertained, but also there's often a religious, spiritual, or moral aspect to the game. So on the left, um, here you see, this is the tomb of Queen Nefe, the Egyptian, uh, queen. And she is playing a game of senate there, an ancient Egyptian game. And the movement of the pieces in that game is an analog for your journey to the underworld. On the right, you see a game that looks a bit like our modern snakes and ladders, but it originated that game from a much older game that that came from India. And it's got this moral dimension to it that, um, the ladders correspond to doing good deeds that get you closer to enlightenment. And the snakes are when you do bad deeds, and they get you further away. So there's this other dimension to a lot of games. A final important dimension is a sort of analogy with, with a war a conflict, you are fighting against your opponent and you are learning strategic thinking. So this is a game of nine men's Maurice, um, that goes back at least 2000 years. Roman soldiers played it in, in Ancient Britain. Now, this game, um, just give you an example board there, you each have nine pieces and you place them on the board. Every time you make a row of three, um, you're allowed to remove one of your opponent's counters. So it's a game with full of strategy, um, a really fun game to play. If you've never played it, I recommend it's strongly. And of course, chess. I guess the ultimate thing we think of, if we're thinking of a, a game that has got even the pieces, kings and queens are, are fighting each other to the death. Well, when we are playing all of these different games, each game has its own particular flavor and the experience of playing the game we'll depend on various factors. And as part of our kind of exploration of the mathematics of games, I'm gonna just mention three factors that really influence our experience of each game. The first one is how complicated are the rules? And there's a continuum. We can think of low complication, uh, something like naughts and crosses, otherwise known as tic-tac toe or X's and O's. In some places, that is a game I can explain. I'm sure you all know the rules, but we can explain the rules of that very, very quickly. We've got a square board, three by three. Uh, each player plays their counters in turn crosses and naughts. You take turns until somebody gets a row of three, and then that person's the winner. If it doesn't happen at all, then it's a draw, right? Done. We now fully know the rules. Very simple. Here's another very simple game. It's called domineering. This is a good game because you can play it probably with gaming pieces you already have at home. Take a chessboard, for example. You can actually play it on any size grid. And then the first player places, uh, a domino horizontally and will continue to place some horizontally. The second player plays vertically. They place their dominoes vertically, and you keep going, placing them wherever they'll fit. Each one covers two squares until somebody can't move and the last person to place a domino wins. So at some point, the board is filled, there isn't enough space, and the last person who's actually managed to put a domino down will win. This isn't the the complete game. So again, super simple rules, very easy to, to learn the rules very, very quickly so that those games are at the low end of the complexity, uh, spectrum. Then a bit higher. The medium kind of games will be chess, back gam, and those kind of games where obviously we couldn't explain the rules in a minute, but if we spent an afternoon playing those games, then, then, you know, you'd know that what the rules are. And you'd, you wouldn't have mastered them, of course, but you would at least know what the rules are. Now, there are higher levels of complication in games, and I had a look around what, what might be the most complicated game or the most complicated set of rules. I think it's this, this game. The campaign for North Africa almost isn't a game. I mean, what is a game? It's more of like a very, very long history lesson. So it's, it's recreating, um, this part of the, the action in the second World War with the opposing forces in North Africa. Um, the board is divided into hexagonal cells. Each turn. You have, you have to do a whole long series of things. You've got to, I think you always have to invade malter for some reason, but <laugh>, poor Malter. Um, but, but you have to do, you have to make sure your troops have fuel and food and water and the detail. Here are some of the instruction books, things you need. The detail is extremely, extremely, uh, precise. For example, uh, the troops have to have enough fuel. So everyone except the British troops, their fuel stores evaporate at a rate of, I think it's 3% per turn. The, the British fuel evaporates at a rate of 7% per turn. The reason for that is that in the actual second World War, everyone except the British stored their fuel in 50 gallon, uh, barrels or tanks. And, um, the British stored theirs in small jerry cans. So there's evaporated faster. This is the level of precision of this game. Uh, here is the board. It's over three meters long. It's been estimated a single game would take, uh, 1500 hours to play. Like your first game of this just, you know, kind of a practice game. Um, if you give up everything else, give up school, give up work, and full-time, spend 35 hours a week playing this, it's gonna take you 43 weeks. And then, you know, if you do win, your opponent immediately wants a rematch, right? So it's, it's a full-time job. This is on the high end of the complexity level. There it is. Um, we are going to concentrate much more on, on the games over to the left hand side. So that's complexity of rules, how complicated the rules are. The second aspect, how many players game, obviously that's a very important, uh, part of the game. Now, there's kind of no upper limit theoretically, but we are sitting round a board. So there's a practical limit. Um, most games have, you know, single figure number of players that are ideal. I did find one that had seven players designed for seven players. This is called astronomical chess. I don't know why it's got nothing to do with chess. But you can see the board is heta. Seven people can play, uh, a game like Monopoly. Classic Monopoly has six tokens, so up to six people can play, but most board games are based on square boards. And that lends itself to four players, a maximum of four players like Ludo. Here you're set up one person at each corner. So at most, four players is quite common. Three people can play this game. Um, but if you a good game perhaps for three players, um, it's Chinese checkers. Uh, it's nothing to do with checkers. It's also not Chinese having been invented in Germany in 1892. But nevermind <laugh> good for the marketing, right? So this game, because it's the board is a hexagonal or a six pointed star, it's quite good for three players because if there's three of you, then, um, everyone has a, an opposite pair of triangular, uh, sets of counters. So that's okay for three people. But the games we're gonna focus on today, the board games today are going to be two player games. Um, like all the classics, you know, draft checkers, man, Carla, all its variants, uh, backgammon, chess, uh, those, those and naughts and crosses and, and many others. Now, of course you need two people at least to play a game, don't you? Well, no. Solitaire is a game you can play for one player. So this is a game where you have to, uh, take marbles by jumping over them. And the ultimate aim is to end up with just one marble left. It's quite challenging and difficult, but very good fun. Uh, okay, well, okay, game for one player. You can't have a game for zero players though, can you? Well, <laugh> well, I give you, I give you John Conway a great mathematician, and he invented the game of life. So this is an example of what's called a cellular automaton. Actually it's a game that plays itself a game for zero players. All you do is you pick an initial configuration. So that's the only input. Uh, and you put, so the configuration is you have a as large as you like square grid, and then you select some of the cells, some of the squares are going to be alive to begin with. I've colored them green there, greenish. Um, and then at every step there's a precise collection of rules. There's a precise algorithm for what happens next. And so cells come alive or die according to various rules. And the rules say it's called sort of somehow mimicking a population growth. And it says, okay, if a cell doesn't have enough neighbors, it's gonna die because it's too isolated. Uh, and if a live cell has too many neighbors, it will die because of overpopulation. So what are the neighbors of a cell? Well, every cell, this one here, every cell has eight neighbors. The immediately surrounding eight squares. So if there's a live cell and it has fewer than two neighbors, it dies, or more than three neighbors, it dies. And if the other cells that aren't live, they're dead cells, any dead cell that has exactly three live neighbors will be become alive next time round and everything else stays the same. So you can see what happens with this initial configuration. Um, the live cells at the corners of the rectangle, they each have exactly three neighbors. So no change, they stay alive. But the ones in the middle of the rectangle, they have five neighbors, five live neighbors. And so their overpopulation, well they will die. And as a couple of cells, the cells are immediately above and below the middle ones. They have three live neighbors. So they become alive. So that's the rules. Uh, this configuration now is actually quite interesting one because this stays the same at this point, no dead cell has exactly three live neighbors and all the live cells have two live neighbors. So everything stays the same. So it's just fixed at that point. But there are so many amazing and interesting things that can happen in this game. This is a real object of study and interest to mathematicians. This kind of thing can happen. So in this situation, it sort of cycles periodically through, um, the same three designs forever and ever and ever. Um, you can make spaceships, this one's called a glider and it carries on forever and ever and ever moving diagonally down the down the board, um, to infinity. You can make machines. This is a machine, it's called go's gun. It fires gliders and regular intervals forever. This is fantastic. You can do so much with this game. Um, depending on the initial configuration, you can have, you can create, um, machines that are self-replicating. You can create logic gates and if you can make logic gates, you can make computers. And if you can make computers, maybe you can make a computer that plays the game of life. So there's so much fun to be had with this, with this game for zero players. So the, that, those are the extremes. How many plays you can get. The third really crucial, uh, characteristic of any game is what proportion is chance and what proportion is skill. Um, here is the kind of spectrum here at the bottom, a hundred percent chance you don't get to make any decisions, you just follow what the role of the dice will tell you to do. Snakes and ladders is in that category. Um, you don't, you don't get to make any decisions at all in the middle there. We've got games like backgammon where there is lots of skill involved, but there's also some, uh, chance and luck because you are rolling dice to determine, um, how, how many steps you can take at the top. And this already tells us we're going to need to something more than this. Um, chance versus skill spectrum because games that are a hundred percent skill include naughts and crosses, which obviously you don't, it's not a very hard game, but you are making all the decisions there. There's no luck involved. Uh, connect four is another one, chess. So those kind of games, and these are the ones we want to consider and talk about more the rest of our time. So from now on, the board games we're gonna talk about are going to be games for two players that do not involve chance. So it's pure skill, maybe not very much skill, but pure skill. And the final technical requirement I'll mention is that we, they should be games that have perfect information. What that means is the players both have access to all the information about the game. No one's got any secret hidden things. We're not playing cludo or anything where they, where everyone's got a sort of different piece of the puzzle that they can see. Everyone knows exactly what's happening in the game all times. So those kind of games are, are what we're going to think about. And we can already see, as I've said, um, just knowing that a game is a hundred percent skill, 0% chance does not really tell us how hard that game is. We know naughts and crosses is easier than chess. So how are we gonna sort of tease out those differences? Here's where we start to think about complexity. So the first measure of complexity in this context is what's called the state space complexity. And the question really is we're asking there is how many different positions can the game be in during the course of play? Because if there's, you know, if there's only three different configurations we can be in, we could learn each one and we could learn what to do. And that would mean presumably it's quite an easy game. But if there's a hundred billion squillion, uh, that's a big number <laugh> of positions that maybe then it's harder to develop a strategy. So this is one measure, it's called the state space complexity. So we can do a couple of small examples, knots and crosses. Uh, how could we measure, count the number of possible ways that the board could look? Um, well we can say okay, there's nine squares and any one point each square is either empty, it's got a cross in it or it's got a naught in it. So there are three possibilities for each square. And there are nine squares. So it's three for the first square times, three for the second times, three times three times three and so on. That gives you three to the nine possible configurations, which is sort of 19 and a bit thousand. But that's clearly an overestimate. Why is it clearly an overestimate? Because it includes things like this that can never arise, that can never happen in a game of lots and crosses because uh, we alternate. So let me just know, pick one to go first, but let's say crosses go first, then we go cross, put a cross down and then a naught and then a cross and then a naught. So you never get all crosses on the board. So we can count in a slightly different way. We can say okay, we could have a completely empty board with no pieces. That's one possibility. Or what about if it just has one piece? So where can the cross go? There's nine places it could go. So there's nine boards that have one piece. What about having two pieces? Well, there's nine places to put the cross times eight places, there's one fewer available to put the north. So nine times 8 72 and you can carry on like this. The calculations get a bit more complicated, but you can carry on like this, it's not too bad. And you come out at about 6,000 possibilities. So the state space complexity, we could estimate a 6,000. That's what you can do without having to think too hard. But it has to be said. There are still some duplicates and repetitions here, or sorry, not repetitions, some illegal spaces here because this for example, can never arise. We never get both players having three in a row.'cause when you get three in a row, you've won the game finishes. So this game would've finished when we got three crosses. So this can never arise that configuration. So if we eliminate those illegal, uh, configurations and just stick with the legal ones, which you can sort of do by brute force, it's about five and a half thousand. There's one more efficiency saving that we can make. And that is to do with symmetry. This configuration really is the same as this one.'cause all you've done is rotated the board. It doesn't actually affect anything about the game to do that. So there are various, you can reflect, you can rotate and end up with basically the same game, um, with not any difference made to any strategy you might develop. If you do that, um, then you actually reach a smaller number 765 and that is the state space. Complexity of NSS and crosses feels like a lot, right? If we're of such a simple game. But as we'll see, this is nothing <laugh>, this is nothing. Let's look at a slightly more complicated game, uh, north, not norths and crosses, uh, connect four. So this is played on a vertical board and the aim here is not to make a row of three, but to make a row of four vertically horizontally or diagonally somewhere in that board. Um, there are seven columns. Each one has space for six counters. Um, you play, so one player is red counters, one is yellow. You alt, you alternate putting them in. Um, of course they will drop down to the bottom of, uh, as far as down as they can go in the given column that you put them into. Uh, and then the first person to make a row of four, we'll win. So in this case, we can't do that thing we did for Ns and crosses of saying every space is either empty, red or yellow. Because if you've got an empty space at the bottom, then you can't have anything, you can't have any full spaces above it 'cause they just fall out. So we have to think slightly differently here. Let's imagine a single column. This by the way, is my favorite slide of the entire talk. Very, very exciting. I'm so happy that I managed to do this. So I've, each column, it could be empty, right? That's one possibility. Let's say we have one counter <laugh>, so proud. Um, so it could be red, right? Or it could be yellow. Uh, there's two possibilities. Then what about if we have two counters? So there's two possibilities for the bottom one, and then the next one can either be red or it can be yellow. So two times two is four possibilities for having two counters. And if there were three counters, it's times two again and four and five and six, so on. So you can add up all of these. You get 127. So this is how many different ways you can partially or fully fill this column. But we've over counted again, there are some illegal positions in here. You could have four yellow counters that would win you the game, but you then would never, you'd never see a fifth counter going in because the game is over. So there are some illegal configurations in there. If you take away those, you get 111 legal columns. So you could say, all right, well there are seven columns, each one 111 possibilities. So we'll do 111 raise to the power seven. That's the, uh, state space complexity. That's about 200 trillion. You could do that <laugh>, but that would be again, an overestimate. Why? Because obviously the columns are not just in isolation. Um, you have seven of them next to each other. And if you at any point get a horizontal line of four of the same color or a diagonal line, then the game finishes. So this is an overestimate. It's not too bad, but it still is, is too many. It can be calculated by brute force, not by me.<laugh> a computer calculated that actually there's about four and a half trillion possible genuine, valid legal positions that the game can be in, in connect for. That's the state space complexity. Now normally we, we can't, we can't give an exact answer anything much more complicated. I mean, this is already far too hard for a human to do. Um, but you know, you get tired and fall over. You can't calculate an exact answer usually. So normally we just say what it is to the nearest power of 10 best estimate. So for this, it would be 10 to the power of 13. Uh, for Norths and crosses, 10 cubed is the nearest power of 10. Well, that's one thing we can calculate the number of different configurations, but actually maybe what we're interested in is how many different games you can play, how many different ways there are through the game to the end. Because any of these configurations might turn up in lots of different games. Really, we, if we think about how we can make a strategy, we might be interested in what are the different outcomes of the game and how we get there. So the different games that can be played. And to explore that, we need something called the game tree. So the game tree, by the way, I have to warn you, mathematical trees are always upside down.<laugh>, um, trees have branches, right? And so this is a tree because we're going to, at each point our decision about what to do next, the possible moves are going to be branches that come outta that point. And then we'll get smaller and smaller and smaller branches. So here's my tree. This is the beginning of a game of naughts and crosses. So starts off with an empty board. Uh, crosses go first. There are basically three choices. The cross can go in the center, it can go at a corner, or it can go in the middle of an edge. That's your, that's your option. So three branches. And then let's take the left hand branch. What can naughts do? Where, where can we put our naught? Well, there's, again, there's, there's two options. This time, really, once you take account of moving the board, you know, rotating the board, you can either put your naught in the middle of a, an edge or you can put it at a corner. Two options. And there are other, there are more options in the other cases, which I'm not going to draw. And more options. And you can keep going and keep going. This already is too big to fit on a slide <laugh>. Um, so this even NSS and crosses the game tree is sort of big for a human being to, to actually conceive of. I wanted to give you a full game tree. It won't be for NSS and crosses. So I picked domineering, remember we talked about domineering, but like on a chessboard, you can play it on a smaller board. Same rules. Um, player one places their dominoes horizontally, player two places them vertically. So if you are playing a game of three by three domineering, there are just two choices really for where you can put your first domino. You can rotate the board yet and reflect it. But basically either you can put your domino along an edge or you can put it so that it covers the center square. Those are your options. Now let's, let's focus in on the left hand side, the left hand fork of this. What can red do? Player two, they've got to put their domino vertically. And there are four, you can easily see there are four places they could put it in one of these places. This one, that's a winning move because where can blue put a horizontal domino? Nowhere. There's no space for a horizontal domino after, uh, at this point. So red has won the game at that point. Um, but the other three are not yet a victory for anybody. So you carry on. Um, here is that whole left branch here is the whole game tree. We're not going to look in detail at it, but I wanted to, at least I, I feel I've managed to fit one on a slide that that's the smallest possible game I could think of that made any kind of sense to do. Um, here is the whole tree. Now at these end points where the game finishes, these are called the leaves of the tree for obvious reasons. That's the last thing you get on a tree. And here they are. I've highlighted them all the game tree size. Um, that is the word we use for the number of leaves on the game tree. And that is because each one of those represents an individual, a specific game. So you can follow back from a leaf, you can follow all the back to the beginning. You can see all the moves that have been made. It specifies a unique game. And these are all the possible games. There are 11, um, eight of them are one by blue, three of them are one by red. So that's the game tree. In this very, very tiny example, 11 games are possible. Um, there's a related concept which I intend immediately to conflate with game tree size. And its game tree complexity. It's slightly different because this is the number of leaves on the smallest part of the game tree that allows to fully determine the outcome if everyone's playing optimally. So not just sort of moving at random, um, maybe you choose the best move in each case, as we saw, you know, if red chooses that particular move, they can win straight away on their first move. Um, so we don't really worry about the other little bits of the tree however often. In fact, almost always we are having to estimate this. We don't know this. So we say, we'll estimate it by estimating the game tree size, the total number of leaves. That itself is also an estimate almost always. And so I'm basically, as I said, I'm gonna essentially treat these as if they're the same thing because almost always our estimates are estimates for for both of those. Okay, so here's a few little examples. Game tree complexity. So three by three domineering 10 to the power one. As I said, we always pick the nearest power of 10 naughts and crosses 10 to the five. And the exact number is there. I've said assuming arbitrary stupidity. You don't even notice that your opponent has two crosses already and you should fill in the, the gap there. I'm, I'm taking account all possible moves, uh, almost absent minded, not paying attention. Um, this is the size of the game tree connect. Four bigger, 10 to the 21 possible games of connect four, eight by eight domineering the full size one bigger than that, even 10 to the 27. So it grows very quickly. We can see why at some point we just, we approximate. We do not want to count actually the exact number of games of eight by eight domineering or whatever. It's, so this is all interesting stuff. But of course when we play a game, we usually want to win. Can this help us win? Can we use this, all this stuff for the game sheet complexity to find a winning strategy? Well, if you happen to actually have the whole game tree, then yes, of course you can, uh, say you are blue, you're the first player in three by three domineering. Look at the right hand branch of that tree. You can see every outcome. There is a win for blue. So to win this game, all blue needs to do is make sure they're in the right hand fork. In other words, their move should be cover the central, uh, the central square and that will win for them. So we can find a strategy if we have the whole game tree by just sort of looking at what the best option is at any moment. Normally we don't have the whole game tree because they get very, very big. Um, but this game we could say absolutely we, this is a solved problem. So we say a game is solved. If we, if we know how to get the best outcome possible, we might not always be able to win. Maybe we can force a draw at least. But, but that's what we mean by saying it's solved. However, there are, there are little qualifiers to the word solved. There are three kinds of being solved. You can be strongly solved like three by three domineering. That means you can be parachuted into the game at any point. Whatever's happened so far. And you, there'll be an algorithm that tells you how to make the best of it. You might not always be able to win, but how to make the best outcome, um, starting from any point weekly solved is there's an algorithm known from the start of the game that will give you the best outcome you can achieve. And then there's this weird category, ultra weekly solved, which says there is an algorithm which will allow the best outcome from the beginning of the game, but we don't know what it is <laugh> seems. How can that be? Well, we'll we'll come back to that. So examples of strongly solved games three by three domineering and connect four both strongly solved. Um, three by three domineering. We already know the strategy. It's try and cover the central square and actually works for red as well. If blue fails to cover the central square, if red then does cover the central square, red will win. So that's a full strategy that works throughout the game. Connect four, I'm not going to tell you the full strategy because although the first player can guarantee a win, it will take, um, up to 41 moves for them to do that. So I'm not gonna talk you through those 41 moves, but I will just mention that it's crucial what you do first. So that little kind of schematic there tells you if the first player plays, um, the middle column, then they can force a win. If they go in either column immediately adjacent, they can only guarantee a draw. And if they go in any of the four outer columns, the second player can guarantee to win if they're playing optimally. So those are strongly solved. Some weekly solved games we know about drafts, a k a Checkers, nine Men's Morris, those are both weekly solved as a strategy from the start of the game. What about this ultra weekly solved thing that which is so weird? Well, I'm gonna present to you, this is gonna be a brilliant game if you've never played this. Um, it's the only game I know of that involves eating the board. As you go along, be careful what your board is made of. So this game is called chomp. Uh, so it's, you have a rectangular board of some dimensions. You can determine advance and the idea is when it's your turn, you eat a square and then you have to eat all the squares below it and to the right. So you keep going doing that's an example game here. And we all know it's really rude when you're sharing a bar of chocolate to be the one who eats the last cue. Yes, that's really rude. So as a penalty for this terribly rude behavior, the person who eats the last square loses the game. Okay? So this game, you either win or you lose. I claim that there is a strategy that will allow player one always to win. There's no draw this game 'cause someone will end up eating this square. Um, but I dunno what the strategy is. It's may not be very helpful, but we can prove that there is one. And what you do is this, let's say that's not true. Let's say that player one cannot, doesn't have a strategy like this so that we player two, um, could force a win. If player two could force a win, then they've got a strategy that whatever player one does, they, they've got something that they can counter that and ultimately win. Okay? So what player one will do is this. Say, okay, if I were to, if my first move is to eat the bottom right hand square, then player two we know by our assumption, which is gonna turn out to be wrong by this assumption, is going to have a counter to that. Some counter move X, we dunno what it's, now what Player one is now going to do is to steal that strategy. It player one steals that strategy and instead they don't open with bottom right hand square, they begin with move X and, and, and obviously have the rest of the strategy in mind. So you might think, okay, it looks like they're in the same position now that player two would've been in and player two can, can win. But, um, but maybe, well maybe it's not because the bottom right hand square is already missing. So maybe it's not identical. However, in this game, remember whatever square you eat, you always eat all the ones below and to the right. So any move you make will involve, um, eating the bottom right hand square if it hasn't already been eaten. So after this move X, whatever it is, the bottom right hand square will not be there. So this is indistinguishable from first eating the bottom right hand square, then doing whatever move X is. Uh, so this really is, uh, you can steal their strategy, um, without any worries, apart from the moral worries. Um, so player one can always win. So this is, this is, this proves that this game is ultra weekly solved player. One can always win. It's just we don't know how. So I suggest we all go home and practice extensively <laugh> this game until we know what the strategy is. Okay? So there are levels of being solved, but let's talk about chess. Chess is not even ultra weekly solved. However, we all also know that computers are very good at chess and can beat even the best players. So how that's, how is that happening? Well, it's interesting that in fact, machines that play chess are older than we might think. In 1770 a, uh, a chess playing automaton called the mechanical Turk wowed the world, this, um, automaton. So that's not a human there. That's this automaton that, that moves and plays chess against you. It toured Europe and America for 80 years, and it played chess against and beat both Napoleon Bonaparte and Benjamin Franklin. And, uh, ed Gar Poe wrote an essay about this and he thought it was a hoax. Um, he said, and here's his reasoning, and I find it very interesting that this is the reasoning. He said, it can't be a machine because machines have a, you know, a thing that thing that they follow, a process that they follow, they don't make mistakes. They're not like, you know, there's no human error with a machine. So the fact that this machine sometimes loses it's very good, but it doesn't always win, therefore it must be, um, a hoax. There must be a human who's secretly playing. That's a very interesting take. Um, I mean, it's wrong <laugh>, it's a wrong take. But sadly, the conclusion, even though the argument was wrong, the conclusion was correct here is, here is the inside of this, uh, machine. You, because there's lots of, uh, you know, gears and levers and stuff going on, but the suspicious, large empty space on the right hand side and even more suspicious a r and a little cushion <laugh> almost as if to make someone more comfortable. And indeed, unfortunately, that this was, it was a hoax. So inside this machine, there was a, a very, very good chess player. And there we even know the names of some of the good chess players who, who were actually playing being the mechanical turk over the years. They were playing against a human, a very good human, but yeah, it was not really a chess playing machine. So when's the first chess playing machine you gonna be thinking? What do you think it is? Well, would 1912 surprise you? Okay, slight Doral of this. It was a machine that could play a specific special kind of sub game of chess. It knew how to play a particular end game and to win at that end game. The end game in question is where you've, where the, the machine has an a king and a rook and the human player just has a king. So obviously the machine, slight advantage, slight advantage, but this, it was still pretty amazing for that time that, that this could be done, the machine could be built that would do this without any human involvement. And the reason it could do it is because that very specific sub game is strongly solved. There's an algorithm that can be followed by a machine, uh, kind of mechanically and it would win every time. That's pretty amazing. It wowed the world when it was put on show in Paris in 1914. But what about, okay, what about real chess computers? When does these start to come in? Well, there's a groundbreaking paper in 1950 by the mathematician Claude Shannon, that here's who wrote a paper called Programming a Computer for playing chess. And he wasn't saying like, here's my program. He was saying, what are the challenges of this? And then how might we address them? And in that, um, he, it was kind of the really early paper in this sort of area, and he talked about the complexity of chess. So he was thinking like, how many possible games of chess are there, what we now call the game tree, uh, complexity. So here's how he did the calculation. It's very difficult to, to do this. Here's a good estimate. So the first thing you need is what's called the branching number. When you're playing a typical game, think of the game tree. How many branches are coming out of each node on average? So it's not always exactly 30, but the average number is 30, might be less at the end of the game when you've only got your king left or whatever. But on average during gameplay it's 30. How long does the game last? Oh, so yeah, what's a move in chess? This is sort of technicality, but a move actually strictly speaking, in chess, not in all games, but in chess it's why does something then black does something. So actually that's what we might actually think of as two moves to make this distinction in the area of, um, game complexity theory, uh, or combinatorial game theory, which is what we're talking about now, that that's the name for the mathematical, uh, subject we are talking about. Um, to make this distinction, we say like a turn for an individual player is called apply, and the plural is applies. So a move here is apply for white and then apply for red, uh, for red for black. So if there's 30 choices for each ply, then a white, then black move would be roughly 30 squared, which to the nearest power of 10 is 1,010 cubed. Okay? So we know how much choice you have for each move. How many moves are there in a game? Well, data from lots and lots of games says that in, in a game between good players, there are about 40 moves, 40 kind of exchanges of turns. Now the game between good players is important. Bad players tend to fight to the death when they should resign. I should know I'm a bad player <laugh>, so their game's gone a lot longer. But, uh, but yeah, about 40 moves. So you can then use that to estimate the game tree, uh, complexity because you say, okay, at each of these 40 moves, there are a thousand options. So it's sort of 10 to the three times 40 10 to the 120. That's now known as the Shannon number. It was a kind of an early estimate for the game complexity of chess. Now even modern computers have an upper limit of around a quintillion calculations, a second 10 to the 18. There's no way that can happen. They're not gonna be able to find the whole game tree. So we've got to think of something else. Well, what about says Shannon? Uh, what about instead we imagine a database, a computer could have a database of all the possible legal positions. So now he's talking about the state space complexity, right? How many legal positions might there be? And then so a lot, let's see if we can have an estimate for it. He says, um, and then you could imagine in your database you have each legal position and then the best move when you're in that position. So can we estimate that how many legal positions there are? What's the state space complexity? Well, here's a chess board, it's got 64 squares. There are some pieces, uh, each side, each player has 16 pieces at least to begin with. So 32 pieces and they've got to go on the board. Let's forget that sometimes, you know, there are fewer pieces than that. Let's just pretend we are looking at when there are 32 pieces on the board, where are they going to go? If you want to worry about, sometimes there aren't on the board, perhaps you say there are 65 squares on the board and some of the pieces may be in square 65 i e they've been taken. But just for the moment, let's have 64 squares like, like we would expect and we've got to put 32 pieces. So let's say the white king, uh, he's got th uh, 64 places it could go. Um, so 64 choices for that. Then where's the white queen gonna go? There are 63 remaining squares. The white queen can go in and so on and so on and so on. And so you get something like this all the way down to 33 places for the very last of the 32 pieces you're going to put down leaving 32 blank squares at the end. So is it that, is that a good estimate? No <laugh>, it's really not. I mean there are many reasons why it's not, but there are one important one that, that Shannon, uh, takes account of in his calculation in his paper is that this duplicates an awful lot. Here's why. There are several pieces that there's more than one of. So for example, uh, white has two rooks and when you, you know, put all the pieces down, you can't distinguish which one of those rooks was placed down first. So that means you're gonna get that precise configuration twice. Um, you know, the first one goes down on the green square or the first one goes down on the white square. So you've, you, you've doubled the amount of, um, positions that you are trying to count. So you've gotta divide by two 'cause of that. And there are lots of pairs of pieces, um, knights, bishops, so on. There are six pairs of pieces for which you have to worry about this. And even worse or better, depending on which way you're looking at it, each, each player has eight pawns, eight indistinguishable pawns. I mean, that's where they might start off at the beginning of the game, but we are looking at where could they possibly end up, you know, at some far point in, in the, in the middle of the game. So those eight pawns could again, have appeared in any order and still look like the same configuration. So I won't go into the details of it, but this is the, um, equation or the, the, the formula that, that Shannon came up with for this estimate of the, uh, the state space size. So you've got that 64 times 63 all the way down on the top, but then you're dividing by two, six times because of all those pairs. And then you're dividing by this thing eight factorial, which if you dunno what eight factorial is, don't worry about it. But that takes account of the pawns and there are two sets of pawns, that's why it's squared. So this is the calculation Shannon did and that comes out at about 10 to the power 43, which again is a big number, very big number. And if even if you were able to put each individual position and what to do next on one single atom of silicon, um, your computer that can store all this information is going to have to be quite heavy because 10 to the 43 atoms of silicon weighs 600 trillion tons. So no, that's not gonna work either. Okay? But we still are sitting here saying, we know there are chess playing computers. So Shannon says, okay, don't despair, thank you. We, there are, there are things we can do, what can we do? We can't learn the whole game tree, but we can think a few moves ahead. We can calculate the next few levels of the game free from where we are. Maybe three moves. So six plays, so each player has three goes. Now that feels like, oh, not gonna be too awful, too big. Actually it does get quite big. So even from the beginning of a game of chess, if, if, if you do white moves, black, white, black, white, black that already think of what it might be, how many different games have we created by doing that? 119 million. Even with that, it's crazy. Um, and I actually some of those have already finished, right? If you, if fool's mate can be done in, in, in a very few number of moves. But yeah, 119 million games, um, just in three moves. So this is still a lot, but computers can handle these big numbers. So that's one thing you do look a few moves ahead and pick the best move based on what though? Well you can rank them according to some carefully chosen function. For instance, um, it's well known sort of rule of thumb in chess that um, the queen is, I mean obviously the king is infinitely valuable, but the other pieces that you can lose, the queen sort of scores nine, um, I think the rook is seven and then you work down and the porn is one. So you could score the number of pieces that you have left on the board versus your opponent. Um, if you've lost your queen, that's worse than if you've only lost a pawn. So you can rank them in in various ways and then pick, somehow pick the best move to play based on looking three moves ahead. Uh, you can also incorporate some standard openings and, and end games so that you know what to do in those standard situations. There are still some issues with this. The first one is what's called the horizon problem. Well that's the main one actually the horizon problem. This is where maybe some amazingly brilliant uh, strategic maneuver that gets you to checkmate four moves from now, but begins with you sacrificing your queen. If you're only looking three moves ahead, um, you're not gonna spot that. So you miss that opportunity. So this problem of the horizon prevents strategies that might be very successful or things that look good but actually turn out to be catastrophic errors. You don't spot them 'cause they're just over the horizon. Now this init for early chess programs, this is a huge issue, but, um, developments including something called quiescence searching have improved this. So quiescence searching looks at it, doesn't uniformly search the same number of moves ahead. It kind of looks at how in how much of a state of fluxx the game is at that if you do that particular move. So suddenly, like if you lose your queen, that's a very interesting thing to have suddenly happened. It looks a bit further down that branch then it does for something where nothing much is happening. Maybe you just moved your porn forward one space. So it's not perfect. But these kind of things where there's a way of assessing how exciting or dynamic the game is at that moment and looking a bit further along those branches and less far along others means with the same amount of processing power, you can do a more intelligent search. And with these, uh, innovations and others, as I've said, chess, uh, chess programs can now beat even the best players in the world. So chess is complex, it's unsolved, but although it's theoretically unsolved kind of for practical purposes, it sort of is solved. Um, so are there any harder games? Let's look at what we've got kind of a few examples so far. We can see there is this kind of correlation between the game tree complexity and how whether the thing is solved. So the lowest game tree complexity that we see, you know, your naughts and crosses connect four strongly solved strategy from any point. The next one's up, these are quite high, 10 to the 40, 10 to 50. Those are weekly solved. So they can be solved, but not to the same extent. Chess is unsolved with 10 to the one 20, but computers can, can beat us. So if we use as a proxy for hard, um, highest game tree complexity, is there a game that's harder than chess? Now there are some games that, but I'm not gonna talk about them.<laugh>. I've got sort of five minutes. I'm gonna talk about a particular game that is played by millions of people. I'm not gonna talk about infinite chess or billion by a billion domineering. Yes, those would have higher complexity, but no one's playing them. One game that people do play is go, this is a very ancient game. Um, you play it on a 19 by 19 grid, but it's not 19 squares, it's 19 lines. And you put your stones, the counters are called stones on the intersection points there on the points, the grid points. And this game, it's, it's a strategy game. The aim is to capture territory. So just so little examples, beginners are advised usually to play on a nine by nine grid. I e essentially like a chess board. You've probably got one of those already. Um, so what you do is you try and capture territory. Black goes first, then white, you alternate, you put the, your stones on the grid points and you try and capture territory. So at the end of the game, um, anything that is completely encircled by either your color stones or the edges of the board is yours. You can also take prisoners. So that thing, um, that letter a there says at some point in the game, this is a finished game that we're just showing you at some point in the game there was a white stone there. But then black engulfed it as you can see happening in the right two, uh, pictures. And when that happens, when black or or white completely takes and encloses account of another color, it takes it prisoner. So at the end of the game, you count up how many points of territory you've got and add, add on any prisoners you've got, you get a total. In this example black has 16, but white, even though white has no prisoners, white has more territory. So white wins by one point is example. Now there are some subtleties which I'm not going to talk about, um, that prevent things like constant flip-flopping between two states where you constantly are taking a prisoner and then being captured and losing a person and lose and then winning a person again. So the coru, for example, deals with that kind of situation to avoid an eternal game that comes from the, I believe the Japanese word for eternity. So this, this game then go, uh, how complex is it? Oh, by the way, yes. Plug for British Go Association. Oh see association in your country wherever you're watching this. But that, those diagrams come from their website, they kindly allowed me to use them. And there are loads of people across the world who play ghost. If you're interested there you will find many friends who will play with you. So how complex is go, let's do a comparison with chess state space, complexity of go. So the number of possible configurations. Chess was about 10 to the 43. What about go? It's got, so the little go board there, nine by nine. That means there are 90, uh, 81 places, nine squared, 81 places, um, that you can put counters. Each one at any point is either empty or has a Blackstone or a white stone. So three choices, 81, uh, points, that's about 10 to the power 38, uh, not too far off chess, but 19 by 19, which is the standard size. Now there are 19 squared places you can place your counters. And three to the power 361, which is 19 squared is about 10 to the power 1 71 with 170 zeros after it. Way, way, way hugely more complex state space than chess, uh, what about the game space complexity? Chess 10 to the one 20, that's Shannon's number. Um, in Go, you can do the same kind of estimate. This time, an average go game lasts 150 plays on average. And the branching number this time is ridiculous. There are on average 250 moves you can make. And so when you combine those together, you get a crazy game tree complexity of 10 to the 360. So again, way, way more complex than chess. So where does this leave us in terms of computers? Computers can beat us at chess. What about Go? It's what The techniques that, that allow computers to play chess quite often are gonna fall over with Go. It's just too big, but there are ways to attack it. Um, so can a machine ever beat us at go? Well, let's see. Nowadays we haveis. And so an AI called Alpha Go, um, was one of the first to combine Monte Carlo methods with deep learning. So what does that mean? Well, Monte Carlo methods are, what you do is each point, instead of going like many, many moves ahead, you try out a move. And what, and the way you test it is you do that move and then you play against yourself, let's say a thousand different games at each point, choosing at random what to do next. So you do, you play a thousand or 10,000 random games to the end and see who wins. And then that gives you a kind of a waiting for that move at the, the one that wins the most random games in this process is the one you're gonna pick. And the learning is because you then remember and you learn by your experience. So ai, um, like AlphaGo have through this other techniques become very, very good at go to the extent that in 2016, AlphaGo beat the then world champion, go, uh, by several games and you know, okay, is it all over? Well, it's not quite all over. I've good news for you. This very year, a human bounced back came back and beat a top AI by a massive 14 games. And the way he did it was to exploit exactly the horizon problem. We mentioned in chess, uh, that these machines are very good, but they can't look too far ahead. Even with this Monte Carlo thing, if there's a really good strategy, but it's, you know, that's one thing to do. Out of a million choices, the computer may not see it. And indeed he exploited this. He played a really long-term strategy that the machine did not see coming until too late. So there is hope for the humans <laugh>, there's hope for the humans still. We'll see how that one continues to play out. Um, so we love board games. We love them because in our leisure time we like to use our brains why you're all here watching this lecture. We don't like to just sit around. We like to use our brains playing games. It's one way of doing it. Solving puzzles is another. And that's gonna be the subject of my next lecture, which you're very welcome to come along to, um, on the Masses p Sudoku. But for now, I will stop. Thank you very much. Okay, so we've got time for a couple of questions. Uh, remember, uh, if you could use the Slido that, and the good news is if we don't get time to get to the questions, uh, if you send to Slido, there might be a chance that we'll be able to come back to Sarah a bit later on, um, with our podcast series. Any further questions. So don't worry, we will try. If, if you've got a burning question, we will definitely try and get it to Sarah one way or another. However, we do have a couple of questions to start off with. Now, Sarah, um, so I'm going to, I'm going, where is it? Here we go. So we have one question. Are quantum computers likely to be able to solve chess? And to which I think we could safely add go there too. Now, I dunno how you are with quantum computing. So I, yeah, I, when I was researching this talk, that exact question occurred to me and I thought maybe it's like we hear they're gonna, you know, smash cryptography, quantum computers. So I had a little look at this and it seems that in fact, not necessarily in that the things that quantum computers are super good at are not quite what you need to fully search a game tree. So as far as I can tell, actually, it's not gonna be a magic bullet for this, um, unless some amazingly wonderful new concept is, is thought of. Um, but you know, at any point we can, we can invent a new method. So with, you know, these new methods like quiescence searching or, or Monte Carlo search methods, each of these have been like, overused the word, but game changers <laugh> in, in this space of suddenly revolutionizing what's possible and go playing computers went from like amateur level to, you know, Dan level of, of, of brilliance super fast when, when Monte Carlo search, uh, was, was incorporated. Yeah. So who knows? And, um, maybe sort of connected to that, I mean, we've got a great question here about, um, how do people use maths in actually coming up with ball games, do you think? And then, you know, we could add on to that. Maybe that's what quantum computing could do. It could generate new ideas for games. Yeah, yeah. So that's, that's a good question. I, I think in your, if you're designing a game, I mean there are some, even at the most basic level of if you are rolling dice, we haven't talked about that kind of game. But if you're rolling dice, what do you want the outcome to be? And for that, if you understand what the most likely outcome of a dice roll is gonna be, so if you throw, if you roll two dice, um, the most likely total is seven. So you have to, throwing a seven has to be something that it works in your game to happen a lot. Whereas throwing a six or an eight is slightly less likely. So understanding those kinds of things, even at that level of mathematical, um, understanding that is gonna help you with game design. So there's all sorts of ways that mathematics can, can, uh, can contribute to designing games that are fun to play, not too hard, not too easy, which really matters. Hi. Um, my friend and I used to play three dimensional Knotts and crosses every night, um, until we'd got to the stage where whoever started always won. Mm-hmm. So I'm assuming that that is strongly solved. Yes. Uh, yeah. But How many dimensions would you have to go up to until it's not? Well now <laugh>, I mean, how many dimensions have you got space for in your house? So if you have a handy Tesser act, it'd be fun to see how the four dimensional version, I mean, all of these games, you know, you can make bigger. So you can make a game where instead of getting three in a row, you have to get four, or there's, the board is much bigger, or as you say, you can go up, uh, higher dimensions and even so infinite chess that I mentioned, that isn't a joke. There really is a game of infinite chess. You set up, you have an unlimited square board, you set up your chess kind of configuration as normal, but then the pieces can move however they can move. So porn can still move one forward, but the queen can go as far as she wants in any direction. So that is a game. It's, and that's gonna be very, very hard and certainly is not solvable.<laugh>, oh, well I shouldn't say that. It's not solved yet, let's say. Yeah, <laugh>. So, um, we play a game at home called, uh, um, prison Rules Scrabble, which is quite similar. It means that anything, anything goes, anything goes, goes very weakly solved that one, I think <laugh>. Um, so we have an inquiry here. Why didn't you mention Hex? I know, I I knew this. Yes.<laugh>. So Hex is a very well-known game among mathematicians in the community of, uh, re game theory. I think it's fair to say. So this is a game that it's, uh, I believe Ultra Weekly solved that there's a known strategy and you can do it by this strategy stealing method on a big enough board. But I didn't mention it because I wanted to concentrate on games that most people would've played Al be at least a little bit familiar with. And Hex is less so they're brilliant resources on Hex online and yeah, it's a very fun game. Hex 'cause of the hexagonal, uh, array. But yeah, uh, uh, just focused on the games that most people will know, I guess What is meant by a game being cheering complete, Right <laugh>? Well, I, I think that what it means is that it is hard to, it, it's, you can't quite prove that these things are impossible to solve because maybe something comes along and we can do it, but it is equivalent to other problems that we know are very difficult to solve, and there's no algorithm that can do it within, um, a reasonable length of time, let's say, without getting too technical. So probably that is what is meant by that. Okay. And then we do have just one, which, which may be more of a comment, but, um, um, someone interested in why the hexagons in the campaign of North Africa, which is quite possibly the most scary game I've ever, ever seen. Um, that's Christmas taken care of. And by the way, have you found in the Heart of the Sea, Nathaniel Filbrick? Okay. No, the second question, but I will obviously be looking that up right now.<laugh>, why are there hexagons? It's actually because, so what are your choices? If you want things to fit together seamlessly, you could either have, I mean this is sort of the mathematics of how shapes fit together, but you could either have squares or you can have hexagons or you can have equilateral triangles. So I, I dunno exactly why hexagons were chosen over squares or triangles, but that is basically, you've got three options, really. Yeah. Brilliant. Okay, well, um, please join me in giving a really warm thanks to our speakers today, Sarah Hart. Thank.