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. I don't think it's on youtube anywhere, but there's a beautiful video of it running here: github.com/twanvl/snake/
Congratulations on your channel. I am from Greece , I do not speak English and this text is from a Google translation. Your video inspired me to deal again with a snake game for excel that I had created 2 years ago. From my tests I concluded that you can reduce the final movements by more than 20% with a simple trick, to set as a tail a virtual tail in half, or at any other point you wish, of the snake's body. with this technique you drastically reduce the unnecessary movements to fill the inaccessible area.. Ιn my tests so far the game on a 20x20 surface ends with an average of 10.200 moves with a higher 11.100 and a lower 8.950 with zero failures
Also, you don’t need to check for a mapwide path until the snake is longer then half the board, so a separate algorithm could control the first “half” of the game.
I'd be extremely eager to see you make a video on your viewer's results! Perhaps you could collab or ask the viewer for permission to make a (shorter) follow up video?
Very elegant algorithm. Keep up the good work. This kind of hard coding should be used more with ai and neural nets. This blew the neural nets out of the water. Keep up the good work.
@@LucasPlay171 I just think back to AOL dial-up in 1993, on a 486-DX66 with 2MB of RAM - and I think, bruteforce technology just needs more time! At the moment the trend is creating NP-Hard based encryption. But I think in future, NP-Hard defeating bruteforce software will become all the rage !
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.
I had the same idea, but I think it’s subtly not at all simple and non-trivially chaotic. If you modify the hc to include a future snake, the present snake no longer follows the hc that would predict that future.
That essentially boils down to calculating the entire entire path before taking it, which is not better (and with the current code might never terminate, whenever the snake would get stuck in a loop), or calculating all possible paths to make use of it, but that's gonna take a couple heat deaths to finish.
like david smith said, the repaired hc is actually just a tiny change to a small part of it. The snake as it is NOW still exists in the hc and so leaving it there is free, plus after eating the apple you only have one more segment of snake and nothing else has changed
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...
We did that in an university course. It was a modified snake games with two snakes playing against each other in the same field. You could either win by points (which did rarley happen) or win if the other snake dies. Attacking and trying to trap the other snake was allowed. Also there were power ups one could pick up and use, like moving the apple or setting a blocking wall piece. At the end of the course all the snakes fought against each other. Was a great course!
Dude. Now that you mention it, I have never seen an expanded version of Snake. Out of all the hundreds of millions of snake clones, about the only variety is the Paint-roller version; where there are four or more players on a single board competing to make the other snakes collide into them. We need a Snake 99 now. Wait. That's just Slither io.
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!
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.
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.
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.
I don't think the snake necessarily needs a Hamiltonian cycle after reaching the apple. Since you can still make your choice of direction after the new apple appears (at least according to the rules I'm familiar with), you can break the chain as soon as your path past eating the next apple has a choice of direction.
This was actually the main thing I was thinking about as I watched this. All you actually, really need to do is go from current position to apple in a way that leaves a valid Hamiltonian. You can even do a quick check for non-Hamiltonian solutions to verify the number of squares left in that Hamiltonian is more than the length of snake cutting you off, then you can even use some half cycles that eventually connect.
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.
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
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.
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
You can use flood fill and a time-weightmap to make it be able to predict how it can dodge its tail. Use flood fill to make a weightmap of how many steps it would take to reach a given location, and if the step count at the index of that weightmap during the Hamiltonian search is greater than the snake segment's distance to its tail at that location, that location will be available to the Hamiltonian search as a clear spot. Idk if that made any sense, but if it did, I think it'd be a better step optimization than "Applefear Mode".
You give us really exceptionally great content here! Love the style and honesty of everything! That graphic at 4:50 had colors in it that made it hard to see for me as a person with mild color blindness.
Neat video, I’ve always been interested in elegant algorithmic solutions to games. I assume you could make a machine learning AI that could get even faster than what you’ve designed if you gave it the same information you were checking for with your algorithm, but to get to that point it would likely take a long time, even longer than the full Hamiltonian cycle computation method. But if someone did do so, it would be nice to see if the resultant neural network could be viewed as an algorithm. I see you’re also a user of graph paper for everything, I go though the stuff like nobody’s business.
I switched to pens from pencils a few years ago and then unfortunately had to mostly switch away from graph paper cause the ink soaked through. However snake was just too perfect and I have piles of the stuff laying around xD I’d love to see a neural net capable of rebuilding Hamiltonian cycles. You could even do all the linear algebra on a gpu then and it would fly. I don’t know how you’d design such a structure though... interesting...
Yeah, neural networks aren't quite a magical hammer that fixes everything. In particular, they suffer from being somewhat "fuzzy" - they have a hard time thinking ahead, and they can be quite unpredictable. My immediate intuition tells me that you would have a very, very hard time getting a neural network to never fail. With something like this hamiltonian path fixer, it's relatively easy to prove that your algorithm will never die. With a good neural network, my suspicion is that it will do exceptionally well most of the time and then randomly die in bizarre ways every once in a while.
@@clonkex Pens just feel way smoother to write with and good pens have only two states - enough ink or not enough ink. When the second state is hit, you just get a new pen. Pencils have good, dull, broken, too short, no eraser, bad eraser, etc. Plus they feel way rougher to write with. The cited reason people prefer pencils over pens - erasability - tends not to impact much in practice. It will always be faster and easier to just scratch out a mistake than flipping over the pencil or grabbing a separate eraser. I guess when you've spent a lot of time in school or doing math, you start thinking about ways to make it easier. Or I'm just a nerd. I've also switched from lined paper to printer paper for most applications.
@@dumonu I personally find pens quite difficult to write with _because_ of how smooth they are. Every time someone says "here, sign this" and hands me a pen I have to mentally prepare so as not to go flying off the page on the first stroke.
Is the algorithm provided to find the hamiltonian-cycle is by MatLab? I just found the article that mentioned how to use Prim's Algorithm to generate a Hamiltonian Cycle
I remember going to Wichita State University in 2000-2001, studying Computer and Electrical Engineering. I also remember beating Snake on my Nokia phone by filling the entire screen up with my snake. Going up and down but leaving the bottom path open so I could continue the loop. I ended up enlisting in the Army and being an IT Specialist. During war, even an IT Specialist gets the opportunity to be shot at.
You wake up old memories, when I implemented a Snake variant for the open source "Rockbox" firmware for mp3-players. Then I also implemented the most simple minded strategy for the npc opponents: Go straight for the apple. But I didn't call that AI. I called AS (Artificial Stupidity) - and that's what ist was! Thank you!
Interesting video. I think i have a far simpler solution based on the way I played the game myself back in the day. this would take a stepped approach factoring the length of the snake. First, find the perimeter of the map and hug it. only dip down at the correct x coordinate of the apple, eat it, go all the way to 1 pixel before the perimeter and go back up back to the safety of the original perimeter path(i will call this a full dip from here on). Then when the snake gets long enough that it can almost reach its own tail, add an additional full dip at one side of the map before continuing along the perimeter as per usual. Add a full dip to the left of the map each time this happens until the snake is the maximum length and the game is complete. This will cut out the need for all complex algorithms as there would be no risk of getting stuck. The marginal loss of efficiency at the beginning of the game is significantly outweighed by the increased simplicity and efficiency of the pathing across the rest of the game and these gains continue to show dividends all the way through to the end of the game. This method is foolproof and significantly improves on the pure Hamiltonian method without the significant added complexity.
@@nikolatasev4948 I have not, based on the logic though, I don't see how it could be wrong. The strategy is so simple that I can't imagine it having enough variability to be wrong. The only limiting factor is the player and his ability to concentrate for the length of the game. computers of course don't have this variability and can play it perfectly every time. If someone does actually program it, I'd be very interested in hearing about it.
I made one when i was in high school ! Not so complicated, because of my knowlege, and it runned on javaME on phones ! I'll try to dig it out to see how it performed. From what I remeber it can trap itself but it was fast because it's main mode was going strait to the apple in 2 lines, one turn ! To fine tune it i used variables and tried out a lot of settings. But un 2008 on a java platform it was painfully slow. Your version is great, congratulation and the video is fun, which for a programming video is not easy !
SIR WHAT YOU HAVE DONE IS PURELY AMAZING!!! I have no words to explain my gratitude for taking your time to 1) make the AI and implement the algorithms and 2) to make the video, edit it and upload it for us - the viewers.
I didn’t really understand the entire video, but I got a decent idea of what’s happening, so basically you have the snake always following a Hamiltonian cycle, but it cycles through all possible (based on parameters such as, length of snake and whether it will collide with itself or walls) paths to find the fastest way to the apple. It will reset every time the apple is acquired. Anyone who actually understood everything, let me know if I’m correct.
I must point out that the makers of Snake missed a huge opportunity by not adding more complex sound fx. Your options at 10:20 definitely made my day. Probably more of an audio improvement to any next-gen reboots of Snake.
theoretical minimum would be then number of cells in the level. So for a 10x10 grid it would be 100 moves. This would only happen in the extremely unlikely case that each apple would spawn in the next cell that you are going to
Your videos are so technical to the point where you can probably write this all down and get publications. You could even collaborate with profs in these branches of mathematics too, I don't see videos this technical often, you have skills. It's great to see you know MATLAB, I spent years learning it in school and making projects, but employers usually don't like it compared to other languages.
As a university professor, I can safely say I will NEVER collaborate with this person, who spreads misinformation over the internet. If you seriously think this individual should publish something (I thought you were joking at first!), then you desperately need to open a book and start studying. Any book, doesn't matter the subject. Currently, you live in a fantasy world where donkeys fly and ignorant youtubers publish mathematical papers.
@@aaaab384 If I understand well, you are arguing on internet, that there are people on it, who are spreading misinformation, without proofs neither adding serious arguments to your accusations? ( I can't believe the authoritative one, a professor would not be so childish, nor hypocrite, and we wont answer to your second argument cause it's just a disguised insult).
I doubt you are a university professor. All math professors I met are ready to give arguments even for nonsense questions without laughing at the person who asks. Will you give such an argument?
i played snake as a kid on my old flip phone (first phone) enjoyed the hell out of it I never stopped to think about the science that went into it. cool video man
So cool! Back in the 90's, I wrote Snake inside of an IVR (interactive voice response) system. You played using DTMF tones - touch tones on a dial phone! Love seeing this kind of stuff, such fun!
There's definitely significant room for improvement from a mathematical perspective- ideally, you wouldn't want to use hamiltonian cycles at all; you'd want to use some new mathematical construct like "time-adjusted hamiltonian cycles" where new edges form based on time. That said, you'd need to be a math professor to make that improvement, so it's not something feasible for a coder who uses other people's results/code. I think this is a possible direction for a math research project not gonna lie- maybe I'll recommend it to my highschool math friends.
"it's not something feasible for a coder who uses other people's results/code" I don't think you meant any offense with that, but if read with the wrong eyes, it sounds a little bit condescending. There are reasons to re-use other people's work: you save time, don't reinvent the wheel and, you know, honor their efforts. Stand in the shoulders of giants and all that. It's what science is about, right? Also, sometimes using other's code requires overcoming a certain resistance that some of us have for not writing our own stuff (and I speak for myself mostly, boy am I hard to convince to reuse code instead of doing my own implementation). My point is, reusing other people's code is in no way indicative of the level of skill of this person to invent new maths. Maybe you don't need to be a professor to do it, maybe you can figure it out with enough dedication to research and fill the gaps. After all, solving hard problems is how you become a professor, and not by letting gatekeepers tell you what you can and what you can't do. Even if I was convinced that you need to be an authority in a certain field in order to contribute to it, I have no idea of this person's background. However, if he's a computer's science major (and since I don't know about him, I don't have any reason to believe that he isn't), for instance, he has all the authority in the world to make that and other improvements. Again, I don't think there was the slightest ill intent in your comment, but maybe it can be a little bit discouraging for someone passing by and reading. "Why would I try any hard problem if I'm not a professor?"
I wonder if a simpler ruleset could be used to make sure there's always an escape route. Perhaps to explore possible rules, a sort of "turn-based strategy game" version of Snake could be implemented, in which a human has an unlimited amount of time to decide on the ideal route to the next apple, and then has to draw it on the screen. Infinite chances to redraw the route, and a confirm button onscreen and/or on the keyboard to execute the move. This would be boringly easy for a human player, but might be a good tool to help figure out an AI ruleset that ensures safe and reliable navigation.
@@hemartej Sorry for any offense. I meant it literally, that if you only intend to use already published results, you probably wouldn't find the research I'm talking about. All I meant was that you'd have to do mathematical research for that direction.
@@Benw8888 Of course, don't worry :) I was convinced you didn't have any sort of ill intent with your comment, but some people could give it a different interpretation based on the wording.
Coming up with a smarter algorithm reminds me of an undergrad scheme assignment. We wrote the exponential function pow(x,n) with plain recursion; [if n =1 return x; if n > 1 return x*pow(x,n-1)]. Prof had us test the time it took to run for 2^trillion or billion. My computer needed a memory upgrade, so it took a little over 30 minutes to run. When we added checking for even values of n [since x^(2y) == (x^y)^2], the same calculation took a few milliseconds on my underpowered box.
Ah yes, algorithm again This is the most relaxing video it really wants me to watch after doing physics, math, and chemistry homework before I go to 2 hours sleep before it's 6 AM
"MatLab was probably not the best tool for this job. But it is the hammer that I use to pound nails, screws, and rivets alike." I've never felt more seen by a youtube video in my life.
Really liked the through experiments conducted for this video, deep dive analysis of each attempt. This is almost equal to undergrad/master thesis level work.
Commenting my thought in the hopes that it alleviates the nerd sniping and I can do literally anything else with my time: the path finding can be improved by knowing which parts of the grid will become available after each step. Just keep count of how many moves until each ‘tail’ tile becomes a free tile, and a* can consider it not to be an obstacle after that many iterations from the present state. Thanks for posting the video, but also curse you for trying to trap me in a snakey part of my mind. Evil!
Hey. I'd love if you mentioned me - because afaik I invented the Hamiltonian cycle idea, as CodeBullet said. I was sponsored by Nokia themselves, for the California MOMA museum. I love your new additions and ideas.
What if you Split it up into tow algorithms, One that just has the snake take the fastest possible path that doesn't run into itself, and at some point later on when that becomes unsafe(unsure when that would be, probably determined through experimentation) Switch over to the algorithm you showed? That would probably save a substantial amount in the early stages of the game.
The fact that I already knew the Hamiltonian Cycle strategy and used it to beat the game when I first played this game in middle school makes me feel smart af
I loved playing Snake Byte on the Apple //e. There were two game plays--the harder one had a bouncing plum that could crash into you. In both game plays, the player had 10 seconds to eat the apple. If that didn't happen, another apple appeared. I think each board required the player to eat 10 apples (aside from any extra that appeared because of the 10-second rule). Successive boards include obstacles that you had to move around. I never beat it, and I have been looking for that game ever since.
@@sit33darshanpagar16 nobody needed to??? They were just saying that it would be funny if they imported it in python, because, well, snake close to python.
@@y2kona It's a slow turd that condone bad practices. Guess where people bring those practices once they grow out of that toy? You guessed it, other languages. It truly is a cancer.
Got an idea to speed up the algorithm. No need to have a path ahead that is strictly Hamiltonian. As long as the upcoming path always allows to continue into any path that leads back to the tail you will always be able to reach any point of the board (if Apple appears in an area for which no such path exists, simply follow the tail until it does. Not sure if the snake is quicker but the math behind it seems more simple.
Really fascinating, one of the most interesting aspects is comparing purely algorithmic solutions, machine learning solutions, and "the human way" which is a mix of logic and "intuition", in the sense that we know something is the right move but can't readily explain why. Exactly how our brain manages that is probably the missing step to achieve general AI.
Does this algorithm ever consider the length of its path with respect to its tail? The length of tail that is equivalent to the length of the path to the apple won't matter for finding a new Hamiltonian cycle, it looks like. Avoiding a board split only seems relevant when the apple has been picked up.
no, that would take it out of its hamiltonian cycle. He tried making a "simple formula" that could solve all parts of snake, doing the lenght compared to tail lenght would only work until 30-50% of the board got filled (depending on the shape) and trying to do so in a hamiltonian cycle would take more processing power the longer the snake got. Which is technically what he tried early on where it didn't load anything for 15min during 1 move.
The issue I see is this early/mid algorithm (at around 2/3rds the video length) needs a full and complete hamiltonian cycle, meaning that it will essentially prioritize filling in space compactly over dashing to the apple. I would check to make sure that if it did break the hamiltonian cycle, it makes sure that the cycle it is on has more spaces in it than its actual length. Though, I could see some other problem arising quickly from there during late-game play...
I've got a simple idea... Have the snake compare the distance to the apple to the distance it's tail needs to move to survive, that way it won't go back to fill in area's it doesn't need to. Half of the game is forcing the apple to spawn near the head so another idea is to calculate the distance traveled to each tile for an apple and make the snake move in a way the apple spawns the fewest moves away as high as possible. Results would be the snake recklessly charging towards the apple in a way that makes the apple likely to spawn fewer tiles away.
Love the video! But I have to nitpick slightly, specifically the section that starts at 6:17, because the question of whether the snake has a Hamiltonian cycle that reaches the corner (or more generally, can ever go into the corner) is a bit trickier than your answer makes it seem. For your given example, a Hamiltonian cycle exists for both possibilities, but for an AI to 'see' it requires it to have the foresight that while its body currently occupies said Hamiltonian, it will not in a future state when the head crosses. Which is a much more computationally complex route to go when designing an algorithm and obviously not something you want to do, but is still true none-the-less.
16:00 When machine learning is not sufficient to produce perfect enough solutions the trick is to make the AI responsible of a subroutine and not of the entire decision making. By exemple in your program you have a baseline algorithm on top of which you have added "special cases optimisation" so the idea would be to make all this "special case subroutines" into a generic format for an AI output (like something suggesting several candidate paths in order of preference) that would be validated and selected by the main program. (and as usual AI suggestion are trained based on a criteria to determine to evaluate how they have performed) It would require to rewrite the program to be efficient, because good training would required at the bare minimum 10th of thousands of games. But it definitely would be fun to see how it would crush manually crafted subroutines :p
Code Bullet is fun to watch, but none of his stuff is original. He just finds what gaming AI algorithms are already out there and implements them in an entertaining way. Props to you for researching the theory behind this stuff!
Just a really tiny nitpick: if a problem Π ∈ NP-hard, that actually just means that Π is at least as hard as every problem in NP via polynomial time reductions. There is a class called EXP-Time (exponential time) which is a superset of NP and (NP ∩ NP-hard) ⊂ EXP-Time (but not a superset of NP-hard). Problems in Exp-Time actually have the runtime you described in the video but there could be problems in NP-hard that can not be solved in exponential time. I'd be happy to provide more details if anyone is interested because it is actually a pretty cool topic once you demystify the whole P=NP thing
You confused him even more. His problem is that he doesn't understand the definition of NP (he thinks it means "not polynomial"!), and you didn't state the definition, either! You just added more (unnecessary) information, and you didn't even do a very good job at explaining it. If you actually want to help him rather than confuse him, tell him what NP really means.
I loved math and comp science..but I was in a really bad car wreck and well..lost the ability to go into your field.this was interesting and I'm glad there's people like you out there who like this,my friends always made fun of me lol. Thx God for TH-cam to find like minded people
Saw Snake AI in title, clicked, thought about CodeBullet, saw CodeBullet in description. Reference to XKCD in first second of video... Went to click "subscribe", already subbed. That was a fast 8 seconds.
I can't really remember when this was recommended to me and I still don't really know how (I'm no programmer, I'm interested in it and was searching up bits about AI), but I do remember just giggling like a young teenager at 3am when 10:31 happened as it clearly shows your frustration in a very practical way😂. Thanks for informing me a bit more about AI.
When the snake realises it's closed in I would suggest, from the "entry point" of the closed area, to calculate a few moves ahead to see if a two-cell gap opens up, then build a route inside the closed area, twice as long as the length of the tail beyond the entry point and which is an HC containing the two points of the gap. Then to "plug" into that route, that is, build a path for the snake to get on that route after its midpoint. That's roughly the idea. . I mean, the whole point is not to get trapped, so we can build the whole algo off of that. We should compare the outer area cell number with the length of the snake to realize whether we will need to go back into that closed area because the open area has ended. And if the outer area is bigger, we can just run the shortest path to exit from the closed area.
I feel like a 2 step a* would be my solution. First step is finding the path to the apple, second stage checks that a path from the apple to the tail will still be available once it arrives. When building the Path the AI compares steps taken to TailTimeToLive to verify if the tail will exist at that step and would thus be allowed to path through tiles that will open. In the second stage finding a tile set to expire before the apple is collected would be enough to say a survivable path would exist. No clue how performant it would be at the various stages though.
The dude got stroke by a question one morning and basically did a PhD on it, just for that you owe my infinite respect. Ps: About your remark about yourself at the beginning, did you know about MBTI classification ? I swear you're an INTP dude 👍
I think you can improve your algorithm when it calculates how far the tail has to move to make the path short. This means that it calculates multiple scenarios of eventual positions and chooses the fastest one. But this may require processing power we might not have. This could also solve the issue of doing a long run to not cut the hamiltonian cycle as after a certain amount of time it can reconnect again.
I'm currently writing my own snakeAI and the problem is much more daunting than i thought it would be. I've taken a different approach to you and am trying to make a system where there is a set of rules and as long as all these rules are obeyed, there is a hamiltonian cycle which means no bruteforcing is needed (when i say brute force i mean testing all possibilities) (and its no brute forcing apart from brute forcing the next move out of the
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.
I don't think it's on youtube anywhere, but there's a beautiful video of it running here: github.com/twanvl/snake/
Congratulations on your channel. I am from Greece , I do not speak English and this text is from a Google translation. Your video inspired me to deal again with a snake game for excel that I had created 2 years ago. From my tests I concluded that you can reduce the final movements by more than 20% with a simple trick, to set as a tail a virtual tail in half, or at any other point you wish, of the snake's body. with this technique you drastically reduce the unnecessary movements to fill the inaccessible area.. Ιn my tests so far the game on a 20x20 surface ends with an average of 10.200 moves with a higher 11.100 and a lower 8.950 with zero failures
Also, you don’t need to check for a mapwide path until the snake is longer then half the board, so a separate algorithm could control the first “half” of the game.
Whut
I'd be extremely eager to see you make a video on your viewer's results! Perhaps you could collab or ask the viewer for permission to make a (shorter) follow up video?
Very elegant algorithm. Keep up the good work. This kind of hard coding should be used more with ai and neural nets. This blew the neural nets out of the water. Keep up the good work.
"I underestimated what NP-Hard really meant" spoke to me on a spiritual level.
You always underestimate it until you try to bruteforce it
NP stands for Not Plausible, after all.
@@rykehuss3435 you never understimate it with a potato PC like mine
It means Not feasibly Possible
@@LucasPlay171 I just think back to AOL dial-up in 1993, on a 486-DX66 with 2MB of RAM - and I think, bruteforce technology just needs more time! At the moment the trend is creating NP-Hard based encryption. But I think in future, NP-Hard defeating bruteforce software will become all the rage !
10:25 When I'm explaining to my colleague, what my algorythm does.
www.smbc-comics.com/comic/2014-02-24
@@AlphaPhoenixChannel you nerds and your applicable comics 😂 I love it
Dis day dzz daz dzz dzz
Autocorrect had to get used to that
I mean...there's something to be said for an explanation that is both correct *and* Tweet-sized :)
Lol
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.
nice
I had the same idea, but I think it’s subtly not at all simple and non-trivially chaotic. If you modify the hc to include a future snake, the present snake no longer follows the hc that would predict that future.
That essentially boils down to calculating the entire entire path before taking it, which is not better (and with the current code might never terminate, whenever the snake would get stuck in a loop), or calculating all possible paths to make use of it, but that's gonna take a couple heat deaths to finish.
like david smith said, the repaired hc is actually just a tiny change to a small part of it. The snake as it is NOW still exists in the hc and so leaving it there is free, plus after eating the apple you only have one more segment of snake and nothing else has changed
@CodeBullet should feel good about this. Maybe. Sorta.
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...
Some algorithms may work better at different sizes of the board, so it may be a good idea to not change the size
@@blakceyedpeas Or you encourage people to write generalized algorithms that work across a variety of grid sizes.
We did that in an university course.
It was a modified snake games with two snakes playing against each other in the same field. You could either win by points (which did rarley happen) or win if the other snake dies. Attacking and trying to trap the other snake was allowed. Also there were power ups one could pick up and use, like moving the apple or setting a blocking wall piece.
At the end of the course all the snakes fought against each other.
Was a great course!
@@XoXkS So was it like a combination of Snake and Tron with additional boosts? Nice.
BMTron is the game this reminds me of :)
Played that in high school constantly
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.
as a software engineer this scares me lol. but i understand hes more comfortable with matlab as a tool
@@supernovahm1178 like I’ve never seen matlab used when I haven’t specifically looked up a matlab tutorial
@@supernovahm1178 I mean most people don’t know what matlab is. Unless you’ve used it in college people know python and others more
@@supernovahm1178 I don’t know what that is but it’s still a programming language.
@@supernovahm1178 implying intelligent people prefer matlab over python
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
no it is win
Dude. Now that you mention it, I have never seen an expanded version of Snake. Out of all the hundreds of millions of snake clones, about the only variety is the Paint-roller version; where there are four or more players on a single board competing to make the other snakes collide into them.
We need a Snake 99 now. Wait. That's just Slither io.
@@endlesswanderer1753 That paint roller game sounds like Tron, specifically Light Cycles.
@@endlesswanderer1753 what about google’s snake? That comes packed with tons of weird extra versions?
@@endlesswanderer1753 google snake has several different modes and has had them for years and is still being updated
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!
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.
How much sleep are getting?
Congrats, you've been nerd sniped
this doesn't actually optimize the algorithm, it sounds easy but what you propose is also np hard
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
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.
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.
I don't think the snake necessarily needs a Hamiltonian cycle after reaching the apple. Since you can still make your choice of direction after the new apple appears (at least according to the rules I'm familiar with), you can break the chain as soon as your path past eating the next apple has a choice of direction.
This was actually the main thing I was thinking about as I watched this. All you actually, really need to do is go from current position to apple in a way that leaves a valid Hamiltonian. You can even do a quick check for non-Hamiltonian solutions to verify the number of squares left in that Hamiltonian is more than the length of snake cutting you off, then you can even use some half cycles that eventually connect.
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.
uhh
not nerd enough @@7anx2142
This is a childhood fever dream come true
Get lost, another fake channel of Dan
@@RamkrishanYT Dan?
Your channel logo is brilliant!
yes, so many levels
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
Wow what a great effort on this video and the algorithmic solutions to games!
"I need to plan a route ASAP to tour all the labs working on NP-hard problems!!" - I see what you did there :p
traveling salesman, classic NP-Hard problem
Why don't you people study some more? You are so ignorant.
@@aaaab384 what about the original comment was 'ignorant'
@@aaaab384 do you not understand what an NP hard problem is?
@@aaaab384 who?
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.
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
9:35 if that was a speedrun strat it would be called a wormhole
You can use flood fill and a time-weightmap to make it be able to predict how it can dodge its tail.
Use flood fill to make a weightmap of how many steps it would take to reach a given location, and if the step count at the index of that weightmap during the Hamiltonian search is greater than the snake segment's distance to its tail at that location, that location will be available to the Hamiltonian search as a clear spot.
Idk if that made any sense, but if it did, I think it'd be a better step optimization than "Applefear Mode".
You give us really exceptionally great content here! Love the style and honesty of everything! That graphic at 4:50 had colors in it that made it hard to see for me as a person with mild color blindness.
The red and blue for the nodes and edges? Or red and green from the edges and snake?
@@ufffd Red-green is the most common form of colourblindness, so most likely that I suppose. I wouldn't be surprised if it was both of them though.
"The hamiltonicity of arbitrary bipartite rectangular grid graphs"
43 seconds in and I can already tell my brain is too small for this.
Omg, dude! Kudos for your amazing efforts on digging into this topic. Appreciate your work on this⚡️
Neat video, I’ve always been interested in elegant algorithmic solutions to games. I assume you could make a machine learning AI that could get even faster than what you’ve designed if you gave it the same information you were checking for with your algorithm, but to get to that point it would likely take a long time, even longer than the full Hamiltonian cycle computation method. But if someone did do so, it would be nice to see if the resultant neural network could be viewed as an algorithm.
I see you’re also a user of graph paper for everything, I go though the stuff like nobody’s business.
I switched to pens from pencils a few years ago and then unfortunately had to mostly switch away from graph paper cause the ink soaked through. However snake was just too perfect and I have piles of the stuff laying around xD
I’d love to see a neural net capable of rebuilding Hamiltonian cycles. You could even do all the linear algebra on a gpu then and it would fly. I don’t know how you’d design such a structure though... interesting...
Yeah, neural networks aren't quite a magical hammer that fixes everything. In particular, they suffer from being somewhat "fuzzy" - they have a hard time thinking ahead, and they can be quite unpredictable.
My immediate intuition tells me that you would have a very, very hard time getting a neural network to never fail. With something like this hamiltonian path fixer, it's relatively easy to prove that your algorithm will never die. With a good neural network, my suspicion is that it will do exceptionally well most of the time and then randomly die in bizarre ways every once in a while.
@@AlphaPhoenixChannel "I switched to pens from pencils a few years ago" Wait, that's a thing people think about? I just grab whatever's closest.
@@clonkex Pens just feel way smoother to write with and good pens have only two states - enough ink or not enough ink. When the second state is hit, you just get a new pen. Pencils have good, dull, broken, too short, no eraser, bad eraser, etc. Plus they feel way rougher to write with. The cited reason people prefer pencils over pens - erasability - tends not to impact much in practice. It will always be faster and easier to just scratch out a mistake than flipping over the pencil or grabbing a separate eraser. I guess when you've spent a lot of time in school or doing math, you start thinking about ways to make it easier. Or I'm just a nerd. I've also switched from lined paper to printer paper for most applications.
@@dumonu I personally find pens quite difficult to write with _because_ of how smooth they are. Every time someone says "here, sign this" and hands me a pen I have to mentally prepare so as not to go flying off the page on the first stroke.
Is the algorithm provided to find the hamiltonian-cycle is by MatLab? I just found the article that mentioned how to use Prim's Algorithm to generate a Hamiltonian Cycle
Big coding mood when you said your algorithm was great...when it worked. I felt that in my soul lmao
Thanks for showing this. Now I can implement it in my professional snake gaming career.
I too believe in ‘The Of Grid’
I remember going to Wichita State University in 2000-2001, studying Computer and Electrical Engineering. I also remember beating Snake on my Nokia phone by filling the entire screen up with my snake. Going up and down but leaving the bottom path open so I could continue the loop. I ended up enlisting in the Army and being an IT Specialist. During war, even an IT Specialist gets the opportunity to be shot at.
mate you ventured beyond being just programmer, you became scientist.
You wake up old memories, when I implemented a Snake variant for the open source "Rockbox" firmware for mp3-players. Then I also implemented the most simple minded strategy for the npc opponents: Go straight for the apple. But I didn't call that AI. I called AS (Artificial Stupidity) - and that's what ist was!
Thank you!
oh dear, rockbox takes me back - I spent many hours playing snake on my little 1-bit display Sansa player
I call those AU - - Artificial Unintelligence
I'll give you a like, but only because you didn't gave up after one day. Props to you, really enjoyed watching every single minute of this.
Interesting video. I think i have a far simpler solution based on the way I played the game myself back in the day. this would take a stepped approach factoring the length of the snake. First, find the perimeter of the map and hug it. only dip down at the correct x coordinate of the apple, eat it, go all the way to 1 pixel before the perimeter and go back up back to the safety of the original perimeter path(i will call this a full dip from here on). Then when the snake gets long enough that it can almost reach its own tail, add an additional full dip at one side of the map before continuing along the perimeter as per usual. Add a full dip to the left of the map each time this happens until the snake is the maximum length and the game is complete. This will cut out the need for all complex algorithms as there would be no risk of getting stuck. The marginal loss of efficiency at the beginning of the game is significantly outweighed by the increased simplicity and efficiency of the pathing across the rest of the game and these gains continue to show dividends all the way through to the end of the game. This method is foolproof and significantly improves on the pure Hamiltonian method without the significant added complexity.
Have you tried coding it and checking how it performs?
@@nikolatasev4948 I have not, based on the logic though, I don't see how it could be wrong. The strategy is so simple that I can't imagine it having enough variability to be wrong. The only limiting factor is the player and his ability to concentrate for the length of the game. computers of course don't have this variability and can play it perfectly every time. If someone does actually program it, I'd be very interested in hearing about it.
I made one when i was in high school ! Not so complicated, because of my knowlege, and it runned on javaME on phones ! I'll try to dig it out to see how it performed. From what I remeber it can trap itself but it was fast because it's main mode was going strait to the apple in 2 lines, one turn ! To fine tune it i used variables and tried out a lot of settings. But un 2008 on a java platform it was painfully slow.
Your version is great, congratulation and the video is fun, which for a programming video is not easy !
SIR WHAT YOU HAVE DONE IS PURELY AMAZING!!! I have no words to explain my gratitude for taking your time to 1) make the AI and implement the algorithms and 2) to make the video, edit it and upload it for us - the viewers.
I didn’t really understand the entire video, but I got a decent idea of what’s happening, so basically you have the snake always following a Hamiltonian cycle, but it cycles through all possible (based on parameters such as, length of snake and whether it will collide with itself or walls) paths to find the fastest way to the apple. It will reset every time the apple is acquired.
Anyone who actually understood everything, let me know if I’m correct.
I must point out that the makers of Snake missed a huge opportunity by not adding more complex sound fx. Your options at 10:20 definitely made my day. Probably more of an audio improvement to any next-gen reboots of Snake.
They couldn't. Snake was originally written in basic on a system 80 with only 16k ram.
I really like how you ended up with an algorithm that switches between "strategies" because that's more or less how the ghosts from Pacman work
Did you calculate what the theoretical minimum runtime a game would take? Like could an optimal algorithm on average solve a game with like 30k moves?
theoretical minimum would be then number of cells in the level. So for a 10x10 grid it would be 100 moves. This would only happen in the extremely unlikely case that each apple would spawn in the next cell that you are going to
This is awesome! It is really amazing how complex seemingly simple problems can be!
Your videos are so technical to the point where you can probably write this all down and get publications. You could even collaborate with profs in these branches of mathematics too, I don't see videos this technical often, you have skills. It's great to see you know MATLAB, I spent years learning it in school and making projects, but employers usually don't like it compared to other languages.
As a university professor, I can safely say I will NEVER collaborate with this person, who spreads misinformation over the internet. If you seriously think this individual should publish something (I thought you were joking at first!), then you desperately need to open a book and start studying. Any book, doesn't matter the subject. Currently, you live in a fantasy world where donkeys fly and ignorant youtubers publish mathematical papers.
@@aaaab384 If I understand well, you are arguing on internet, that there are people on it, who are spreading misinformation, without proofs neither adding serious arguments to your accusations? ( I can't believe the authoritative one, a professor would not be so childish, nor hypocrite, and we wont answer to your second argument cause it's just a disguised insult).
@@dakorjparie2425 try again in English.
@@aaaab384 I can't find any reason to do it, peoples aren't your mupets, fake teacher :)
I doubt you are a university professor. All math professors I met are ready to give arguments even for nonsense questions without laughing at the person who asks. Will you give such an argument?
i played snake as a kid on my old flip phone (first phone) enjoyed the hell out of it I never stopped to think about the science that went into it. cool video man
So cool! Back in the 90's, I wrote Snake inside of an IVR (interactive voice response) system. You played using DTMF tones - touch tones on a dial phone! Love seeing this kind of stuff, such fun!
I had no idea I'd actually know what you were talking about in the beginning, by minute 15. This is some insane meal-time content right here.
There's definitely significant room for improvement from a mathematical perspective- ideally, you wouldn't want to use hamiltonian cycles at all; you'd want to use some new mathematical construct like "time-adjusted hamiltonian cycles" where new edges form based on time.
That said, you'd need to be a math professor to make that improvement, so it's not something feasible for a coder who uses other people's results/code. I think this is a possible direction for a math research project not gonna lie- maybe I'll recommend it to my highschool math friends.
"it's not something feasible for a coder who uses other people's results/code" I don't think you meant any offense with that, but if read with the wrong eyes, it sounds a little bit condescending. There are reasons to re-use other people's work: you save time, don't reinvent the wheel and, you know, honor their efforts. Stand in the shoulders of giants and all that. It's what science is about, right? Also, sometimes using other's code requires overcoming a certain resistance that some of us have for not writing our own stuff (and I speak for myself mostly, boy am I hard to convince to reuse code instead of doing my own implementation). My point is, reusing other people's code is in no way indicative of the level of skill of this person to invent new maths. Maybe you don't need to be a professor to do it, maybe you can figure it out with enough dedication to research and fill the gaps. After all, solving hard problems is how you become a professor, and not by letting gatekeepers tell you what you can and what you can't do.
Even if I was convinced that you need to be an authority in a certain field in order to contribute to it, I have no idea of this person's background. However, if he's a computer's science major (and since I don't know about him, I don't have any reason to believe that he isn't), for instance, he has all the authority in the world to make that and other improvements.
Again, I don't think there was the slightest ill intent in your comment, but maybe it can be a little bit discouraging for someone passing by and reading. "Why would I try any hard problem if I'm not a professor?"
I wonder if a simpler ruleset could be used to make sure there's always an escape route.
Perhaps to explore possible rules, a sort of "turn-based strategy game" version of Snake could be implemented, in which a human has an unlimited amount of time to decide on the ideal route to the next apple, and then has to draw it on the screen. Infinite chances to redraw the route, and a confirm button onscreen and/or on the keyboard to execute the move.
This would be boringly easy for a human player, but might be a good tool to help figure out an AI ruleset that ensures safe and reliable navigation.
@@hemartej Sorry for any offense. I meant it literally, that if you only intend to use already published results, you probably wouldn't find the research I'm talking about. All I meant was that you'd have to do mathematical research for that direction.
@@Benw8888 Of course, don't worry :)
I was convinced you didn't have any sort of ill intent with your comment, but some people could give it a different interpretation based on the wording.
Coming up with a smarter algorithm reminds me of an undergrad scheme assignment. We wrote the exponential function pow(x,n) with plain recursion; [if n =1 return x; if n > 1 return x*pow(x,n-1)]. Prof had us test the time it took to run for 2^trillion or billion. My computer needed a memory upgrade, so it took a little over 30 minutes to run.
When we added checking for even values of n [since x^(2y) == (x^y)^2], the same calculation took a few milliseconds on my underpowered box.
It would be super cool to see how much moves snake spends in each mode.
Ah yes, algorithm again
This is the most relaxing video it really wants me to watch after doing physics, math, and chemistry homework before I go to 2 hours sleep before it's 6 AM
That totally looks like something Code Bullet would do.
He did do it XD
@@Felape_xiop But not for as long or as well.
"MatLab was probably not the best tool for this job. But it is the hammer that I use to pound nails, screws, and rivets alike." I've never felt more seen by a youtube video in my life.
Why not active Hamilton algorythm when snake length is almost at max?
perhaps it only activates in full once the snake takes up >60% of the grid?
The snake is not unintelligent, it always has a plan. You just want it to speedrun Snake
Really liked the through experiments conducted for this video, deep dive analysis of each attempt. This is almost equal to undergrad/master thesis level work.
Commenting my thought in the hopes that it alleviates the nerd sniping and I can do literally anything else with my time: the path finding can be improved by knowing which parts of the grid will become available after each step. Just keep count of how many moves until each ‘tail’ tile becomes a free tile, and a* can consider it not to be an obstacle after that many iterations from the present state. Thanks for posting the video, but also curse you for trying to trap me in a snakey part of my mind. Evil!
Why not code it to get the apple until a cycle is actually needed for it to clear the board that way it moves even faster until the snake is too long
Hey. I'd love if you mentioned me - because afaik I invented the Hamiltonian cycle idea, as CodeBullet said. I was sponsored by Nokia themselves, for the California MOMA museum. I love your new additions and ideas.
I immediately thought of codebullet when I saw the vid, and was not dissapointed
What if you Split it up into tow algorithms, One that just has the snake take the fastest possible path that doesn't run into itself, and at some point later on when that becomes unsafe(unsure when that would be, probably determined through experimentation) Switch over to the algorithm you showed? That would probably save a substantial amount in the early stages of the game.
Love this idea, was thinking the same thing while watching
The fact that I already knew the Hamiltonian Cycle strategy and used it to beat the game when I first played this game in middle school makes me feel smart af
Please no Hamiltonian cycles, I had enough of that in undergrad
I loved playing Snake Byte on the Apple //e. There were two game plays--the harder one had a bouncing plum that could crash into you. In both game plays, the player had 10 seconds to eat the apple. If that didn't happen, another apple appeared. I think each board required the player to eat 10 apples (aside from any extra that appeared because of the 10-second rule). Successive boards include obstacles that you had to move around. I never beat it, and I have been looking for that game ever since.
You implemented snake game without using python, shame...
I'm just happy not to see that cancer
No body ask you. 😂😂😂
@@sit33darshanpagar16 nobody needed to??? They were just saying that it would be funny if they imported it in python, because, well, snake close to python.
@@Chriva wait, why is python bad?
@@y2kona It's a slow turd that condone bad practices. Guess where people bring those practices once they grow out of that toy? You guessed it, other languages. It truly is a cancer.
Got an idea to speed up the algorithm. No need to have a path ahead that is strictly Hamiltonian. As long as the upcoming path always allows to continue into any path that leads back to the tail you will always be able to reach any point of the board (if Apple appears in an area for which no such path exists, simply follow the tail until it does. Not sure if the snake is quicker but the math behind it seems more simple.
Unreal how much thought and time went into this - and for such a frivolous matter
The easier method would be simply solving P vs NP. 🙂
Just assume P!=NP. Works well enough in practice.
Really fascinating, one of the most interesting aspects is comparing purely algorithmic solutions, machine learning solutions, and "the human way" which is a mix of logic and "intuition", in the sense that we know something is the right move but can't readily explain why. Exactly how our brain manages that is probably the missing step to achieve general AI.
Does this algorithm ever consider the length of its path with respect to its tail? The length of tail that is equivalent to the length of the path to the apple won't matter for finding a new Hamiltonian cycle, it looks like. Avoiding a board split only seems relevant when the apple has been picked up.
no, that would take it out of its hamiltonian cycle. He tried making a "simple formula" that could solve all parts of snake, doing the lenght compared to tail lenght would only work until 30-50% of the board got filled (depending on the shape) and trying to do so in a hamiltonian cycle would take more processing power the longer the snake got. Which is technically what he tried early on where it didn't load anything for 15min during 1 move.
man this is an amazing video and explanation! I learned a lot about algorithms and how to implement them in such a game.
The issue I see is this early/mid algorithm (at around 2/3rds the video length) needs a full and complete hamiltonian cycle, meaning that it will essentially prioritize filling in space compactly over dashing to the apple. I would check to make sure that if it did break the hamiltonian cycle, it makes sure that the cycle it is on has more spaces in it than its actual length. Though, I could see some other problem arising quickly from there during late-game play...
I've got a simple idea...
Have the snake compare the distance to the apple to the distance it's tail needs to move to survive, that way it won't go back to fill in area's it doesn't need to. Half of the game is forcing the apple to spawn near the head so another idea is to calculate the distance traveled to each tile for an apple and make the snake move in a way the apple spawns the fewest moves away as high as possible. Results would be the snake recklessly charging towards the apple in a way that makes the apple likely to spawn fewer tiles away.
How about this idea: FIRST you learn grammar, and THEN you write stuff.
Love the video! But I have to nitpick slightly, specifically the section that starts at 6:17, because the question of whether the snake has a Hamiltonian cycle that reaches the corner (or more generally, can ever go into the corner) is a bit trickier than your answer makes it seem. For your given example, a Hamiltonian cycle exists for both possibilities, but for an AI to 'see' it requires it to have the foresight that while its body currently occupies said Hamiltonian, it will not in a future state when the head crosses. Which is a much more computationally complex route to go when designing an algorithm and obviously not something you want to do, but is still true none-the-less.
I didn't catch that on the first watch, but you make a very good point.
This is the first vid i watch of alpha phoenix
I love the "plan a always goes up in flames" thing
16:00 When machine learning is not sufficient to produce perfect enough solutions the trick is to make the AI responsible of a subroutine and not of the entire decision making. By exemple in your program you have a baseline algorithm on top of which you have added "special cases optimisation" so the idea would be to make all this "special case subroutines" into a generic format for an AI output (like something suggesting several candidate paths in order of preference) that would be validated and selected by the main program. (and as usual AI suggestion are trained based on a criteria to determine to evaluate how they have performed) It would require to rewrite the program to be efficient, because good training would required at the bare minimum 10th of thousands of games. But it definitely would be fun to see how it would crush manually crafted subroutines :p
Code Bullet is fun to watch, but none of his stuff is original. He just finds what gaming AI algorithms are already out there and implements them in an entertaining way. Props to you for researching the theory behind this stuff!
He sounds like Mark Rober when he first started TH-cam
Just a really tiny nitpick: if a problem Π ∈ NP-hard, that actually just means that Π is at least as hard as every problem in NP via polynomial time reductions.
There is a class called EXP-Time (exponential time) which is a superset of NP and (NP ∩ NP-hard) ⊂ EXP-Time (but not a superset of NP-hard).
Problems in Exp-Time actually have the runtime you described in the video but there could be problems in NP-hard that can not be solved in exponential time.
I'd be happy to provide more details if anyone is interested because it is actually a pretty cool topic once you demystify the whole P=NP thing
You confused him even more. His problem is that he doesn't understand the definition of NP (he thinks it means "not polynomial"!), and you didn't state the definition, either! You just added more (unnecessary) information, and you didn't even do a very good job at explaining it. If you actually want to help him rather than confuse him, tell him what NP really means.
6:11 I'm firin mah lazor WAHHHHHHH
I loved math and comp science..but I was in a really bad car wreck and well..lost the ability to go into your field.this was interesting and I'm glad there's people like you out there who like this,my friends always made fun of me lol. Thx God for TH-cam to find like minded people
The Of Grid: How To Win At Snake
Saw Snake AI in title, clicked, thought about CodeBullet, saw CodeBullet in description. Reference to XKCD in first second of video... Went to click "subscribe", already subbed. That was a fast 8 seconds.
2:16 It's probably a bible thing.
I can't really remember when this was recommended to me and I still don't really know how (I'm no programmer, I'm interested in it and was searching up bits about AI), but I do remember just giggling like a young teenager at 3am when 10:31 happened as it clearly shows your frustration in a very practical way😂. Thanks for informing me a bit more about AI.
Now spice things up with a hostile apple-placing algorithm. Although your snake seems pretty fastidious about avoiding traps.
Cool vid! And recognizable thumbnail. First thought was: "Ah Codebullet!"
You sound exactly like Mark Rober
for real
When the snake realises it's closed in I would suggest, from the "entry point" of the closed area, to calculate a few moves ahead to see if a two-cell gap opens up, then build a route inside the closed area, twice as long as the length of the tail beyond the entry point and which is an HC containing the two points of the gap. Then to "plug" into that route, that is, build a path for the snake to get on that route after its midpoint. That's roughly the idea.
.
I mean, the whole point is not to get trapped, so we can build the whole algo off of that. We should compare the outer area cell number with the length of the snake to realize whether we will need to go back into that closed area because the open area has ended. And if the outer area is bigger, we can just run the shortest path to exit from the closed area.
Xpress TV 👊
Eso es todooooo XD
Thanks for letting me know!
"i'm only going be using a couple of [these words] for the rest of this video" had me shout-laughing. Well played.
Yeah I can see how hacking on this could turn addictive
I feel like a 2 step a* would be my solution. First step is finding the path to the apple, second stage checks that a path from the apple to the tail will still be available once it arrives. When building the Path the AI compares steps taken to TailTimeToLive to verify if the tail will exist at that step and would thus be allowed to path through tiles that will open. In the second stage finding a tile set to expire before the apple is collected would be enough to say a survivable path would exist. No clue how performant it would be at the various stages though.
For my own personal use: 10:30
Best moment
I love the Red vs Blue reference xD also, good work figuring this out
The dude got stroke by a question one morning and basically did a PhD on it, just for that you owe my infinite respect.
Ps: About your remark about yourself at the beginning, did you know about MBTI classification ? I swear you're an INTP dude 👍
I think you can improve your algorithm when it calculates how far the tail has to move to make the path short. This means that it calculates multiple scenarios of eventual positions and chooses the fastest one. But this may require processing power we might not have.
This could also solve the issue of doing a long run to not cut the hamiltonian cycle as after a certain amount of time it can reconnect again.
Why do you sound so much like mark rober
Fascinating, as impressive and interesting to watch as Code Bullet!
the amount of times he said "half the board"
👇
2 times
I'm currently writing my own snakeAI and the problem is much more daunting than i thought it would be. I've taken a different approach to you and am trying to make a system where there is a set of rules and as long as all these rules are obeyed, there is a hamiltonian cycle which means no bruteforcing is needed (when i say brute force i mean testing all possibilities) (and its no brute forcing apart from brute forcing the next move out of the