If you're following video games, Pokémon isn't really anything special. It's an RPG. It's doesn't have any innovative gameplay. What was new at release, is the way it combines things which already existed at the time.
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).
It's special to me, the tv show and the trading cards assisted with that. I rekindled my love of the franchise getting into speed running a few years back. 10yo me would spend weeks slow grind progressing. 22yo me trying to speedrun it in sub 2 hours.
I'm not denying that it's special to many people, but this is true of many things in pop culture. I was answering the GG-parent with regards to "understanding" Pokemon. I'm arguing that it's easy to understand as a video game. As a pop culture phenomenon, the question doesn't really make sense, calling for a tautological answer.
> If you're following video games, Pokémon isn't really anything special. It's an RPG.
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."
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
> 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.
If you tell it directly what the meaning of the text is then I disagree, you've done the hard part. Then it's not beating Pokemon, it's beating the next task on your list, e.g. 'Go and get this thing from this city and bring it to this person in this city'. The alternative is don't go for teaching it the meaning at all, where there is a functionally zero chance of it randomly taking the plot token to the right place and then realising it can progress further.
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?
I think the battling issue may be a hard one for AI to deal with alone, though not so much in terms of the main game. Remember, the main story is meant to be beatable by people who don't want to think very much and who don't really care about training their team beyond 'reach a certain level'. Hence in the main story, 'grind until you significantly outlevel the next opponent' would probably be an optimum strategy for an AI.
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.
A pokemon can be one (or two) of a bunch of different types like "bug" or "rock" or "ghost," each of which comes with a particular set of types it's vulnerable to (2x damage taken) and another set of types it's resistant to (0.5x or 0 damage taken). So no one pokemon has an advantage over all the others, and there's no 2-3-4-...-J-Q-K-A strength ordering for types.
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.
Right, but IRL blackjack the human is the pokemon, vulerable to various type of human tells etc to what is otherwise grindable.
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).
Any multi player game with hidden data lets you troll the other players. So if its the dealer and two or more players sharing a deck you can mess with them.
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.
Three players off the same deck is not unheard of, I suppose it depends on state regulators and casino policy.
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)
It doesn't matter how many people are playing off the same deck, you're only playing against the dealer, and they're following protocol. When its your turn, its you vs. the state of the game.
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.
Most people who battle at a high level play on a simulator where any legal Pokemon is available to everyone, or alternatively use tools to 'hack' whatever Pokemon they want into the game. Some of the most popular strategies use Pokemon/Move combinations that were only available through events 10+ years ago, but since it's possible to transfer those Pokemon forward to the latest games those moves are available to use.
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.
They can't possibly verify that the Pokemon came from a network of breeders instead of one of them hacking it in right? Is it just that if you have a suspiciously perfect lineup you need at least a plausible sourcing explanation?
There are a surprising number of hidden values / details with which a naive hacker could be tripped up - especially for event Pokemon - but it is definitely possible to create undetectable hacked Pokemon with enough work. There are also cloning glitches in many of the games that allow one perfect Pokemon to be replicated and distributed to multiple people, although that's mostly used for casual play because it'd be suspicious for multiple competitors to show up at a tournament with exactly identical Pokemon.
Given the results obtained by the OpenAI in Dota[1] (with asymmetrical teams nonetheless) I am pretty confident RL could be used to train a pretty efficient pokemon pvp agent. From my experiences the nuances and mindgames/predictions in a pokemon battle are much simpler than those in a high level chess/go game.
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.
What experience do you have? Because this seems opposite my expectations; I doubt standard techniques will do all that well. The only thing harder about chess seems to be that people take it more seriously, so the average skill of the playerbase is higher.
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).
The poker analogy seems like the right one to use, although Pokemon is made messier by the level of variance. (Meaning both "semi-random effects" and also "far more than 52 possibilities for mon and moves".) I'd imagine the completely-hidden playstyles would be incredibly hard for an AI to learn, but the popular Showdown style that has team preview might be workable. The poker analogy seems like a good one, at least for studying the sorts of things an agent would need to do.
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.
> 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.
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.)
It really depends on what I'm predicting. U-Turn on Lando wins a surprising number of options:
* 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.
The comparison to chess and go seems strange to me, I wonder if you could elaborate?
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.
I think one major difference between pvp games and games like mario/pokemon campaign is that in the former case, the machine is competing with a meat learning algorithm. That is, it doesn’t have to find a good enough solution to a static map, but best an alternative optimization strategy (powered by wetware) before it can reasonably claim success.
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)
Meta doesn't imply cycling, just that the best strategy may be a mixed strategy which involves randomly picking between different pure strategies.
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.
However, the meta does in fact exist. The optimal, mixed strategy is only optimal when your opponent uses the same mixed strategy. We don't, so if the AI can predict us then it can do better.
An optimal AI should therefore include theory of mind, and human-prediction in particular, such that it can stay ahead of the meta.
I wasn’t suggesting that meta’s naturally cycle, but that the ideal meta (for human play, based on my experience on what people enjoy about pvp games that aren’t purely emphasizing skill) is one that lacks an optimal strategy, because the usage of an optimal strategy implies its own downfall, and that this meta-countering operation is acyclic. (A cyclic meta is likely created by accident, and kills the pvp community if left as-is)
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
There have been at least two attempts (that I know of) to create a competitive (6v6 singles) battling AI, although they were a few years ago and relatively primitive by modern standards. I expect that the relatively limited official support for competitive play would make Pokemon less appealing to the types of institution doing AI research, so you're limited to what a handful of amateurs can do.
In 2014, I wrote a minimax-based AI to play games on Pokemon Showdown. We adapted Showdown's battle simulator for our tree search. The hardest part was syncing the local simulator state with the actual game state - the battle state in Pokemon is both complex and partially observed. Bugs in this process could result in the AI using Protect twice because the state wasn't updated with the fact that it used Protect the previous turn.
The minimax AI was able to use tactics like Pain Split, Spikes, and Magic Guard.
This is super interesting. I would like to see a real (learning, à la AlphaGo) A.I. play on Showdown OU someday, without cheating (i.e. about the number of matches per day a real human player would play).
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...
Discover as much of the map as possible? Talk to as many NPCs as possible? Try to get as many different dialogues from NPCs as possible? (I assume that to get to the you won dialogue means you encounter more dialogues than if you cleverly lose.)
With the bayesian mesh you could arbitrarily apply heuristics over what otherwise looks pretty similar to a simple coordinate map.
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.
Sure, the heuristic function can be as complex as one wants, but what's a good heuristic? How can we formalize winning Pokemon? (Without getting too low level, so that ideally the same heuristic would work for other RPGs too.)
I could go many ways with that but I guess it depends how much we assume about the a.i.
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.
The card game is orders of magnitude more complicated than the video game battles - all that they are is very vanilla JRPG combat with a couple layers of rock, paper, scissors mechanics. One could probably write a finite state machine that would win 95% of the time in a couple hours.
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.
For actual gameplay, I said A card game, not the card game. Had something like war in mind. Although, I see how that may have been confusing as I made the connection of the card game version in the sentence before.
Branching factor alone doesn't tell you much. The important thing is how many branches are meaningful. Consider the board game Arimaa, which has an enormous branching factor[0]. It was designed to be difficult for computers, but in 2015, David Wu's "Sharp" software beat some of the best humans players[1]. This didn't need any revolutionary new AI techniques, only some clever human-written heuristics used in combination with classical computer chess techniques to prune the game tree. There are many possible moves each turn, but most can be discarded as obviously bad. The same could be true of Pokemon.
back to "mari/o", i was wondering why is it that a human brain can learn to play mario without having to die a billion times? Why is it that humans don't need a large training dataset? Is there a way to design a neural network in such a way where there is very little training to get a pretty good model?
Because artificial neural networks work nothing like human neural networks, despite the same names.
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.
While Pokémon might have a higher branching factor than Mario, I don't think that means a "machine can't beat it". First, I'm going to use Gen I/II (Red/Blue/Yellow // Gold/Silver/Crystal) here as "Pokémon", the game, as I am most familiar with them; I am not particular aware if the formula has changed in more recent generations.
> 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.
I think this article's key conclusion is incorrect, and that is is likely possible for modern AI techniques to beat Pokemon.
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.
This isn't exactly a case where a machine beats a game, but if you want to get an idea of how such a machine would need to think, and if you want to see someone apply a lot of interesting algorithms to brew a sequence of steps to speedrun a game with much more complexity than Pokemon, check out Artjoms Iškovs's series where he comes up with a speedy approach to become the head of all factions in Morrowind:
75 comments
[ 3.0 ms ] story [ 151 ms ] threadrpgs have too many choices and no score.
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."
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.
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.
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.
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?
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.
Imagine a world where someone can buy and trade towards a deck with 90% aces going up a person with 80% aces.
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.
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.
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.
[1] https://blog.openai.com/openai-five/
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.
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.
An optimal AI should therefore include theory of mind, and human-prediction in particular, such that it can stay ahead of the meta.
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
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...
https://en.wikipedia.org/wiki/Bayesian_network
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.
[0] http://arimaa.com/arimaa/ [1] http://icosahedral.net/downloads/djwu2015arimaa_color.pdf
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.
> 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...
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.
https://kimonote.com/@mildbyte/travelling-murderer-problem-p...
Absolutely awesome.