VGC Problem Definition

[caymansimpson]

First Discussion! I wanted to formalize the problem definition of Singles and VGC from an AI perspective that make them such hard problems to solve. All of us working in this area have already thought deeply about this -- and I'm sure this stream-of-consciousness will miss a ton! I would love people's thoughts and feedback, and I can go back and edit/add to this; I hope to use this as a foundation on which we can start discussing promising angles/approaches to tackling this problem.

Problem Area	Singles	VGC
Agents	This is a multi-agent problem.	Ditto.
Actions	Players decide actions simultaneously when making decisions and those joint actions result into a transition to a different game state, dependent on several random factors; This problem is stochastic. One thing that makes this problem very hard is that actions very often interact (e.g. roar before trick room).	In VGC, this problem is a lot worse, because the interactions between actions are even more complex (e.g. trying to self-Swagger in front of a mon with Follow Me).
Action Space	For singles, the action space is very straightforward; 13 (assuming dynamax). This means turn action space (both agents) is 169. Because there are so few actions one individual agent can make, this makes Singles prime for Minimax. However, Singles games.	For VGC, the action space is 418 (assuming dynamax), which means turn action space is ~175K. This means that any attempt at Minimax approaches will need to critically focus on pruning.
Game Length	Average turns per game are far higher in Singles, which means that reward-shaping is critical.	For VGC, especially in the dynamax world, games can end very quickly, which means that reward-shaping may not be as critical, as reaching terminal nodes (end of games) is more computationally feasible (with efficient pruning).
Imperfect Information	Pokeon is a game that is partially observable; this means that no player has perfect information (EV spreads, movesets, items). At high levels of play, agents should consider the information they expose to their opponent, and how that could possibly increase an opponent's efficacy.	In VGC, there is an extra element to this as well, which is "out of the 6 mons in team selection, which 4 did my opponent bring?"
Team Choice	Not relevant for Singles.	VGC offers this extra layer of strategic complexity -- given imperfect information and past information learned from a previous game (if applicable), what team offers the best chance of winning? This can be considered a separate problem.
Teambuilding	How to build a team to optimally perform in the meta is an interesting problem, but can be considered a separate problem.	This is more intricate in VGC, because of the "4 out of 6" mechanic mentioned above.
Contextual Knowledge	In Pokemon, there is a huge amount of contextual knowledge needed -- from items, to the meta, to movesets, abilities, stats and interactions between different battle mechanics. A successful agent will probably have some element of predictions of an opponent's moveset/items/EV spreads as it learns more information through a battle in order to refine its decision making. Another additional complexity is that this game is a game of edge-cases. Thinking about the actual battle engine coded out makes me cringe!	This is slightly more complex due to the ability to affect your own mons with your moves.
Luck	Because of move probabilities (accuracy and secondary effects), abilities (Moody), item probabilities (Quick Claw), damage rolls, critical hit chances, etc., actions don't reliably translate to states.	This is even harder to predict in VGC, where more actions mean more random variables, which means more possible states.
State Space	For all intents and purposes, we should treat it as infinite due to PP, HP and timer.	State space is technically bigger in VGC due to more possible interactions, but for all intents and purposes, they are the same.
Markov property	We can't assume that this game follows Markov properties, since past player behaviors will offer insight into future behaviors (eg risk-taking, defensive playstyles); this is especially true because there is often no optimal move.	Ditto.
Strategic Optimizations	Pokemon is a game of win conditions; best players see multiples ways of winning and aim to get closer to those setups. Because "reverse sweeps" are not uncommon, reward shaping to bias AI towards win conditions may prove especially difficult. This makes tree-based approaches very attractive over RL-based ones.	Ditto.
Other Properties	Pokemon is a zero-sum game, so there is technically a nash equilibrium. This means minimax solutions are possible (despite large action space and essentially a continuous state space).	Ditto.

From the above, my view is there are two approaches that might work for VGC: tree-based and RL.

	Pros	Cons
Tree-based	Don't need to encode contextual knowledge and edge-cases	Need ability to simulate Most of this problem is how to prune efficiently.
RL	Will handle continuous state spaces well	Reward shaping is difficult Encoding knowledge of move interactions will require incredible amounts of custom logic and training data.
Both	Most promising RL AIs are a combination of both. They're able to take Pros of both Tree-based and RL-approaches.	Cons are that there are no RL AIs that have been successful in the area that VGC lives in (continuous state space, high degree of chance). Also heavy computational cost.

[hsahovic]

This is a good summary of a lot of important issues related to this problem.
One thing I would add regarding the last section is that you can combine RL and Tree-based approaches - that's what AlphaZero does, for instance.

[caymansimpson]

Took PTO today, so I read AlphaZero's loose description and dug in its open source replications. What I learned:

• AlphaZero is a deep neural network that takes in the state and output action probabilities, along with the predicted value of an action
  • where the predicted value = E[expected outcome | state]
• It learns through self-play
• It doesn't use alphabeta pruning; instead it uses a Monte-Carlo tree search
  • It just self-plays a bunch
  • In each self-play, they branch off to explore different outcomes
  • How does it select states to explore more?
    • low visit count
    • high max(move probability)
    • high predicted value
  • Neural network aims to:
    • minimize error between predicted outcomes and game outcomes
    • maximize similarity of win probability with action probability
    • Mathematically, minimize the following:
      • (predicted outcomes - actual outcomes)^2 - sum(prob_actionlog(predicted_prob_action)) + constantsum(parameters^2)

My initial thoughts on it's suitability for VGC:

• Thanks @hsahovic for pointing me to this. It's very clear that if there is a future viable superhuman AI, it would come from a combo of tree-based and RL-based approaches.
• Because state space is continuous, AlphaZero's implementation does not smoothly translate to VGC. That being said, the above high-level principles should still apply:
  • Simulate 2-3 steps in the future
  • Need a proper reward function -- P(win), and in future iterations P(win | policy). One thing that is critical is that this output of this latter function is calibrated and represents the true probability of winning, esp given the compounded randomness that I reference in the table above.
  • Have a policy to guide tree search
  • Have heuristics to guide learning
• Pokemon is a noisy game given all the chance, so this method will actually be much harder to converge -- to be accurate, we'd need to run many different simulations with the same state-action pair to understand the true value of that pair; we'd need to generate a lot more training data
  • Initial estimations I found online said it would take a regular computer 170 years to train the network; this would likely be exponentially more for VGC
• Imperfect information will also make this task much more difficult, but we may be able to circumvent it with individual classifiers on the following things. If we could tap into showdown to get training datasets, this would be trivial (compared to the larger task at hand):
  • Ability
  • Items
  • EV / IV spreads
  • Mons brought
• We'll need to support "forking" games to generate training data to enable any type of tree-based algorithm
• The idea of self-play is extremely enticing to me! We should probably consider ways to speed up the initial state of the algorithm and set it on a globally optimal path -- either through transfer learning and/or heuristics.

From this, I think if we want to get coordinated, there are four areas that can be thought of independently:

Theme	Needs
Poke-env Development	Supporting simulations & Forking games / More VGC support / Parsing messages (ie to determine speed tiers)
Information Prediction Models	Models to predict mons' abilities, items, stats, and the opp's team. We'll need showdown training data to do this. This should help with convergence and speed, and can be eventually deprecated if we get to the point where our model learns the value of obtaining/hiding information.
Building learning/pruning heuristics	This can be in the form of an initial P(win) model, with some basic rules-of-thumb that will save significant computation cost. We can use just these as initial milestones for a V0 of our AI
Actual RL Development	This is the area that I'm least experienced in, but is where the bulk of work will go

[acxz]

Whenever AlphaZero comes up it is also important to mention its brother MuZero.

Essentially AlphaZero requires domain knowledge of the game, whereas MuZero does not need to know the rules of the game.

[caymansimpson]

Agreed. I do think Stochastic MuZero can solve VGC (MuZero only applies to perfect information games), but given the complex game mechanics, I would consider the solution intractable since Stochasric MuZeros solution requires such high amounts of training data for more simplistic games like chess, and hundreds of GPUs with custom-built infrastructure. Stochastic MuZero has also not shown great promise in stochastic environments either, so that’s another thing to solve.

[acxz]

the solution intractable since Stochasric MuZeros solution requires such high amounts of training data

Agreed. For folks without infinite hardware there must be a trade-off between theoretically elegant solutions and practical ones (i.e. something that I can throw in Pokemon Showdown).

Stochastic MuZero has also not shown great promise in stochastic environments either, so that’s another thing to solve.

Could you clarify this? For example, Stochastic MuZero has not shown promise in stochastic environments as opposed to what alternatives?

[caymansimpson]

Sorry for the lag in response; I think Stochastic MuZero has shown promise in more mechanistically straightforward and low stochasticity games; I think it's a cool and valuable algorithm! I chatted with a few folks at DeepMind who think that the scale and training requirements of the models for VGC would be intractable, even for professional teams at their respective companies.

The two areas that I think have shown promise in domains similar to VGC (within Deep RL) are ESCHER and rNAD, but neither has been validated/tried. Though their teams seems think their algorithms may be fits?

[melondonkey]

Great discussion here. I'm a bit late to it, but want to get involved as I've been thinking about RL for VGC (here's my current blog but more basic analytics) . I do believe deep RL + MTC + self-play is the ultimate answer to this problem but I don't know how attainable a good enough version is for pedestrians like me with both limited brain power and compute power.

Here are some intuitions and random thoughts I have about the problem currently, but have not yet gotten far along enough to put ideas into practice:

• Seed the algorithm with data from the meta. Most people describe the team space in terms of combinatorics but when you think of it in terms of entropy the uncertainty is vastly reduced (I have some blog posts tracking meta entropy in VGC). This does go against the design philosophy of AlphaGo Zero in that it uses data, but it also greatly reduces the search space and could be a path to topping the ladder. For example, we could have a team generator that constructs by marginalizing the usage statistics and then iteratively sampling based on the joint distribution. I've written some scrapers for the meta in R but would need to port them to python to work into a team constructor on poke-env.

• Probabilistic programming? I'm kind of iffy on this one because I'm not sure how much this adds with deep models but was wondering if tf-probability could aid with representing the uncertainty

• Updating the network appropriately for simultaneous moves. Assuming the architecture has a combined policy and state network like AGZero, I'm unclear on how the network would update "simultaneoulsy" given that it has two different imperfect perspectives of the game without one player getting to "cheat" with updated parameters. This problem has probably already been tackled or solved though I just don't know the answer.

• Make use of pre-trained mon-embeddings/move-embeddings, etc for transfer learning. Perhaps even the move descriptions could be used.

As added bonus here's a scraper script to extract meta info for a given format. Like I say, I'll try to submit a PR one day with something like this but I have a pretty steep learning curve ahead of me getting acquainted with all the current tooling.

Gist here

[NoahvdV]

Hi, big fan of your blog, been following it for quite a while.
Thanks for sharing your meta scraping code!

[melondonkey]

Thanks! Actually means a lot as sometimes it feels like I’m posting into a void. The chef post got a lot of attention but everything else has been pretty mum. However, that has taught me that the abstract really needs to connect with the concrete to resonate. That’s part of why I think VGC is the best meta to try for a proof of concept with AI.

[melondonkey]

Can you go over the calcs for the action space for VGC being 418? I calculated it as:

• 4 moves into 4 targets = 16
• 4 special moves (dynamax, terastalize, etc) into 4 targets = 16
• 2 switch options
• 16 + 16 + 2 = 34 options for one Pokemon
• 34*34 = 1156 for two Pokemon
• 1156 - 1 = 1155 (since both Pokemon cannot switch into the same mon)

The edge cases I didn't include are pivot moves like U-Turn and Parting Shot.

[caymansimpson]

This is my math, where I break each state space by how we choose mons switch: - if two switches: 2 (cuz positions matter) - if one switch: 2 (cuz either mon could switch) * - switch mon: 2 possible switches - if non-switch dynamaxes: 4 moves * 2 targets - if non-switch doesn't dynamax: 4 moves * 3 targets = 80 - if no mon switches: - if one dynamaxes: 2 possible dynamaxes * (4 moves * 2 targets) * (4 moves * 3 targets) - if none dynamaxes: (4 moves * 3 targets)*(4 moves * 3 targets) = 336 I think where we differ is: 1/ position matters if we switch two 2/ dynamax moves only have a max of two targets 3/ im assuming moves have a max of three targets (can’t think of ones that have 4 off the top of my head; but I’m probably missing multiple 😛) 4/ only one mon can dynamax on a turn 5/ pivot moves, which is something I definitely consider

…

Sent from my iPhone

On Sep 15, 2022, at 10:10 AM, melondonkey ***@***.***> wrote:  Can you go over the calcs for the action space for VGC being 418? I calculated it as: 4 moves into 4 targets = 16 4 special moves (dynamax, terastalize, etc) into 4 targets = 16 2 switch options 16 + 16 + 2 = 34 options for one Pokemon 34*34 = 1156 for two Pokemon 1156 - 1 = 1155 (since both Pokemon cannot switch into the same mon) The edge cases I didn't include are pivot moves like U-Turn and Parting Shot. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.

[acxz]

Imperfect Information
Pokeon is a game that is partially observable; this means that no player has perfect information (EV spreads, movesets, items). At high levels of play, agents should consider the information they expose to their opponent, and how that could possibly increase an opponent's efficacy.

I'd like to add more here.

Observability, Im/perfect information, and In/complete information are all different concepts, although closely related.

As you mentioned, Pokemon Battles are partially observable, as the state of pokemon battles includes opponent stats, movesets, items that are unknown to the agent.

Pokemon battles are also imperfect information games as the stats, movesets, items of the opponent are hidden from the agent, but important to keep in mind the action (i.e. opponent moves at a specific turn) is not hidden.

Pokemon battles are (I believe) are incomplete information games as while the objective of each agent (knock out opponent pokemon) is known to all other agents, the policies and strategies are not.

Just my two cents.