Perfect Snake AI
An answer to this question on Stack Overflow.
Question
Before reading this question, please note that I use the term AI to describe an algorithm that doesn't learn from it's mistakes, just an algorithm that plays a game in an efficiently and smart way.
After seeing this video a while ago, I decided to make my own snake AI. You can find it here (it is a couple of files, and that's why I don't include them here). This AI was far from perfect and now I wonder what the perfect AI algorithm is for the Snake game. Unlike my version, the original version of Snake doesn't contain walls, but it would be good if your AI algorithm could handle it. Your algorithm has to support multiple sizes of the board, and the food is placed out randomly. With perfect AI, I mean an AI that would collect all the cherries/food without dying, not one that would stay alive for as long enough.
Answer
Finding the perfect algorithm for playing any game is hard!
Consider the game Connect 4. In 1988, Victor Allis proved that under perfect play conditions, white will always win (if a draw doesn't result). His thesis is 91 pages long.
The game snake, as I played it, involves multiple snakes as well as apples and other items that appear for limited amounts of time.
Thanks to Giovanni Viglietta (2013), we know that collectible items and paths that can only be traversed a single time (you can't cross over yourself in snakes) are hallmarks of problems which are NP-hard. Viglietta uses his techniques to show that Boulder Dash, Deflektor, Lemmings, Lode Runner, Mindbender, Pac-Man, Pipe Mania, Prince of Persia, Puzzle Bobble 3, Skweek, Starcraft, and Tron are all hard (in some sense).
I do not know if Snakes falls into this same category, but similarities in its structure (collectible items, temporarily one-time paths) suggest that it might. If so, then there is no efficient (in some sense) algorithm to guide the behaviour of a snake other than a brute-force approach which would be too slow for real-time play.
Therefore, if a perfect algorithm is possible, you should expect the proof of this to be long and complicated. And you should get a Master's degree if you figure it out, which may take about two years.
If the problem is NP-hard, then you're unlikely to like a perfect algorithm and you'll have to abandon your quest in favour of a heuristic or approximate algorithm.