The minimax AI was able to use tactics like Pain Split, Spikes, and Magic Guard.
Writeup: https://varunramesh.net/content/documents/cs221-final-report... GitHub: https://github.com/rameshvarun/showdownbot
I think there are a few challenges not found in most other online games, one being that strategies that win on different strata of the ladder are not the same (e.g. hyper offense is the most efficient on the lower ladder, but at some point around 1500 / 1600 you will start losing using it...). Also, I wonder how well an A.I. trained on the ladder would do in a tournament (e.g. SPL), where the metagame is a bit different.
Your code looks like a good entry point for that, all that's needed is to write a new bot using ML libraries...
That, and ofc, games with a competitive scene come about because of their complexity: a pvp game is not expected to be “won” in the fashion that a single player game can be. In fact, ideally there would be no perfect/optimal play; merely optimal play given a particular meta, which should shift as the meta does (a near-optimal strategy is found, but as it becomes common, a normally weak but counter-strategy becomes more useful, in a perfect world this would be acyclic)
Instead of cycling, the meta ought to converge to a Nash equilibrium.
With the right mixed strategy, an opponent choosing a pure strategy would be at a disadvantage.
Randomising over a huge choice of pure strategies may be infeasible of course and in the real world players have to train for particular strategies which is why we see meta shifts. (Plus of course in the real world the conditions (assumptions) change due to gameplay patches.
And notably, a random strategy selection being optimal is non-ideal for human consumption. And as you note this doesn’t naturally occur in human pvp, because there are heavy natural biases (information spread, natural leaders in the subject, limited skillsets, time for the community to learn between dev balance shifts, etc). But even if we could have it, I don’t think we’d want it.
I think what competitive pvp wants are somewhat obvious optimal solutions, with natural counter-play. But these near-optimal solutions are tied to the current popular strategy. That is, half the fun is figuring out what the community at large is up to, and tracking it.
Which, finally, implies that the kind of games that grow a significant pvp community are naturally selected because they offer no clear, and static, optimal strategy. If an ML program did find such a strategy (outside of requiring superhuman capabilities, like zerglings dodging siege tanks), it would either kill the community, or get patched out. You could consider the ML algorithm as competing with an adverserial meat learning algorithm, in both strategy and spirit
An optimal AI should therefore include theory of mind, and human-prediction in particular, such that it can stay ahead of the meta.
I would say the model isn't as straightforward as the Mario or Sonic AI players, but is still achievable. Actually, I wish I had more time because this is definetly a project I would like to tackle.
Poker is a better example, because Nash-Equalibrium estimating algorithms have begun to perform better than humans in the past year or two.
Pokemon, like Poker, is a game of bluffing and partial information. I expect Pokemon's optimal strategy to be the same mix of fold (aka: switch your Pokemon out to a defensive Pokemon... eating an attack but minimizing the opponent's damage to your team), and bluff (stay in, maybe use a move that exactly counters your opponent's choice. Ex: An unrevealed Choice Scarf Draco Meteor, surprising the opponent that your pokemon is faster than the opponent expected).
There's definitely a recognizable 'tempo' to pokemon, where A picks a move that threatens B, B switches to something that can take it and threaten back, then A in turn switches to take the hit and threaten back. Which, much like just accurately betting your hand strength in poker, is enough to beat a lot of amateurs. The metaphor goes from there - though I might use 'raise' for leaving a threatened pokemon exposed, which lets us differentiate a strong hand ("I'll use a coverage move with higher speed") from a bluff ("I can hit his switch if I call it.") As an example, opening Koko v Landorus. The fold is switching Koko to Skarmory, the honest raise is HP Ice, and the bluff is Thunderbolt.
The basic ebb and flow of the game seems like it's that and one more layer - double switches and attempts to predict them. Above that, there's just not enough probability mass left to benefit from trying to triple switch, counter-counter-switch, and so on.
Of course, it's all made vastly more complicated by trying to trap, set hazards or status, and make space for setup moves. I'm not sure what it would take to get an unsupervised learner to value e.g. Rocks appropriately. My experience has been that neural nets struggle badly on assessing that sort of long term state change, though of course I'm not working at OpenAI or DeepMind levels.
I'd argue that the raise is U-Turn :-). Which instant-wins any switching contest (ex: U-Turn on the switch, leaving the option to switch into Magnezone to trap the Skarmory, or if Lando stays in you can switch to your dedicated Lando counter... not that Lando really has a solid counter mind-you, but you get the idea.).
The U-Turn war however, between Lando and Koko demonstrates the bluffing game once again. Koko staying in and doing something weird like Calm Mind, or even Reflect/Light Screen would be absurd, but it would definitely beat the Lando U-Turn in most cases.
Heh, good example. I keep running into defog Koko, I think precisely for this reason. In raw number terms it's not a great use of a Koko or a moveslot, but Koko forces so many U-Turns or outright switches that it's a strong way to gain momentum. And if Lan-T just switched out to avoid HP Ice, the check might not be ground, opening the door to Volt Switch away for even more momentum. Taking a time-biding move for specific switches is a pretty great example of this back-and-forth pattern.
(Although - I'm not sure Lan can/does U-Turn on Koko? If it's scarfed it can lead with Earthquake for a kill, if it isn't it'll drop to HP Ice before the turn.)
* Beats Koko Volt-Switch: Lando is immune, so Koko fails to switchout.
* Beats the Koko Uturn: Lando is slower, as the 2nd U-Turner you capture the switching momentum.
* Beats the Koko Thunderbolt: Its prediction-on-top-of-predictions going on here, but this happens sometimes.
* Beats the Koko Hard-Switch: Hey, maybe they thought your Lando was scarf'd so they hard switch out.
--------
* Loses to HP-ice: This is the "obvious move" for Koko to do, and will happen more often than not. But as you go up the ranks, people start going for 2nd tier or 3rd tier mind-games, and you see fewer and fewer "obvious moves", especially in the early game where momentum is such a big deal.
It really depends where you are on the ladder: how stupid or aggressive you think your opponent is and all that.
Certainly chess has a mental component, players develop styles, study one another, and try to throw opponents off balance. But all of that happens as a layer on top of the need to actually make good moves over the board - a bishop and knight endgame simply has a correct answer. Go is less constrained, but it's still alternating turns in a deterministic, perfect information setting.
Pokemon, meanwhile, looks to me somewhere between DOTA and poker. It's nondeterministic on crits, paralysis, accuracy, and a great deal else. It's effectively nondiscrete, in the sense that there's lots of variance which has only a chance of mattering. And it's heavily hidden-information - defining features like moveset aren't revealed. Meanwhile, the OpenAI Dota restrictions are heavily centered on removing hidden information (invisibility, wards) and unexpected state changes (summons, quelling blade, infused raindrop).
I expect Pokemon would be more tractable on these issues because the hidden information is usually discrete. (Think "does he have Protect" as opposed to "is he standing invisible on this pixel?") But they're still major stumbling blocks, especially with randomness that massively expands the branching factor of each interaction. A given Pokemon move might look something like "if Ferrothorn uses Leech Seed, will it hit, and if so will he switch out, and if so will he go to Kartana, and if he does will it Swords Dance or does it have Choice Band or does it have Fightinium Z, or will he go to Koko, and if so does it have HP Fire or is it a bluff?" Everything there past "use this move" is laboring under a high branching factor with high randomness.
I don't think it'd be impossible to do fairly well on the Pokemon Showdown ladder with a medium amount of advance work; an AI can run a damage calculator and just assume every enemy has one of the recommended movesets from the wiki, and be assigned a viable team with relatively low variance and branching. But if you take away any of that hand curation, I expect things would go downhill pretty fast. And if you take it out of Showdown premades into a format where the enemy lineup isn't known in advance, I'd expect the now-intractable branching factor to lead to very poor performance with incredibly slow progress.
It'd be a damn interesting experiment, though.
Imagine a world where someone can buy and trade towards a deck with 90% aces going up a person with 80% aces.
The exception is official Nintendo events, but most serious competitors at those will have a network of breeder friends to produce flawless Pokemon for them to use.
Feel free to ask if you have any questions about the competitive Pokemon scene, I was very into battling on simulator for a number of years and have a pretty good knowledge of the scene.
You can also freely substitute among your team of 6, though subbing replaces your attack for that turn. If you anticipate the opponent using an attack of a particular type, you can sub in something resistant to that attack.
In single-player/story mode, you never encounter an opponent at the maximum level, and the NPCs tend not to build type-diversified teams, so the player gets a huge advantage in most battles by just grinding a couple pokemon of the right type.
As far as the various pokemon vs another vs the simplicity of jkqa it seems to me something like a weighted adjacency matrix could handle the increased complexity even in a relatively simple ai (imagine two pokemon doing a graph traversal to opposite ends of a node graph, whichever gets there first wins).
Everyone counts cards so under extremely rare circumstances given card count X you can play as if the count is X+1 or X-1 thus mess with the minds of people who accurately believe the count to be X, possibly leading to an advantage, if, statistically, they're in a position where being one off in the count is worse for them than it is for you, or if you're in such a bad spot that it doesn't matter if you signal something false you're doomed anyway.
Most of the people claiming to shuffle track, are not. Still, you got three guys watching the dealer shuffle by hand, then two can troll the third by pretending and the third's all like "what did I miss?" maybe panic and do something dumb.
Its not as much fun as poker, no.
I agree theres no direct me vs you money transfer but plenty of "we're all gonna start with $500 and whoever has more at the end of the night is the winner".
Although I would agree with you in spirit, if you want to feel like you're playing poker, theres no point in simulating it poorly with blackjack unless theres extenuating circumstances (one of your buddies is nuts for the game, or thinks he's gods gift to the card counting art, etc)
You can add rules on top of a game all you want (e.g. we're all gonna start...) but that doesn't change the actual game that's being played.
Intermediate player (where its possible to mess with people) : I'm not good at this, whats the count now?
(edited to note: I think external card counting devices like a phone app are illegal everywhere, which does leave some of the fun in the game)
Experienced player : Everyone is effectively perfect at card counting making it boring again.
Something I don't like about blackjack as a game is casinos minimize the entertainment of the game by having like six decks that are shuffled constantly, how super boring why not just play slots or set your cash on fire and watch it burn. If you play it at home with one deck multiplayer and no shuffling foolishness its a moderately entertaining arithmetic game with multiple meta levels of "press your luck" although the house doesn't have guaranteed boring income under that format, which is why casinos won't play that way. Its a game that's too much fun not to be made boring, or something like that. Casinos could take sex and make it boring. Not a fan.
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.