S3E05.3 - Chess (Bonus - Teaching computers to game)

#Chess #AI #ArtificialIntelligence #ComputerGaming #BoardGames #Science

Summary

Welcome back to our miniseries on teaching computers to game! In our second minisode we talk Chess, arguably one of the most iconic games of man versus machine--which we lost thirty years ago. Chess is our poster child for brute-force approaches, where we use computers massive power to analyze millions of options and pick the (hopefully) best one, which affects everything from stock exchanges to weather prediction. We cover games that have been solved by brute force and those (like chess) that probably can never be truly solved, the iconic match between Gary Kasparov and IBM's Deep Blue computer, and how even that can be eclipsed by a modern cell phone. So grab some pawns and check your mates, and settle in for another episode of Gaming with Science!

Timestamps

00:00 Introductions
01:36 Chess
07:10 Origin of teaching computers chess
09:53 Brute force approaches
15:54 Deep Blue and Gary Kasparov
22:11 Other brute force applications
23:51 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:06
Hello, and welcome to the Gaming with Science podcast, where we talk about the science behind some of your favorite games.

Jason Wallace 0:12
In today's minisode about teaching computers to game, we'll be talking about chess and brute force computation. All right, welcome back everyone to Gaming with Science. This is Jason.

Brian 0:22
This is Brian, real Brian.

Jason Wallace 0:24
Yes, no AI-generated host this time, and not ever, actually. Welcome back to the second part of our four-part mini series on teaching computers how to game. So, last time we talked about basic algorithms and Tic Tac Toe, and an algorithm is really just a set of instructions for a computer, so everything we're going to be talking about over this whole series is just algorithms, but the key part of the ones we talked about last time is they're relatively simple algorithms, they're like, oh, here are these five or eight or 20 different rules to follow, and if you follow those, then you will win, or at least bring the game to a draw. Today we're going up to the next level, which is brute force computation. This is where you're basically taking advantage of the fact that computers are extremely fast to calculate tons and tons and tons of options, and then pick among them.

Brian 1:11
So, I think you said before, computers are fundamentally dumb, but what they are is quick and efficient.

Jason Wallace 1:18
Yes, very fast, very efficient, and very, very stupid,

Brian 1:21
so it kind of answers the question, if you can put enough stupid things together and get them to work fast enough. It's like it's smart.

Jason Wallace 1:28
Yes, we actually talked about this way back in episode two on Robo Rally and how GPUs work, so you can check that out if you want to know more about that. Our poster child for brute force computation is going to be one of the poster childs for teaching computers a game across all time. Chess. Now I'm assuming most people listening to this podcast know what chess is, but we're going to go over it just in case. So, chess is an ancient game, it's 1000s of years old, it's played on an 8x8 grid, and the two players each have 16 pieces of six different types. You've got your pawns, which you have eight. They can just kind of move one ahead and make little captures of the opponent's pieces. You've got two rooks, which move in straight lines. You have two bishops, which move diagonally. Two knights that have sort of like little L-shaped movements. A king, which is simultaneously the weakest piece, because it can only move one at a time, but also the most important, because if you ever get in a place where it's going to get captured, you lose the game, and then finally the Queen, who, befitting her Majesty, is the most powerful piece in the game, able to move as far as she wants in any straight line, up, down, left, right, or diagonal.

Brian 2:33
What is the history of the Queen as the most powerful piece in the game?

Jason Wallace 2:38
I'd say that's a relatively recent addition, I mean, as of several centuries ago, but basically, when the modern rules of chess were getting codified sometime in medieval Europe, basically that's when the queen was given her current moveset. Originally, she only could move just like a king, she could only move one section at a time.

Brian 2:56
Interesting, it was a game rebalancing.

Jason Wallace 2:59
Yeah, so chess has its origins in India. Yes, and actually that explains the pieces a lot better. So two of the piece names have mutated since they were originally there. So bishops were originally elephants, so the little pointy thing with the ball on the end was not a bishop's hat, it was an elephant's tusk.

Brian 3:17
Really? interesting.

Jason Wallace 3:19
And rooks were originally chariots, and so with that, you had the four divisions of the Indian army: you had your foot soldiers, the pawns, your cavalry, the knights, the chariots, the rooks, and then the elephants, now the bishops, and then you had the king and the queen, who were directing their armies to go attack the other army.

Brian 3:37
What is the origin of the name rook? Where does that come from, or like, as we called them when we were kids, the castles?

Jason Wallace 3:44
Apparently, the rook is just a romanization of the Persian word for chariot,

Brian 3:50
so it's even still in the name.

Jason Wallace 3:53
Yeah, and that's actually where the name checkmate comes from. So, checkmate is also from Persian, it's like Shamat, meaning the king is dead. Okay, so India to Persia to Europe, and chess is a little interested in that the rules of winning aren't just you have to capture the king, you actually have to put the king in a position where he cannot escape and will inevitably be captured on the next turn, that's checkmate, that is where you have placed the king, so that defeat is inevitable, and unlike many of the other strategy games we played, you can't sort of trick your opponent into it by them missing a move. You have to tell them, by the way, I have now placed your king in check, I've threatened him, and your opponent must move the king out of the way if they can. It's actually illegal to not move the king if you're able to. So basically, you can't win chess by accident. You can't win because someone had a way to escape, and simply did not take it. You actually have to maneuver them in a place where they cannot escape from your move. Now, there have been a bunch of variants of chess made over the years, for as befits any ancient game, but also apparently a lot of them have come up in the last few decades. I assume, as people have gotten kind of bored and figured out, what else can we do with. A chess game, one Brian and I both like, is chess. Neither of us, to my knowledge, knows how to play that, but popularized in Star Trek, it actually does have rules. There's infinite chess where the board is unbounded, so being eight by eight board, you have an infinitely sized board, and then you just have your pieces laid out as normal, which I'm sure makes things with the rooks and queens and stuff that can go theoretically in infinite direction, very interesting.

Brian 5:24
I'm curious about the what you had to say about three dimensional Tic Tac Toe is actually being like way easier to play and easier to win if the same would apply to three dimensional chess.

Jason Wallace 5:34
I don't know, although one thing you did mention last time, you mentioned a solved version of chess where you can guarantee that white will lose.

Brian 5:43
Yeah,

Jason Wallace 5:44
I think I found that variant is called losing chess.

Brian 5:48
Okay,

Jason Wallace 5:48
the goal of that game is actually to force your opponent to win. You put your pieces out, and if they can capture, they must capture your piece.

Brian 5:56
Okay,

Jason Wallace 5:57
and so the goal is to force them to capture all your stuff first. Apparently, that has been solved, at least for white,

Brian 6:04
so that actually makes a lot more sense, because I never were like, well, what's the difference between this and, and just black winning? It's like, oh, I get it.

Jason Wallace 6:11
There's been a lot of stuff with chess over the years. Looking this up, I found a bunch of fun facts. Um, I'd argue possibly one of the most interesting early, early versions of a computer playing chess was a hoax, that was the Mechanical Turk that I think we mentioned last time, which was actually a guy in a box that was controlling an automaton playing chess. Also, interesting note, apparently in World Chess Championships, there's all these rules about chess and what's allowed and what's not, but there's no defining way of setting who gets to pick which color they want to be first. White always goes first, and so there's arguably some advantage. And so, how do you pick that? Oftentimes, it's just a coin flip, but apparently you can do other things. And so, there was one China versus US chess match where they decided this by having the two teams play Jenga against each other. China won, by the way.

Brian 6:59
I mean, I guess that's true in football too. They usually just flip a coin, or maybe it should be more like, I don't know, like a goofy modern game where the person who most recently washed their hands has to go first, or something.

Jason Wallace 7:10
All right, so that's the history of chess in a nutshell. Obviously, for something that is this old, there's way more than that. The key part for our discussion today is that chess has, from the very early days of computing, been an important part of teaching computers how to play games, and in fact, I ran across a really interesting paper from 1950 by Claude Shannon. So, if any of you are familiar with computational theory, you've probably heard of the Shannon entropy, which is a measure of information content. It's named after this Dr. Shannon.

Brian 7:38
Oh, yes, of course I use it all the time. No, I have no idea what you're talking about.

Jason Wallace 7:41
I know, I know, I do. But anyway, he had this 1950 paper called Programming a Computer for Playing Chess, and his introduction has this great quote that describes really why we're doing this minisode, like why we're talking about teaching computers to game at all. Here he is talking specifically about chess, although perhaps of no practical importance. The question is of theoretical interest, and it is hoped that a satisfactory solution to this problem will act as a wedge in attacking other problems of a similar nature and of greater significance. And then he goes off and lists what several of these are, including routing telephone calls, translating languages, doing logical deduction, military operations, and even composing music, which I mean, here we are nearly 80 years later, and you know he's right, like,

Brian 8:27
yeah, kinda

Jason Wallace 8:28
pretty much all of those taken care of,

Brian 8:30
not all of them using this approach, though.

Jason Wallace 8:32
No, not using the approaches we're talking about today, but yes, using the ones we're going to talk about next time. So this has been one of those holy grails of trying to get a computer to play chess well for a long time, and the main way that it has been done, and what we're gonna focus on today is what's called brute force approaches.

Brian 8:50
Okay, here's the thing about chess, though, that I think is interesting, and why this interests people, and you can tell me what you think about this. Chess has a reputation as a smarty, smarty, smart game that smarty smarty smart people play, and like, if you're really good at chess, that must mean that you're smart, and like, the people that are chess masters are considered geniuses, although probably they're just really good at this one thing, but I think that idea of like, well, only really smart people can play chess, therefore, in a horrible set of logical fallacies, if a computer can play chess better than a person, then it must be smarter, or at least as smart as that person. Does that sound about right to you?

Jason Wallace 9:25
Somewhat, yeah. I think it's also just that chess is an extremely complex game. So I think in the same paper Dr. Shannon put out this number that's now called the Shannon number, which is sort of the lower bound for the number of possible games of chess, it's 10 to the power of 120

Brian 9:42
I'm trying to... I'm used to hearing enormous numbers, like the atoms in the universe. I'm trying to think of what is something at this scale.

Jason Wallace 9:50
Atoms in the universe is 10 to the power of 80.

Brian 9:52
Oh,

Jason Wallace 9:53
So this is 40 orders of magnitude larger than there are atoms in the universe. So that's another thing is. It is a very, very complex problem, and this actually brings us to different types of brute force solutions for games. So, last time we talked about solved games, specifically ones that were solved by elegant little algorithms. You may remember the one for Tic Tac Toe. It's an eight-step algorithm. It's something very easy to understand. Brute force is what you have to turn to when that fails, when you can't have just a few little rules to use, where you have to look up lots and lots of possible states. In this case, like for chess, there are so many possible states, it's not possible to have an algorithm to solve them all. You have to look and figure out what will work, and so brute force approaches use the fact that computers are very fast and they're very efficient, and so they can explore the search space, the number of possible options you have way, way faster than a human can, and look for optimal routes among the 1000s to millions to billions of different possibilities to find what is best, and they have all sorts of applications you can actually use them for the solved games we talked about last time, like Nim and Tic Tac Toe. I ran across one training exercise where you could actually program a computer to exhaustively calculate every possible move in Tic Tac Toe, and then you store that in the lookup table, and then as the computer is playing, just looks like, okay, where am I? Okay, I met this game state, which means this is the move I need to take next, and these lookup tables are sort of how the next class of games has been solved, beyond just Tic Tac Toe and Nim, we have these more complex ones like Connect Four or Checkers. Checkers is an interesting one. So, checkers was solved in like 2007 I believe.

Brian 11:33
Oh, interesting. I didn't realize Checkers was solved.

Jason Wallace 11:35
It is. It took 18 years of them running computers basically continuously, anywhere from 50 to 200 computers, because checkers is another one where, although the number of pieces is very small, there's actually only one type of piece,

Jason Wallace 11:48
the number of game states is enormous, and so checkers has specifically, it's been weakly solved, which, if you remember from last time, that means it's been solved from the starting position, but not from every possible position, however, they used a kind of clever trick for it, in that they, instead of trying to calculate out from every possible beginning position, what they actually did is they calculated every possible ending position, so every possible game of checkers that ends with 10 or fewer pieces on the board, they calculated out that was 39 trillion different games.

Brian 12:23
I'm just gonna have to stop reacting to large numbers, because this all this entire episode is going to be

Jason Wallace 12:29
- we're in the brute force section. There was a lot of zeros added to a lot of these things. They calculated every one of those out again. It took nearly 20 years, and they could show that if played perfectly, you would end up at a draw every single time, and that is now in a database of like 250 gigabytes that can be looked up, and not surprisingly, the person who did this then made a new checkers playing computer program, which is functionally unbeatable.

Brian 12:53
Okay, cool. Like online, like, what do you?

Jason Wallace 12:56
I don't know if it's out there, widely available or not. I just think he did it to do it. You can look it up if you want.

Brian 13:02
I'll, this is like why you climb Mount Everest, because you can.

Jason Wallace 13:06
Yeah, another one that was only recently solved was Connect Four. So, Connect Four is Milton Bradley game. You drop the checkers in from the top, and you're trying to get four in a row. It's basically an evolved version of Tic Tac Toe, if you think about it, with a larger grid and a few more rules that one was solved a few years ago with one of these lookup table approaches, so they calculated out exhaustively, which apparently with modern technology only took them two days, and they now have a 90 gigabyte lookup table for looking up where the move is, and then to do the next one. To put that in perspective, 90 gigabytes is 18 dvds of nothing but connect four games.

Brian 13:41
Oh, what's a DVD? No, I'm kidding. I'm kidding.

Jason Wallace 13:45
18 DVDs or three and a half Blu-rays.

Brian 13:48
What's a Blu-ray? These, these were ancient forms of physical media.

Jason Wallace 13:55
Blu-rays aren't that ancient.

Brian 13:56
You're just forgetting how old we are, Jason.

Jason Wallace 13:58
I don't know how many streaming hours that is okay. It kind of depends on your network connection. It's a lot. If you want, I can do that in terms of human genomes.

Jason Wallace 14:09
That's probably about 15 human genomes.

Brian 14:12
15 human genomes actually seems like a lot.

Jason Wallace 14:15
All right, so those are fully solved games. They have been exhaustively searched. They have their lookup tables they're, completely solved, even if, like, for checkers, it's weakly solved. Unsolved games are probably actually more interesting to talk about, the ones where the complete solution either has not been found or cannot be found. So, examples here: Reversi, if you play the game Othello, Othello is a slightly modified version of Reversi. It has markers that have two-colored sides, you put your things down, you're trying to capture your opponent's pieces, Go, which we'll talk a lot more about next time we get into neural networks, and so we'll leave that there. But is arguably even more complex than chess, and then, of course, chess itself, which is probably the poster child of unsolved, computationally difficult games,

Brian 14:56
not only unsolved but unsolvable?

Jason Wallace 14:59
Arguably Yes, because of the number of game states possible with 10 to 120 being the lower bound of the number of games. Yes, it is probably functionally unsolvable.

Brian 15:10
That sounds like an interesting math question, right There is how to prove that a game is unsolvable. Is it just the scope? Anyway, totally different thing. I think we're going to have a mathematician on for one of these, yes?

Jason Wallace 15:22
Computer scientist, which is basically just an applied mathematician.

Brian 15:25
Yes, I was gonna say that's the same as far as I'm concerned.

Jason Wallace 15:28
All right, so that then brings us to chess, and I already mentioned Claude Shannon's 1950 paper about programming computer to play chess. There was the first world computer chess championship in 1974 but that's where you have computers playing against each other to figure out which computer is the best. The first one in 1974 was won by a Soviet team, and the trophy is even called the Shannon Trophy, because Dr. Shannon kicked off this. Yeah, he comes up again and again and again in this. Now, in the history of teaching computers to play chess, there is one moment that probably, if you've heard of any point, you've heard of this, which was the 1997 game between Garry Kasparov, the the grand master among humans, and Deep Blue, and this was actually their second play, so they played first in 1996 Garry Kasparov was just the best chess player in the world, and then Deep Blue was an IBM computer that was made and had been iterated on and improved upon in 1996 mr. Kasparov beat Deep Blue pretty handily, and so it was not that much of a contest. 1997 changed that, though. And if you want more details about this, there's lots of information out there. There's an entire documentary called Game Over: Kasparov and the Machine that goes over this. Nate Silver, in his book The Signal and the Noise, has an entire chapter dedicated to this, which is available online. We'll put that in the show notes. And this was an incredible match, because it was the first time that a computer legitimately beat the best human player in the world. And the computer that they rolled out for this, Deep Blue, was amazing. It could calculate 200 million positions per second.

Brian 17:00
Like I said, I can't react to every big number that you say anymore. If I do, that's all it's going to be.

Jason Wallace 17:05
What's interesting is that, okay, spoilers, Deep Blue won, but maybe it shouldn't have, and this is what mr. Silver goes into. That win would have happened eventually, but it may have happened a little sooner than it should have, because of something that happened in the very first game, so in the first game Kasparov actually opened by doing something very smart. He knew that he was playing against a computer that'd been trained on all sorts of previous Grandmaster games, and so he played in such a way to get outside of the training data. He, within a few moves, they had gotten to a board state that had only occurred like once in the entire history of the training data that Deep Blue had, and so he had suddenly gotten outside what the machine could draw on past information for.

Brian 17:48
Clever

Jason Wallace 17:49
it's one of the weaknesses of computers - they're very good on what they know and not very good at what's outside that. So he put it to that position, and then they played forward, and around move 44 something weird happened. Kasparov was in a winning state, and everything, and there was a move that made a lot of sense, which was to move a rook from one position to another to position it somewhere, but instead Deep Blue moved it to a different position. He did move the rook, but he moved it somewhere else. The computer psyched him out. Well, yeah, and then the next turn it conceded, and Kasparov was really confused about this. It's like, what on earth was going? Were the programmers trying to mess with his head? Were they just sandbagging? And so he and his team went over information. Like, later that night, they apparently realized that, okay, if it had taken the obvious move, it actually wouldn't have worked out pretty well, because it would have set Kasparov up to win by checkmate in about 20 moves, which was obscene. Like, Kasparov apparently could only, at his absolute best, see like 12 to 15 moves ahead,

Brian 18:47
so it wasn't a bug. The computer was like, if I do this, this is the most likely outcome.

Jason Wallace 18:52
Well, we're getting there, because computer only thought to be able to get up to about eight or nine moves ahead.

Brian 18:58
Okay,

Jason Wallace 18:58
and so the idea that the computer had seen 20 moves ahead was extremely unnerving for Kasparov, and Nate Silver speculates that that actually is why he lost, because people have commented he wasn't playing that well the rest of the games against Deep Blue. He forfeited a match he could have put to a draw and other things, and so mr. Silver speculates that Kasparov got a little bit psyched out, and so was playing poorly, but here's the thing, it was actually a bug, the computer had reached some sort of loop it could not get out of,

Brian 19:31
so it just conceded?

Jason Wallace 19:33
no, it executed a failsafe when a certain amount of time had passed and no valid move had been found, or whatever, it made a random move.

Brian 19:41
Oh no,

Jason Wallace 19:42
just a completely random move.

Brian 19:44
That's like my normal go. That's what I do all the time.

Jason Wallace 19:47
Yeah, and because mr. Kasparov didn't consider that the computer had entered a bug state, he thought there was a reason for it. He suddenly thought the computer had all this more capacity than it did, and apparently between matches the. Computer programmers realized what had happened, and they fixed that bug in between matches, so it wouldn't happen again. They apparently thought they'd fixed it during training, but apparently not entirely.

Brian 20:11
This is something I know we've talked about a little bit, and something I'm hoping we can talk about as we move through other minisodes, but there is this cultural assumption that computers don't make mistakes. You work with computers, you know that a computer is programmed by a person, and that the computer is going to do exactly what it was programmed to do, but that does not mean it doesn't make mistakes.

Jason Wallace 20:30
Oh, yes, yes, getting my students to understand that a computer will do exactly what you tell it, no more and no less, is very important, which is why we put in these fail states for all the cases that we haven't anticipated, because a computer just gets paralyzed by those anyway. So that was the first loss of a human grandmaster to a computer program. Xkcd has this wonderful comic that marks this as the very first win of a computer against a top human, and then also marks 2005 as the very last win by a human against a computer, because computers continue to get better, the algorithms and processing power continued to evolve, until by 2009 there was, I don't know, what chess categories are, there's a category six tournament, so presumably a very high level tournament that was won by a mobile phone, and so at this point, if you're ever playing a computer program and it's not playing at grand master level, it's because some human told it not to. If you ever win against a computer program, it's because it's been programmed not to play as well as it could, because at this point no human can beat a computer program out there. I believe the current reigning computer champion is one called Stockfish, although some of the algorithms, like Alpha Zero, that we're going to talk about next time, I believe, are giving it a heavy run for its money, and may have started to dethrone it.

Brian 21:45
Wait a second. So, now the computers are just having their own tournaments.

Jason Wallace 21:48
Well, the computers have been having their tournaments for 50 years, but now we humans can't compete.

Brian 21:53
Oh, geez, okay,

Jason Wallace 21:54
we cannot play at the level the computers are playing against each other.

Brian 21:57
Does that mean 2005 is marking the emergence of the singularity, or

Jason Wallace 22:01
possibly I don't know,

Brian 22:04
like that is a question for future historians to concern themselves with, I guess.

Jason Wallace 22:08
Yeah, someone will have to draw an arbitrary line somewhere. So this part of computers and games probably brings us up to roughly the year 2000 when brute force was the reigning approach, and it proved a lot of very useful things, and we still use brute force for some very important things, like weather forecasting. Well, okay, up until this point, we did. The fact is, what we'll talk about next time is rapidly displacing a lot of these brute force methods, but weather forecasting traditionally has been by brute force. There's a lot of computational problems that have cute names, like the knapsack problem, like how do you pack a knapsack, optimally, or like the traveling salesman problem, which is basically, if you have a bunch of towns you're trying to visit, and you can visit them in a bunch of different orders, and you're trying to figure out the most efficient way to do so, so you spend the least amount of time, or gas, or whatever.

Brian 22:53
I remember getting exposed to that problem accidentally when we were planning out our trick-or-treat route in our neighborhood. It's like, well, wait, how there's got to be a best way to do this, right?

Jason Wallace 23:03
You know, I hadn't heard it applied to trick or treat, but I like that now. Anyway, they have cute names with very real applications. I, for example, used the traveling salesman algorithm to assemble a genome when I was a postdoc. These are very important, and for many decades they were the bread and butter of really hard computational work, and to some extent, they still are. Brute force is not going to go away. As we talk about these different developments in computation, it's not like one replaces the previous one and suddenly we don't use the previous one anymore. It's just that a new option opens up additional possibilities. It takes over some space, but there's still some places where basic algorithms work. If you're going to train a deep neural net to play Tic Tac Toe, you're doing way overkill, like the algorithm works. So that brings us up to probably about early 2000s in terms of state of the art computers and playing games. Next time we're going to be going to the next level as we bring in a deep neural networks reinforcement learning and the game go. So tune in next week for that, and until then, have a great week, and great games,

Brian 24:04
and have fun playing dice with the universe. See ya.

Jason Wallace 24:10
This has been the Gaming with Science podcast. Copyright 2026 Listeners are free to reuse this recording for any noncommercial 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 endorsements 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.3 - Chess (Bonus - Teaching computers to game)

Summary

Timestamps

Links

Full Transcript