The snake was travelling down the left side of the screen when it got to a food item. The next food item was generated on the other side. A cursory glance at this static image would indicate that there is no clear, unblocked path from the snake to that point. This is what makes it an "impossible" situation.
In the game of snake however, this situation is actually easily solvable. The parts of the snake blocking the way will move themselves out of the way if given enough time. The snake can move in the open space beside where it is currently moving until that time. The snake has a length of 81 and there are at least 95 spaces next to it. Those could be utilized to get it out of the bad situation.
There is some problem in the AI algorithm that prevents it from considering this more complex, but optimal path.
My guess is that it has something to do with how we track visited tiles. It seems that the view of what has been visited (and therefore needs to be skipped) is a static view of the game. It does not correctly model that tiles that have been already visited may become viable again once the game shifts.
This check is still imperative however, since there needs to be a way to exhaust the search and not search down paths searched before.
Perhaps there is a way to track visited situations rather than visited tiles. A situation being the exact state and orientation of the snake for a given goal. That means tracking the cost for a given path that the snake might take and being able to look that up in order to avoid calculating the cost of a given path more than once. This should accurately model the dynamic nature of this problem while accounting for the fact that most paths are the same. It is necessary to hash the entire body of the snake as that affects the path that can be taken in that situation.
The main insight to take away from this is that tiles are not the same as situations. By guarding against and skipping already seen tiles, we are missing out on possibly favorable situations.
Take the following situation as an example:
The snake was travelling down the left side of the screen when it got to a food item. The next food item was generated on the other side. A cursory glance at this static image would indicate that there is no clear, unblocked path from the snake to that point. This is what makes it an "impossible" situation.
In the game of snake however, this situation is actually easily solvable. The parts of the snake blocking the way will move themselves out of the way if given enough time. The snake can move in the open space beside where it is currently moving until that time. The snake has a length of 81 and there are at least 95 spaces next to it. Those could be utilized to get it out of the bad situation.
There is some problem in the AI algorithm that prevents it from considering this more complex, but optimal path.
My guess is that it has something to do with how we track visited tiles. It seems that the view of what has been visited (and therefore needs to be skipped) is a static view of the game. It does not correctly model that tiles that have been already visited may become viable again once the game shifts.
This check is still imperative however, since there needs to be a way to exhaust the search and not search down paths searched before.
Perhaps there is a way to track visited situations rather than visited tiles. A situation being the exact state and orientation of the snake for a given goal. That means tracking the cost for a given path that the snake might take and being able to look that up in order to avoid calculating the cost of a given path more than once. This should accurately model the dynamic nature of this problem while accounting for the fact that most paths are the same. It is necessary to hash the entire body of the snake as that affects the path that can be taken in that situation.
The main insight to take away from this is that tiles are not the same as situations. By guarding against and skipping already seen tiles, we are missing out on possibly favorable situations.