View Single Post
Mar 31st, 2010, 12:25:34 PM   #29
callforjudgement

Join Date: Jul 2009
Posts: 300

Quote:
 Originally Posted by Fat obi I am working on an AI to play Pokemon (I'll make a more in-depth, general thread on it later), and one of the things I need is an evaluation function. I am using an expectiminimax algorithm with alpha-beta pruning, which functions best when moves are already ordered best. This means I need a relatively simple function that can try and "guess" at how good a particular position is. Therefore, I need to assign values to various things so that my program can properly weight things. Unfortunately, Pokemon has elements of luck in it. This is why I have to use an expectiminimax tree instead of a minimax tree (I'm simulating the game as being a three-player game: AI, foe, and God. God moves whenever there are elements of luck). This means that I can't just get the order of things correct, I have to get their magnitude correct.
There is a huge huge risk with using expectiminimax with a game that contains prediction, such as Pokémon: the AI would be open to get outpredicted really really badly. (I've had some thoughts along these lines myself.) A contrived illustrative example: suppose your Starmie, on relatively low HP, has a choice of using Thunderbolt or Surf (let's say, its other attacks are out of PP...) and your opponent has only a slower Vaporeon (currently out) and faster Jolteon left, both on relatively low HP. You can KO either of them if you predict which one will be out at the time, but each will need a different move. Let's further suppose that the Jolteon's only attacking move is Thunder (maybe it was on a baton pass team), the Vaporeon will try to use HP Grass if it stays in (as the best attacking move available), and the Vaporeon can't survive switching out and back in due to Stealth Rock. Now, expectiminimax will think "if I use Thunderbolt, he'll switch to Jolteon and use Thunder to kill me next turn; if I use Surf, he'll stay in, use HP Grass and kill me this turn. But Thunder might miss, and HP Grass won't; so I should use Thunderbolt this turn, as it gives me a better chance of winning." There's one obvious failure in the reasoning here (the reasoning assumes that the opponent will outpredict; expectiminimax does that). There's a subtler failure, in that a human opponent can go through the same reasoning and decide to switch.

As you mention later in the thread, finding a mixed equilibrium avoids this problem (and shouldn't actually be too difficult; you can do 81 separate, relatively shallow, analyses, one for each of the possible 9 moves that the opponent could use, and one for each of the possible 9 moves that you could use, then use the standard formulae to calculate the perfect mixed strategy). The usual caveats about mixed equilibria apply here, though; they make you impossible to predict, but also make the prediction level of the opponent irrelevant, in that any possible prediction by the opponent, so long as it's plausible (as in, counters something you have a chance of doing), leads to the same outcome on average; I wonder if trying to use psychology on prediction would work better than the purely random method?

Quote:
 Originally Posted by Fat coolking *Brain explodes* Interesting but complex. I have a couple thoughts. How will the AI make its team? Will we make it for it, then let it play? I would find it interesting to know the "best" team possible, according to the AI.
I've had some thoughts along these lines myself; I was using the switching stats in order to generate a team that had a good switchin to any OU that the opponent might come up with, and left the opponent with no switchins that devastated the team in general. (How good one Pokémon was as a switchin for another was estimated in terms of of how often people actually made the switch in question, with adjustments for the relative usages.) I produced an RMT calculator from the results, which was discussed in this C&C thread; but one obvious thing to do with such a calculator is to try all possible OU teams in it, and see which is considered the best; doing this over the course of days gave me Blissey, Gliscor, Vaporeon, (Zapdos|Rotom-H), Forretress, Weavile as the resulting team. (There was only a very marginal difference between using Zapdos and using Rotom-H.) Of course, there are all sorts of problems with this method; the two biggest problems are that it doesn't take sets into account (because the statistics it was based on don't contain sets), and that it can't allow for a Pokémon being "just better overall" than another Pokémon (i.e., it calculates what Pokémon are good at, but not how good they are relative to other Pokémon). Some day I'd like to build that team and see how well it actually does; it would likely be the only team ever built either entirely on theorymon, or not at all on theorymon, depending on your point of view.