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 !
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.
Before this I thought of snake as a simple and charming game from the days of old. Something to bring nostalgia and play endlessly just for some simple good old fun. Now it haunts me as the complicated process of ai that it is. Thank you :)
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.
On the topic of more snake AIs... There is a competitive snake AI programming game called battlesnake. It has a global leaderboard with hundreds of people competing and a lot of them seem to open source their implementation at some point. Granted, it is not an exact match for this video, since battlesnake is a multiplayer game with typically four snake AIs on a single board.
I was designing this twistypuzzle that I started about 10 years ago. Yes, some "distractions" might have crossed my way. When the rendering took waaay to long, I had a quick look at my favorite attention black hole (RUclips) and stumbled across your video. Dammit that cannot be so hard, can it? Hmm let's start with the 1D-problem. Ah got it, now 2D cannot be so much harder... Several hours later I finally had the answer: 4/π-1/2, achievement unlocked - I finally could watch the rest of the video, i.e. everything after 5sec X_x... You are talking about the "perfect" AI, but then you let it play only so many games. Wouldn't the AI be more perfect, if you tolerate it to fail in say 1% of the games whcih on the other hand lets it play far more "risky". This would allow you to dive into a say 20% temporarily enclosed sub-area. The chance of all apples appearing one after the other in the enclosed area is non-zero, yet veeery unlikely. Forget about strict Hamiltonicity. Actually, when allowing for slightly risky play sacrificing perfectly Hamiltonian board cycles you might on average still score better in terms of average steps until won than with your flawless, yet imperfect algorithm. Have a think! ;-)
Most likely the reason that the snake is doing all those unnecessary moves is maybe because it doesnt want to get stuck on its tail so it has to quickly figure out a place to put the rest of the snake without crashing. This may make the gameplay longer but it will be useful. You can see how the snake doesnt die during the gameplay.
Speaking of snakes and AI, have you ever asked AI to draw a snake? Its mindblowing how bad it is lol. Half of them have eyelids and either lizard, or crocodilian heads. Ive never seen a convincing snake from AI. It's honestly really strange how bad it is. Almost like it was an intentional prank. It somehow looks even worse than when kids draw snakes.
2 года назад
Nice job! I would start with Hilbert curves but probably end up like you 😊
have you tried the worker pool in Matlab and used parfor loops? I have found out, that Matlab with parfor runs 3.5 times faster on my workload if I used parfor and an intel chip performs better than an amd one or my MacBook Air m1 chip. But I think snake can't be parallelized. I also use python /w numpy, torch, etc. its very fast and maybe if you convert your code to python it will run much faster and maybe you give ML a try /w Python. ML is perfect for this types of problems, because the parameters are easy to catch and so you can train the nn very good.
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!
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
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.
@@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.
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.
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.
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.
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.
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.
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 !
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
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.
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 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.
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?
F*ck… I don't want to write a snake AI… No… Please… Yes, I'm talking to you, my brain! What do you mean "We do what we must because we can"!? No, I'm not doing it. No. No… Oh no… Help! anyone… please…
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.
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.
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.
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
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.
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
I'm amazed that humans like this exist. The determination and dedication of this individual to achieving a simple goal is mind blowing. Meanwhile I just want to eat, piss, shit, and hit the strip club every now and then. I wish humanity can funnel this intelligence into solving more important challenges, like curing disease, reducing poverty, etc. But at least we get to watch a pixelated snake eat an apple.
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 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!
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.
Why not just code the snake to follow a direct path to the apple avoiding itself till it wraps a size equal to half it's distance to the closest open space where the calculation takes into account only a way in and out of a given space and avoids it while calculating the remaining space in contrast to itself and it's exit(the way in and out that it's left open) then once it has taken any exit route it will then follow your current ai's path, shaving 1/6'th of the unnecessary moves off.
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
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.
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.
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.
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 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 RUclips to find like minded people
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
Yall neeeded an AI to come up with a perfect snake game, you could have just put a snake game bot on twitter and gottan a bunch of people in a discord server to figure out how to finish the game perfectly
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!
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 👍
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.
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 !
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.
Omg, dude! Kudos for your amazing efforts on digging into this topic. Appreciate your work on this⚡️
Before this I thought of snake as a simple and charming game from the days of old. Something to bring nostalgia and play endlessly just for some simple good old fun.
Now it haunts me as the complicated process of ai that it is. Thank you :)
I hope code bullet start to upload again... its been 2 years!
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 of grid” -AlphaPhoenix 2021
On the topic of more snake AIs... There is a competitive snake AI programming game called battlesnake. It has a global leaderboard with hundreds of people competing and a lot of them seem to open source their implementation at some point. Granted, it is not an exact match for this video, since battlesnake is a multiplayer game with typically four snake AIs on a single board.
I was designing this twistypuzzle that I started about 10 years ago. Yes, some "distractions" might have crossed my way. When the rendering took waaay to long, I had a quick look at my favorite attention black hole (RUclips) and stumbled across your video. Dammit that cannot be so hard, can it? Hmm let's start with the 1D-problem. Ah got it, now 2D cannot be so much harder... Several hours later I finally had the answer: 4/π-1/2, achievement unlocked - I finally could watch the rest of the video, i.e. everything after 5sec X_x... You are talking about the "perfect" AI, but then you let it play only so many games. Wouldn't the AI be more perfect, if you tolerate it to fail in say 1% of the games whcih on the other hand lets it play far more "risky". This would allow you to dive into a say 20% temporarily enclosed sub-area. The chance of all apples appearing one after the other in the enclosed area is non-zero, yet veeery unlikely. Forget about strict Hamiltonicity. Actually, when allowing for slightly risky play sacrificing perfectly Hamiltonian board cycles you might on average still score better in terms of average steps until won than with your flawless, yet imperfect algorithm. Have a think! ;-)
I immediately thought of codebullet when I saw the vid, and was not dissapointed
Him: The Hamiltoncity of arbitrary bipartire rectangular grid graphs. You probably don’t know what any of this means.
Me: Hey! I know what “of” means!
2:23 Texas
YEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEHAW
Next generation AI maker
Most likely the reason that the snake is doing all those unnecessary moves is maybe because it doesnt want to get stuck on its tail so it has to quickly figure out a place to put the rest of the snake without crashing. This may make the gameplay longer but it will be useful. You can see how the snake doesnt die during the gameplay.
Speaking of snakes and AI, have you ever asked AI to draw a snake? Its mindblowing how bad it is lol. Half of them have eyelids and either lizard, or crocodilian heads. Ive never seen a convincing snake from AI. It's honestly really strange how bad it is. Almost like it was an intentional prank. It somehow looks even worse than when kids draw snakes.
Nice job!
I would start with Hilbert curves but probably end up like you 😊
have you tried the worker pool in Matlab and used parfor loops? I have found out, that Matlab with parfor runs 3.5 times faster on my workload if I used parfor and an intel chip performs better than an amd one or my MacBook Air m1 chip. But I think snake can't be parallelized. I also use python /w numpy, torch, etc. its very fast and maybe if you convert your code to python it will run much faster and maybe you give ML a try /w Python. ML is perfect for this types of problems, because the parameters are easy to catch and so you can train the nn very good.
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
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
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.
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
This is a childhood fever dream come true
Get lost, another fake channel of Dan
@@RamkrishanYT Dan?
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.
9:35 if that was a speedrun strat it would be called a wormhole
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
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
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.
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.
Your channel logo is brilliant!
yes, so many levels
"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?
Please no Hamiltonian cycles, I had enough of that in undergrad
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
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.
I too believe in ‘The Of Grid’
Wow what a great effort on this video and the algorithmic solutions to games!
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 !
He sounds like Mark Rober when he first started RUclips
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
The easier method would be simply solving P vs NP. 🙂
Just assume P!=NP. Works well enough in practice.
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.
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
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.
Big coding mood when you said your algorithm was great...when it worked. I felt that in my soul lmao
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?
You sound exactly like Mark Rober
for real
Thanks for showing this. Now I can implement it in my professional snake gaming career.
The Of Grid: How To Win At Snake
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.
Xpress TV 👊
Eso es todooooo XD
Thanks for letting me know!
Why does he sound like mark rober? I was confused at the start of the video when I heard his voice
Now spice things up with a hostile apple-placing algorithm. Although your snake seems pretty fastidious about avoiding traps.
Why do you sound so much like mark rober
6:11 I'm firin mah lazor WAHHHHHHH
2:16 It's probably a bible thing.
Would a deeplearning based method work better with enough resources? Or is it totally mathematically optimized now?
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?
F*ck… I don't want to write a snake AI… No… Please… Yes, I'm talking to you, my brain! What do you mean "We do what we must because we can"!? No, I'm not doing it. No. No… Oh no… Help! anyone… please…
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 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.
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.
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
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.
"The hamiltonicity of arbitrary bipartite rectangular grid graphs"
43 seconds in and I can already tell my brain is too small for this.
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
I'm amazed that humans like this exist. The determination and dedication of this individual to achieving a simple goal is mind blowing.
Meanwhile I just want to eat, piss, shit, and hit the strip club every now and then.
I wish humanity can funnel this intelligence into solving more important challenges, like curing disease, reducing poverty, etc.
But at least we get to watch a pixelated snake eat an apple.
It would be super cool to see how much moves snake spends in each mode.
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 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
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.
Yeah I can see how hacking on this could turn addictive
Why not just code the snake to follow a direct path to the apple avoiding itself till it wraps a size equal to half it's distance to the closest open space where the calculation takes into account only a way in and out of a given space and avoids it while calculating the remaining space in contrast to itself and it's exit(the way in and out that it's left open) then once it has taken any exit route it will then follow your current ai's path, shaving 1/6'th of the unnecessary moves off.
That totally looks like something Code Bullet would do.
He did do it XD
@@mono2656 But not for as long or as well.
This guys sounds so much like Mark Rober
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
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.
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.
Reminds me of Theseus navigating the labyrinth with the golden (I think it was gold?) string that was given to him by Ariadne
For my own personal use: 10:30
Best moment
Now I need to see if my old IBM 386 laptop will turn on so I can play Nibbles in Qbasic. The graphics will be amazing on a monochrome LCD monitor.
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.
Has anyone ever told you that you look kinda like Reid Ewing (the actor of Dylan from modern family)?
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 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 RUclips to find like minded people
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
Yall neeeded an AI to come up with a perfect snake game, you could have just put a snake game bot on twitter and gottan a bunch of people in a discord server to figure out how to finish the game perfectly
Amazing work, I really appreciate it
hey, if you do end up finding a non-exponential way to solve the hamiltonicity of a graph, at least you can get a free nobel prize for it
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!
For a moment I was confused like when did I upload a video... Like, looking at your name ...
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 👍
Would it suffice to look for a cycle just larger than the current snake length rather than a hamiltonian
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.
its ironic because you used python to beat snake
the amount of times he said "half the board"
👇
2 times
The moment you realize the whole thumbnail is the snake you understand what kinda of japanese he was speaking in the first 2 minutes
Welp, I have been nerd sniped during exam season.... Farewell GPA lol
Anyone know where code bullet is? Hope he hasn’t gone FPS Russia on us lol