https://cdn.sanity.io/images/sb4bkg44/production/520536acccdf0ca8f22cf1cd3fce91ae9b540a70-145x32.svg

Redbrick sponsors the return of TEDxVictoriaRead More

Community

BattleSnake 2018: A Retrospective

https://cdn.sanity.io/images/sb4bkg44/production/13b5fb51dfbf939bc71c4481e7d11c93013a6643-96x96.png?q=75&fit=clip&auto=format
Redbrick
Mar 13, 2018
Link copied to clipboard
share

It was Redbrick’s third year sponsoring BattleSnake – an artificial intelligence programming competition held every year in our hometown of Victoria, BC, Canada and organized by our friends at Sendwithus.

The contest works like this: your objective is to write a program that plays the classic arcade game Snake. Your “snake” is placed on a board with other snakes, and the last snake slithering wins the round. With three divisions (beginner, intermediate, and expert) and cash prizes for the top three winners of each division, the competition is fierce.

As we were defending champions, the stakes were especially high for Redbrick’s teams this year. Could we pull off another victory? We brought four snakes to the Expert division this year, plus a Bounty Snake:

Unfortunately, we were unable to repeat last year’s success, with each of our snakes falling in the first round. Just like last year, each of our teams has offered to share some information about their strategy and design process: Queen B This snake is a ‘local search’ snake that considers a large number of situations (no predictions on what other snakes are going to do).

During development, we opted to use a variety of configuration variables so that we could easily modify it to face different bounty snakes. To help make sure this type of approach would work we created a set of static tests and dockerized several ‘test’ snakes. These helped a lot to ensure that future changes did not break the existing code. Linting was also run periodically. For the day of the competition, this was deployed to an instance in AWS (uwsgi and nginx). Seeing as we don’t do any lookahead, we didn’t need a large instance and we were responding within ~50ms on average. General Flow of Code:

  1. Gather data then setup board by freeing up spaces and finding ‘bad_positions’ we don’t want to move in to (using floodfills and other logic).
  2. Determine if we are ‘boxed in’ by judging immediate available space.
  3. Determine if we have the opportunity to kill a snake (head to head and tunnel closing). We did not seek out these opportunities.
  4. Determine which food (if any) we want to get.
  5. Do the following in order (skip a step if we determined we didn’t want to do it or found a move in a previous step).
    1. Attacking logic (unless we really need to prioritize food).
    2. Boxed in logic (find an exit then determine the longest path).
    3. Food logic (bfs to predetermined food).
    4. Find ‘safe_spots’ on the board by rating cells and path to the one that has the best rating/best route.
  6. If for some reason we still don’t have a move (caught an error or all moves are relatively bad) do a series of floodfills to determine our best option.

RUTHLESS Ahh, RUTHLESS. Such a disappointment. Contrary to what the name suggests, RUTHLESS is a tail-chasing “scaredy snake.” In a former life, RUTHLESS was known as “The Battle Constrictor,” a bounty snake from the empire of Workday. However, during late spring 2017, high atop Trump Tower in NYC, The Battle Constrictor molted and RUTHLESS began to emerge. Internally RUTHLESS uses the A* search algorithm to seek food, enemy heads, and its tail. Search results are collected and scored based on game conditions.

For example, if the snake is hungry, paths that do not lead to food are penalized. After all of the penalties and discounts have been applied, the result with the lowest cost is selected. If no path to a goal can be found, RUTHLESS falls back to a “largest space” algorithm. Each possible move is examined, and the one with the largest contiguous space is selected. There are two modes for evaluating the space size: pessimistic and optimistic. The pessimistic mode assumes that nodes next to the heads of enemy snakes are not safe to travel.

The optimistic mode removes that constraint. It is safer to be pessimistic, so that mode is attempted first and RUTHLESS only falls back to the optimistic mode if a pessimistic evaluation of space size fails to find an area it can fit into. Both modes attempt to look-ahead and trim the tails of snakes to find openings that should appear N-moves into the future. This tail trimming technique is also applied to the A* search. When finding paths to goals the length of the current route is used to trim tails. This improves the efficiency of paths and increases the likelihood of finding valid paths to goals.

To reduce the risk of being trapped, a heuristic is applied to each node in the generated route. The heuristic raises the cost of nodes that are close to walls or snakes which causes RUTHLESS to plot longer, safer paths. The eating habits of RUTHLESS also warrant some explanation. It is always trying to be the closest snake to a piece of food. This is called ‘food advantage.’ If it does not have food advantage, it will identify the most available piece food and chase it.

Once RUTHLESS has secured food advantage, it waits until it is hungry to eat. If health gets too low, or the path to the nearest piece of food would consume >60% of health, it enters a reckless mode. In reckless mode, results that were previously eliminated for being too dangerous are re-introduced, and the A* heuristic is disabled in an attempt to find shorter paths to food. Shiffany Shiffany was designed to be a passive snake with the main objective of surviving the longest amongst all the other snakes on the game board. The code was written keeping this primary objective in mind. The approach used by Shiffany was as follows:

  1. Check if you are at a corner, because if you are, then you will only have one viable move—make that move.
  2. Compute the path to both your tail and the closest piece of food on the board.
  3. If you are hungry and there exists a path to the closest piece of food, make the best move to get closer to the food.
  4. If you are not hungry or there doesn’t currently exist a path to the food, check to see if there is a path to your tail, if there is, then make the best move to get closer to your tail.
  5. If there isn’t a path to your tail, make a move in the direction with the most “promise.”

Algorithms and strategies used by Shiffany:

  1. A* search: used to compute an efficient directed path from your current head location to the nearest piece of food, and also to your tail.
  2. Flood fill: used to compute the amount of “promise” moving in a particular direction presents you with – both of the entire board and also a limited number of squares accessible from your head.
  3. Tail trimming: under certain circumstances, there may not be a path to your tail; however, there may be a path to an enemy snake’s tail. To avoid getting stuck, you can mark the squares where the enemy’s body is as walkable if, by the time you reach that square, the snake’s body would have disappeared from that location.
  4. Appending fake heads: one of Shiffany’s secret weapons. Every snake gets fake heads appended in every direction it could move. The flood fill takes these fake heads into account, helping you avoid dangerous wall death situations and getting yourself stuck.
https://cdn.sanity.io/images/sb4bkg44/production/06d2240ef423234283d9829b6c3f10051ea4ffe5-640x335.png?q=75&fit=clip&auto=format

Thief Snake The Thief Snake has an interesting history. Some time was spent creating a testing framework that could hit snake endpoints with a specific board situation, and expect a certain move back. Many of these involved life or death situations where if you make the wrong choice, you’re guaranteed to die at some point within the next few moves. After a good number of these tests were created, the Thief Snake was born.

The code from RUTHLESS was forked, and many changes were made to make sure the Thief Snake could pass the tests. These changes involved a custom floodfill that would begin by blocking out extra spaces (any possible moves of enemy snakes), but if that couldn’t find any good moves, it would run again for each of your possible moves without the extra spaces blocked. Otherwise, multiple additional checks were added to avoid dangerous moves that were covered by the test cases.

The Thief also tries to eat food more aggressively during the first 250 turns. This is because early in the game when it is likely there are more snakes alive, starvation is more of an issue if there isn’t a lot of food on the board. Afterward, the Thief is more conservative, mostly tail chasing until it begins to get low on health. The main functionality in this situation was already in the base snake when Thief was forked, which involved making sure you are closer to food than other snakes, and if you feel confident that nobody is going to eat your food, don’t grab it until you are quite low on health.

The only tweak to this functionality was to make the Thief Snake favor food a bit more than the original snake, to avoid tail chasing too far away from food.

Son of Robosnake A derivative of the original Robosnake, Son of Robosnake was Redbrick’s official sponsor snake / Bounty snake for 2018. Bounty snakes are handled differently than standard snakes – each sponsor comes up with a set of conditions for defeating their bounty snake, and if those conditions are met by a tournament snake, the winning team may lay claim to a bounty put up by the sponsor. These battles take place one-on-one at the sponsors’ booths before the tournament. We had multiple bounties this year. The first ten people to defeat Robo at our booth had the opportunity to pick from the following:

  • Portable solar charger
  • Wireless waterproof speaker
  • 2 x Mobile power charger
  • 5 in 1 Universal lens kit for a phone camera
  • Various board/card games:
    • What Do You Meme?
    • Uno – Super Mario Edition
    • Joking Hazard
    • Apples to Apples party box
    • Exploding Kittens

In addition, everyone who defeated Robo was entered into a draw to win our grand prize: a one-year Advanced subscription to our SaaS workflow management software Shift for each member of their team. Robo managed to go 71-3 this year, the three snakes that beat us were:

New this year was the Bounty Snake tournament bracket, in which all of the sponsor snakes were placed together in one grand match-up. And while we managed a beautiful kill against GiftBit’s snake, our algorithm (designed for one-on-one battles) couldn’t handle being in close proximity to multiple snakes at once, and we fell to a head-on collision from Sendwithus’ snake.

For those who want to know more about Robo’s overall design and strategy, watch this space for a technical overview, coming in a few days. You can read about the design of last year’s Robosnake while you wait ? Once again we’d like to extend our thanks to Sendwithus and everyone else involved with organizing and sponsoring this wonderful event! Watch for our return in 2019!