How to Win Snake: The UNKILLABLE Snake AI

I watched the CodeBullet Snake AI video on the morning after Thanksgiving and spent WAAAAYY too much time working on an AI of my own. I present to you: Snake, as played algorithmically with Dynamic Hamiltonian Cycle Repair. The snake can never die - like really, actually, literally, can't be killed - it's just a matter of how fast it wins the game…

If you, like me, enjoy watching snakes run around eating apples for hours on end, enjoy this follow-up where I took the median-length game from my best performing algorithm and posted the whole darn thing on YouTube:

Check out the other social media for updates and ramblings:

#Snake #AI #Math

CODE!

Snake References:
@CodeBullet
@johnflux1

Mathworks File Exchange Reference:
A* code originally written by Einar Ueland

Actual MATH Papers:

Other clips in this video:
Morbo "Dooom" (Futurama)
"That's Illegal" meme (Red vs. Blue)

Music in this video:

[AlphaPhoenixChannel]

Wanted to let everybody know that I've been solidly shown up by a viewer! Twan was able to improve on my method by a massive 20% using a locally-gridded movement scheme that scales as well or better than my method (to my understanding there's still one 2D step that's akin to blobfinding). The snake only moves according to certain rules, which effectively places the snake into a subset of possible graph spaces that are MUCH easier to check for hamiltonicity. It was a broad concept I kicked around while working on this project but never thought up an implementable solution.

[Pklose]

"I underestimated what NP-Hard really meant" spoke to me on a spiritual level.

[JakubYTb]

10:25 When I'm explaining to my colleague, what my algorythm does.

[STUCASHX]

Can you imagine watching a live Snake A.I. competition where many A.I.'s are pitched against each other in 1 v 1 eliminations with the winner being the first to finish and the grids get larger as you get towards the finals?
I think it would be pretty cool...

[cmilkau]

Simple optimization: the repaired hc doesn't need to contain the snake as it is NOW, it only needs to contain the snake as it WILL BE after eating the apple.

[chancylvania]

Holy shit matlab. That’s the first time I’ve ever seen a video use matlab for which I haven’t explicitly looked up matlab.

[BlastinRope]

New snake mechanic: poop button that shrinks you 1/3rd but leaves a dot on the map that never disapears and you lose if you eat it

[MrBenMcLean]

It immediately occurs to me that a complete Hamiltonian cycle of the empty space isn't what's actually necessary to avoid death. What's actually necessary to avoid death is for there to be some combination of future moves which could eventually reach every currently empty square. The distinction is that the Hamiltonian cycle looks only at the spaces that are empty now while the "combination of future moves" idea also allows the snake to move into spaces that will become empty from its tail moving out of them in the future. This would allow the snake to do "riskier" things to get to the apple quicker while still never dying.

[Fortaker]

I'll say this: I know absolutely nothing about coding, programming, or algorithms. I did play Snake when I was a kid, but never knew how it worked. My math skills are in the gutter (like elementary school levels), and unlikely to improve anytime soon.

But for all that, I was riveted to this video. You have a great way of instructing, and I never felt lost. I couldn't help but laugh as your snake made so many "illogical" moves (at least from a human perspective). I loved it! Great job, and I hope to see more in the future!

[six]

This is a childhood fever dream come true

[mullafacation]

14:12 The algorithm is like those cars at traffic lights that slowly move forward thinking that they are getting half a metre closer to wherever they want to be but then can't see the lights when they turn green so they waste more time but feel like they are going faster or if a shop opens in 5 minutes but you go on a 2 hour walk to another city.

[tristanreid]

Saw this a few hours ago and can't stop thinking about it - I have been thoroughly sniped! I think it's useful to think of a scenario where after the next apple every single square encountered is a new apple. In that scenario if the path doesn't follow a Hamiltonion Cycle as it reaches that next apple, the game will fail. So that's the minimum requirement - that as the snake reaches the next apple, it must be guaranteed that the snake has an HC. Note that this minimum requirement is weaker than the current strategy, which is following an HC from the CURRENT position. For example, if the snake is 10 units long and the HC from the current position takes 100 moves to get to the apple, we can send the snake on the shortest non-intersecting path to the 90th step of the HC path. The reason this is guaranteed to work is that at the next time the snake is eat the apple and grow, it will be in the same position as if it had followed the whole HC path.

[tfexcession]

One of the signs that you might be the type of person to get nerd sniped is if you hear "xkcd 356" and immediately recognize it as the nerd sniping xkcd.

[andreamarino]

This was EXTREMELY pleasant to follow. Thank you sooo much! It's not common for games to be that rich of structure and still so enjoyable

"I need to plan a route ASAP to tour all the labs working on NP-hard problems!!" - I see what you did there :p

[elvenderideas]

Wow what a great effort on this video and the algorithmic solutions to games!

[rownrown]

Well done on taking something so arcane seeming and making it accessible and interesting. You made me appreciate all the thinking, hard work and collaboration between people that goes into these ai programs

[knampf]

Thanks for showing this. Now I can implement it in my professional snake gaming career.

[dorabear]

Wow, this is a really good video and very entertaining. This is the first snake AI video that discussed survivability and efficiency. Love to see some deep reinforcement learning algorithm that can achieve a similar performance but I guess a customized reward function is needed to address the balance of survivability and efficiency. I personally don't think a general RL algorithm could be as good without many handcrafted features and customization.

[gavin]

I think this IS my favorite channel I've come across, I started with the one about finding a leak in a vacuum chamber and every video since has been fantastically great at explaining ideas and concepts. They are interesting, and relitively in-depth, plus they have good craftsmanship. 10/10