Bulbanews

Crunching the numbers: Game trees: Difference between revisions

Page Talk page

Crunching the numbers: Game trees (view source)

Revision as of 08:30, 2 January 2012

118 bytes added ,  2 January 2012
m
just adding some links. Also, no space in ThunderPunch
No edit summary
m (just adding some links. Also, no space in ThunderPunch)
Line 17: Line 17:
tagline=Enhance your game with the power of math  |
tagline=Enhance your game with the power of math  |
blurb=Back in 1996, a computer defeated a world champion chess player at a single round of chess for the first time. How did it do this? By computing every possible move and working out which one was best. This may same incredibly inefficient, but it payed off. How does this apply to Pokémon? And how can humans apply this method? Danielle Detering investigates. }}
blurb=Back in 1996, a computer defeated a world champion chess player at a single round of chess for the first time. How did it do this? By computing every possible move and working out which one was best. This may same incredibly inefficient, but it payed off. How does this apply to Pokémon? And how can humans apply this method? Danielle Detering investigates. }}
{{CategorizeIn|Anime|1|12}}
{{CategorizeIn|Columns|1|12}}


If you’re nerd intolerant, you may wish to skip ahead a few paragraphs. Way back in 1996 when I was a wee lass, a technological marvel occurred. For the first time ever, a computer was able to defeat a world champion at a single round of chess. Those interested in the study of AI will quickly recognize this as when IBM’s creation, Deep Blue, defeated Garry Kasparov.
If you’re nerd intolerant, you may wish to skip ahead a few paragraphs. Way back in 1996 when I was a wee lass, a technological marvel occurred. For the first time ever, a computer was able to defeat a world champion at a single round of chess. Those interested in the study of AI will quickly recognize this as when IBM’s creation, {{wp|Deep Blue (chess computer)|Deep Blue}}, defeated {{wp|Garry Kasparov}}.


There are a lot of controversies about the fairness of the match, but those aside, there’s still a lot we can learn from Deep Blue and how it plays. A computer scientist friend of mine once described computers to me as really efficient morons, and it may be surprising to know that chess programs are no different.
There are a lot of controversies about the fairness of the match, but those aside, there’s still a lot we can learn from Deep Blue and how it plays. A computer scientist friend of mine once described computers to me as really efficient morons, and it may be surprising to know that chess programs are no different.


Computer programs are only as clever as their programmer, and the way they work is by following a set of instructions that are laid out for them. This can be really challenging since computers don’t speak and listen in the same sense we do, so programmers transcribe their instructions into a language the computer can understand. Java, C++, and Python are examples of the languages a computer can comprehend.
Computer programs are only as clever as their programmer, and the way they work is by following a set of instructions that are laid out for them. This can be really challenging since computers don’t speak and listen in the same sense we do, so programmers transcribe their instructions into a language the computer can understand. {{wp|Java (programming language)|Java}}, {{wp|C++}}, and {{wp|Python (programming language)|Python}} are examples of the languages a computer can comprehend.
Chess computers compete by looking at all possible moves it can make.
Chess computers compete by looking at all possible moves it can make.


[[File:GameTrees1.png|center|250px]]
[[File:GameTrees1.png|center|250px]]


For example, if the computer was white and was the player to move, it has three choices: move the king up, diagonally up and right, or right. Next, it looks at all the possible moves its opponent could make. Black could move his/her/its pawn down, the king down, down-left, or left. Then the computer looks at each move it could make after that, and then each move the opponent could make after that, and so on and so on and so on until it runs out of time. Finally, it looks at all the possible combinations of moves that it predicted and will choose a move which will give it a better chance at being ahead later in the game. This may seem like an inefficient way to play, especially at the beginning of a game when there are more pieces, but chess computers are very quick. Within one second, Deep Blue evaluated two hundred million positions.
For example, if the computer was white and was the player to move, it has three choices: move the king up, diagonally up and right, or right. Next, it looks at all the possible moves its opponent could make. Black could move his/her/its pawn down, the king down, down-left, or left. Then the computer looks at each move it could make after that, and then each move the opponent could make after that, and so on and so on and so on until it runs out of time. Finally, it looks at all the possible combinations of moves that it predicted and will choose a move which will give it a better chance at being ahead later in the game. This may seem like an inefficient way to play, especially at the beginning of a game when there are more pieces, but chess computers are very quick. Within one second, Deep Blue evaluated two hundred million positions.


Let’s apply Deep Blue’s strategy to our favorite game, Pokémon. Let’s say your friend and you are arguing once more about what movie you guys should watch. Since you mopped the floor with your friend last time (metaphorically, of course), you let your friend decide on the condition of the match. Your friend has gotten into breeding recently and comes to the conclusion you should each pick one level 1 Pokémon with no hold items and duke them out.  
Let’s apply Deep Blue’s strategy to our favorite game, Pokémon. Let’s say your friend and you are arguing once more about what movie you guys should watch. Since you mopped the floor with your friend last time (metaphorically, of course), you let your friend decide on the condition of the match. Your friend has gotten into breeding recently and comes to the conclusion you should each pick one level 1 Pokémon with no hold items and duke them out.  


Your opponent chooses an {{p|Elekid}} who knows {{m|Rain Dance}} (1), {{m|Thunderbolt}} (2), {{m|Ice Punch}} (3), and {{m|Psychic}} (4).
Your opponent chooses an {{p|Elekid}} who knows {{m|Rain Dance}} (1), {{m|Thunderbolt}} (2), {{m|Ice Punch}} (3), and {{m|Psychic}} (4).
You decide to go with your bff, {{p|Magby}}, with {{m|Belly Drum}} (1), {{m|Mach Punch}} (2), {{m|Fire Punch}} (3) and {{m|Thunder Punch}} (4). Both of these Pokémon have their Hidden Ability {{a|Inner Focus}}.
You decide to go with your bff, {{p|Magby}}, with {{m|Belly Drum}} (1), {{m|Mach Punch}} (2), {{m|Fire Punch}} (3) and {{m|ThunderPunch}} (4). Both of these Pokémon have their Hidden Ability {{a|Inner Focus}}.


The Pokémon’s stats are set ups as follows.
The Pokémon’s stats are set ups as follows.
Line 51: Line 51:
[[File:GameTrees5.png|left|650px]]{{-}}
[[File:GameTrees5.png|left|650px]]{{-}}


We also see that Magby’s Fire Punch is always just better than its Mach Punch (especially since it’s faster than Elekid anyway) and Thunder Punch. However, this technique can also be pretty dangerous. Belly Drum and Rain Dance do not have immediate benefits, so if we were only playing for one turn, we could discount them. However, since we’re playing until a knock out, we can’t just throw these branches away. This is where experience as a player really comes in handy. Looking at how this game is set up where there is nothing else to switch into and no one is holding anything, we can be confident in eliminating Pyschic, Ice Punch, Mach Punch, and Thunder Punch since they will always be outclassed.
We also see that Magby’s Fire Punch is always just better than its Mach Punch (especially since it’s faster than Elekid anyway) and ThunderPunch. However, this technique can also be pretty dangerous. Belly Drum and Rain Dance do not have immediate benefits, so if we were only playing for one turn, we could discount them. However, since we’re playing until a knock out, we can’t just throw these branches away. This is where experience as a player really comes in handy. Looking at how this game is set up where there is nothing else to switch into and no one is holding anything, we can be confident in eliminating Pyschic, Ice Punch, Mach Punch, and ThunderPunch since they will always be outclassed.


This makes our graph much less intimidating, and when we take it out to game completion, it will look like this:
This makes our graph much less intimidating, and when we take it out to game completion, it will look like this:
Retrieved from "https://bulbanews.bulbagarden.net/wiki/Special:MobileDiff/38040"