November 21, 2020

884 words 5 mins read

Battlesnake: The Rusty Tapeworm Cronicles

Battlesnake: The Rusty Tapeworm Cronicles

Battlesnake is simple. Take the game of snake, make it multiplayer, but instead of controlling the snake yourself, the snake is controlled by an AI programmed by you.

Battlesnake Saskatchewan is a competition put on by Battlesnake, in partnership with HACKREGINA, Innovation Saskatchewan and SaskInteractive, that ran from November 7th - November 21st of 2020. Programmers of all skill levels had two weeks to program an AI snake, enter it into the arena ladder, and compete in a tournament streamed live on Twitch.tv.

Day to-day I primarily write software in Typescript and node.js, but I’ll use hackathons as an excuse to learn a new technology. I also figured that javascript would perform too slow (we only had 500ms to make a decision). I decided to check out rust because it was StackOverflow’s most desired language of 2020, and my roommate Patrick had hyped it up.

Challenges

Rust

Rust is hard. I consider myself a fairly competent software developer. I’ve done this for over a decade. But rust was unlike anything I have ever used before. The syntax was python-level clean with assembly-level complexity. The concept of borrowing references and memory reference lifetime still goes over my head. Swift introduced me to the concept of Optionals in my past role as an iOS developer, which was helpful, although I still struggled with them.

I can’t figure out how this is the most desired programming language on StackOverflow. However, after a couple of days of practice I started to feel more comfortable with the language, but more work must be done.

Veteran Division

I opted for the veteran division. I’m not one for sandbagging. If you want to be the best, you have to compete with the best. I knew I would be going up against some elite snakes, but I figured that I could make the best Saskatchewan snake in the two week window.

Chess Notation

Beth Harmon: “The squares have names?”
Mr Shaibel: “They do if you’re any good.”

I found the easiest way to debug and recreate conditions to test was representing the grid in chess notation. I haven’t seen any other snake-devs use this notation but it helped me out quite a bit.

Here is a 7x7 grid.

a7 b7 c7 d7 e7 f7 g7
MH MB c6 d6 ++ f6 g6
a5 MB c5 d5 e5 f5 g5
a4 MB c4 d4 e4 f4 g4
a3 MB c3 d3 e3 f3 g3
a2 MB c2 d2 e2 f2 g2
MT MB ++ d1 e1 f1 g1

MH, My Head, is in the A6 postion. “++” indicate food positions. MT, My Tail, is in A1.

  • This made it easier to logically break down sequences: C5 to D5 vs (2,4) to (3,4).
  • Easier to read log files
  • Writing tests was faster: new Pos('a1') vs. new Pos({x: 0; y:0 })

Strategy

So how does Rusty work?

He uses a greedy best-first tree search. I tried out Dijkstra’s algorithm at first but found that to be too inneficient.

Rusty is always hungry. His number one goal is to eat. Long length equals strength. However, any food he eats must have a safe path back to his tail. If Rusty finds himself in danger, with no safe food targets, or just completely confused, he will default to following his own tail. Should his tail be unreachable, then he will follow the closest enemy snake’s tail. Should that fail, he goes into full-on panic mode. A last ditch effort and travels to the next safest cell (if possible).

This simple strategy worked pretty well. I worried that not “thinking ahead” like some of the other veteran snakes would be a significant handicap, but Rusty held his own.

Deployment

Rusty lives in AWS in the us-west-2 region. That is where the Battlesnake servers are, and the reason for his incredibly low latency of sub 5 milliseconds.

I am using the Elastic Beanstalk service with a t2.small instance. Slightly overkill (the container service would have sufficed, a t2.micro probably too) but I’ve been using the Beanstalk for a few years now and quite comfortable operating it. There, Rusty runs in an unreasonably small Docker container (8mb!!) thanks Rust!

Result

I am quite proud of how The Rusty tapeworm did on the ladder. Out of the entire Veteran division, Rusty landed at the top of the ladder… compared to other Saskatchewan snakes. He managed to take a few games off of the more established snakes here and there but not consistently enough to jump up too high on the ladder.

When it came time for the tournament, old Rusty crumbled. In the only two games he played, he made elementary mistakes. However, Rusty was a crowd favourite. His tagline: “Long Length = Strength” definitely made an impression on the Twitch casters and chat.

Rusty the #1 Saskatchewan Snake
The Best of the Worst

Rusty the #1 Saskatchewan Snake

Next Steps

I’ll be taking a few weeks off of Battlesnake, I need to continue working on my Traffic Puzzle game in Unreal Engine, and World of Warcraft: Shadowlands launches pretty soon so I imagine I’ll be sinking a good chunk of my free time into that.

I plan to turn Rusty into a full on logic-based AI snake. He will use Rust’s performance benefits to his full potential and think hundreds of moves ahead.

To be continued.