How an A.I. is Becoming the World's Best Pokemon Player

to master a game you need a plan and a good place to start is to find how many different places you might have to use it for simple games the numbers start small but as the games add pieces and places they can go its amounts of situations and its difficulty to master skyrockets the further games are on this list the closer making a computer that plays it at a human level comes to the limits of what we can build but you know what we're here for so where's pokemon oh wait a minute that's not right that number seems too small oh okay that's just for turn one that does make more sense but if we had the graph show the number for every turn well this happens despite its worldwide popularity surprisingly few people know that underneath the veil of a kid's game pokemon is one of the most complex two-player strategy games out there and with this complexity building a computer that can not only outplay humans let alone those who've played competitively for over a decade sounds impossible right i don't think so i don't think so hi and welcome to the third build today is about my journey in creating future site ai a computer program that learns how to play pokemon like a human and at a competitive level this will not only cover the main steps in how i made it but also how well it did what his next plans are and how you can battle it yourself so let me start by clarifying that intro and tell you what goes into playing competitive pokemon most of you will know pokemon is a game where you go around catching fun creatures however the purpose of all this catching is for your caught pokemon to participate in battles where you and your opponents send out pokemon to face off each turn you choose one of four different moves or switch between one of your six team members with the goal of bringing the health of your opponent's team to zero where the complexity comes into play is in what those move and switch options can do and how many options you have for those options for example let's take our four moves each can be one of 18 different types that come in their own web of strengths and weaknesses and can do a combination of effects like doing damage healing yourself poisoning your target changing the weather and so much more but before you can pick from any of those moves you have to choose them from a list of about 40 useful ones each mod can learn looking at this information alone this mod already has a total of almost 100 000 different ways you can use it or more importantly it can be used against you and again that number only represents picking moves if i explained all the options of choosing your team members all of their stats or even the stats of their stats you'd start to see that that number for how many ways a battle can start might feel like an understatement so that whole explanation said i want to let y'all know that you might feel like there are some over or underexplained topics throughout the video and that comes from my guess that the people watching this at least when it comes to pokemon will be those who know nothing or those who know everything and then amongst all my viewers pretty much no one who has a lot of ai experience myself included so please bear with me because i'm gonna try my hardest to explain it all to best fit you and because things still might get confusing i want to try something new if a question comes to your mind about anything i talk about go ahead and write it down somewhere else see it best place to comment section and if i get more than a dozen or so on the friday of the week i'm releasing this i'll put out a follow-up video where i answer some of those questions and for all two pro data scientists watching this go ahead and take out a large sheet of paper because uh you're gonna need all that space to keep track of all the things i might have done wrong but that's okay because this is my first real data science project and i'm here for the feedback just don't be pretentious i don't have patience for that alright that's enough intro let's just dive into how future site ai works there are three major jobs that this ai must pull off to be effective number one understand whether it's winning number two predict how its choices will play out and number three determine what is not told about the opponent's team we're going to start with the one that this project only started because and could not be done without this project only started because of my interest in the nba i noticed that websites would post a team's current chance of winning during games and i wanted to know how they were making those predictions so i figured that the best way to understand it was to try making my own once i got a little bit into that project it occurred to me that a sporting event and a pokemon battle couldn't be all that different from a data perspective so i tried making predictions for this game too so it turns out that finding the chance to win of a basketball game is relatively straightforward as it mostly comes down to the current score and how much time is left however pokemon doesn't have any concrete indicators for your chance to win since if you used your current health for example as your substitute for a score well anyone who's played the game can tell you that just because you have more hp than your opponent does not guarantee that you're going to win that means in order to do this i had to figure out how a bunch of different factors relate to how well you're doing in a battle and the go-to place for solving a problem like this nowadays is machine learning the reason machine learning is great for an application like this is once you have a machine learning model set up it can sort out hard to solve problems for you this works since you can give it a set of factors you think are part of the answer the model can figure out how important each factor is or how to interpret them and then it will give you an answer by using that importance to put those factors together as a starting point i decided that these are the attributes that could be useful in determining a player's likelihood of winning the pokemon fans out there might be wondering why ideas like each pokemon's type or their ability aren't factored in and that's because at the time i thought those factors didn't change too much for a particular pokemon that just knowing which pokemon it was would do a good enough job in representing those ideas for creating the model i decided to use tensorflow i'd already planned on doing the entire project in javascript and since you could access tensorflow's entire library of machine learning tools directly from that language it was a perfect fit and to my fellow programmer out there who's about to write a comment about why i shouldn't have used javascript for x y and z reason yes i know you're right i found out the hard way it's just i didn't have much of a choice in the language i used and i'll get to why in a moment the biggest requirement for creating most machine learning models is having a bunch of examples of the data that you're going to put into it or the answer you're looking for is already known so it can figure out how those factors relate to that answer so for me that means i have to somehow find tons of different battles where i know the teams of both players can see exactly what happened on every turn and know the answer of who won so enter pokemon showdown a fan made simulator where people can play competitive pokemon against each other and most importantly save their finished battles to the website to be viewed by anyone later this means i potentially had a source of thousands of daily examples that had all the details i was looking for all i had to do was figure out a way to get all those battles and put them into a format that tensorflow can understand at first this meant me manually running a program to download all the battles on their public server on a daily basis but when someone on their team noticed my project they decided to provide me with 2 million battles to train on which was way more than enough to get the job done so big shout out to them for helping me out there i then trained the model so every turn of the battle was a separate example with their answer being whether player 1 ended up winning and in the end i had made a model that could predict correctly who would win from any given turn with at most 81 accuracy i haven't yet mentioned just how much randomness could turn the tide of these battles like when a really strong move that won't always hit misses so getting this right 100 of the time is impossible which makes that accuracy near the upper limit of what's reasonable now because of how i structured my code i realized it was only a few modifications away from creating models that could help predict your opponent's next move it really just took switching out the answer from being whether player one would win to what player one would do in the next turn and in the end i was able to create three models that represent the different aspects of what a player can do each turn with even greater accuracy than before getting these models to this accuracy was a project unto itself so i decided to release these predictions as something you can use if you go to your web browser's app extension store and look up pokemon battle predictor you'll find a free extension that i made which i admittedly don't update as often as i should which enables you to view the predictions these models make for the battle that you're playing or just watching live it works for most singles formats and you can find more information about it in the description that's it for predictions so it's on to step two this step is where future site ai gets its name as it's all about looking at how a battle might play out when the ai makes its next move the basic steps of this are figuring out what move options you and your opponent can choose seeing what happens on all the different combinations of those move choices and choosing the move that led to the most situations that were favorable to you something i didn't realize when i started was that this method of looking at possible turns to figure out your most favorable move is the same one used by the best chess played ais and because my machine learning model can tell you which of those future turns give you a better chance to win that same method can now be applied to pokemon there are some differences that make it more difficult to be applied here but the two main ones or you don't know what your opponent's moves are for sure and this game's random chance let's see how those affect this diagram from earlier which represents the first turn of a battle this chart for the turns that result from the move combinations of both players is already a best case scenario assuming you know everything your opponent can do which won't happen all that often so if you want to cover all their possible moves the opponent's side of this graph gets much larger what this chart also assumes is every move always happens the same way but in reality a ton of moves have a chance to miss or burn its target or just other random side effects and each one of those creates another turn to consider and don't forget all these situations are just for one turn and to look into future turns you'd have to explore at least this many options for all the turns that branch off from this first one if you've played the game you might be thinking yeah that is a huge number but i don't consider nearly that many options when i play and you're right but the thing is you can do that because you've spent time learning what's common and what small fraction of that huge number you actually have to worry about getting the computer to understand what you know intuitively is the tricky part of all of this but that's where the machine learning comes into play let's take another look at that graph since we have models that can tell us the most likely moves our opponent will go for we can remove the less likely ones also because we can know our chance of winning for any situation we can remove our own moves which result in way worse outcomes than the others when you add in limits for how likely a random event must be to be worth considering the ai can reduce how many turns it must explore several times over but how do you explore a battle's future well pokemon showdown is useful for that too as the code to run their battle simulator is available for anyone to use with a few modifications to the javascript code so that way it creates a split path at those random chances and i can explore any turn and this is why i had to use javascript as it's the language the entire battle simulator is written in and to spare myself the absolute headache of writing a fast program that can run between two different coding languages i figured i just needed to pick one and take it all the way so it was either choose javascript and sacrifice some performance or choose different language and rewrite an entire battle system that took almost a decade to get to where it is today also i just like javascript especially a million times more than language i can only guess we were going to suggest so yeah it was a pretty easy choice thankfully exploring different outcomes of return doesn't need to happen in a certain order so if i can process multiple at the same time the ai could get its results way faster that method speed advantage was so great that it left me no choice but to bite the bullet and make my project multi-threaded allowing it to run turn exploring on multiple processors and yes coders that does mean that this is a multi-threaded javascript only program please just roll with it my laptop which was the computer the ai mainly ran on has eight processing cores it could use to explore terms that's enough to make it faster but using only that many meant i was lucky to get through exploring one turn ahead before time ran out when i started looking at ways to increase the number of processors i could run on i realized that my best if not only solution was taking the ai to the cloud this solution had me super excited since a cloud server can have pretty much any number of cores between 32 64 256 you name it a cloud server can handle it but that excitement disappeared when i found out i was limited to only 16 cores don't get me wrong doubling from what i had is still good but compared to what it could have been it's a little disappointing like i was so ready to just rock out with a 64 core computer and just run house but alas for right now because of limitations the ai could only look just shy of 3 turns ahead in its 15 second time limit which is fine for its first run speaking about the first run let's talk about how it did i want to show you something i don't even think some of the most dedicated users of showdown have seen before when you play against a random opponent in showdown you're given a rating based upon how well you've done against other opponents this is a graph of how many people have each of those ratings now this system does have its flaws as people's ratings tend to fluctuate quite a bit but i was able to mitigate that by not only making sure it played plenty of games but also playing enough games until its rating became stable as for how i got this information because i had that system set up to download battles off of showdown on a daily basis i found myself with a mini database of all of showdown's battles this graph clearly won't reflect every battle but this does represent 50 000 battles in the past month so this should be more than enough to make a good estimate for our analysis i'm going to add this line to the graph which represents what percent of player you are when you're at that rating i want to drop down a couple of points to give people perspective so the first one is where the average player is now the second two points of context i want to give are the average rating and the maximum ever rating of the ai's creator so me so about that um i'm actually not that good at this game even despite playing it for the better part of the past 10 years and knowing way too much about how this game works i'm just not good at applying it at least i'm better than the rating you get if you only pick random moves another point of contact i want to give you is from showdown itself as they do publish some of this information but only for the top 500 players in the world and as i'm recording this this is the rating of player 500 so now for the ai so the ai's average rating was 1547 and its maximum rating was 1630 that average rating puts it in the top 10 percent of all players and that maximum rating puts it above the top 5 of all players okay so presenter version of me off for a second i i gotta be real with y'all i truly never believed that the ai would ever get that far like just two months ago i was telling myself that the 1400s was the highest i would ever expect it to get but when i saw it just storm past my expectations yeah i just i still can't really wrap my head around it and the thing about it getting to 1630 that means it was very close to being in the top 500 in the world and the ai entering the 1600s is not even an anomaly as that rating came two weeks ago but then when i ran this yesterday it got back to the 1600s no problem now i do want to clarify that just because it has that rating does not mean it's going to play well every time because there are still some pretty big gaps in this logic and two fundamental parts still holding it back now the first of the two and this is truly a topic onto itself that i'll have to say for later is that the ai builds its own teams in short it does so by trying to build a well-rounded team that counters the pokemon it thinks we'll see more often while also not being encountered itself and for right now i have it playing really safe like you can pick whatever pokemon it wants but their sets don't really deviate that far off of what's standard since i'd rather just have all its teams be fine rather than risk making any bad ones now the second part is a little bit more complicated since i knew the ai would be playing against people in a bunch different skill levels while trying to raise its own rating i had to program in a way to make it play differently against those of different rank because you can't approach different player levels at the same way and expect to win and this might be a byproduct of how i set up its runs but it seems like this programming had an unintended consequence so one would expect that the ai would win more against worst players and lose more against better ones but when i looked at its wins and losses when they were grouped by player ranking it seemed like they were all very close to 50 percent so i guess that means it played to its opponent's skill level which i guess is useful in its own right but i would have preferred if it you know played better i feel like with just a little bit of an adjustment i can get it out of the state but for now it has this weird limitation and now it's time for part three which is here because someone had weatherball hi futureme here so i realized while editing that this next section was a five minute long super tangent all you gotta know is that i saw a super impressive play and realized that there were a lot of parts missing if the ai was going to come anywhere close to making that play itself there's a link to that play and everything else i referenced in the description this made me realize i was hardly addressing a crucial part of playing this game well and in order to fix that i have to go deep down the path of discovering just how much information about your opponent's team you can learn without being directly told and the first step in doing that was inverse damage calculation that's a term i made up to describe finding your opponent's stats based upon the amount of damage you do to each other but it's best explained through an example so here's a situation where our opponent does damage on us when you click a damaging move in pokemon the amount of damage done is determined by this equation with the main components being the power of the move the user's attack and level and its target's defenses we only run inverse damage calculation once the damage has already been done so we can rearrange the equation to find the attack stat which caused this damage since the game tells us our opponent's level we know our own defense stat and the power of the move that hit us can be looked up there's only one more number we need to correctly find their attack stat however that number is where things get complicated it represents the general damage modifier which is a product of potentially dozens of known and unknown effects happening during a battle which can change how much damage a move can do and the two effects that can have the greatest difference yet we have the least likelihood of knowing are from the item the attacker is holding or their special ability there are a ton of different items and some abilities which can affect how much damage an attack can do which could make sorting through which ones they currently have a tedious process but if we can combine the knowledge of how much each of them modify damage with what the opponent's pokemon most commonly has then we can efficiently find the most likely combination of their item and ability which makes this equation return the pokemon's possible stat now i know i don't need an exact stat and an estimate will probably work just fine but the thing is the computer just needs to make so many other guesses that i just can't miss an opportunity to know something for sure this is by no means an exact science and there is a ton more work that can go on here but it already more than exceeds my expectations so it's good for now i could really talk about this code forever because it felt like for every five lines of code i could have added a whole page to the script and considering that there's almost 20 000 lines in here there's so much more i just should have talked about like i didn't even cover how it actually plays the game so i am definitely making this an ongoing series on this channel and it might not be every video but expect this ai to stick around and i recommend you do as well so i know i said that there are three tasks that make this ai work well there's actually a fourth and i'm gonna tell you what it is but how it works will have to come later as i only recently finished it and it's gonna take me some time to put it into coherent words so consider this all three parts i've mentioned exist just to help the ai look through thousands of future terms and although that is an effective strategy i couldn't help but think that there must be a more efficient way so while i was writing code to help the ai get more out of fewer turns i realized that if i changed it a bit it could also be used to help guide the machine learning predictions once i tested that i realized that this guiding code on its own outperformed the machine learning models both in accuracy and even more so in speed it was such an improvement in fact that the ai in its current state doesn't use machine learning at all i'm still not too sure how i feel about that but because of this fourth phase the ai was able to go from doing well because it can think ahead to doing great because it could think sideways uh did i really just call the new center of the program thinking sideways well that's why we're doing this later in the meantime how would you like to battle it yourself for the week of this video being uploaded future site ai is open for challengers all you have to do is go to pokemon showdown type in this username have a team ready in one of these formats and get ready to see what it's made of first hand also if you're not the battling type i've set up a live stream of sorts on my website where you can watch its current battle and see the predictions it's making also it should be noted that it's going to be running at its absolute weakest performance setting which still should be fine but i get if that's disappointing it's just that's just how it has to be because if i had this running at full strength for a full week the only things ai would be beating is my wallet but if you're really interested in battling it at its peak just hit me up and we'll see if we can make something work that being said i do have every intention in making the ai play on the official games on switch as it should be pretty straightforward as long as the computer can read the screen so i can guarantee that's something coming in the ai's future but speaking about the ai's future there are two questions i feel like are going to be pretty common that i just want to address right now number one no unlike my past projects i will not be releasing the code for this if the past however many minutes have shown you anything about me one of them should be that i care deeply about this game's competitive scene and i feel like if i release the code to just let anyone use it that could be opening up the pandora's box of people using this ai to like cheat in tournaments or clog up the server just a whole bunch of other mess similar to how i bundled the machine learning models into the battle predictor i do want to release some of the other tools that it uses like the inverse damage calculator because i do want the community to get something out of this but yeah the code it stays with me and number two yes doubles is coming for those who don't know the format of the tournaments hosted by pokemon themselves is for battles where instead of having one pokemon out per side there's two and although that does complicate a lot of things i am still so ready to tackle that side of the project because i tried to keep doubles in mind throughout the entire coding process and i have most of the ideas about how to implement it worked out and really the only thing stopping me is it's just gonna take some time because at the end of the day i am just one guy working on this well for now but hopefully talking about that is what friday's for as for my other plans i do have some fun things in mind like i really want to see how well this can play through a story of one of the main games and then of course there is no shortage of pokemon challenges i could apply this to but i have my sights on a particular problem that i would like to solve once and for all there is a popular quote amongst pokemon fans that frankly i believe applies to life in general that paraphrasing says that if you are truly skilled you could win with your favorites there's already been some truly skilled people who've tried to be the proof of this on both sides of the argument but their successes or failures were never going to make this definitive and that just comes down to always not knowing who's the weakest link however a computer that can not only keep us play consistent but consistently good fixes all these problems and with a little more coding this ai can also be applied to find the best possible set for a particular team and with all that in mind i think this might be our best chance of seeing this through as for what team to use well i think i have an idea because over the decade of playing this game i've had some time to develop a pretty concrete idea of the team of six i'd want to put up to a task like this they aren't all my favorites but collectively they make up my favorite team in its current state future site ai isn't ready to do this question justice but one day when i'm ready they'll get their time to shine but for now don't forget that you can battle or watch the ai throughout the week come back on friday to get your questions answered and until then i'll see you later

Channel: The Third Build

Views: 780,205

Keywords:

Id: rhvj7CmTRkg

Length: 26min 52sec (1612 seconds)

Published: Mon Jul 19 2021

Reddit Comments

[u/DangerousDildo]

You should X-post this into r/Pokemon. I know there’s a lot of competitive players that don’t know about this sub. And maybe some casual fans would enjoy it too!

The video is so well made and thoughtful, the kid deserves the exposure! Super cool post, thank you for sharing it

[u/aed_3]

Hi! Just wanted to say thanks for sharing my video. Your comments are so nice!

I'm going through and reading your comments and there are some interesting points. First, because I've been hearing this comment for a year, I do agree with the fact that a good prediction tool shouldn't be used in tournaments. Right now, it's not that great because it's still using the faulty machine learning, but when I adapted It to use the code the AI runs with, it might be a problem. I probably won't do that until I can figure out a way to make sure it can't be used in tournament games (I have some ideas and probably will have to work with the Showdown team on that), but until then it should be ok.

When it comes to how many turns deep it could possibly look, I also agree that there is a pretty low limit. From my testing, the most turns ahead I've ever gotten it to look on the first turn of a battle (the one with the most options) is 3. It could totally be optimized to go a good amount further, but the time complexity of this approach makes probably any farther than ~7 turns ahead impractical. I've been working on a way to go around looking turns ahead, and right now it's worse enemy is stall teams because of this limitation.

[u/trolltest123]

I just saw this yesterday! I think it's really neat and he clearly put a lot of work into it. It's probably the highest rated bot I've seen so far. Just some thoughts:

He doesn't reveal any big details about the algorithm, but from what I can tell his final iteration is some kind of expectiminimax + pruning, where essentially the bot is looking forward a few turns and based on all possible (or usually all "reasonable") outcomes, picks the moves that minimize the worst outcome, aka your traditional "safe" player. There are definitely limitations to this approach, first of all is the depth of search. To give context, Stockfish for chess regularly searches to 30 moves ahead. I am pretty sure that a lot of implementations are limited to a mere 3 moves ahead, as illustrated here (https://github.com/pmariglia/showdown/issues/53). So, I suspect that ~1600 is going to be a pretty hard limit because you can't use this approach by itself to really develop long-term strategies. Another thing I wanted to point out is that this algorithm is also really prone to exploitability- knowing that your opponent is always a safe player is going to lead to easy manipulation by the best players. He even mentions it here in his Smogon post:

FSAI, between looking at its predictions and what its worst-case scenarios of your move choices, is quite accurate at figuring out what you will do next, but I have found that making hard reads is not a sustainable way for it to win. That tends to be a very high-risk, high-reward playstyle, and FSAI prefers to make somewhat obvious, but generally reliable plays. As it has climbed the ladder, this risk averse playstyle has started to be a liability, so I do plan on doing some more experiments to figure out what is a good balance and against what kind of players that playstyle should be used. that last part is key as it already plays differently against people who have different ratings, so I must figure out when is the best time to start increasing its risk-taking factor.

This however is incredibly awesome work, and I think 1600 is now the new baseline to beat for Pokemon AI which is exciting. I've been in (very) early development of a Pokemon AI using reinforcement learning through self-play, and I'm hoping it'll also do well!

Edit: included link to Smogon post

[u/AceTrainerOrange]

Hi! So I wasn't too sure if this had already been posted or discussed in this sub, but thought it could spark some interesting discussion-its starting gaining traction less than 24 hours ago and it is extremely fascinating: but I also want to hear the opinion of the sub on what this means for the competitive community.

This is not my video or my project-please support the original creator, I'm just a messenger. Regardless of how it might impact us, this is an incredible feat of coding and might change how we see battles from now on.

[u/Bentyhunter]

The fact that this video has less than 2k views is CRIMINAL! This guy is fantastic and needs to be shared everywhere!

[u/Crossfiyah]

I was thinking about this last year and how really while there is hidden information in Pokemon there are only AT MAXIMUM, 9 options on a given turn for the AI to take.

Glad to see someone is exploring creating an undefeatable Pokemon AI bot.

[u/sleepcousinofdeath]

Great video, I’ve thought about something like this existing for Pokémon would be really interesting seeing how complex the game is. The team building aspect of this seems especially interesting

[u/WoolooOfWallStreet]

I’d like to see it allowed to only select rental Pokémon from Stadium 1 and 2 and see what teams it picks for different cups

[u/ritwique]

Wow, this looks amazing