What is a solved game?

0:47 Welcome to Maths Is Not Boring by kidopoly.com. I'm Mira. And I'm Finn.

0:54 A huge shout out to five-year-old Amelia in New Zealand. Amelia loves documentaries and asked a brilliant question. Why aren't mythical creatures like unicorns real?

1:06 It's such a great question, Amelia. And actually, today we are looking at an idea that feels like a myth, but is completely real.

1:15 If you haven't already, tap follow wherever you're listening so you never miss an episode.

1:20 So Amelia, today we are diving into a game that feels magical, because it is literally impossible to win, as long as everyone playing knows the secret.

1:31 Wait, impossible to win? Are we talking about Norts and Crosses? Because I just played it ten times with my sister, and every single game was a tie. I thought we were just doing it wrong.

1:42 Haha, you weren't doing it wrong, Finn. You were actually playing it perfectly. Perfect? But nobody won. That is the secret. If both people play naughts and crosses perfectly, it is guaranteed to be a draw every single time. So let's picture what we're looking at.

2:04 Right. You draw a grid of nine squares. Three rows of three, just lines crossing each other.

2:11 Exactly. You and your friend take turns drawing an O or an X in an empty square. The first person to get three in a row, sideways, up and down, or diagonally across the middle, wins the game.

2:24 It looks so simple, but you're telling me it's actually impossible to win.

2:29 It is impossible to win if both players always make their absolute best move. Mathematicians have a real name for a game like this. They call it a solved game. A solved game, like a mystery. Exactly. It means the perfect outcome is completely, 100% known from the very first move. In this game, if you play the best move and your opponent plays the best move, it forces a draw.

3:00 There are no surprises.

3:01 Wait, but how long have people known this? Did someone just sit down and map out every single game with a pencil?

3:09 People have known how to play it well for a long time, but the story gets really amazing in the year 1952 in England.

3:17 1952? That was over 70 years ago.

3:21 Yes, at Cambridge University. There was a student named Sandy Douglas, and he was doing something completely wild. He wasn't just working it out on paper. He was teaching a computer to play it.

3:36 A computer? In 1952? Did they even have normal screens back then?

3:41 Not even close. The computer Sandy used was called Edsac, and EdSAc was so incredibly big it filled an entire room. A room-sized computer playing knots and crosses? How did that even work? Well, Sandy wrote a program for it, which he called OXO. And to play against the computer, you didn't use a keyboard or a mouse.

4:06 What did you use? A real chunky rotary telephone dial. The kind that makes that satisfying clicking sound as it spins back into place.

4:16 Wait, like an old-fashioned telephone where you stick your finger in the hole and spin the dial around.

4:22 Yes! Each square on the grid was numbered 1 to 9. You spun the dial to pick your square, and the computer showed you the board on a tiny, glowing cathode ray tube screen.

4:34 That is the coolest thing ever. Imagine sitting in a room full of massive humming machines, spinning a phone dial to play a game against a giant mechanical brain.

4:44 And the giant brain never lost a single game. Because Sandy Douglas had programmed EdSAC to know exactly what a solved game is. It knew every single possible way the board could look.

4:57 Okay, but hold on. That can't be right though. There are nine squares. Every turn you have different choices. Wouldn't there be millions of ways the game could go?

5:07 It feels that way, but if you really count them, a lot of the boards are just reflections or spins of the exact same board. What do you mean? Like, imagine drawing a grid on a piece of glass. If you put your first X in the top left corner, it's exactly the same game as putting it in the bottom right corner, just spun around.

5:30 Oh, so you're just looking at it from a different angle? Exactly. When you strip away all the flipped and spun versions, there are really only three truly different opening moves. You can take a corner, an edge, or the centre square. That's it, just three. Just three. And because the total number of real different games is small enough, Sandy could figure out the perfect response for every single one.

5:58 EdSAC was unstoppable.

6:00 So if I played the giant room-sized computer, the absolute best I could do is tie it.

6:06 Yep, you could never, ever win.

6:09 That is slightly dizzying, but mostly awesome. So, Knoughts and Crosses is solved. Are all games solved? Like, what about chess? Good question! Chess is definitely not solved. Really? But we have supercomputers now, they fit in our pockets.

6:30 We do, but remember, to solve the game, you have to map out every single possible move all the way to the end, holding the whole tree of choices in your head. In Norts and Crosses, the map is small. In chess, there are more possible games than there are atoms in the observable universe.

6:50 Wait. More possible games of chess than atoms?

6:55 Yes! The map is just too huge for any computer that exists today. So nobody actually knows where the perfect chess would end in a win for the first player or a draw.

7:06 That's actually kind of a relief. But what about checkers or wait? In some places people call it drafts, right?

7:13 Yes, checkers or drafts. Now that one is a completely incredible story. For decades, mathematicians tried to solve it. Dozens of computers worked on it, almost without stopping for 18 years.

7:28 18 years? Just playing checkers against themselves day and night?

7:33 Working through every single possibility. And finally, in the year 2007, a huge team announced they had done it. Checkers was officially a solved game.

7:44 And what happens if two perfect computers play checkers?

7:48 It's a draw.

7:49 Perfect play leads straight to a tie. Just like knots and crosses. So basically, if you have a perfect brain, these games just freeze up into a big tie.

8:00 Exactly! The tension of the game, the feeling of play, comes entirely from the fact that we humans don't see the whole map.

8:08 So when we play, the fun is actually in the fact that we aren't perfect room-sized computers.

8:13 Right! And because mathematicians figured out how to map games this way, it became a whole branch of maths called game theory.

8:22 Game theory. Sounds like my kind of homework.

8:25 It's incredible! And it isn't just used for board games. By understanding how to map out choices and perfect moves, this maths now helps people plan things in the real world.

8:37 Wait, like what? What does knots and crosses have to do with the real world?

8:43 Things like traffic lights. Computers use this same kind of maths to figure out the smartest time to turn green, so cars don't have to wait.

8:52 That is brilliant! So the traffic lights are basically playing a perfect game so nobody gets stuck.

8:58 Yes. They don't just guess, they calculate the absolute best outcome. It also helps people run massive online auctions, figuring out the perfect rules, so things are fair for everyone bidding. So this idea of a solved game is really just a way of seeing a map of choices clearly, everywhere in the world.

9:19 Okay, before my brain gets completely full, do you have any mind-bending facts about this?

9:25 I do. Think about checkers again. You know how the computers took 18 years to map every possible position.

9:33 Yeah. How many positions were there? 500 billion billion. I can't even picture that number. 500 billion. Billion? Like an ocean of checkers boards.

9:46 Yes, a five with 20 zeros after it. The computer checked a vast number, but used smart maths to prove the draw, without needing to check every single board.

9:58 And all the way back in 1952, Sandy Douglas and his giant EdSAC computer started it all with just nine tiny squares. That is so cool. Alright, Finn, time for the quiz! Are you ready? Okay, I've got my game face on. First question.

10:17 What do mathematicians call a game where the perfect outcome is completely known? Next one. What year did Sandy Douglas teach a computer to play knots and crosses? Question three. What was the name of the room-sized computer Sandy used at Cambridge? Here's number four. What kind of telephone part did you have to spin to make your move against the computer?

10:55 Last question. Checkers was solved in 2007. If both players play perfectly, what is the result? Great job! Let's see how you did. The first answer is they call it a solved game. For question two, it happened in the year 1952. Number three, the answer is the computer was called EdSac. Question 4. You had to spin a real rotary telephone dial.

11:31 And the final answer is perfect checkers always ends in a draw.

11:36 You know, I'm never going to look at a simple game of naughts and crosses the same way again. Just drawing those nine squares feels like opening a map.

11:46 I feel exactly the same way. It really is a beautiful idea. If you had fun exploring with us today, please leave us a five-star review.

11:56 Yeah, just scroll down and tap the stars. Tell us what you thought of Sandy's giant room-sized computer.

12:03 And make sure to follow this show wherever you're listening, so new episodes turn up on their own. Oh, and we have sister shows too. History, science, and philosophy is not boring. Go give those a listen and a follow as well.

12:17 Want your name on the show like Amelia? Send us an email at hello at kidopoly.com.

12:23 See you next time on Maths Is Not Boring. Bye.