A.I. Learns to Play Tetris

hello you don't know us but we know you we know forests only the best will understand only the best will prevail and just like that I'm back and I'm not even in the right position to talk about everything so let's just talk about Tetris take a look I'm sure you know the game works you have these falling pieces called tetriminos which is just shapes comprised of four squares with your main goal to clear as many lines as possible they fall from the top you can manipulate them move them around rotate them but if you stack it so high that tetriminos touch the top and the game ends I swear it's one of the easiest games to play but one of the hardest games to master and since I'll never be good as this guy how's this gonna play out Oh perfect perfect that's set up now he's still waiting [Music] world champion yeah he's really good so I figured I'd build an AI to do it for me now let's get to code in the game itself we want to start off by throwing the board up on the screen and then we want to make sure we have all of our shapes now this is a little bit more complex than just drawing a 10 by 20 board but it's really just a bunch of matrices in for loops and we use this logic to generate each piece will basically store it in a bag that way we can pull it out at random and plop it on the proper spot on the board all right that's great no but I gotta test out each piece to make sure they're all good so when I hit the spacebar I wanted to replace a current piece with the next piece in our bag until we run out this isn't something we wanted to gain forever but for testing purposes I'm happy with now it's added in some gravity looking good uh no I haven't put in collision detection yet forgot about that one let me just quickly give this up to speed as you can see we can move left right we can rotate the piece and we can also soft drop the piece gets locked in next piece is generated so on and so forth we can also hard job let me just throw in the UI we've got to keep our score here now it's time for testing and if you don't know there are so many different variations of Tetris I figured it would be best that I lay out the guidelines here so every single level is worth ten lines so you get ten lines you advance a level every time you advance a level the speed increases by these values right here this is the only value table I could find for the Tetris speed increase and I took out hard drop for the AI so we can actually see it drop however what you will see with the AI is that it is continuously soft dropping because I said every time you make your move make sure you soft you out there after because every single soft drop is worth one point and if you're watching this is like a pro Tetris player or something and I just like completely botched these guidelines my bad just let me know and I'll fix it if I ever decide to revisit this Tetris ai I decided upscale the game you know make it a little bit bigger and refactor quite a bit of code and make it work properly with the AI and this is my first attempt as you can see it's not really working too well everything is just lining everything up on the right side going from there and it's not really learning anything so that's that was the main problem obviously something went awry when coding up the AI but regardless I knew just by looking at it that even if it was learning it was never going to be as good to some of those grand master Tetris players and that was a goal not necessarily to beat him one on one but to try to at least get around the same high score as them so I did what any competent programmer do and took to the Internet I wanted to find out exactly what heuristics are to look out for when playing the game Tetris so I could know how to train my AI and there were four that just kept popping up this included aggregate height completed lines holes and bumpiness so I just coded up this logic as well as our genetic algorithm to give my a I an actual fighting chance now this is what I wanted off the RIP we're doing much better generation 1 player 1 better than whatever generation we got up to in the previous AI and to give you a better understanding of what is going on here you can see on the right of the screen we have our level we have our lines we ever scored then we have our generation each generation has a population of 100 players currently we're in generation 1 watching player 18 and once player 18 dies if they're not the last living it'll move on to the best player so the one with the highest score once that one dies it'll move to the next one with the highest score until all players of generation 1 are dead and generation 2 is populated using our genetic algorithm it's really just like any other genetic algorithm for starters if you didn't notice we ended generation 1 on player 18 we start a generation 2 with player 18 that is because our genetic algorithm takes the best player from the previous generation and moves it over to the next generation we also have a couple of the best players from the previous generation reproduce to create like a really good child so hopefully they can do better than their parents and then continue to reproduce and get better and better and better and we also mutate a subset of the population ever so slightly to see if it makes them a little bit better a little bit worse and then we adjust and drop a like on this video if you appreciate me not including all 48 hours of this AI at work and don't dislike it if you wish I included all that just leave a comment down below so I can know which one of y'all are maniacs I actually think we got to speed up even more so instead of just 10x speed what I'm gonna do is take the last three or four seconds of each generation so we can see how our a AI progresses and that's it that is the highest score we're gonna get with this iteration of the AI over the next few generations it continues to break over 100,000 points and I'm sure if we kept it running that it would continue to break the highest score maybe little by little but that's not good enough for us if we want to hit that million mark if we want to break Ness Tetris we got to do something a little bit different and that is well give it the key advantage that we have as a player and as the ability to preview the next piece well that wasn't so hard now let's talk about what that means the difference between the old AI and the new AI is only the ability to look ahead on the next piece but it really makes a big difference I mean if I know how to math right without the ability to see you next piece any given Tetris piece has anywhere from nine to thirty four possible next moves and what that means for the AI is that that's all that has to compute anywhere from nine to thirty four moves for any given piece but if we give our a I'd the ability that every Tetris player has and that is to preview the next piece then we got to take into consideration the branching factor of Tetris which it's really just a bunch of anybody who blob but I'm gonna explain it while the AI does its thing at the root of it and computing tree data structures game theory the branching factor is the number of children and each node the out degree thanks Wikipedia and layman's terms is the number of successors generated by a given node or in our instance the number of next possible moves for each current possible move but because our values aren't uniform you must figure out a mean branching factor by taking into consideration every possible move for each piece so for the square since it's symmetric under rotation it can be placed in nine positions the line has two distinct rotations or vertical and a horizontal position it can be placed seven positions and the vertical it can be placed ten the s Z L + J pieces all have two distinct rotations and they're horizontal rotation that can be placed eight positions and their vertical rotation they can be placed nine positions and the T piece it has four distinct rotations and the horizontal rotation they can be placed eight positions and either vertical rotation it can be placed in nine positions these numbers allow us to find the mean branching factor for pieces and that is the average amount of moves for each piece with that if we decided to incorporate our branching factor without the ability to see the next piece our AI would have to evaluate the 18 possible moves for the current piece as well as all possible moves for all seven pieces for that next piece so resulting in the AI needing to perform an average of 2268 heuristic evaluations in order to place the current piece in the most optimal location but because we're given it the ability to see the next piece it only needs to perform 324 all right enough nerding out let's be this thing and while the AI does this thing I want to take this time to I guess just address the elephant in the room and that's the fact I've been gone for what a month and a half two months and I'm not going to talk about what happened over the past month didn't have two months with all that but I would like to ask for y'all's help I plan to continue on with AI but the thing is a lot more time and energy goes into a single video than me just sitting in front of a camera and talking about software engineering so if you want to see more videos like this and be actually coding instead of me talking about coding then share this video liking commenting and subscribing of course that always helps and I'll ask you do that right now give this video big thumbs up and make sure to subscribe if you aren't already but sharing the video with your friends with your family this will help a lot more than you'll ever know and your friend doesn't even need to be interested in coding because this isn't necessarily a coding video like he used to make all the time talking about coding or anything like that this is about artificial intelligence it's about machine learning everyone I know is interested in that type of stuff so thank you and I'll stop begging for shares and likes and comments and subscriptions okay I lied one more thing that I need to touch on me because people have been asking a lot do to covet 19 first apply coffee is still roasting and shipping out coffee every single week I will leave a link down in the description below in case you want coffee delivered to your house instead of going out to the store and getting it during this time but enough of that this is the game this game we're approaching 1 million oh my gosh remember my games not going to break because I don't have it limited up to 1 less than 1 million we're going to do it what's that satisfying you know even if it did just in a ride after 1 million it doesn't matter 1 million 18,000 616 that is our high score I don't even care if we beat it or not we hit a million that was her goal for this video so I think I'm done here and I didn't even use all the tricks up my sleeve I was gonna make the AI prioritised Tetris basically every single time unless I was gonna die although we did see it kind of do this but it wasn't I mean we could have made it better something else I really wanted to do is see how quickly we could get to a million but we hit the goal for this video like I said I'm done here we could save that for another video and if not I have a dozen other game ideas I know y'all really enjoy just subscribe and share this video with a bunch of French and I'll show me you like this new content until then

Channel: ForrestKnight

Views: 262,695

Keywords: artificial intelligence, machine learning, ai, ml, tetris, ai learns, ai learns to play, ai learns to play tetris, a.i., code, coding, programming, software engineer, software developer, software development, java, processing, software engineering, tetris ai, ai tetris, ai games, ai video games, ai beats tetris, ai destroys tetris, i created an ai to destroy tetris, algorithm

Id: LGNiWRhuIoA

Length: 11min 8sec (668 seconds)

Published: Thu May 07 2020