Battlesnake 2019 — What I Learned
This was my first Battlesnake competition. If fact it was the first coding competition I was ever apart of. I ended up competing in the intermediate category. Originally I was going to compete in the expert category, but after speaking with a few people who competed in the expert category previously I decided against it as I didn’t think my snake would be up for the challenge.
Here is my thought process while programming my snake.
1. Choose a programming language
After looking at the API I decided on picking Node.js as the language I would use. I chose this for two reasons:
· I had recently worked with a company that used Node.js to build a web app so I was familiar enough with it.
· I wanted to learn Node.js better.
2. Don’t die
My first few methods were figuring out the best way to parse the data I had. From this my goal was to avoid hitting any walls. Then afterwards, not to run into myself or anyone else.
3. Find food
I then wanted to find out the best way to obtain food. My goal was to simply take the shortest path to the closest food. I used breadth first search for this. The more challenging part was making sure that getting this food wouldn’t trap me in a corner or cause me to be eaten by another snake.
To solve this I predicted my future self. I did this by placing my snake in position it would be in when it grabbed the food. I then used breadth first search again to see if I could reach different points of interest (such as another food or snake’s tail). If I couldn’t I concluded that eating the food would place me in a corner I couldn’t get out of.
While this solution worked it also had an unintended side effect. There were times when my snake would dance around or completely avoid eligible food. This was because it couldn’t reach any points of interest as they were all blocked.
4. Longest path
Another goal I had was to find the longest given path I could take. This would help me to get out of tight situations. I soon realized this was an NP Hard problem. Given that I only had 250ms using this method could be potentially dangerous. After some testing I realized that finding the longest path in even a 7x7 grid could take upwards of 8 seconds. Way too long. I figured I could use this algorithm when I got into smaller spaces, however I ended up putting this on hold as I couldn’t get the method to work the way I needed.
5. Fine tuning
The next task for me was to figure out what I wanted to do when. I had a vague strategy from the beginning, but it was having to change slightly due to the longest path problem not working out as I expected. My goal was to hoard as much food as I could. Thus getting as large as I could and potentially starving out other snakes. Also, if you’re the largest snake you never have to worry about being eaten and can eat others in the race for food.
I added some logic to prevent my snake from going into areas where larger snakes were. I also followed my tail for a bit when I sensed immediate danger (such as a larger snake nearby).
One of the challenges I came across was in using Node.js. It had two problems that I ran into.
It’s not immediately an immutable language
There was a few times when data was being altered without me realizing it. After some research I realized I was unknowingly changing the data. I looked at deep cloning objects in order to prevent this, however I found this to be incredibly slow. It was actually much faster to rebuild parts of the object than it was to clone them. Once I figured this out it became more of a hassle than a problem. I just had to be very careful and test what I was doing often.
Classes not having multiple constructors.
The second issue I had was I wanted to instantiate a class with different types of variables. In JS however you can only have one constructor per class. This was and still is a large annoyance. I ended up having to creating a duplicate class in order to solve this. I looked at using optional parameters, but it was too messy and cumbersome.
At one point I looked at switching over to Python. I decided against it however because I was not familiar with getting Python up and running. Also, from the small amount of research (Google) I did it appeared that Node.js was considerably faster.
Changes to the rules
The other challenge I ran into was out of my control. A few times just weeks before the competition the rules had changed. This meant that some of my code needed to be adjusted and reworked. There were two major adjustments that effected me the most.
First, the order in which a snake would move. Originally the head would move and then the tail would follow. The rules was changed to the tail would move and then the head would move. This change meant you could follow your tail without there being a gab. It also meant all of the code that had been written to avoid hitting your tail was obsolete. I now had to change a few methods to allow for the possibility of following a snakes tail.
Second, how the snake reacted after eating food. Originally when the snake ate a food its tail wouldn’t shrink. The rule was changed so that the tail still did shrink, however two tails spots would be pushed into the new tail coordinate. Then the next turn the tail would remain.
This was a major adjustment in terms of how algorithms worked. I had just rewritten my algorithms so my snake could follow my own other other snakes tails. This change meant I had to add a check to every algorithm to see if a snake had two segments in the same position and to act accordingly.
What I learned and would do differently
I learned a lot about Node.js. I learned that the language can be incredibly frustrating to work with and in some cases inconsistent. It is also incredibly fast. I was able to run the breadth first search algorithm at least a dozen times without even reaching 50ms. My knowledge of using Git grew a lot as well as I was constantly using it.
One of the things I would do differently is probably merge a number of the methods together. Shortly before the competition I realized that a lot of my methods did enough similar things that it would have make sense to merge them. This would have made debugging and testing faster and easier.
I also wish I had been able to properly implement the longest path problem. It it would have helped during the competition.
This competition was a lot of fun and I look forward to it next year.