6 ms·

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 be

by CM30 8y ago

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.

ziaddotcom 8y ago
Is the battle system much different than playing blackjack with your own deck? Imagine a world where someone can buy and trade towards a deck with 90% aces going up a person with 80% aces.
- kd0amg 8y ago
  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.
  - ziaddotcom 8y ago
    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).
    - jknightco 8y ago
      There are no "human tells" in Blackjack. Its you against the deck. Maybe you're confusing it with poker?
      - VLM 8y ago
        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. Its not as much fun as poker, no.
        ghaff 8y ago
        But there are effectively no other players as far as you're concerned. You're playing against the dealer/house who makes purely rule-based plays.
        VLM 8y ago
- 666lumberjack 8y ago
  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.
  - esrauch 8y ago
    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?
    - 666lumberjack 8y ago
      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.
nbeleski 8y ago
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. [1] https://blog.openai.com/openai-five/ https://blog.openai.com/openai-five/
- Veedrac 8y ago
  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.
- dragontamer 8y ago
  DOTA is a bad example. 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).
  - Bartweiss 8y ago
    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.
setr 8y ago
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)
- WorkLifeBalance 8y ago
  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.
  - Filligree 8y ago
    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.
  - setr 8y ago
    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
666lumberjack 8y ago
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.
varunramesh 8y ago
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. Writeup: https://varunramesh.net/content/documents/cs221-final-report.pdf https://varunramesh.net/content/documents/cs221-final-report... GitHub: https://github.com/rameshvarun/showdownbot https://github.com/rameshvarun/showdownbot
- brandonhorst 8y ago
  Considered building something like this last year, and couldn't find any prior art online. Looking forward to reading your report!
- catwell 8y ago
  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...

by CM30 8y ago

ziaddotcom 8y ago

Is the battle system much different than playing blackjack with your own deck? Imagine a world where someone can buy and trade towards a deck with 90% aces going up a person with 80% aces.

kd0amg 8y ago
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.
- ziaddotcom 8y ago
  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).
  - jknightco 8y ago
    There are no "human tells" in Blackjack. Its you against the deck. Maybe you're confusing it with poker?
    - VLM 8y ago
      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. Its not as much fun as poker, no.
      - ghaff 8y ago
        But there are effectively no other players as far as you're concerned. You're playing against the dealer/house who makes purely rule-based plays.
        VLM 8y ago
666lumberjack 8y ago
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.
- esrauch 8y ago
  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?
  - 666lumberjack 8y ago
    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.

nbeleski 8y ago

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. [1] https://blog.openai.com/openai-five/ https://blog.openai.com/openai-five/

Veedrac 8y ago
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.
dragontamer 8y ago
DOTA is a bad example. 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).
- Bartweiss 8y ago
  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.

setr 8y ago

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)

WorkLifeBalance 8y ago
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.
- Filligree 8y ago
  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.
- setr 8y ago
  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

666lumberjack 8y ago

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.

varunramesh 8y ago

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. Writeup: https://varunramesh.net/content/documents/cs221-final-report.pdf https://varunramesh.net/content/documents/cs221-final-report... GitHub: https://github.com/rameshvarun/showdownbot https://github.com/rameshvarun/showdownbot

brandonhorst 8y ago
Considered building something like this last year, and couldn't find any prior art online. Looking forward to reading your report!
catwell 8y ago
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...