I Created a PERFECT SNAKE A.I.

previously on AMC's The Walking Dead sorry I'm just gonna stop you there it's code bullet actually not The Walking Dead that's fine I mean honest mistake it happens to the best of us I mean I did employ you to say literally six words and you [ __ ] it but not let's that's alright that's fine I forgive you we got a show to do let's just try it again previously on AMC's The Walking off [ __ ] you after three months of radio silence Evan remembers his YouTube channel as a thing and decides to reuse ideas from his previous content the plan was simple a snake AI unlike any seen before he will be the god of snake Walt and he will be beautiful he will be perfect however things did not quite go as planned oh [Laughter] okay here we go again get comfortable people we're gonna be here for a while will Evan give up on this project like he's an enigma machine video or will he prevail find out now on code bullet bullet bullet oh hey huh hey how's it going uh been a while yeah that's my bad uh how have you been oh that's great now the kids yeah fantastic Wow really interesting stuff okay great now that we've caught up let's get back into it so picking up where we left off in our journey to create a perfect snake AI this was the best AI I could manage using cue learning which is Adrian you're a [ __ ] disappointment to me and my entire family but apart from that he did fantastically oh you guys gave me heaps of ways I could improve it which is awesome but the problem is I don't really want to do any of them so let's pretend there's nothing I could do to make it work with Hugh learning and let's put Adrian out of his misery am i doin good father are you doing just great buddy keep up the good work do it break this problem down to its bare basics are you guys done thank you where was I okay so as I was saying we're gonna get rid of any q-learning or evolution [ __ ] and just break this problem down to its bare basics so we're given a snake and what we want to do is get some food while avoiding the walls and our own tail if you break it down like this we can essentially treat the game of snake as a series of mazes to solve we've got the start point we've got the end point and we've got the walls this is of course a massive oversimplification because the walls are moving in the way we get the food to find what our next maze will be like but that one step at a time the great thing that mazes is that computers are great at them and computer scientists have been working a ways to solve majors for ages I mean GPS is work and that's essentially one [ __ ] off massive maze solving problem although you're probably not gonna see any code bullet branded GPS is anytime soon because I feel like my style of doing things isn't exactly a great fit hey so you're gonna want to turn left in about five minutes and you can mister your dick get the [ __ ] out of my car thank you for driving with code bullet GPS we hope you had a nice trip oh yeah okay so we've got some mazes that need some solving but how are we gonna do that well let me introduce you through the world of path finding algorithms okay so essentially we have a maze starting from here and finishing here but most humans this should be a fairly easy maze to solve just go around here but for computers it's a bit of a problem the most simple solution is to generate every possible path and pick the first path which reaches the Apple this isn't the best strategy but don't take my word for it let's map this [ __ ] so there are four possible moves at each point in time that's up down left and right and the path will take 34 moves to get to the food we need to calculate how many different paths can be generated which have 34 moves which is 4 to the power of 34 different paths which can take that number of moves and if we times up I can't be [ __ ] doing this and divide everything by a lack of a mathematical degrees we get at least four probably I don't really know why I decided to do the math that was a poor decision I really have no idea how many there are but by the time we checked them all we would probably be getting close to the heat death of the universe so that's not super useful so thanks to my compelling and mathematically sound argument I'm sure you're convinced that this algorithm needs a little speeding up what I'm planning on using is called a star and it's generally considered the heavyweight champ to these kind of searching algorithms what it does is it prioritizes checking paths which get the snake closer to the Apple over paths which take it further away it does some fancy other [ __ ] but that's the gist of it so is that are just like searching randomly and checking every single path it looks in the direction that the food is in all right enough chatter let's go go gadget a-star algorithm all right here we go yeah that's kind of what I expected all right how about now well it drew the background so that counts as progress I'm counting that as a win okay there we go so this is finding the shortest path from the head of the snake to the food this solution is just riddled with issues however let's just sit back and pretend it's gonna work [Music] [Music] [Music] you good bro you still with us hello okay he's just stopped he didn't die he just kind of gave up uh yeah okay so there are two main problems with this the first one is pretty obvious every time you get some food he needs to calculate the best path between the heads and the next piece of food while a star is a pretty good algorithm it's far from perfect and still needs to check about one metric fuckton of paths so that's not ideal and I can make it a little more efficient however I feel that's gonna be an unfixable problem the next problem is a bit more subtle let's quickly go over a star again it sees the situation like this and calculates the best route from the head of the snake to the Apple is just fine however since this path assumes that the body is not moving it moves in a way to avoid the tail which is no longer there and this is also why he just kind of gave up because there's no direct path from the head of the snake to the Apple and it doesn't think the walls are gonna move so it sees this as an impossible situation this isn't too hard to fix however don't get too excited because there's still one whopper of a problem which I'm yet to tell you finding the shortest path isn't really what we wanted to do anyway if you watch the people with no lives who are really good as snake it's not like they go straight for the Apple instead they kind of do the opposite potentially taking the longest path to the Apple oh [ __ ] that's a great idea alright so what I'm thinking is what if we start out using a star to find the quickest route then once the snake gets a little bigger we use the opposite of a star to find the longest path here we go [Music] ah [ __ ] yeah okay that makes sense does it do that every time yep yes it does okay cool cuckoo cuckoo cuckoo cuckoo cuckoo that's fine I'm fine okay okay so that wasn't the best result you would say but I think there is promise with this strategy before it completely [ __ ] itself it was looking pretty good so here is the plan we want the AI to take the longest route without trapping the snake within its tail but to do that I added a rule to the reverse a-star algorithm so here's the rule at all times the head of the snake must be able to reach at least 80% of all empty plots so in this case the head can only reach these blocks which is less than 80% so it's considered trapped and this path is thrown out this prevents the AI from circling the food and will always leave it a way out okay now we're making progress as its standard on this channel whenever I program something which looks like it's working it probably got a massive downside in this case the problem with discarding any paths which get the snake trapped is that sometimes this will discard all possible paths and the snake will get pissed off and taken angry now which is well a problem but fee not because in this case the snake will enter survival mode or to use the more scientific name the oh [ __ ] [ __ ] [ __ ] mode that's yeah that's what's called this mode doesn't give a [ __ ] to where the Apple is all it's doing is trying to survive and I'm sure you guys can figure out when it reaches this mode alright let's put it all together and do a complete run-through [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] [Music] it was at this moment that he knew he [ __ ] up no no oh it's a Kevin I'm sure you're really close to getting it a few more changes and you'll have done it yeah you're right you're right we are really close but [ __ ] the head let's start again wait really yep third time's the charm oh my god all right let's get all this [ __ ] out of here I said yeah I started again from scratch why well because I've got a very short attention span and the way I was doing wasn't working so just kind of forget everything I've explained up until now cuz we're starting fresh this is the last time I'll start again I promise and I always keep my promises what about enigma machine but two and I usually keep my promise what about putting out videos every Saturday guys sometimes keep my promises what about let's move on shall we okay okay let's move on [ __ ] so what's this new and improved algorithm we'll get the implement I would like to claim this one is my brainchild however that would be a lie and I always tell the truth what have had Enigma machine you want to [ __ ] die tonight fantastic I'm glad you could come to an understanding where were we this part was heavily inspired by John Cass Paul's wife he's got a website where he does a bunch of projects one of which is a snake AI he actually did it by hacking into Nokia and playing that way in a video titled snake on phone this guy's like a genius however his video naming skills could use some work that's like some reverse clickbait [ __ ] okay so backhanded compliments aside let's see how this works so this algorithm works using something known as a Hamiltonian cycle Hamiltonian cycle is if gross ass math term which I remember from a uni course which I didn't pay enough attention to so I feel like I'm perfectly qualified to explain this in order to understand this once again we're gonna think of snake as a grid of blocks in our case a Hamiltonian cycle is simply a path which goes through every single block once and finishes where we start to form a cycle okay so a super simple algorithm to solve snake is to generate a Hamiltonian cycle and then just simply follow it and you win but if you look closely you might notice the TAS is [ __ ] boring be so hysterical I regret nothing but if you play for long enough it will work it will win but obviously this doesn't count but this works well as a face which we can make for much more efficient essentially the trick is to make short cuts which cut off large sections of the Hamiltonian cycle so to explain this look at this small example I've labeled each block to show you the order of the cycle if we're doing our boring lame-ass strategy the snake would just follow the order of the numbers however hold onto your hats because you're about to see a mad lad machen don't let your dreams be dreams yesterday you said tomorrow make your dreams come true nothing is impossible yeah so you get it this is kind of the main gist of the algorithm it roughly follows the numbers and is able to take some shortcuts this improvement is even further magnified on larger maps massive sections of the Hamiltonian cycle are cut off this sounds all well and good but it's not quite that simple there are a few cases which will mess you up if you use the shortcuts too liberally for example I wouldn't recommend cutting off any areas which contain the part of the tail because then you'll get [ __ ] also you've got to be careful when the snake grabs our feed and expands business potential that you'll get [ __ ] but honestly I'm getting bored of explaining this [ __ ] so let's run this [ __ ] so startup is a pretty standard game but as the game goes on snake starts to follow the Hamiltonian cycle more closely [Music] this is going to take [ __ ] ages so let's boost the [ __ ] out of the speed [Music] okay so to be honest I'm not a super huge fan of this algorithm it's great and mathematically pleasing however I think it's lost the chaotic beauty of an algorithm which might die at any time like I enjoy watching this one heaps more because you know it's just freaking the [ __ ] out well this one is like cold and calculating but one thing that I can say for this new algorithm is that it's incredibly fast the other one has to pause and calculate while this one can easily run at 50 times speed and that's not the only way of utilizing its speed take a look at this that's a [ __ ] game snake the movements of the snake look fairly normal in human which is in same thing that this is the Hamiltonian cycle right this is gonna take yeah this is gonna take a while so let's crack this [ __ ] up alright so this is true time speed all right very nice let's make it 10 times faster all right 50 times faster 100 times faster 1000 times faster uh yep okay that's I don't know what I expected it to look like but it really doesn't look anything like a game of a snake anymore um but you're gonna have to take my word for it actually let's slow it down so we make to see what's happening yep it's snaking it's snaking alright again speed it back up I guess there you go gamer snake technically [Music] [Applause] [Music] okay I'll slow it down for the end of it let's see alright come on Jesus [ __ ] this takes ages alright keep it up come on you got this you got this go okay [ __ ] this boost stop boost stop Jesus boost stop i boost stop boost Oh this took me like three hours to do it was sped up for you guys that took me like three hours and we got all of it except for two [ __ ] blocks that's it I'm done never touching this piece of [ __ ] game again this [ __ ] you I'm out bye so I'm just about finished with uni and while it's been fun it also really hasn't one of my main issues is they just slap you in the face of the textbook and be like that's all for today I'm going to the pub also that textbook would be $400 sorry I might have gotten a little bit sidetracked my point is that they just give you text to read and that's not how people learn especially if you're illiterate like me which is why I appreciate what the people are brilliant don't all get doing with their courses if you haven't heard of brutal dog it's a problem-solving website and app with a hands-on approach with over 60 interactive courses on math science and computer science and I know that's just a bunch of buzzwords that you probably hear all the time but when I say hands-on and interactive this is what I mean this is a question taken out of the mathematical fundamentals course which sounds as far from hands-on as you could possibly get but they made it work so props for that in this question you asked whether or not it's possible to move the number tiles so that every row and column adds up to the target sum beside it they could have just made a picture of the problem and call it a day but that's not how Bruno does things instead they created a fun interactive minigame which makes the problem less like homework and more like a puzzle game where install our courses are filled with these interactive elements which make it more engaging and the information more digestible if you want access to all the interactive courses and if you like what I do here and want to support me head over to Britain and all slash code bullet to get 20% off their premium membership hey yeah so I'm back if you didn't figure that out from the previous 20 minutes of content yeah I'm back this project took [ __ ] ages oh my god I'm so sick of steak but I had my pride was just like Evan [ __ ] finish this [ __ ] ass game it's like one of the easiest games to make ever surely you can beat it yeah so that that probably took way too long and uni was a thing which was a thing so [ __ ] that but I am done now I am completely done with unique like 100% graduate assuming I pass actually so maybe I'm celebrating a little early but let's let's hope for the best you guys for the sake of the channel it's pray to God that I pass these [ __ ] courses yeah so I'm done I'm actually going on holidays in a sec though so it won't be much different for you but yeah I'll be back and in action and ready to [ __ ] go start of the next year start of the new year however you say that 2020 new year new me I'm gonna be a free man gonna be doing code bullet full time I don't know what I have planned I don't have anything planned I had something planned I would know what am i [ __ ] talking about here so yeah sorry long story short we'll get four new content in the new year it's gonna be great it's gonna be fantastic I'm not gonna get a job or anything which frankly means my degree was useless which is great that's a wonderful thought but whatever that's behind me that's done let's just [ __ ] do this alright bye again

Channel: undefined

Views: 7,775,629

Rating: 4.9283633 out of 5

Keywords: artificial, intelligence, coding, processing, java, machine, learning, genetic, algorithm, evolution, computer, science, programming, comedy, educational, snake, ai, hamiltonian cycle, rage, gaming, games, code bullet, math

Id: tjQIO1rqTBE

Length: 24min 3sec (1443 seconds)

Published: Thu Nov 28 2019

Reddit Comments

[u/voronaam]

Have you seen https://play.battlesnake.com/ ?

It is a lot of fun. And actually challenging to write an AI for, since the win condition is not necessary to last longer. If you are the biggest snake at the moment, you can hunt the others.

[u/indenturedsmile]

I know this is a naive solution, and not the point of creating an AI for a game, but couldn't the brute force version be the best? Basically, go vertical up and down covering the whole board up and down except for the top row and just keep going over it until you've covered all space?

[u/krete77]

This was really fun to watch and listen to

[u/Ignisar]

I love your videos, glad to see you around again! Have you considered streaming your development process?