Game On: Computers vs. Humans

now I'm hungry for Pepperidge Farm. You can't get that from hreh Um. We're going to talk today about some pretty famous matchups between human beings and computers, uh, in in various games. And this is one of those things that people have been interested in. Well, really it goes back even before computers, because it really kind of dips into the whole man versus machine, um the idea, right, I mean this goes all the way back to John

Henry versus the the steam steam engine. Yeah, and uh, people have wondered like when we're when we reach a point where computers would become better than humans at various games and we've reached the point with several games where we can pretty much definitively say computers are better at it than we are, you know, And a lot of the podcast where we've mentioned artificial intelligence or AI in the past, UM, we have talked about gaming and in

those situations we were talking more about computer opponents when you're playing against something in a computer game or a console game, and that's a little different than what we're

talking about here. But because and UH, I think actually I was I was reading an article UM by Jonathan Schaefer, Vadim Blikko, and Michael Burrow in the I E E. Spectrum and UH, it was talking about computer opponents in UH in software, specifically the game Fear f E A R, which is the first Encounter Assault Recon and how that has that's known as for its excellent AI. But UM, basically these games we're talking about today are are classic board games, classic tests of UH, you know, one player's

skill and strategy and thinking against another human being. And we wanted to know, you know, whether that's possible now and sort of depends on the game and it sort of depends on the opponent. But that's really according to

the authors in this in the Spectrum article. Um, it really started with with board games, and that's one of the things that has gone into a development of AI in computer games of all kinds, was you know, these attempts in the past to develop a formidable opponent, somebody that or something that you can play against where you don't have to go you don't really like to play a game at chess, but you know, Steve's work in a night and and I don't have anybody else that

I can think of, and I really want to play a game of chess. We want something. You don't want to, uh, something that's going to annihilate you instantly, nor do you want something that's going to be a complete pushover. So yeah, exactly, he's like playing me and chess. I only know how to lose it chess. Um. So yeah, I mean it's it's an interesting question and sort of a philosophical question.

It's not just programming. Yeah, I mean, there's a lot of these games have have elements to them that go beyond just a the physical number of moves that are possible at any given point. Right, some games that's pretty much all the game is. For example, Connect four. Oh yeah, Connect four. We're gonna talk a little bit about solving games. Now, to solve a game means that you have determined what all the possible moves are, and you know what the

best possible move in any given situation is. Um. If you have perfectly solved a game, then in theory, you would be able to play a game, even pick up a game that had already been started by someone else, and play it from that point forward, playing the best possible moves, even if that person who had previously been

playing made a lot of mistakes. Not many games have been solved to that level, but that a lot of games have been solved to the point where two players starting off with a fresh board and going from there. Uh is there is there a perfect way to play where you will either what will essentially where you'll never lose. Yeah,

you're speaking for personal experience. I think Reversey is one of the games, UM, if you're not familiar, it's the game with the black and white pieces that you try to basically surround your opponent to the point where you flip all the pieces to your color and or or

as many as you can and outnumber your opponents. Now I've played, uh, computer opponents in which on the easy mode it was a cakewalk, and I'd switch to the next level, and it already it seemed as though the machine had already been programmed with the best possible counter move to whatever it was, to the point where if I played on easy, I would almost always win unless I did something really stupid, and on even medium, it would know exactly how to counter every move I make,

to the point where I could not win no matter how well I would play the game. And uh, I think there are certain games for which you could say, okay, well these are the moves. In this case, it's the best possible move. And you know, when you're playing a person, you go, well, I you know, oh, look he made a mistake. And you know that. You know, Jonathan in this case is sitting across from me. He made a mistake. Well, he may not have been thinking about it. The computer

is not going to make a mistake. It's already been programmed with that in mind. Yeah. The mistakes computers make are based upon not expecting behavior from a human, right, right, I mean that's that's the way computers make mistakes. They don't make mistakes in the same way humans do. So for example, getting back to the Connect for uh example, that game has been solved to the point where, assuming perfect play on both sides, yes, the first player will

always win. Yes, there is no way for the first player to lose if both players are playing perfectly. Uh. Perfect play means you go for that center spot, folks, Just just an f y I if you need to, uh, if you need to play Connect four and you're the first player, get grabbed that center spot on the bottom row and uh and then just play perfectly from there and you'll always win. Easier so than done. Really, but that that was one of the games that was solved

fairly early on. But there are other games have been solved as well, and some games are not truly solvable. In fact, I wrote an article about computer versus human game matchups and the first one I mentioned was b KG nine point eight. That would be the computer versus Luigi Villa or Villa so uh so Luigi here he was a backgammon player. Yes, as am I, I nowhere

near as good as Luigi. So so Luigi played a match against b KG nine point eight in June nineteen seventy nine, and the game was got a fair amount of press because the computer program beat the the player. However, backgammon has an element in it that is unlike games like connect for or checkers or chess. Yes, that would

be dice. There's an element of chance in backgam and so depending upon the dice rolls, you may be luckier than your opponent, and that luck might be enough for you to beat someone who is technically more skilled at the game than you are, someone who is who is better at formulating strategies and picking the right moves and the best possible outcomes. Uh, you might win just because you get on a lucky streak, and that seems to

be what happened with this computer program. Yes, should we mention our earlier podcast on random number generators, because if you were playing a computer and you were not using an actual die or in this case dice, then uh, and you're relying on the computer to generate random numbers, Well, in general you can't because they're they're using an algorithm

and the computer number generators will generally go in a sequence. Now, this kind of goes back to what Chris was saying earlier about playing a video game in a video game world where you're playing against video game opponents. Technically in that kind of environment. Uh, the AI is totally different from a board game because it controls the entire environment. So you could create a video game that compensates for really strong players by pitting the environment against the players. Yes,

you know. I mean it's it's completely within the realm of possibility. In the situations we're talking about. It's supposed to be a fair game between our as fair game as you can get between a computer and a human. There's not supposed to be any element that's going to be within the computer's control that could that could weigh it in favor of the computer, right, because it's supposed to be a test of intelligence relative intelligence, like as

we mentioned with Alan Touring, Yes, yes, the touring test um. Now, in that case, the touring test was a tested determined whether or not you could tell the difference between a human respondent and a computer responded to a series of questions. In this case, we're talking about what or a computer is able to formulate a winning strategy against the human. The next one on my list was Chinook versus Marion Tinsley with Checkers. Yes, this was Checkers. Now Tinsley, Uh,

was an accomplished checkers player, amazing champion. He had won the championship from nineteen fifty five to nineteen two, and he had only lost five games between nineteen fifty and that seems reasonably decent. I think I've only played five games since n probably lost all five of them. Well, this is another game, though, if unless I misunderstand the article that you so aptly wrote, um uh, in which

there is a way to play perfectly. Yeah, this was that was not discovered till two thousand seven, or not not truly proven until two thousand seven. So when Tinsley played against chinook Um, the game had yet to be solved, and sadly, Tensley actually passed away before he could. Before they could definitively say whether or not the computer was a superior player, they would play thirties something games in

a row and end and draw a draw every time. Um. But that suggests that I'm sorry, go ahead, I'm just gonna say that suggests that that Tense was able to play a perfect game. Yes, because in two thousand and seven, the team that that created chinook did prove or demonstrate that they had solved the game, and that if you play perfectly on either side. Let's say both sides are playing perfectly, it will the game will always end in

a draw. So checkers is different from Connect four and that if you if both sides are playing perfectly, there is no winner, It's going to be a draw, whereas

with Connect four, whoever goes first wins. There's actually I remember reading about a game I didn't jot down it shot down my notes unfortunately, where it was the second play if the second player plays perfectly, If both players are playing perfectly, the second player will always win, which is which is interesting because you know, it just shows that it all depends upon the actual style of the game. Now, the next one that's on my list is probably the

biggest one. Yes, yeah, the one that everyone knows or has heard about, right, IBM's famous deep blue Yes against Gary Kasparov, who was the world champion chess player at the time. And uh they actually had two matches to two series of games. The first was in n and in that series Kasparov actually came out the victor. He managed to thank you, came out the winner, you know, wiener.

Uh So Kasparov one in the first series of games in and then IBM redoubled their efforts, and as Kasparov says in one of his articles, um they redoubled it's uh, they doubled its its processing power. Uh. The article I was referring to it is called the Chess Master and the Computer, which was a uh, actually pretty interesting article at any rate. In that game, Kasparov won the first game of the match in the series, lost the second one. The next three were draws, and the final game deep

blue one. So in that case, deep Blue one the series. And this was this made news worldwide because chess was one of those games that that people thought this game is so complex and it relies so much upon intuition and and strategy that goes beyond just numbers, that it was going to take ages before a computer could beat a true chess champion. And go ahead, I was gonna say, And this isn't just any chess champion. I mean he had the highest rating, yes, offered by the the world

body that covered chess. Yeah, there are various ways to rate chess players, but yes, Kasparov held the highest rating of all human players at this point. There are computer players that have higher ratings, in fact, ratings higher than what people thought were possible. UM. But UH. The interesting thing here about this, this UH matchup was that Kasparov said he thought that he had not prepared properly for the games, and that he wished he could have had

another rematch. But ibm H shut down that that project because they had pretty much proven their point, you know that they were They set out to create a computer program that could beat the world champion in chess, and it and it worked, So why continue that? I mean, there's no other application really for that. So they shut down that program and and Kesperov never had a chance to to try and and UH and and prove that

he could beat this this computer. Now, since then, Kasparov has played other computer programs that are on UM extremely powerful machines, and in some cases he has played to a draw or one, and in other cases he has lost. And he has said that we have essentially reached the era where a a powerful computer running the right software, or even desktop computers running the right software, can beat

a a grand master chess player. UM. And part of that is because these these computer programs often have an entire database of opening moves available to to UH to look at before making any kind of a move against an opponent. And the other is that chess is a really complicated game. You can't really map out all the possible moves easily because there's so many different pieces and they all behave differently, and there are a lot of

different options at any given time. But what chess computers do very well is they can plot out all the possible moves once you get down to a certain number of chess pieces towards the end game. And so a lot of these chess programs are very very good at plotting out the best moves when they're only say seven or eight pieces on the board. Once you get more than that, the the different variables are so vast that it's a lot harder to account for all of them.

That being said, it's gonna be pretty much it'll it'll take a lot of luck, really to beat a powerful chess program at this point, it can happen. Um. Casparov has shown that by playing in a kind of unconventional way you can fool a machine. He he actually did fool Deep Blue into sacrificing a piece that it shouldn't have, and that was how he managed to win one of the games in the round. So computers do make mistakes, but um, it's it, you know, it's it's hard to

it's hard to predict when that's gonna happen. They don't behave the same way humans do. So um and Kasprov actually has said that now champion chess players are starting to adopt more computer like approaches to playing and has even uh talked about he's he's kind of a champion to a concept called advanced chess, which involves a player

consulting a computer during play. So it's so it's a combination of human intuition and the ability of a computer to have that entire database of every game that's ever been played, essentially, and to rely on that and see like, oh, well, what what is this series of opening moves? Is that? Is that something that's been played before? And if so,

what's the best thing for me to do? And you know, there are points where the human takes over and starts to make moves, or perhaps the human has a move in mind and programs it into the computer, or to see what possible counter moves could happen. Um, And it's it's kind of it in a way. You might think, well, that's sort of cheating, but in another way, you might think, Hey, this is an example of computers and human intelligence merging

in a way. Yeah, yeah, I see what you're saying. Yeah, that's one of the things that I have a problem with with certain games is the lack of encyclopedic knowledge of everything you could possibly do. And in reading your article, I actually was thinking about this from a personal standpoint before I got to the next example. But yeah, I um, I'm a fan of the Scrabble brand cross word game. I love their trademark. We have to use that trademark, um. Although I love the game, so it doesn't bother me

so much as quirky. UM. So the thing is, if you go to a lot of the uh, the clubs that really get into the game, UM, you will find that a lot of them offer lit and lists and lists of words, all kinds of words, lists of words that you can make with different particular letter combinations that you might have on your tile rack. And I keep thinking, Man, if I had access to all these words without having to study these lists, I might, you know, really be

able to wamp up on some people playing scrabble. Now, there are people who spend lots and lots and lots of time studying the word lists, so they will be armed with all these different lexicographical weapons. Um. Yeah, I don't know if lexicography is a word. I'll have to look it up. I'm not sure that would work in scrabble. Um. Okay, However, Um, it seems that, uh that in your next example, that there is a computer able to play at that level, and that seems like it would have a severe pose,

a severe disadvantage for the human opponent. Yeah. Quackle is the the program um that you're referring to calls a computer program that um that was able to beat a champion named David Boys in a series of games of scrabble and Quackle. Again. Scrabble is one of those games that also comes down in part to luck, because it all depends on what tiles you have in your you know, you have at your disposal. Uh. And Quackle was able

to beat David Boys fair and square. Right, It was able to fair and square in the sense that it wasn't it wasn't making guesswork of the game. It was building words based upon what it had available and what was on the board already. Um. And yes, it did have an enormous database of words. So that gave it an advantage in that, you know, human beings, some of us are really good at remembering you know, thousands of

different word letter combinations that make legitimate words. Others we rack our brains like I've got a V, A, B, and F and in a queue, and oh what can I make? You know? So that one was playing pretty much by the rules. What was interesting to me was I ran across a story about a graduate student named Mark Richards who came up with a program, a scrabble program that goes a step further. It doesn't just have

a massive database of words that can play uh. And another advantage that scrabble UH computer programs have is that let's say that you have two lines of like two words that are fairly close to one another on the scrabble board, um, and but you know they're separated. There's maybe like five blank tiles between the two words. These computer programs are much better at looking at those those configurations and determining words that can span those gaps that

are than humans are. And so you'll see words played by computers that most humans never would have thought of. Because to to have taken that into account, that big gap into account is just kind of beyond what most

of us do when we play. There are good players out there who are really good at this, but most of us, you know, well, we sit there and we concentrate on one letter at a time, or if words are close enough, we might be able to get two letters that are already on the board incorporated into whatever we're about to lay down. Well, what Mark Richards did was he on a step further than that. He created a program that could guess what letters the opponent had

at his or her disposal bye bye. You know, there are only so many letters that are in a scrabble game, so it's counting tiles, counting cards. By counting cards in Vegas, it would count tiles. So you would start playing the game, and at the beginning of the game, the computer really can't tell what you have because it's only the only information it has at the very beginning of the game is which tiles are in it's uh, it's vault right.

Anything beyond that it doesn't know. So I mean it would know like, okay, well one of the q you tiles is in uh in my hand, which means that there is one less one fewer out in the actual game, right, Yeah, you can't really say, well, what are the odds that

he's holding that? You know, it's it's astronomical. You know, there's no qu and scrabble, right is not qu I thought of what it's just Q some of the some of the others that are similar, because almost every instance that Q appears in the English language is followed by

the letter you. Um, that's right. So at any rate, the so Q, I'm just gonna say, somebody's gonna write in so well, I don't play a lot of scrabble, clearly, but at any rate, so the computer what it can do is as the game goes on, it can start predicting with better and better accuracy, which tiles you probably

hold in your in your hand. So what it what it does, It will start playing words and playing parts of the board that will block off the best options you would have and when it becomes your turn, so it's blocking you from the combinations that would get you the most points. So so you're you're handicapped even further than you were just from playing the game fair and square even. You know, another interesting thing, and another interesting point you made that was nice um in the Uh.

Discussion of Quackle is that it in order to actually play uh David Boys, it actually had to beat another computer in tournament play before it was allowed to play him, which I think is funny. So I had computer versus computer. Yeah, there are a few. There are a few tournaments that I've seen like that where it's been computer pitted against

computer and then the winner goes up against a human champion. Um. And then there have been other exhibit games like I remember there's one with Kasparov where he was playing against thirty two computers and he won all of all of those games. Yeah, thirty two to nothing. Uh. And then the last one in my list was a computer program

that was playing the game of Go. And Go is particularly interesting in that it has if you're playing on a full board, it's a grid of nineteen by nineteen lines, and you play your pieces on the inner where those lines intersect in the grid, and that's a huge number and and so the the potential moves and go is big. Is there there are more potential moves in that game than than pretty much any of the other games we've

talked about. And there are also situations that can pop up where just because of the nature of the game, a move may or may not be technically legal, or there may actually be room for you to discuss the legality of a particular move, which makes it even more difficult for a computer to win because the computer just can't make that consideration. So um Go is one of those games where we have seen computers beat champions at Go.

But we've also seen cases where these these really powerful computer programs have been beaten by Go players, and sometimes they are Go players who are, you know, eight or nine years old. So it's one of those where if you're talking about solving a game, it's probably gonna take a while to solve that nineteen by nineteen grid game because it's just like I said that, the potential number

of moves are I mean, it's it's it's enormous. Yeah yeah, but that's uh, I mean, it's such a difficult game too. And I mean the the player that this particular Go program took on certainly one of the best in the world, and it took a supercomputer, a crazy supercomputer, yeah, with five and twelve corps, Yeah, five and twelve corps to to calculate the best possible move. If nothing else, this

kind of says. It kind of points to that the huge hurdle of creating an artificially intelligent machine capable of thinking in a way that humans think. You know, we take it for granted how complicated thinking actually is until we try to mimic it using machinery. Because just even using something where you've got a a closed environment with known rules that you have to follow, it's still incredibly

difficult to match human performance in that. Yeah, yeah, fascinating stuff though, Yeah yeah, And all the players we talked about could beat the pants off of me and just

about any game. There are other computer program problems that are interesting to to look at, like um, the people who solved checkers, or some of the people who worked on the whole checkers problem have moved on to things like poker and poker like Texas hold Them and that's a game that is also difficult to uh to beat or two, it's it's hard to figure out a way to program a computer to play that at the same

level as a human champion. Because you think about poker, you're dealing with hidden information because you don't know what cards someone else may or may not hold. UM, and you're dealing with strategies like bluffing and um. Another thing

about computers is you can upset them. So you're not going to get a computer to play on tilt, but you can make a computer think that your cards are better than what you hold or or worse, because there are a lot of strategies that involve tricking someone into thinking that you're holding a weak hand so that they over commit themselves in a bet and then you sweep in and you just take all that money and then

you run away laughing and throwing chips at people. That's how I Playone likes to play with me, well except for the people who pick up the chips because they're like awesome free money. So you're saying then that if you were playing a computer opponent at poker, you wouldn't necessarily need to worry about walking away or running, and you might even be able to count your money while you're sitting at the table. Yes, that's exactly what I'm saying.

I mean, even if the machine didn't get upset with you. Climb stairs. What a gambler? Yeah, well it's yeah, I'm no, I'm not gonna quote anymore from that song. That's done. But anyway, Kenny. Nice. Nice, So this will wrap up this discussion before I have an aneurysm Um, speaking of running,

I should probably get to that. Yeah, So it'll be interesting to see what what the future of of computers and gaming holds, because we've already gotten to a point, like I said, where we've reached a state where computers can beat the best players in many, not all, but many games. Um, will we eventually see UH chess championships played between computers? Well, well, will we ever actually say, you know what, this comes to a point where we have to legitimately award a computer program the title of

world chess Champion? I doubt it. Well, I mean they do use the UH console games on no Play to predict the outcome of the Super Bowl. So yeah, but I mean, if we allow a chess game to become world champions, shouldn't we also allow things like I don't know, like the Tesla Roadster to compete in the hundred yard dash. Me. I'm just saying, like, you know, you're already stacking the deck.

I mean, yeah, I don't. Well, I mean it takes all the fun out of it for people to Yeah, I would hate to get run over by a roadster while trying to run the dash. Take the fun out of it. But that's a good point. Yeah, So don't get run over by a computer, is what what we're getting at. It was a long way around to that moral of the story apparently. At any rate, if you want to learn more about it, you can read the article. It's it's about the hang on. I've got the title.

Actually I supposed to say. I'm about to work my way around it. It's top five computer versus human game matchups. Um, it's a It was fun to write, and I was so pleased that I could find other games besides chess, because that's the one everyone thinks of. But there are other games out there that people have created programs that are you know, these computers are really good at playing those games. Haven't found one that can really take me on shoots and ladders yet. I'm sure it's coming and uh,

of course. Sorry. We're gonna wrap this up, you guys. If you have any comments or questions, you can contact us on Facebook and Twitter are handled. There is tech Stuff h s W or you can email us. The address is tech stuff at how stuff works dot com. And Chris and I will talk to you again really soon, Jonathan. Um, actually this was just handed to me. It looks like how stuff Works dot Com now has an iPhone app.

Sweet that awesome. Yeah, actually, um, I got to to take a look at this earlier, and guys, this is pretty cool. The iPhone app is a sort of a way to integrate all the cool stuff we do at how stuff Works dot com. So you, guys may have listened one of our podcasts and we talked about there's this great article on the like, but you're not at

your computer, so you can't really check it. Well. The iPhone app actually lets you browse articles and blog posts, even lets you interact on Facebook and Twitter, and you can listen to podcasts at the same time. And it has all the house stuff works dot Com podcasts on it, not just ours, but you know good ones too, so you can listen to those and look at the articles and and go on Facebook and Twitter, and it should work perfectly with your iPhones and iPod touch it awesome.

What's it looks like. It's now available on the iTunes store, so that's good to know. How much does it cost? It's freeze Ah brought to you by the reinvented two thousand twelve camera. It's ready, Are you