How to Win Snake: The UNKILLABLE Snake AI

if you've ever seen xkcd 356 you'll know that a certain type of mind is very easily distracted by interesting problems and for better or for worse I seem to have one of those Minds this video is the story of one such instance where I watched a code bullet video one morning about making an algorithm to play the game snake and by 2:00 a.m. the next morning I found myself unable to sleep trying to teach myself about efficient ways to determine the hamiltonicity of arbitrary bipartite rectangular grid graphs and if none of those words made any sense to you don't worry they didn't make sense to me before that day and I'm really only going to be using a couple of them in the rest of this video after the first three-day weekend of furious coding I had a running snake algorithm that I believed was actually faster than code bullets when it worked about half the time it would get stuck in loops like this never dying but also never actually completing the game it also had a few really annoying sort of poor efficiency behaviors like a tendency to draw these huge spirals across half the screen it just did nothing but waste a whole lot of moves after about a month completely addicted to this problem I had added a whole bunch of features to my snake playing AI I had dropped the play times by about 15% and I dropped the failure rate when it could stuck in loops like that to basically zero let me show you how it works if you haven't seen it before snake is an old arcade and early computer game where you are a highly pixelated snake that eats highly pixelated apples in a highly pixelated grid this one happens to be a 30 by 30 grid now I have taken a little artistic liberty with this rendering out of MATLAB the apples are little red circles in full HD it's absolutely amazing how new technology can enhance old games the hard part is that you aren't allowed to run into the walls or yourself and every time the snake eats an apple the snake gets one pixel longer as if snakes are just stretchy green tubes full of apples that never get digested I try not to think about it too hard bottom line is the game gets really difficult when the snake is really long because it's really easy to get yourself into a situation where you've trapped the head of the snake and it can never escape or in this case because I didn't bother to write a failure condition it just realizes that it can't see the Apple anymore and the program blows up the game is won if you literally fill the whole board with snake as in when the snake eats the last Apple it's next bite would be its own tail my goal was to make an algorithm that filled the board every single game in as few moves as possible the single absolute easiest way to win snake is to make a path that passes through every point on the board exactly once and follow it you will eventually eat every Apple and because you're always going in the same path you will never run into yourself so it's a guaranteed win however as code bullet mentioned in his video it's boring and as I'm about to quantify it's also painfully slow the expected travel of the snake before eating an apple is half of the exposed tiles so at the beginning of the game that's half of almost 900 so about 450 steps per Apple by the middle of the game the snake takes up enough space that the Apple actually has to spawn closer to the snake's head and for the last Apple of the game you know the Apple will spawn exactly in front of the snake because it's the only available space so we'll only take one move to eat the apple that means we can actually analytically determine the average 30 by 30 game will take about 200,000 moves that's really slow this path that covers every square on the board exactly once is known to graph theorists who know a lot more math than I do as a Hamiltonian cycle if you imagine a game of snake is basically a square grid of nodes the Hamiltonian cycle is a way to connect all of those nodes with a line the only passes through each node once and returns to where it started so it makes a cycle not all connections between nodes are available of course because the snake itself is on the board and crossing the snake is illegal so when you try to draw Hamiltonian paths on a snake board the entirety of the snake needs to be included in that Hamiltonian path in order because there's no way that the snake can cross itself or you can like exit the snake and then come back in that doesn't make any sense code bullets ii AI is an implementation of an algorithm created by john capsule called the perturbative hamiltonian cycle it's a really mind bogglingly efficient algorithm that was designed to be simple so that it could run on a phone but basically it runs the snake across this full board Hamiltonian cycle but occasionally it decides to jump the line and skip sections of the full board cycle in order to get to the Apple faster the problem is that especially late in the game this means that certain parts of the board become locked until the snake traverses the whole map if this section of the Hamiltonian path was skipped and the Apple fell here you now have to wait for almost an entire boards worth of moves until the snake traverses the entire path returns to this point and then it cannot skip this section to grab the Apple but what if the Hamiltonian path could change what if on the way back you just took this little skipped part and added it back in in order to collect the Apple faster that would work just fine and that is actually the basis of my snake playing algorithm what I haven't mentioned yet is that while some graphs have many Hamiltonian paths some graphs have none at all if you imagine this tiny snake board the snake neither goes straight or turn left and each case yields a new graph for us to check if the snake goes straight there are a bunch of Hamiltonian cycles but if the snake turns left there are zero Hamiltonian cycles the biggest dead giveaway here is the lone node on the bottom right it only has one connection to the graph so there's no way to get in out of that node to complete a cycle clearly if the snake values its life it wants to go straight so it knows that it can always get to every space my first instinct when designing a snake AI was to do exactly this for every move look at the hypothetical graphs with the snake were to move in any given direction and move towards the Apple as long as a Hamiltonian path existed in that direction the problem with this strategy is that determining the hamiltonicity of a graph or determining if a Hamiltonian path exists is an np-hard problem when people say something is exponentially difficult they normally aren't being literal but an np-hard problem is how computer scientists refer to computation that is actually literally exponentially difficult the bigger the graph the more CPU cycles you burn trying to find a Hamiltonian path or even if a Hamiltonian path exists for a given graph naively my gut reaction was that I had a nice computer I should just crank through it by brute force turns out I underestimated what np-hard really meant I downloaded a pre-written bit of MATLAB code to find a Hamiltonian path on an arbitrary graph and I let it churn on a pathetic ten-by-ten snake board now keep in mind a 10 by 10 snake board is actually a graph with 100 nodes after 15 minutes of it not finishing the very first step in the game I had decided that I would need a more intelligent strategy that's why I spent so much time reading about it in the first few days I was trying to find a moderately efficient algorithm to determine hamiltonicity of you know some sort of arbitrary snake board it turns out that a snake board is a very restricted definition of graph so you know you could make a little bit of progress but it didn't find anything that was super satisfying turns out that just making tiny changes to a pre-existing Hamiltonian cycle is sufficient for the vast majority of cases when a human plays snake they don't reevaluate the entire board with every move they just look at the stuff around the head of the snake imagine that you have this and it wants to write but the Hamiltonian path takes it straight if the snake does turn right it creates another smaller loop and leaves behind this little disconnected loop of path neither of these paths are actually Hamiltonian cycles because they don't cover the entire board but if you find an easy spot and splice them back together now you have a new Hamiltonian path and the snake still gets to turn right towards the Apple that's the basis of my dynamic Hamiltonian cycle repair algorithm so here we go this is an early version of the program that was trying to repair the paths nothing special it looks pretty darn good it's going along it's getting apples wait there are a zillion nested ifs and piles and piles of minus signs in this code and it is an awful lot to keep track of even when it's performing properly it's important to note that this algorithm is really really lazy and it doesn't actually try very hard to repair the Hamiltonian path before giving up if it can't find a solution if it does give up the snake is forced to follow the old Hamiltonian path which might actually take it farther away from the Apple but at the very least it ensures that the snake won't die because it always remembers its escape route it's always following a Hamiltonian path I was pretty pleased with the snake algorithm but it was seeing some weird results you see how it kind of squiggles everywhere at the start like look at all these wasted moves they can just go or even but instead it has to you know go bad and make all this mess when I played 30 games with just the loop splicing repair algorithm I got an average game length of about 68 thousand steps or about 76 steps per Apple when I made the repair algorithm smarter and able to fix even more situations more than just the simple loops it actually got worse with an average game length all the way up at 72,000 moves which is over 80 moves to collect the average Apple on the surface this seems really weird and I mean deeper down it seems really weird that you can make the algorithm better at moving towards the Apple but the game length goes up like it takes longer on average to get to the Apple even though it can normally get there better that sort of was my first clue that actually the direction from which you approached the Apple and the strategy surrounding that turns out to be very important so some of my later things had to start to correct for that one of the first things that I did notice about you know the wasted zigzag enos of the algorithm was that it was much better at going in straight lines than when it was actually attempting to zigzag so I went into the a-star algorithm that I had downloaded from the math works website which is basically the algorithm that says which direction is the fastest way to the Apple now and I fiddled with that algorithm so that it preferred straight lines and did some other things so that it respected the existing Hamiltonian path a little more this combination of repairing the Hamiltonian cycle with the more advanced version of that algorithm and trying to travel in straight lines turned out to be extremely powerful and dropped my average game length to only 65,000 moves now the snake plays pretty darn well and it looks much more human-like at the beginning of the game because it travels in a lot of straight lines and it almost never gets stuck in loops but it still has a few annoying behaviors I have burned an awful lot of hours watching the snake wander around the board and you know you're sort of rooting for it you're like oh that was great oh you see how it's just like wrapped around that corner to the Apple and sometimes you're like oh no no don't do that don't get stuck and then you watch the thing fill in half the board and waste all these moves before it gets to the Apple most of the small changes that I made to the algorithm were out of frustration and watching the snake do unintelligent things and me having to sit through it again and again so I started playing whack-a-mole with especially annoying special cases for example in this situation right here the snake sees the Apple and goes straight for it but now it has cut the map in half if it grabs that Apple right now and then turns towards its tail there's no way to get to all of these notes a Hamiltonian cycle would not exist so instead it has to waste a whole lot of time filling in half of the board before returning to the Apple and consuming it any human playing would just say well I should go along the edge and not have this issue so that is the first special case that I addressed when the snakes path would cut the board in half the line to the Apple turns gray and instead it hugs the walls I had to utilize a couple of parody arguments so that it knows which wall to hug you know always turning left are always turning right but getting that figured out brings the median game length down to fifty nine thousand so that was an awful lot of coding effort for an additional eight percent improvement are you noticing the diminishing returns here so with this change in the mid-game the snake looks brilliant until it closes itself into a loop if you were playing a game of snake and got here you'd realize that a couple zig zags would let you wait until the tail got out of the way and you could go on your merry Apple eating way but is that what the snake does no it's always trying to follow the red path to the Apple and less explicitly prohibited by the non-existence of a Hamiltonian path so it ends up staying close to the edge and leaving itself only a single escape route which it's not allowed to use until it's filled in the whole spiral these big curly Q spiral formations can take up like half the board and it just wastes a ton of moves so the second critical special case that I addressed was that when the snake realizes it's closed in it tries to run away from the Apple and the line turns yellow this prevents the spirals and sometimes lets the snake get away a whole lot faster this is a quick rundown of the stats from my many many trials of snake the best recorded game was actually played by the most advanced algorithm which made me feel very accomplished that all of my bells and whistles were actually helping in that particular game only took 50 2698 moves for the final two versions I saw no looping failures so I guess it's still possible for it to fail by getting stuck in a loop but I've never seen it happen so it can't be very likely this thing runs at a blistering couple hundred frames per second when it's not plotting but when it is plotting and actually rendering out video frames that drops to like three fps so I'm playing it back a little bit faster than that rendering the complete game video takes like six hours MATLAB is probably not the right tool for this job but it is the hammer that I use to pounding nails and screws and rivets alike the bottom line is that AI is to play snake R Orion and I would love to see more of them a quick Google search actually doesn't turn up very many there's a lot of like machine learning tutorials which are fun but I don't see them reaching the sort of unkillable and efficiency that these algorithmic solutions can provide if you've watched code bullets video or this video and get nerd Smike the way I did please go make a snake AI and then post a video of it and tell me how it works because I would love to see more of these things out in the wild in the meantime remember to subscribe for more projects making photography and I guess the occasional simulation or artificial intelligence thanks for watching [Music]

Channel: AlphaPhoenix

Views: 923,294

Rating: 4.9154172 out of 5

Keywords: Alpha, Phoenix, Alpha phoenix, Alphaphoenix, Math, graph theory, game, ai, artificial intelligence, computer, science, teaching, education, Snake, arcade, Hamiltonian, cycle, path, algorithm, win, steps, optimization, solving, efficiency, np-hard, dynamic, repair, statistics, analysis, matlab, simulation

Id: TOpBcfbAgPg

Length: 17min 5sec (1025 seconds)

Published: Sun Feb 16 2020

Reddit Comments

[u/phire]

Rather than hand writing algrothms to account for special cases, I'd like to see a game tree based search approach.

Something that can look ahead to see and exploit those cases where it might block an exit now, but have one open up later.

[u/statystician]

Cool idea for the AI. Never thought about augmenting hamiltonian paths like this. It's nice since it's easy to see that you can't lose (as in get trapped).

I made a snake AI way back also. IIRC I never saw it fail, but I have no idea if it's really fool proof. The idea was to follow the shortest path to the apple, granted that the snake can then reach its tail. If it can't reach the apple, or if it wouldn't be able to reach its tail after eating the apple, instead follow the longest path to its tail.

[u/Alpha-Phoenix]

If anybody want's to see the detailed goods, I've got it all out on github_DHCR_with_strategy). The video talks about the actual theory of the algorithm, but I implemented in MATLAB (I know I'll get shade for that lol). If anybody just wants to watch the snake play, this is the entire median 30x30 game.

[u/tekknolagi]

This is excellent and exactly the sort of long-form content I enjoy watching.

[u/Gblize]

Wait what, you didn't do this in 24 hours? ^/s

It was way more enjoyable than I was expecting. Keep it up.