Smarter AI

[GSalty]

Hi, all. New to the forums, not new to Pokemon. That said, I am back to the game after a bit of a hiatus and got back into it watching LPs of fan-made games. I've pretty well outgrown main series playthroughs because they're too easy, and unfortunately I'm even having trouble staying hooked on fan-made games because they tend to be made difficult primarily by over-leveling your opposition as you progress, forcing you to grind or exploit the AI to progress.

I want a Pokemon game that not only allows you to battle strategically (by resetting PP after every battle) but requires it of you, with gyms based not on types but on different strategies (e.g., aggro, balance, stall, hazard stacking, volt-turn, etc.), that will have players sometimes get stuck at random trainers rather than just gym leaders or other major characters. In short, I want a Pokemon game marketed towards its older fanbase that can appreciate the complexity of this otherwise childish game.

But a game like this requires a genuinely challenging AI, which I haven't yet seen in a Pokemon game and, based on the Googling and thinking on the subject that I've been doing for the last couple nights, doesn't appear to exist yet (and may not currently be achievable). So I've come here to ask all of you whether any of you have any examples to counter my pessimism or personal experience trying to come up with better AI, yourselves.

Either way, I'm interested in discussing what anyone interested in improving Pokemon AI might think is the best approach, though if this isn't the place for that then I'll happily find another place to have that discussion.

From my understanding, the minimax approach used in chess AI's wouldn't be viable for Pokemon battling (unless modified somehow) given that turns are taken simultaneously as opposed to sequentially and that Pokemon is not a deterministic game (i.e., in chess a move has only one possible outcome whereas in Pokemon a move can have different outcomes - Will scald burn or not? Will it crit or not? Exactly how much damage will is do? Will its user be fully paralyzed or not? Will its user hurt itself in confusion or not? Etc.). Additionally, in the worst case scenario, a single turn has 625 different move combinations (each player could switch to 5 different pokemon, and each move could cause the user to switch to another pokemon (4*5) --> (5 + 20)^2 = 25^2 = 625. And this is before calculating outcomes (i.e., damage, status, possible speed ties, etc.) The first turn of a pokemon battle could have hundreds of thousands if not millions of different possible outcomes. Any algorithm capable of making those calculations even just a few turns in advance will need to run for days before deciding on a move.

Alternatively, one could try designing an AI that evaluates its team's strengths and weaknesses relative to its opponent's at the start of every battle, and constructs a more proximal win condition than KOing every Pokemon on the opposing team. For example, it could realize that its Dragonite could sweep its opponent's team after one DD once the opponent's mons have fallen below a threshhold level and then aim to accomplish that without losing Dragonite or getting it status'd - and also while avoiding falling into any traps of its opponents'. The downsides of this could be that it might forgo an obviously superior short-term move with a high chance of KOing an opposing Pokemon in favor of bizarre choices with high long-term payoff. I suspect it would also be very susceptible to really cheesy styles of play unless monstrously convoluted logic trees were built into it.

And this is pretty well where I stand right now. Not sure what, if anything, anyone will do or wants to do with these thoughts, but I wanted to put them out there before they escape my head and hopefully get some feedback from people who'll give me good ideas or put into perspective how impossible a task this is for me. Thanks.

*To be clear, I am asking about this because I am personally interested in developing better AI for future fan-mane Pokemon games. Though, for the record, I am also very inexperienced with this. Before I even decide to start working on it, I want to know how feasible it is at all.

 

[mgriffin]

First off let me say that I basically agree 100% with your opinion and proposed solution.

Here's some pointers:
1. Technical Machine.
2. Percymon.
3. ScotchKorean27's AI client for Showdown. Unfortunately he seems to be inactive on PC.

I also have a demo that has an AI that works a bit like the others, except that I have developed the engine that it runs on and so it's missing some features: notably there's only 3 moves, no items, abilities, natures, EVs, levels or PP, and no randomness of any sort; some of those towards the end of the list are intentional, and some are in development (right now my biggest problem is that adding items has caused my AI to get much slower).

You're right that the naïve solution of iterating over all the combinations ends up being a lot of computation. My approach drastically shrinks the size of the search space by making some assumptions, the most important of which is: "if you don't switch Pokémon the turn after your opponent's Pokémon changes then you won't switch at all". This means that we consider (4+5)² combinations for the first branch in the tree, but only 4² for the branches thereafter (until a Pokémon faints or switches—so it's a little more than 16 in practice).

This, along with a decent function for evaluating the game state seems to do alright. My AI will try to KO Pokémon that are preventing a sweep (or status opposing Pokémon that are threatening a sweep) because it computes the value of each Pokémon vs each opposing Pokémon (via "who would win in a 1v1") and iterates these values until they stabilize. So it will see that setting up a Dragon Dance suddenly means that it can KO four of the opposing team, instead of only one. Or it will know that Chansey is the only thing keeping the special sweepers in check (because when it looks at states where Chansey has fainted its team's score will be tiny).

If you do give my demo a go, you should note that it gets harder as you win battles. The way that the difficulty works is by using the same team evaluation functions to generate a team for you to battle that is appropriately good vs yours (e.g. not good vs yours to begin with, and then "too" good later on).

So in summary, yes this is possible.

 

[GSalty]

My Googling led me to Technical Machine (do you know whether the guy who made it still working on it?), but not the other two. I'll have to take a look at them.

I was impressed with your demo. It's simplistic but a great proof of concept and looks to me like a really solid foundation for more to come. I only played through a few games with one team and lost when I tested whether it would get stuck in a disadvantageous loop because it accurately predicted I'd switch to a flying type against an earthquake for the second or third time. Awesome stuff.

I'm not sure what you're developing your demo for, but I wonder whether it wouldn't be better, if designing AI for single-player games rather than Showdown battles, to give the AI some information instead of having it figure it out on its own - things like movesets, abilities, and held items - to improve its running time. Obviously it would be ideal for that information to be hidden, but maybe things like that can be worked in after it knows how to respond to and use any given item?

Anyway, thanks for sharing. I'm looking forward to getting started on this now.

 

[mgriffin]

My Googling led me to Technical Machine (do you know whether the guy who made it still working on it?)

I guess Technical Machine is still being worked on, at time of writing the repository says it was updated 3 hours ago.

I'm not sure what you're developing your demo for, but I wonder whether it wouldn't be better, if designing AI for single-player games rather than Showdown battles, to give the AI some information instead of having it figure it out on its own - things like movesets, abilities, and held items - to improve its running time. Obviously it would be ideal for that information to be hidden, but maybe things like that can be worked in after it knows how to respond to and use any given item?

My demo is for a single-player game, and so actually the AI does know exactly what sets you have at the moment (and theoretically you know all the AI sets—because it picks from the same Pokémon as you do). As you say, this simplifies things. I'm actually planning on keeping things this way, and making it fair by giving the player a way to see all that information themselves (in-universe I'll explain it as a feature of the Pokédex).

EDIT: Also because I'm just simulating naïvely with some relatively safe pruning the AI mostly "just knows" how to use items. There's some trickiness like:
- it won't know that Electric Seed does anything until it's in a state that has Electric Terrain (or is very close to it).
- it won't know that Substitute until Liechi Berry is a good idea (but it might work it out if it thinks that Substitute is a good move).
But it didn't need any special help to know things like "it's better to use two weaker attacks to prevent the foe being knocked into Liechi Berry range", or "I have to lock Specs Raichu into Surf because the foe has a ground type", or "I use a different move because Close Combat will lower my defenses and get me KOed".

Anyway, thanks for sharing. I'm looking forward to getting started on this now.

I'd love to watch your progress. Do you have a blog, or are you planning on posting updates here? If not you can expect to get some PMs from me in the future ;)