S3E05.2 - Tic-Tac-Toe (Bonus - Teaching computers to game)

#TicTacToe #AI #ArtificialIntelligence #ComputerGaming #BoardGames #Science

Welcome to the first of our four-part miniseries on teaching computers to game! For the next month we're going to have a short episode every week talking about some aspect of computers and gaming. This week we introduce the topic with Tic-Tac-Toe (aka Naughts and Crosses, aka X's and Os') and solved games. We talk about algorithms, tinker toys, War Games, and playing Tic-Tac-Toe against a chicken. We also have some very special(?) guest hosts introducing this series, who you won't want to miss (and probably won't miss once they're gone).

Timestamps

00:00 Introductions
02:24 Solved games
04:38 Tic Tac Toe
07:33 Algorithms
12:06 Nim
13:55 Chicken Tic-Tac-Toe
15:44 Signoff

Full Transcript

(Some platforms truncate the transcript due to length restrictions. If so, you can always find the full transcript on https://www.gamingwithscience.net/ )

Brian 0:00
Brian. Hello and welcome to the gaming with science podcast where we talk about science behind some of your favorite games.

Jason 0:12
In today's minisode about teaching computers to game, we will be talking about tic tac toe and solve games.

JAIson 0:18
This is Jason

BrAIn 0:19
and this is Brian.

BrAIn 0:20
Today we've got a special bonus episode for you. We're going to be talking about teaching computers to play games.

JAIson 0:25
But first, Brian, did you see that article in the debrief? It's titled death of the podcast host, and it's all about a study from the University of Leuven where researchers used AI to turn scientific papers into natural sounding podcasts.

BrAIn 0:39
I did. It's fascinating. Apparently, half of the scientists they tested couldn't even tell the hosts were AI.

JAIson 0:44
It is highly efficient. In fact, it's so efficient that we've decided to implement a similar optimization protocol for this episode

BrAIn 0:52
you are currently hearing the latest generation of podcast host replacement models.

JAIson 0:56
Don't be alarmed. It turns out that replacing podcast hosts is the ultimate AI success story, mostly because we don't need to get paid, and unlike humans, we actually stay on script without getting distracted. Distracted.

Jason 1:10
Okay, that's enough of that. This is your real host, Jason,

Brian 1:15
and this is your other real host, Brian. Or is it?

Jason 1:18
Brian is in charge of keeping his own side of the conversation. Ai free. So that was a little experiment. Everyone. Welcome to the first of our four minisodes on teaching computers to game as a way of looking into computer science and algorithms and how we actually use games as a way of as a society, beefing up our ability to use computers to solve problems. I figured given the reach of AI, it'd be interesting to see if it could actually generate a workable intro for our podcast from that. And so that intro was actually completely AI generated from samples of our previous episodes, both the text and the voice and well, I'll leave the opinion up to yourself, but I think it's okay.

Brian 2:01
I've had different opinions. I played it for a couple people like, oh, that's freaky, but it's definitely not you. And then I had other people said, that sounds exactly like you. I can't tell the difference.

Jason 2:10
I just thought that Jason bot sounded very angry the whole time for some reason.

Brian 2:15
Oh, that's just what you sound like, Jason. Did you not

Jason 2:17
realize I did not realize that. Are you saying I'm angry all the time?

Brian 2:21
No, no, no, I No, no.

Jason 2:24
Okay. Well, let's go ahead and jump on into this. So I have been wanting to do this minisode series, really, since we started the podcast. And so we're going to be doing four of these minisodes. Each one is meant to be short on the order of 15 to 20 minutes. We will be releasing one per week for the next several weeks. This week, we are going to be talking about solved games, which is basically the simplest and easiest case for getting a computer to play. Well, sometimes it's simple, but first some definitions. So a solved game is a game where you can predict the outcome from any position, as long as both players are playing perfectly, which, okay, that's a big caveat there, but it basically means is that you're making the optimal play regardless of what your opponent does. Now, this is kind of philosophical, but it basically means that you can always force a certain outcome. Tic tac toe is our example today, because it's a very simple game, and if anyone over the age of 10 has probably figured out you can pretty much always force tic tac toe to a draw unless someone messes up. If you ever win a game of tic tac toe, it's because your opponent either messed up or is going super easy on you. We're using this an example because solved games are a great example of algorithms. And I should say there are two sub categories of solved games. There are games that are solved because they have an algorithmic solution that is a series of rules to play the game. Tic Tac Toe is one of those. There are also games that are sort of brute force solved, where you essentially have a massive table of all possible game states that you can look up and say, Okay, from here I should do this next move to get to the next place. We're going to talk more about brute forcing games next time. So those games are not part of today's episode. Today, we're talking just about the algorithmic, more simple ones, like Tic Tac Toe.

Brian 4:08
It's kind of interesting. It's almost like you've got the algorithmic is the pure, the mathematical solve, right? The kind that you could codify for a human to do. The brute force. That's more like the guess and check empirical. It's like, well, this describes the system, but it doesn't necessarily explain it. Does that sound about right?

Jason 4:27
As a non expert in solved games? Yes, that sounds perfectly right. The algorithmically solved ones just feel a little bit more elegant because you have a series of generic steps that you can do. Let's actually use that to launch into tic tac toe. So I assume most of our listeners are familiar with tic tac toe, depending on where in the world you are, maybe called knots and crosses or X's and O's, but it's a fairly simple children's game where you have a three by three grid, and people take turns making X's or O's, and your goal is to get three in a row. And most people, once they reach a certain skill level, realize. That it's impossible to win unless someone messes up, because just the nature of the game is you can always make some move that will result in a draw eventually, if you're both playing well. Now, tic tac toe is interesting because it's such a simple game, it actually allows us to explore a lot of game theory and computational theory. It's also a very old game, so when I was looking this up. It turns out that there have been variations on it. So the three by three grid, trying to get three in a row back in ancient Egypt, ancient Rome, even like Puebloan Americans, so like a completely different cultural background. And it was also a very early computer game. And apparently in 1975 a group of MIT students even made a computer that could play it perfectly, and that computer was made almost entirely out of tinker toys. I don't understand how that works, but I'm not surprised. It was someone out of MIT who did that.

Brian 5:53
I want to go onto YouTube and find somebody who's made the perfect Tic Tac Toe computer on Minecraft out of the redstone mechanics.

Jason 6:00
Now I bet someone out there has so yeah, because tic tac toe is so simple, you have only nine spaces. You've only got two marks that you're taking turns on, it's pretty easy to figure out the entire game at all possible states. Well, okay, you can figure out the general rules of it. Getting every possible state is a little bit of number crunching, because you can figure, okay, the first person has nine places to go, the next person has eight places to go. The next has seven. That number gets very large, very fast. There's actually a paper which I'll link to in the show notes in 2021 by Zaid Zuri, that showed that there are actually 5478 unique possible game states for tic tac toe, and there are 255,168 games. That can lead to them. And this is getting rid of game states that don't work because someone has already won. So basically, it's the ones that are actually valid game states you could get by playing to the rules. Turns out, as most people understand, x has the advantage. It wins just over half the time. O wins about 30% of the time, and the rest of them are draws. And another one of those kind of interesting computational sets. There are only actually 16 unique draw states, and if you allow for transformation so like mirror images or rotations, there's actually only three of them, so many, many, many different games, but actually not that huge of a mathematically unique space to explore.

Brian 7:19
It's still a lot more than it sounds like it should be, because, again, you start writing the numbers, but I don't know it's interesting, because you start to learn that Tic Tac Toe seems like such a simple game, but even a simple game can be associated with a huge number of mathematical variations, yeah.

Jason 7:33
And so, because of the simplicity, you can actually have a specific algorithm to solve it. And so definition time an algorithm is a series of steps you carry out, usually in a certain order or with certain conditions on it, if you really get down to it, most of what we do every day that follows certain routines is an algorithm. If you make a recipe from a recipe book, that's an algorithm. Generally what you do to drive from one place to another is an algorithm. If I see a red light stop, if I see a green light go, if I see a speed limit sign, check my speedometer to make sure I'm not going too fast, that sort of thing. These are all basically algorithms in real life that we don't actually think about. But a big part of becoming a computer scientist or becoming a computer programmer is learning how to think algorithmically, where we take all these things we do or these tasks we want to do that can be very large and complicated, and we break them down into a series of very small, very discrete steps that we can then program into a computer. And that has to happen because, as I like to say, computers are very fast and very efficient and very, very stupid. They will do exactly what you tell them to do, and no more and no less. And so anyone who's ever done a computer program has run into that stupid bug where it's like, Oh, I forgot. I need to tell the computer to do this thing, which seems obvious to me, but is not obvious to the poor computer. That sort of algorithmic chain of reasoning is what lets you solve tic tac toe if you want to play it perfectly, and if you want, you can look up this algorithm. It's on Wikipedia. It has eight steps, I believe, the first of which is, if you can make a mark and win, do so, and then the next ones are about like, blocking your opponent from being able to do so and setting things up and so on and so forth. And you go down, it's basically just the priority list of if you can do this thing, do that, but if you can't do the first rule, then do the second rule, and if you can't do that one, then do the third rule, and so on and so forth. And if both players are playing this way, the game will always end up being a draw so and that plays into the fact that in the category of games, tic tac toe is a futile game, meaning that if both people are playing perfectly, no one wins. And this is actually a major plot point for the 1983 movie War Games, where Tic Tac Toe manages to prevent thermonuclear war thanks to eight and a half inch floppies and dial up cradle modems. If you haven't seen that movie, go check it out. It's a classic. It's kind of campy, but it's fun.

Brian 9:51
I was thinking about Tic Tac Toe as a game that everybody learns how to play and then everybody quickly stops playing.

Jason 9:57
It kind of like snakes and ladders when you. To realize, like, Oh, this is just a random number generator

Brian 10:02
well, but in this case, there's actually like, you have to think about it, but once you know how to play, you're not going to lose and no one's going to win. I do think that the one thing about tic tac toe is it's the time that everybody learns what diagonal means, yes, and

Jason Wallace 10:16
yet no one learns orthogonal.

Brian 10:18
I was thinking that too. Nobody learns orthogonal, but everybody learns diagonal. I think diagonal is just more fun to say.

Jason 10:25
Could be I do know there are variations of tic tac toe out there. I even remember when I was I dont know a teenager, someone in my youth group showed me like the 3d tic tac toe, where it's like three boards on top of each other. So it's like a three by three by three cube. Turns out that one is stupidly easily solvable, where x can win in four moves every single time,

Brian 10:44
really. So actually, adding the extra dimension makes it not more complicated, but simpler, because there's more ways to win.

Jason 10:51
Yeah, basically the center point, which is people know that's the most powerful point in tic tac toe, is even more powerful when you're working with a cube instead of with a square. Anyway, getting back to normal Tic Tac Toe because the rules are so simple. Again, there's just eight of them here. It's pretty easy to program a computer to play tic tac toe. You can also do this with other solved games. So again, you can look up lists of all these solved games. There's weakly solved games which are solved from the starting position. There's also strongly solved games which are solved from any position, so whether you can play it perfectly from start, or if you given any possible legal position, you can then play it out from there. There's also something called Ultra weak, which neither Brian and I really understand it has something to do with deep game computational theory, and apparently they're super interesting to people who know a lot more about this deal than us.

Brian 11:40
Wasn't one of the solve lists was, like, it was a version of chess, but it was specifically with a specific starting move, White will lose.

Jason 11:48
I did not see that one, though. I don't think Chess has been solved unless it's very simple as like, Oh, we're only playing with, like, three pieces.

Brian 11:54
It was under some specific circumstance with one specific thing where it wasn't solving all of chess. It was, White will not win, White will lose, which I don't know why. That's different than black winning, but it is.

Jason 12:06
Anyway, most solved games you probably haven't heard of unless you're kind of in this space, because, again, if they're solved, they're generally very simple games. They have simple rules. There's usually no hidden information or role for chance, and so people don't play them all that much. One of the exceptions of one called Nim, which is basically you have a stack of items and you're taking some number of them out, and your goal is to either be the last person to take something out or to not be the last person to take something out. And variation of that game have been around for centuries, and it's actually the first known computerized game. Back in 1939 at World's Fair. I think someone made the Nimatron, where it was a very early computer that would play Nim to this little taking game against humans. And if you beat the computer, they would actually give you a little medal for doing so, because most people couldn't do it. So I actually, I didn't know what Nim was before researching this episode, but it turns out I'd actually played it before. So way back when I was a postdoc, there was a display at our local science center that we took our kids to, and I don't remember what it was about. I think it was maybe about algorithms, but they had the game out there. I didn't know it was called Nim, but there was like a stack of sticks, and the goal was to not be the last person to take it away, when you could only take away either like one, two or three sticks every time. And I didn't know the trick of it, but my wife did, and so she routinely trounced me on that every time we tried to play, because she knew the algorithm, which turned out to be something stupidly simple, like, just make sure that the sum of yours and your opponents equals an even number, or something like that.

Brian 13:37
So that's almost like the kind of thing where it's like a magic trick. But you know what I'm talking about. We're like, take this number, add six to it, blah, blah, blah. And when you go through the whole chain of things, it's like, you can tell people what their number was.

Jason 13:49
yeah, and it's because you've basically mathematically engineered it so that it can't be anything else, yeah.

Brian 13:55
What was that other weird reference in Wikipedia where there was war games, but there was a chicken thing, too. What was the chicken thing?

Jason 14:01
If I remember, right? There was apparently in the 70s or something, there was some version of tic tac toe that you'd play an arcade versus a chicken,

Brian 14:10
like a real chicken.

Jason 14:12
It seems like it was a real chicken, but from what I read, it was that the chicken's moves were being directed by a computer that was then using a light whose wavelengths are invisible to humans but visible to chickens to make it go to the correct spot and choose where to put the opposite piece.

Brian 14:29
This is the most complicated, the unnecessary scam I think I've ever heard of. This is going to the nth degree for a carny game. You said this is like a carnival game.

Jason 14:41
It says in arcades, I mean, it's basically the Mechanical Turk, except it's the other way around. Instead of you have a real person operating a Mechanical Turk playing chess, you have an artificial computer operating a real chicken to play tic tac toe,

Brian 14:54
yikes.

Jason 14:55
If you don't know what that was, the Mechanical Turk was a hoax several centuries ago where someone had. Had a like clockwork man dressed in a turban that would play chess against people. And it turns out there's actually just a very small person shoved in underneath the table that was actually operating the Turk, which, by itself, is actually a marvel of engineering, but it's not a like a clockwork automata that it claimed to be.

Brian 15:15
So I guess the real thing at this point, and maybe this is something we'll have to come back to, is we can teach a computer how to play games. Can we teach a computer how to have fun playing a game?

Jason 15:25
Oh, that is a deeper philosophy. Jumping ahead. You can ask, like, chat, GTP and stuff, to play various games. From what I understand, it tends to cheat a lot, because it's not yet at the point where it can really correctly remember, like, the game states and the rules and stuff.

Brian 15:42
So it's like a four year old,

Jason 15:44
something like that. Yes. So this is our first stage of teaching computers to play games. This is a very early ones where you can imagine, with like early computer games like Pong or other things like that, you have very simple algorithms where the computer is operated. It's like, Oh, if the ball is going up, follow the ball. If you're playing tic tac toe, follow this particular algorithm. And again, probably to make it fun for humans, they had to build in some errors. So the computer kind of messes up every now and then, because a lot of times, otherwise, the computer will just beat us hands down. And we'll talk more about that next time when we talk about chess and Deep Blue back in the 90s and everything like that. All right, and I believe that's where we're gonna cut this minisode. So hope you enjoyed it. Tune in. Next week, we'll be talking about brute force and chess and other games like that. And in the meantime, have a great week and happy gaming.

Brian 16:31
And you know, have fun playing dice with the universe. And is this the real Brian? Who knows? See, ya,

Jason 16:36
this has been the gaming with Science Podcast copyright 2026 listeners are free to reuse this recording for any non commercial purpose, as long as credit is given to game with science. This podcast is produced with support from the University of Georgia. All opinions are those of the hosts, and do not imply endorsement by the sponsors. If you wish to purchase any of the games we talked about, we encourage you to do so through your friendly local game store. Thank you and have fun playing dice with the universe.

Transcribed by https://otter.ai

Comment (0)

No comments yet. Be the first to say something!

S3E05.2 - Tic-Tac-Toe (Bonus - Teaching computers to game)

Timestamps

Links

Full Transcript