Writing computer programs to play snake is very interesting! Here's an overview, which I have many thoughts on including a straightforwardly implementable clear improvement (thread)
A much algorithm thing which works by dividing the board into 2x2 cells which makes calculation easier for reasons is here github.com/twanvl/snake/
The inefficiencies added by the limitation to cells are extremely small and not really worth discussing, there are vastly larger optimizations to be had for much less effort and risk.
When improving something step 1 is always debugging. Here's a situation in which it fails to fill out a region which appears to be an outright bug
Bugs aside and looking at strategy, hugging the walls matters A LOT. If you go directly for the apple you can cut the board in half forcing yourself to go around your whole length to get an apple in the future or even worse having to kill time filling a whole half
Here's a situation in which it goes straight for the apple which is a clear error. It would have had to spend very little time hugging the bottom which would have avoiding having to fill the bottom region immediately after
And here's another one with an even bigger region
In terms of things which it's overlooking it sometimes maneuvers to work around tail which will be gone by the time it matters. For example here it could hug the wall and by the time it gets to the apple the problematic part of the tail will be gone
And here's a similar situation
Handling these things properly in the general case seems to involve deep planning and is highly nontrivial, but I promised you a clear improvement so here it is:
Parts of the tail which you couldn't stomp on even if you headed towards them as the crow flies can be safely virtually trimmed and you can plan out as if they aren't there. This is simple to implement and leads to clearly better behavior in some situations
For example in this situation if it were trimming it would realize that hugging the wall on the left isn't a thing and hugging the right is clearly the way to go
And finally another thing which looks like a bug: Here it was hugging the wall, then decided to go straight for the apple, then realized that was stupid and decided to turn around and hug the wall again with nothing changing
Share this Scrolly Tale with your friends.
A Scrolly Tale is a new way to read Twitter threads with a more visually immersive experience.
Discover more beautiful Scrolly Tales like this.