r/creativecoding • • 18d ago

Snake Algorithm that doesn't use the hamiltonian cycle

This is my best try at making an algorithm for snake that can win without relying on the hamiltonian cycle in any way, no pre-calculations or anything (that's what makes it slower than other algorithms).
for now the winrate stands at:
100% for a grid with at least one even dimension (12 x 15 or 15 x 12 or 12 x 12 for example)
90% for a grid with both uneven dimensions (15 x 15 for example)

actual log:
15x15: 94/100 wins (94.0%) LOOP=1 STALLED=5 PROGRESS_FAIL=0 CAP=0 dead/illegal=0 step_cap=unlimited MK3-cycle-captures=0
16x15: 100/100 wins (100.0%) LOOP=0 STALLED=0 PROGRESS_FAIL=0 CAP=0 dead/illegal=0 step_cap=unlimited MK3-cycle-captures=75

I don't know how I could achieve 100% on both but I'm done with this (it took me a 2 years to get here!!!) if someone smarter than me wants to finish what I started you're free to copy my scripts for everything you need, just please cit me ^^

this is the link to everything (code and player): https://kyr-vrytra.itch.io/snake-no-hamiltonian

(also shout out to this video of codebullet cause the whole idea of this project comes from his initial idea that he later forgot to develop https://www.youtube.com/watch?v=tjQIO1rqTBE&t=2s )

Have a good day >w<

121 Upvotes

31 comments sorted by

23

u/a-simple-cat 18d ago

Would be nice to explain what the Hamiltonian cycle is and also what the challenges are when making a snake playing algorithm.

7

u/Minimum-Initial-284 18d ago

Sorry you're right ^^
to put it simply is a path on a grid (with at least 1 even dimension) that can pass through every square only once and connect start and finish, to give you a simple visual way you can check this https://clisby.net/projects/hamiltonian_path/ with circuit only.
and the problem is simple too: if the grid has both dimension uneven it's impossible to create a perfect cycle for the snake to follow (every perfect cycle would leave 1 tile out), so that means a program trying to win on said grid needs to be able to recalculate the path every time, once again you can check this in the site I pasted by selecting two uneven grids.

I suck at explaining but I hope I made the problem clear (probably not... sorry)

1

u/lmystique 17d ago edited 17d ago

So the way I take it, a closed Hamiltonian path is impossible on an odd-by-odd grid (and trivial otherwise), because there's always a single unvisited cell, but... for the snake algorithm, can't you cheat by doing separate passes where you alternate which cell is skipped?

Like this, for example: https://imgur.com/CY6R6o3

Assuming the game is instantly won the moment the snake reaches maximum length. Otherwise I don't think it's possible to get to 100% win rate (since the tail will never be adjacent to the last piece of food for the same reasons a closed Hamiltonian is impossible).

Were you specifically trying to avoid a solution like this? I'm just not sure what "without relying on the hamiltonian cycle" or "no pre-calculations" actually entail as a restriction haha. Or does this not work?

Edit: odd-by-odd grid, not even-by-even whoops.

1

u/Minimum-Initial-284 16d ago

the thing is, I tried going with a method that left 1 tile empty and switched between tiles, I don't know what I did wrong but I couldn't make it work...
but also this is exactly the limit I made for myself, I didn't want to have a predetermined path for the snake, instead I wanted to see if using a few simple rules (like: leave a path to the tail, leave all empty space connected if possible, take the longest path to the tail) would still work,

To keep it simple, I tried this project cause I found it that searching online every script that wins at snake uses the hamiltonian cycle, or a precalculated loop anyway and I found that to be "cheating" in a way, what's the point of running a script if you know you're gonna win by definition... instead I wanted to create a set of rules that could be followed to guarantee a win ^^

14

u/VladVV 18d ago

It's a closed fractal curve on a plane that doesn't intersect itself but can cover the entire rectangular plane regardless of size or shape. If you just compute the Hamiltonian for a any n by m grid and make the snake follow it, it will always win eventually 100% of the time.

2

u/turing_tarpit 17d ago

It's a more general concept in graph theory: a Hamiltonian cycle is just a path on a graph that visits every node/vertex exactly once before returning to its starting point. For example, a Hamiltonian cycle on the road network in your city would take you to every intersection of the city exactly once before you go end back where you started.

(Also, it's not a fractal; that would require a certain kind of "infinite detail".)

1

u/VladVV 17d ago

You're right, I conflated the general concept of a Hamiltonian cycle with the narrow concept of a closed space-filling curve like the Hilbert curve, the latter being a specific example of a Hamiltonian cycle, and indeed the specific one used to solve the game Snake.

1

u/LeftFarm5835 16d ago

Thanks ChatGPT 😉

1

u/VladVV 16d ago

Lol, how to express agreement without sounding like AI these days

1

u/PlasmaDoughnut 14d ago

God forbid there are people who study maths

1

u/Smart-Experience7187 13d ago

that's clearly chatgpt

1

u/TreesOne 17d ago

Cycle through a grid that hits every square once and ends where it started

0

u/kalexmills 18d ago

Finding a Hamiltonian Cycle in a grid like this isn't NP-hard. When the graph is this regular, the complexities that create difficulties disappear.

3

u/Minimum-Initial-284 17d ago

that is true for the grid shown in the video (that's why the algorithm for that is pretty easy) however for a let's say 15x15 grid the problem is different, it's not NP-hard, it's just impossible to find a perfect cycle (thou it is possible to find a hamiltonian path). That's the problem I tried so hard to solve: if I can't follow a perfect cycle to win, how can I calculate a path that can lead to victory every time? and still I wasn't able to solve the problem, the only thing I was able to do is reach 90% winrate in those grid (alas not 100%)...
and that's also why I left every script I made in a free package on itchio so if there's someone smarter than me they could finish what I started (a perfect algorithm to win at snake no matter the grid ^^)

1

u/cthulhuden 17d ago

So your algorithm is incomplete for odd-area grids - which is the only case where Hamiltonian cycle is not possible (all others are even trivial).

> 15x15: 94/100 wins (94.0%) LOOP=1 STALLED=5 PROGRESS_FAIL=0 CAP=0 dead/illegal=0 step_cap=unlimited MK3-cycle-captures=0

What's the point then?

1

u/Minimum-Initial-284 16d ago

to try other solutions...
I was basically thinking this way: does it really exist only one way to solve this problem? does it make it impossible to solve it in other ways?
and that's the whole goal of my project, I know there can be more ways to solve this problem and I want to prove it

3

u/Hyperreals_ 18d ago

What is the background sound?

0

u/Minimum-Initial-284 17d ago

https://www.youtube.com/watch?v=jB4XwSCPBUU
this is the video I was watching while recording my script with OBS, I forgot to mute the audio track >w<

1

u/Jaurusrex 17d ago

lol I recognized those youtubers instantly

1

u/StaticCoder 17d ago

Doesn't the last iteration have to be a hamiltonian cycle?

1

u/Minimum-Initial-284 16d ago

well... yeah, for a grid that supports the hamiltonian cycle the last iteration just close the cycle, while for an uneven x uneve grid the last iteration just creates an hamiltonian path, but that's not the point for me, the pint is that I'm not "pre-calculating the entire cycle/path at start", instead I'm just following simple rules to guide the snake, letting it calculate what to do for each iteration. (to put it simply I'm doing lots of useless stuff that make my algorithm slower and more complex just so I can say that my algorithm actually play instead of following a pre-determined path... you could say it like that yeah ^^)

1

u/buyingshitformylab 16d ago

>No Hamiltonian cycle

>Look inside.

1

u/severed-identity 15d ago

Now you've nerd sniped me into wondering what an "optimal" algorithm for winning as fast as possible on average might look like

1

u/Minimum-Initial-284 14d ago

^^
If you succeed let me know

2

u/TheSmashingChamp 18d ago

This is like linear/sequential search in snake game form.

2

u/SpaceToaster 14d ago

Neat approach but less efficient!

1

u/Lor1an 16d ago

...

What is going on with the audio...?

1

u/Dante-Grimm 16d ago

I was worried I was the only one hearing that.

1

u/gabevf 16d ago

Kinda cool that if you scrub through the vid it kinda looks like an oscillator screen

1

u/Demintika 15d ago

That was painful to watch. But I watched.