Why Can a Machine Beat Mario but Not Pokemon?
medium.com
medium.com
But in PvP battles? Yeah, that would be interesting to train an AI on. In that case, everyone is the same level, so grinding doesn't help. Players actually use strategies beyond 'attack with whatever is roughly super effectice against their opponent's current Pokemon', and the number of choices available is in the tens/hundreds of thousands rather than merely what's available at any point in the main game.
Teaching an AI to work in that environment would certainly be a tricky challenge. I mean, at least chess and go had 'symmetrical' teams, meaning that any strategy could be done in any game. Pokemon? You have no idea what your opponent has on their team, and if you're unlucky, that could basically hard counter your own strategy without much you can do about it. Heck, even certain Pokemon are hard to predict on their own, with stuff like Charizard, Mewtwo or Necrozma having at least two possible form change options at any time.
It'd be interesting to see someone try and make an AI to do that, to fight against players in the Nintendo World Championships or on Smogon or what not.
The minimax AI was able to use tactics like Pain Split, Spikes, and Magic Guard.
Writeup: https://varunramesh.net/content/documents/cs221-final-report... GitHub: https://github.com/rameshvarun/showdownbot
I think there are a few challenges not found in most other online games, one being that strategies that win on different strata of the ladder are not the same (e.g. hyper offense is the most efficient on the lower ladder, but at some point around 1500 / 1600 you will start losing using it...). Also, I wonder how well an A.I. trained on the ladder would do in a tournament (e.g. SPL), where the metagame is a bit different.
Your code looks like a good entry point for that, all that's needed is to write a new bot using ML libraries...
That, and ofc, games with a competitive scene come about because of their complexity: a pvp game is not expected to be “won” in the fashion that a single player game can be. In fact, ideally there would be no perfect/optimal play; merely optimal play given a particular meta, which should shift as the meta does (a near-optimal strategy is found, but as it becomes common, a normally weak but counter-strategy becomes more useful, in a perfect world this would be acyclic)
Instead of cycling, the meta ought to converge to a Nash equilibrium.
With the right mixed strategy, an opponent choosing a pure strategy would be at a disadvantage.
Randomising over a huge choice of pure strategies may be infeasible of course and in the real world players have to train for particular strategies which is why we see meta shifts. (Plus of course in the real world the conditions (assumptions) change due to gameplay patches.
And notably, a random strategy selection being optimal is non-ideal for human consumption. And as you note this doesn’t naturally occur in human pvp, because there are heavy natural biases (information spread, natural leaders in the subject, limited skillsets, time for the community to learn between dev balance shifts, etc). But even if we could have it, I don’t think we’d want it.
I think what competitive pvp wants are somewhat obvious optimal solutions, with natural counter-play. But these near-optimal solutions are tied to the current popular strategy. That is, half the fun is figuring out what the community at large is up to, and tracking it.
Which, finally, implies that the kind of games that grow a significant pvp community are naturally selected because they offer no clear, and static, optimal strategy. If an ML program did find such a strategy (outside of requiring superhuman capabilities, like zerglings dodging siege tanks), it would either kill the community, or get patched out. You could consider the ML algorithm as competing with an adverserial meat learning algorithm, in both strategy and spirit
An optimal AI should therefore include theory of mind, and human-prediction in particular, such that it can stay ahead of the meta.
I would say the model isn't as straightforward as the Mario or Sonic AI players, but is still achievable. Actually, I wish I had more time because this is definetly a project I would like to tackle.
Poker is a better example, because Nash-Equalibrium estimating algorithms have begun to perform better than humans in the past year or two.
Pokemon, like Poker, is a game of bluffing and partial information. I expect Pokemon's optimal strategy to be the same mix of fold (aka: switch your Pokemon out to a defensive Pokemon... eating an attack but minimizing the opponent's damage to your team), and bluff (stay in, maybe use a move that exactly counters your opponent's choice. Ex: An unrevealed Choice Scarf Draco Meteor, surprising the opponent that your pokemon is faster than the opponent expected).
There's definitely a recognizable 'tempo' to pokemon, where A picks a move that threatens B, B switches to something that can take it and threaten back, then A in turn switches to take the hit and threaten back. Which, much like just accurately betting your hand strength in poker, is enough to beat a lot of amateurs. The metaphor goes from there - though I might use 'raise' for leaving a threatened pokemon exposed, which lets us differentiate a strong hand ("I'll use a coverage move with higher speed") from a bluff ("I can hit his switch if I call it.") As an example, opening Koko v Landorus. The fold is switching Koko to Skarmory, the honest raise is HP Ice, and the bluff is Thunderbolt.
The basic ebb and flow of the game seems like it's that and one more layer - double switches and attempts to predict them. Above that, there's just not enough probability mass left to benefit from trying to triple switch, counter-counter-switch, and so on.
Of course, it's all made vastly more complicated by trying to trap, set hazards or status, and make space for setup moves. I'm not sure what it would take to get an unsupervised learner to value e.g. Rocks appropriately. My experience has been that neural nets struggle badly on assessing that sort of long term state change, though of course I'm not working at OpenAI or DeepMind levels.
I'd argue that the raise is U-Turn :-). Which instant-wins any switching contest (ex: U-Turn on the switch, leaving the option to switch into Magnezone to trap the Skarmory, or if Lando stays in you can switch to your dedicated Lando counter... not that Lando really has a solid counter mind-you, but you get the idea.).
The U-Turn war however, between Lando and Koko demonstrates the bluffing game once again. Koko staying in and doing something weird like Calm Mind, or even Reflect/Light Screen would be absurd, but it would definitely beat the Lando U-Turn in most cases.
Heh, good example. I keep running into defog Koko, I think precisely for this reason. In raw number terms it's not a great use of a Koko or a moveslot, but Koko forces so many U-Turns or outright switches that it's a strong way to gain momentum. And if Lan-T just switched out to avoid HP Ice, the check might not be ground, opening the door to Volt Switch away for even more momentum. Taking a time-biding move for specific switches is a pretty great example of this back-and-forth pattern.
(Although - I'm not sure Lan can/does U-Turn on Koko? If it's scarfed it can lead with Earthquake for a kill, if it isn't it'll drop to HP Ice before the turn.)
* Beats Koko Volt-Switch: Lando is immune, so Koko fails to switchout.
* Beats the Koko Uturn: Lando is slower, as the 2nd U-Turner you capture the switching momentum.
* Beats the Koko Thunderbolt: Its prediction-on-top-of-predictions going on here, but this happens sometimes.
* Beats the Koko Hard-Switch: Hey, maybe they thought your Lando was scarf'd so they hard switch out.
--------
* Loses to HP-ice: This is the "obvious move" for Koko to do, and will happen more often than not. But as you go up the ranks, people start going for 2nd tier or 3rd tier mind-games, and you see fewer and fewer "obvious moves", especially in the early game where momentum is such a big deal.
It really depends where you are on the ladder: how stupid or aggressive you think your opponent is and all that.
Certainly chess has a mental component, players develop styles, study one another, and try to throw opponents off balance. But all of that happens as a layer on top of the need to actually make good moves over the board - a bishop and knight endgame simply has a correct answer. Go is less constrained, but it's still alternating turns in a deterministic, perfect information setting.
Pokemon, meanwhile, looks to me somewhere between DOTA and poker. It's nondeterministic on crits, paralysis, accuracy, and a great deal else. It's effectively nondiscrete, in the sense that there's lots of variance which has only a chance of mattering. And it's heavily hidden-information - defining features like moveset aren't revealed. Meanwhile, the OpenAI Dota restrictions are heavily centered on removing hidden information (invisibility, wards) and unexpected state changes (summons, quelling blade, infused raindrop).
I expect Pokemon would be more tractable on these issues because the hidden information is usually discrete. (Think "does he have Protect" as opposed to "is he standing invisible on this pixel?") But they're still major stumbling blocks, especially with randomness that massively expands the branching factor of each interaction. A given Pokemon move might look something like "if Ferrothorn uses Leech Seed, will it hit, and if so will he switch out, and if so will he go to Kartana, and if he does will it Swords Dance or does it have Choice Band or does it have Fightinium Z, or will he go to Koko, and if so does it have HP Fire or is it a bluff?" Everything there past "use this move" is laboring under a high branching factor with high randomness.
I don't think it'd be impossible to do fairly well on the Pokemon Showdown ladder with a medium amount of advance work; an AI can run a damage calculator and just assume every enemy has one of the recommended movesets from the wiki, and be assigned a viable team with relatively low variance and branching. But if you take away any of that hand curation, I expect things would go downhill pretty fast. And if you take it out of Showdown premades into a format where the enemy lineup isn't known in advance, I'd expect the now-intractable branching factor to lead to very poor performance with incredibly slow progress.
It'd be a damn interesting experiment, though.
Imagine a world where someone can buy and trade towards a deck with 90% aces going up a person with 80% aces.
The exception is official Nintendo events, but most serious competitors at those will have a network of breeder friends to produce flawless Pokemon for them to use.
Feel free to ask if you have any questions about the competitive Pokemon scene, I was very into battling on simulator for a number of years and have a pretty good knowledge of the scene.
You can also freely substitute among your team of 6, though subbing replaces your attack for that turn. If you anticipate the opponent using an attack of a particular type, you can sub in something resistant to that attack.
In single-player/story mode, you never encounter an opponent at the maximum level, and the NPCs tend not to build type-diversified teams, so the player gets a huge advantage in most battles by just grinding a couple pokemon of the right type.
As far as the various pokemon vs another vs the simplicity of jkqa it seems to me something like a weighted adjacency matrix could handle the increased complexity even in a relatively simple ai (imagine two pokemon doing a graph traversal to opposite ends of a node graph, whichever gets there first wins).
Everyone counts cards so under extremely rare circumstances given card count X you can play as if the count is X+1 or X-1 thus mess with the minds of people who accurately believe the count to be X, possibly leading to an advantage, if, statistically, they're in a position where being one off in the count is worse for them than it is for you, or if you're in such a bad spot that it doesn't matter if you signal something false you're doomed anyway.
Most of the people claiming to shuffle track, are not. Still, you got three guys watching the dealer shuffle by hand, then two can troll the third by pretending and the third's all like "what did I miss?" maybe panic and do something dumb.
Its not as much fun as poker, no.
I agree theres no direct me vs you money transfer but plenty of "we're all gonna start with $500 and whoever has more at the end of the night is the winner".
Although I would agree with you in spirit, if you want to feel like you're playing poker, theres no point in simulating it poorly with blackjack unless theres extenuating circumstances (one of your buddies is nuts for the game, or thinks he's gods gift to the card counting art, etc)
You can add rules on top of a game all you want (e.g. we're all gonna start...) but that doesn't change the actual game that's being played.
Intermediate player (where its possible to mess with people) : I'm not good at this, whats the count now?
(edited to note: I think external card counting devices like a phone app are illegal everywhere, which does leave some of the fun in the game)
Experienced player : Everyone is effectively perfect at card counting making it boring again.
Something I don't like about blackjack as a game is casinos minimize the entertainment of the game by having like six decks that are shuffled constantly, how super boring why not just play slots or set your cash on fire and watch it burn. If you play it at home with one deck multiplayer and no shuffling foolishness its a moderately entertaining arithmetic game with multiple meta levels of "press your luck" although the house doesn't have guaranteed boring income under that format, which is why casinos won't play that way. Its a game that's too much fun not to be made boring, or something like that. Casinos could take sex and make it boring. Not a fan.
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.
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.
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.
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.
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.
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.
Item Shops would IMO be the largest issue, but I did not see anything that looked like one.
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.
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.
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.
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.
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?
The main reason a machine has not already beaten Pokemon is that it is a nontrivial amount of work to connect a standard AI algorithm to a new video game, and nobody has crossed that hurdle for Pokemon. Mario is one of the most popular video games of all time, and so it is one of the few games that people have connected AI to.
If there was an AI that was connected to a Pokemon game, I am fairly confident the AI would be able to beat Pokemon. The article discusses the problem of having an unclear goal metric. That doesn't seem like a very hard problem to me - you can start with something like, win as many battles as possible. You might beat the game just randomly after you become powerful enough, or you might need some more tweaks to the metrics, but it doesn't seem like that should be a showstopper.
A lot of people are pointing out that Pokemon is fundamentally harder than games like poker or go. That is true, but the bar in this article is beating the game. For poker or go, AI is now better than any human. That is a much higher bar, that is not even relevant for the single-player Pokemon game.
For example, in Final Fantasy V (which came out 3 years before pokémon), a character could already catch monsters and have them battle against others. Many games already had a collecting element. The exchange/trading might be new though, as well as selling the same game twice, with only a few differences between the two (to encourage exchanges… and boost sales).
Pokemon Red, Green, and Blue are the number two Game Boy video games of all time. Behind Tetris of all games. This is a pretty extreme reductive statement, akin to calling Super Mario 64 "just a 3D platformer."
[0] http://arimaa.com/arimaa/ [1] http://icosahedral.net/downloads/djwu2015arimaa_color.pdf
https://kimonote.com/@mildbyte/travelling-murderer-problem-p...
Absolutely awesome.
Its a false equivalence. Its no more valid a comparison than asking why "CLOS Networks" can't play Mario by themselves, despite also being a network. (A CLOS Network is one kind of network topology for switches)
The human brain does NOT take the derivative of the error function and glide down it using gradient descent. There are no matrix multiplication circuits in the brain. Things work in completely different ways that biologists and psychologists barely understand today. It has to do with chemicals, neurotransmitters and other such, which are completely alien to Comp. Sci.
If you happen to die near a certain node you could add an ajacent node of "scary" or whatever. Reverse idea for nodes where you get free food and pokemon.
However, although the card game came out after the video game, I actually have thought about this pokemon a.i. a fair amount and I think its fair to same that the video game is in many ways a visualization of a card game and the traversing of the map isn't as critical as it seems.
We know that the video game can't be beat without collecting x amount of Pokemon, so my thoughts on which heuristic would be to start there before even worrying about the battle system. Consider how a game of starcraft works, is a pokemon battle system more advanced than starcraft a.i.? I don't think so but open to being convinced otherwise.
On the grand scale, Pokemon is essentially unloseable, as you can never really paint yourself into a corner you can't get out of. I've seen stupid challenge playthroughs where more than half the game can be beaten with only a single Magikarp... There are only a handful of unique encounters. Pure bloody-minded grinding will always see you through.
Can you elaborate? I’m familiar with both individually, but am not sure what you mean by doing pathfinding over a directed graphical model.
> Pokemon is an open world game
… not really. While you can walk around, sure, the actual game is mostly linear; the order in which you explore and visit towns is mostly predetermined. (It has to be, as the Pokémon and trainers you encounter become more and more powerful, so have to progress with that.) Most of the "branches" that occur while walking around any given part of the map will all coalesce on one of the entrances/exits to that part of the map. (I.e., either you leave the town, or you visit one of the buildings in the town, or you talk to someone in the town. Mostly, that's it; my point here is that one can simplify all the "standing at coordinate X, coordinate X+1, ... etc. greatly; those positions are essentially equivalent.)
As for a goal, I would just say "AND them together, then". Or just do the Elite Four; the credits scroll when you beat them, which I think is a pretty clear indication of "win". Catching them all is more akin to completing all the achievements in the game. (And requires running multiple coordinated games, as, for example, the starting 3 are only available once, at the beginning of the game. In order to "catch them all", you need two games where the player 1. doesn't evolve their starter and 2. trades it to you. Since usually the starter is the core of someone's team in a normal human game, I think one would normally run a small game. Or find someone you trust and only briefly trade the Pokémon, then trade it back, which counts as far as the Pokédex cares. Eevee, a Pokémon that can evolve 3 different ways in Gen I, represents a similar problem: you only get one, and have to choose. (I think Gen II's breeding system might work around some or most of this issue.))
While Super Mario is perhaps comparatively easy, I would offer up NetHack. It is "open-world" in much the same sense as Pokémon: you have an explorable area, but one that is still mostly linear. There are several "sub-modes" to solve, like the article notes about Pokémon: in Pokémon, you need to explore, train, capture new Pokémon, battle; in NetHack, you also need to explore, battle, manage items, solve Sokoban puzzles, etc.
Pokémon is fairly hard to "lose"; losing a battle just returns you to the nearest Pokémon center w/ half your money gone. (That might be more of an issue in Gen I, where, IIRC, money is finite until you beat the Elite Four; in Gen II, as soon as you have a trainer's phone number, I think money is technically infinite. Regardless, simply training a few Pokémon to Lvl 100 should be sufficient.) NetHack, however, is very easy to lose; death is permanent, and requires restarting from scratch.
And NetHack has been won by a machine: https://www.reddit.com/r/nethack/comments/2tluxv/yaap_fullau...