6 ms·

The complexity of Pokemon is much lower than the author implies. It's not really an open world game. There are lots of choke points where your branching factor

by phire 8y ago

The complexity of Pokemon is much lower than the author implies. It's not really an open world game. There are lots of choke points where your branching factor is limited drops down to two, continue forward to the next trainer or go back and regroup. There is no issue regrouping in Pokemon, you always end up stronger. There is also very little punishment for pushing fowards and failing, you lose half your money and maybe some time/frustration getting back to the same point, which is meaningless for an ai.

hiccuphippo 8y ago
And the main objective is pretty much beating the Elite 4. If it is difficult to make the bot decide which goal to go for, just pick one goal for it.
chongli 8y ago
All of the details you're referring to are way above the level of any machine that plays Mario. For SMB1 the branching factor is uncommonly low. Pokemon has an extremely high branching factor by comparison. This being measured at the level of controller inputs and memory content outputs. SMB1 can be beaten by applying random controller inputs, measuring the player's x value, and seeing what works. Yes, you do need to look a few seconds into the future on some levels but you never need to look ahead further than what's in the current level. Pokemon has no simple, short term, monotonic measure of progress to work against, akin to Mario's x position. That's it, really.
- chongli 8y ago
  To be fair to the machine, a human wouldn't even be able to tell what game they're playing, let alone be able to finish it, if all he had to go on was the raw memory values in response to controller inputs. The fact that Mario can be beaten at all given such an incredible dearth of information is impressive. RPGs and action adventure games like Pokemon or Zelda are too laden with human-specific cultural details: heroes, villains, a world, exploration, battle, progress. Think of Zelda for example. The wooden sword is not even necessary until the final encounter with Gannon. This isn't even immediately obvious to a human player: he knows that the hero needs a sword to defeat the villain. These are all cultural details a human already knows before beginning to play the game. The machine, on the other hand, knows the sword only as a bit in memory that causes a different branch to be taken in response to pressing the A button; a branch that returns to the main loop very quickly without any other obvious indication of progress. Yes, if used at the right time with the right position and direction, thrusting Link's sword causes enemies' health values to decrease. But since there are multiple ways to kill every enemy in the game (except Gannon) the sword is a luxury until the end.
  - Retric 8y ago
    I once watched my 8 year old sister play an RPG in a language she did not understand. She had only the vaguest idea what was going on but still made progress. Just randomly trying things looking for novelty is enough to progress through such games given sufficient time.
    - chongli 8y ago
      The RPG may have been in another language, but it presumably still depicted human or humanoid characters, objects, enemies, etc. Your sister knew far more about life (and consequently the game) than what a computer would know. Just having a basic concept of reality, that the world is made up of objects and agents, that some things can be interacted with, cause and effect, etc. is way beyond what a computer has (which is basically nothing). To a computer playing a game, "randomly trying things" has only one meaning: random control inputs. As mentioned earlier, random control inputs will not get you very far in any open world game. A computer playing Zelda would be lucky to reach the bottom right corner of the map (by maximizing x and y positions) using only random inputs and reinforcement learning. Actually completing the game is so far beyond that it's ridiculous.
      - Retric 8y ago
        This was simple menu driven early Final Fantasy style game on rails. So, some basic path finding and press X near stuff would be useful. But, it did not need to react to enemies, or have complex environments like Zelda games do. On the other hand, the meaning of all those random text blurbs was rather critical.
        chongli 8y ago
        Without being told, a machine is not even going to know the difference between a menu and the game world. Pathfinding? You need to have a goal in order to do that. How does a machine set high level goals without having any high level concepts of the game itself? It's all just a bunch of memory to the machine. There's no meaning attached to any of it.
vntok 8y ago
At basically any time during the game, you might want to suddenly abandon everything, go to a shop, buy pokeballs and/or incense, go into the grass and catch a particular pokemon that you will then train for some time before fighting a particular dresser. For example, in the first generation games, if you started with the fire pokemon, the first arena was much more difficult than with other starter pokemon, so you probably wanted to catch and slowly train more beasts before that fight. Delayed gratification patterns like this one are everywhere in Pokemon, which complicates AI approches. As an other example, consider Magikarp, a useless pokemon that unless is trained for quite a long time does not give any hint by itself of evolving into the much more powerful Gyarados. An AI would maybe catch it once by chance, but very soon it would learn that that pokemon is useless in fights and would discard it. A beginner human would too at first, although speaking to some NPCs revealed hints about perseverance paying off in training Magikarps. Without external help and knowledge, I doubt current AI technology is close to being able to speak to NPCs, understand these kinds of subtle cues AND act on them with a gratification delay measured in hours.
kurtisc 8y ago
The AI can't always know if it's going closer to the next trainer if the next trainer is off-screen. There's also no visible counter of how many trainers you've defeated, only how many badges you have. If you're giving the AI knowledge of where and what a trainer is and how to get closer to one, why not give it knowledge of the map of the routes? Then your branching factor is binary: are you further along, or not? That's not an AI beating Pokemon, that's an AI beating your decision tree. In fact, if the AI knows what RNG it's on, it's deterministic. So all it needs is a script. At one point in Gen 1 there are 4 gym leaders you can to get closer to. You can also go after one of two HMs. How can an AI determine success in that in a human timeframe? Additionally, one failure mode is ending up with no money, a level 1 Rattata, and no pokeballs. The AI might not feel frustration, but its branching factor just grew again. And the branches have loops. Edit: the crux of this is that it's not an AI (as described by Alan Turing) taking on Pokemon, it's ML. A general Pokemon-beating AI would need other tricks.
- roenxi 8y ago
  The issue with this logic is that the AI is being held to a subtly higher standard than a human. Consider this - how do _you_ know that there is a next trainer if it is off screen? I'd guarantee you didn't figure that out from the context of the game, because then you'd have the same problem as the AI - it isn't data that is provided in the game.
  - kurtisc 8y ago
    Because I can read and understand a context of a video game, a map, vision, etc. So now it's reduced the problem to creating a general human AI. Good luck! FWIW, a (ML) bot can beat Mario with just the x-value - what a human understands by viewing the screen.
    - roenxi 8y ago
      > Because I can read and understand a context of a video game, a map, vision, etc. Did you spontaneously figure out how to read? I put it to you that you didn't, and that you were taught how to by someone else. I'd also put that the entire concept of interaction has to be a learned thing in practice, because realistically nobody learns how it works without interacting with someone else who is already reasonably knowledgeable. Now obviously that AI can't read because we don't have a good way of telling it how to map glyphs to concepts that it understands. However, to call the glyph->concept mapping the core challenge of a Pokemon game is clearly silly. The concept of there being something off the edge of the map on screen isn't something you are figuring out from the game either, it is just an assumption from knowledge that the real world is larger than what you can see. Similarly, that is obviously not an important aspect of the game - it is assumed knowledge. The challenge of the game is to navigate and explore a simple world, figuring out which order of actions to take. Short-circuiting the knowledge acquired through reading and the priors about how a world behaves is completely fair when saying that an artificial intelligence has been developed and can beat the game. A human player is expected to already know how to do that too.
tveita 8y ago
The article is a bit misleading, of course you can make a bot that can beat Pokemon, just like you can make bots that can play e.g. World of Warcraft, but you'd end up embedding knowledge of concepts like trainers, shops, battles and probably even map-specific info into the code. What we probably can't do at the moment is make a bot that can learn to play any Pokemon-like game, with no specific knowledge of the mechanics, just by operating the controls and observing the pixels. For that you need to try a large number of strategies and see which works better, and "very little punishment" is a disadvantage when you're trying to tell a good strategy from a bad one. You'd much prefer being swiftly and brutally punished for mistakes so you can go back and try something different. E.g. how do you know that winning is good and dying is bad? How do you know that getting past a choke point is better than just wandering around town? How do you know getting stronger is progress, but reshuffling your inventory isn't?

by phire 8y ago

hiccuphippo 8y ago

And the main objective is pretty much beating the Elite 4. If it is difficult to make the bot decide which goal to go for, just pick one goal for it.

chongli 8y ago

All of the details you're referring to are way above the level of any machine that plays Mario. For SMB1 the branching factor is uncommonly low. Pokemon has an extremely high branching factor by comparison. This being measured at the level of controller inputs and memory content outputs. SMB1 can be beaten by applying random controller inputs, measuring the player's x value, and seeing what works. Yes, you do need to look a few seconds into the future on some levels but you never need to look ahead further than what's in the current level. Pokemon has no simple, short term, monotonic measure of progress to work against, akin to Mario's x position. That's it, really.

chongli 8y ago
To be fair to the machine, a human wouldn't even be able to tell what game they're playing, let alone be able to finish it, if all he had to go on was the raw memory values in response to controller inputs. The fact that Mario can be beaten at all given such an incredible dearth of information is impressive. RPGs and action adventure games like Pokemon or Zelda are too laden with human-specific cultural details: heroes, villains, a world, exploration, battle, progress. Think of Zelda for example. The wooden sword is not even necessary until the final encounter with Gannon. This isn't even immediately obvious to a human player: he knows that the hero needs a sword to defeat the villain. These are all cultural details a human already knows before beginning to play the game. The machine, on the other hand, knows the sword only as a bit in memory that causes a different branch to be taken in response to pressing the A button; a branch that returns to the main loop very quickly without any other obvious indication of progress. Yes, if used at the right time with the right position and direction, thrusting Link's sword causes enemies' health values to decrease. But since there are multiple ways to kill every enemy in the game (except Gannon) the sword is a luxury until the end.
- Retric 8y ago
  I once watched my 8 year old sister play an RPG in a language she did not understand. She had only the vaguest idea what was going on but still made progress. Just randomly trying things looking for novelty is enough to progress through such games given sufficient time.
  - chongli 8y ago
    The RPG may have been in another language, but it presumably still depicted human or humanoid characters, objects, enemies, etc. Your sister knew far more about life (and consequently the game) than what a computer would know. Just having a basic concept of reality, that the world is made up of objects and agents, that some things can be interacted with, cause and effect, etc. is way beyond what a computer has (which is basically nothing). To a computer playing a game, "randomly trying things" has only one meaning: random control inputs. As mentioned earlier, random control inputs will not get you very far in any open world game. A computer playing Zelda would be lucky to reach the bottom right corner of the map (by maximizing x and y positions) using only random inputs and reinforcement learning. Actually completing the game is so far beyond that it's ridiculous.
    - Retric 8y ago
      This was simple menu driven early Final Fantasy style game on rails. So, some basic path finding and press X near stuff would be useful. But, it did not need to react to enemies, or have complex environments like Zelda games do. On the other hand, the meaning of all those random text blurbs was rather critical.
      - chongli 8y ago
        Without being told, a machine is not even going to know the difference between a menu and the game world. Pathfinding? You need to have a goal in order to do that. How does a machine set high level goals without having any high level concepts of the game itself? It's all just a bunch of memory to the machine. There's no meaning attached to any of it.

vntok 8y ago

At basically any time during the game, you might want to suddenly abandon everything, go to a shop, buy pokeballs and/or incense, go into the grass and catch a particular pokemon that you will then train for some time before fighting a particular dresser. For example, in the first generation games, if you started with the fire pokemon, the first arena was much more difficult than with other starter pokemon, so you probably wanted to catch and slowly train more beasts before that fight. Delayed gratification patterns like this one are everywhere in Pokemon, which complicates AI approches. As an other example, consider Magikarp, a useless pokemon that unless is trained for quite a long time does not give any hint by itself of evolving into the much more powerful Gyarados. An AI would maybe catch it once by chance, but very soon it would learn that that pokemon is useless in fights and would discard it. A beginner human would too at first, although speaking to some NPCs revealed hints about perseverance paying off in training Magikarps. Without external help and knowledge, I doubt current AI technology is close to being able to speak to NPCs, understand these kinds of subtle cues AND act on them with a gratification delay measured in hours.

kurtisc 8y ago

The AI can't always know if it's going closer to the next trainer if the next trainer is off-screen. There's also no visible counter of how many trainers you've defeated, only how many badges you have. If you're giving the AI knowledge of where and what a trainer is and how to get closer to one, why not give it knowledge of the map of the routes? Then your branching factor is binary: are you further along, or not? That's not an AI beating Pokemon, that's an AI beating your decision tree. In fact, if the AI knows what RNG it's on, it's deterministic. So all it needs is a script. At one point in Gen 1 there are 4 gym leaders you can to get closer to. You can also go after one of two HMs. How can an AI determine success in that in a human timeframe? Additionally, one failure mode is ending up with no money, a level 1 Rattata, and no pokeballs. The AI might not feel frustration, but its branching factor just grew again. And the branches have loops. Edit: the crux of this is that it's not an AI (as described by Alan Turing) taking on Pokemon, it's ML. A general Pokemon-beating AI would need other tricks.

roenxi 8y ago
The issue with this logic is that the AI is being held to a subtly higher standard than a human. Consider this - how do _you_ know that there is a next trainer if it is off screen? I'd guarantee you didn't figure that out from the context of the game, because then you'd have the same problem as the AI - it isn't data that is provided in the game.
- kurtisc 8y ago
  Because I can read and understand a context of a video game, a map, vision, etc. So now it's reduced the problem to creating a general human AI. Good luck! FWIW, a (ML) bot can beat Mario with just the x-value - what a human understands by viewing the screen.
  - roenxi 8y ago
    > Because I can read and understand a context of a video game, a map, vision, etc. Did you spontaneously figure out how to read? I put it to you that you didn't, and that you were taught how to by someone else. I'd also put that the entire concept of interaction has to be a learned thing in practice, because realistically nobody learns how it works without interacting with someone else who is already reasonably knowledgeable. Now obviously that AI can't read because we don't have a good way of telling it how to map glyphs to concepts that it understands. However, to call the glyph->concept mapping the core challenge of a Pokemon game is clearly silly. The concept of there being something off the edge of the map on screen isn't something you are figuring out from the game either, it is just an assumption from knowledge that the real world is larger than what you can see. Similarly, that is obviously not an important aspect of the game - it is assumed knowledge. The challenge of the game is to navigate and explore a simple world, figuring out which order of actions to take. Short-circuiting the knowledge acquired through reading and the priors about how a world behaves is completely fair when saying that an artificial intelligence has been developed and can beat the game. A human player is expected to already know how to do that too.

tveita 8y ago

The article is a bit misleading, of course you can make a bot that can beat Pokemon, just like you can make bots that can play e.g. World of Warcraft, but you'd end up embedding knowledge of concepts like trainers, shops, battles and probably even map-specific info into the code. What we probably can't do at the moment is make a bot that can learn to play any Pokemon-like game, with no specific knowledge of the mechanics, just by operating the controls and observing the pixels. For that you need to try a large number of strategies and see which works better, and "very little punishment" is a disadvantage when you're trying to tell a good strategy from a bad one. You'd much prefer being swiftly and brutally punished for mistakes so you can go back and try something different. E.g. how do you know that winning is good and dying is bad? How do you know that getting past a choke point is better than just wandering around town? How do you know getting stronger is progress, but reshuffling your inventory isn't?