Presentación
Vídeo
Transcripción
Extracto de la transcripción automática del vídeo realizada por YouTube.
- Let's go ahead and get started. My name's Randy Coulman, I work at a company called Zeal. And we're going to talk about teaching computers to play games, today. So, computer game-playing has been a fascination for years, and years, and years, and actually a lot of the things we know today came out of teaching computers to play games.
A lot of algorithms that we use, data structures, search techniques et cetera, there could be games as simple as tic-tac-toe, which I'm sure we've all played. Teaching a computer to play tic-tac-toe is not actually that hard anymore. Then you can get into some slightly more complex games that you might recognize, or maybe not.
And then you can get into the really advanced stuff, which you've probably never ever played before. If you don't recognize the screen shots, they're from a movie called WarGames in 1982. Classic Matthew Broderick, Ally Sheedy when they were like, really, really, young.
Anyway, so games, like I said, have been an area of research for a long time, and you might recognize this more recent example. They taught Watson to play Jeopardy and now they're using it for all kinds of other things. So, what I'm going to talk about today is mostly really simple game stuff, pretty basic level.
But it's at least a way to get started. A lot of what game playing involves are graphs, trees, and algorithms. So why would we care about those? I mean, yeah they're great for games, but what else? Well, we might have to represent hierarchical structures in our apps.
I actually worked on a project six or eight months ago where we had the hierarchical structure we had to represent and work with and actually was able to suggest one of these algorithms to solve a problem that people had with that. Relationship maps, you know the, "You are "only two connections away from this person "on LinkedIn," that's a graph.
And there's algorithms for traversing those graphs, and no, I'm not going to ask you if I can add you to my personal network, don't worry. Trip planning, trip planning is a graph problem. Network routing, how do you get your packets from here to there. That's another graph problem and these algorithms, much more advanced versions of these algorithms can be used in these kind of places.
But those are kind of boring business problems, let's talk about game playing instead. So for my example, I'm going to use a board game called Ricochet Robots. I was introduced to this game a couple years ago and as soon as I played it I thought, "I bet you I could write a program "that would play this game for me.
" And so like any side project, what you do is you have this idea and you let it sit, and then you propose a talk on it and then you have six weeks to write the gameplayer and the talk and get it all done, so that's my bonus lesson how to do a side project, don't do it that way.
Anyway, so in Ricochet Robots, you have a 16 by 16 grid, like you see here, the center four squares have a little grey thing on them, you can't go there and on the grid, there's some walls and then there's those colored areas are called goal targets. So a game of Ricochet Robots, you have to move the robots around the board and achieve the different goals depending on which turn it is.
So the robots are distributed randomly about the board when you start, and then you turn over a little disc with one of the goal symbols on it and that tells you what you have to do to play. So, this game can be played by any number of people, which is really cool, most games you have your own little token you have to move, and so everybody looks at the board and tries to figure out, "How many moves does it take to get "the green robot into the green square?" You can move any of the robots, but robots can't stop once they start unless they hit something.
So they can run into walls, or they can run into other robots, but they don't stop and then they change direction and go a different direction. So, in this case, to get the green robot into the green square, I come up with a seven-move solution which looks like this.
You move the blue robot around and then chase it around with the green robot, bounce off the blue one and down into the goal. And that's basically how the game's played. And then, you turn over another disk and so there's 17 disks and the entire game is made up of going through all 17 disks, and you're just trying to be the person that can find the shortest solution.
There's a little bit of a chance to find a better solution, you have about a minute to do that, and there's a tiebreaker rule, so that if two people come up with the same length of solution, the person who's behind in the game gets to trump the other player, which really helps to even the game out a lot.
Even if you're not the fastest player, you still have a chance to stay in the game. It's a lot of fun, it's pretty cool. But if we're going to teach a computer to play this game, you have to kind of get a sense of the scope of the problem you're dealing with.
So, in this game there are actually 976 and a half billion possible states the board can be in. So, you've got the cells in the walls, there's five robots and 252 squares and you do the combinatorics math for that and you get 976 billion, that's a lot. And at each level from each state of the board, there's between nine and 20 possible next states you can get to, depending on which robot you move in which direction.
Sometimes robots are stuck in a corner, that's why there might be less moves but nine to 20 moves, so that's a pretty huge amount of data, and you're not really going to get through all that in a reasonable amount of time, so you need to come up with some ways around that and we'll be talking about that today.
So the first thing you need to do when you want to write a computer gameplayer is you need to figure out, "How am I "going to represent the game? "What are the data structures going to look like?" So, we have to start by representing the board, and if we think about the game a little bit, the board never changes, the board itself never changes.
You have the 16 by 16 grid with the center island, that's static, then you have the walls and targets, there are different combinations of those but for one single game of 17 turns, that never changes either, that's static as well. The goal cell changes each turn so a little more frequently than the walls, but less frequently than some other things, and then the robots, every time you move a robot, the robot positions change.
So you've got this combination of really static information and really dynamic information and if you have to keep track of a lot of states of the board at a time, you want to minimize the amount of storage you need for that amount of data that you need to store.
And so you want to kind of split up what's static and what's dynamic so that you can reduce your storage. That's one of the things you'll find solving big problems is storage efficiency is often almost as important as actual time efficiency, and a lot of times what you do is you trade off, "Oh, I can "use up a little more storage but then "I can get faster, or gee I'm running "out of memory on my servers and I can't "add more, so I need to maybe trade "off a bit of speed so I can reduce my storage usage.
" And that's classic in a lot of performance problems. The next thing we have to represent is how do we figure out how to represent robot movement. What we can do is we can represent the board states and then the movement of robots as lines between them. So, here I just got a few examples of moving the red robot a couple directions, moving the green robot a little bit and so you can think of the board states as these boxes with the lines between them being which robot moved to get to that new state.
This data structure, you may not recognize it, or you may, is actually called the tree. It's fairly classic in computer science data structure, for some reason, we always draw them with the root at the top instead of at the bottom, like a real tree. I don't know, it's like starting from zero, right? So, in a tree, the very top most node is called the root and it has no parent nodes above it.
[ ... ]
Nota: se han omitido las otras 3.932 palabras de la transcripción completa para cumplir con las normas de «uso razonable» de YouTube.