How the snake slithers

When I first started writing my previous entry about Battlesnake I wanted to write a technical deep dive of how my snake worked. However, it didn’t quite turn out that way - I wrote more about general lessons that I had learned while creating my snake rather than the technical details.

For those who are not familiar with Battlesnake, it is an AI programming competition in which developers compete to make the best algorithmically controlled snake. It’s based off of the original snake game but turns it into a battle with multiple snakes vying to be the last one remaining. A detailed rundown of the rules can be found here.

Each move in Battlesnake begins with all active snakes receiving a JSON representation of the current board state. Once the board has been sent by the server every snake has 500 milliseconds to respond with its next move; it can go up, go down, go left, or go right. If a larger snake lands on the same tile as a smaller snake then the smaller snake is eliminated. Snakes must also feed off of randomly generated food pellets on the board. Each time a snake consumes a pellet it becomes one tile longer and if a snake does not consume a pellet once every 100 moves it dies.

In this article I will attempt to break down step-by-step what my snake does every time it makes a move. This is likely to change before the 2020 Battlesnake tournament, but hopefully this can serve as a helpful guide to somebody looking to start a new snake or trying to improve their existing one (which I’ll definitely continue to do).

Overview

Here’s an extremely high level view of what my snake does when it receives the board state. Each step listed below is described in further depth later in the article.

• Set up a framework for scoring data, scan metadata, goroutine execution, and timeout detection
• Recursive scanning and scoring until moves are depleted or time is up
• Evaluate the scoring data and select the highest scoring direction
• Respond to the server

A flowchart of the scanning process - maybe I need to work on my flowchart skills…

Set up the framework for scoring, scan metadata, goroutine execution, and timeout detection

Since my snake is designed to make use of as many processors as possible I’ve made considerable use of goroutines and channels to pass data around.

There is a for/select block that polls four different channels related to movement - each channel corresponds to a direction that the snake can go from its current place on the board. These channels receive this data whenever a lookahead move is completed:

type ChannelScoreValue struct {
	Depth                     int
	Score                     float64
	Coord                     Coord
	ScoredCoord               ScoredCoord
	PlayerSnakeHealth         int
	PreviousChannelScoreValue *ChannelScoreValue
	DeepestActiveScan         int
	IsDeadEnd                 bool
}

Coord contains the x and y coordinates for the current move. ScoredCoord has detailed data for the coordinate such as the type of tile, the score of that tile, and data about any snake that might be occupying the tile.

The above data is passed into a multi-dimensional slice that uses the first dimension to store the depth of the move and the other dimension is used to store the above data. This is later used to find the highest scoring move for that direction.

There is also a scan metadata channel in the for/select that is used to maintain a scheduler that executes the goroutines for deeper scans:

type ChannelScanUpdate struct {
	Depth    int
	ScanFunc func()
	IsTimeUp bool
}

type ScanData struct {
	IsTimeUp          bool
	DeepestActiveScan int
	ScanFuncs         [30][]func()
	LastUpdate        time.Time
}

Previously I had my recursive scoring functions fire off goroutines whenever they needed in order to scan deeper and deeper. This approach didn’t allow for quick termination, so it didn’t work well with making my endpoint scan as much as possible within a strict timeframe. Sometimes the large number of goroutines being executed at the same time would cause my endpoint to take up to 800ms to respond to the server, which is registered as ‘no response’ and can often result in death.

I tried several approaches to get around this, including keeping track of the scoring metadata to tell certain depths to hold off on executing the next level of goroutines until the other directions caught up. That worked a bit better than letting everything go wild, but was still fraught with its fair share of issues. I would still have occasional timeouts and I couldn’t help but feel that the code wasn’t as efficient as it could be.

I ended up implementing a system in where a separate goroutine monitors the number of active goroutines. This goroutine polls the ScanFuncs in ScanData (which are supplied through updates to ChannelScanUpdate) and executes the function in the lowest array value when the number of running goroutines falls under a certain level. This has multiple advantages: the lowest depth scans are always prioritized, making it so that one direction doesn’t take all of the lookahead time, and executing the goroutines on a tightly controlled basis allows us to exit quickly when the timeout happens.

Now that we’ve taken a look at how the main function of the program will be receiving and processing data let’s take a look at how the data is actually generated.

A high level view of the scanning and scoring function

Once the channel listeners are set up the snake checks all directions to see which moves are valid - if a move goes off the board or hits a snake’s body then it is not a valid move. There are also a few extra checks checked by a function named IsValidMove which mostly involve checking that the snake will be able to ‘fit’ into the direction (aka won’t become trapped) and handling some edge cases for the early game where the snake isn’t fully extended. (Tail logic is a little more complex than it seems at first glance.)

If the move is valid then a recursive function called GetDeepScores is called using a goroutine and provided with the current board data and a ChannelScoreValue channel specific to the direction. Once the score has been computed the ChannelScoreValue channel is sent the data. GetDeepScores is a recursive function, so once the function is complete checks the next four directions for valid moves and then sends a reference to a GetDeepScores function to the ScanData channel for each valid direction, effectively adding that move into the scan queue. This cycle continues until there are no more valid moves for this direction or the timeout is hit.

The logic within GetDeepScores roughly follows this outline:

• Move the targeted snake into its new location
• Score and sum enemy snake moves
• Generate a map of the player’s board
• Score the map of the player’s board
• Emit scoring data to channel
• Fire off new goroutines to start scanning all valid moves for the next depth

Although it looks like Spot has an easy meal to the right it’s dangerous, so he should go down

Making the map

In order to score the current layout of the board we need to transfer the JSON data into something that makes a bit more sense for evaluating the snake’s options. I create a multi-dimensional slice that uses a typical [x][y] layout to represent the board. Each space on the board is represented by this type:

type ScoredCoord struct {
	Type    CoordType
	ID      string
	Score   float64
	Scanned bool

	IsBiggerOrEqualSnake bool
	SnakeHealth          int
	SnakeCouldHaveDied   bool
}

Each Type has a corresponding Score that can vary depending on the snake’s state. Food is scored high when a snake is ‘hungry’, lower when it is not. Larger snake heads have a lower (or even negative) score compared to the high score of smaller snake heads. Snake bodies are never scored highly, as they represent the hazard of becoming trapped. As stated earlier, Scores can vary depending on the context of the Type (as seen with food and the idea of the snake being ‘hungry’ or not).

Once the slices have been created and the empty board is set up food is added, which is relatively simple. After the food is added then any enemy snakes are added to the board map - according to my benchmarks this is where a large amount of processing time is spent!

While it may seem like placing snakes on the board would be quick it’s important to consider that with each depth scan the number of enemy snakes being evaluated has the opportunity to grow exponentially. A single enemy snake is moved into up to 3 possible positions with the first scan, 9 possible with the second, 27 with the third, 81 with the fourth, etc.

When enemy snakes are added to the board there are a number of checks to ensure that smaller snake heads do not overwrite larger snake heads, that food is updated if there is the potential for there to be a snake head on it, and that a snake’s tail is treated as part of its body if its health is full (this is done as if a snake eats then its tail does not change position the next move - they have grown one tile larger).

I also record whether the snake on the tile is bigger or equal in size, its current health, and whether it could have died in a previous lookahead move. These are used in later scoring calculations to determine potential risk.

Evaluating the map

Now that we have a easily traversed version of the board state, we need a way to evaluate it. This is where ScanSector comes in - it’s a recursive summing function that takes the board map and scans the provided x and y coordinates from the perspective of the provided snake in order to return a numeric score of what that area of the board is currently worth to the provided snake.

ScanSector uses a flood-fill algorithm to determine what tiles on the board are currently available to the player snake. If it detects an invalid move or tile that has already been scanned it returns, otherwise it will grab the score placed onto the tile by our earlier map making function and add it to the sum before calling all other possible directions.

It’s a pretty simple function and not much exciting happens in it, but it’s pivotal in evaluating the board state. I had tinkered with the idea of having each scan away from the first coordinate be worth less than the last, but this didn’t accomplish much. I thought it would be helpful to have objects closer to the player snake be worth more, but actually simulating the upcoming moves proved to be far more valuable.

Once the scan has completed the sum is modified according to whether the snake should attack or feed, the enemy snake in the target could have died in a previous move, the sector is too small for the snake to fit in, and whether a move has the potential to remove the last enemy snake from the board.

Adding it all together

Once the snake has run out of moves to score or has hit the time limit it looks at the direction based arrays of ChannelScoreValues that have been being saved into a multi-dimensional slice by the direction based channel listeners.

These arrays are evaluated by starting at the deepest level and reverse tree walking up from there, adding the value of each node to a sum that is subsequently added to an array that will be used to find the series of moves that score the highest for this direction. Once all branches of the tree have been walked the highest scoring value is returned from the function.

There are a number of modifiers applied as the tree is walked for each possible series of moves, including whether the branch has a hazard, a bigger or equal snake head with food, whether it ends with a dead end, or if the snake runs out of health.

This all happens quite quickly thanks to the ChannelScoreValue struct being arranged in a one way linked-list fashion, allowing the values to be quickly traversed. And in the same of concurrency friendliness each direction that is being scored is done so in its own goroutine.

Once all scoring goroutines have completed then their results are compared. The highest value is chosen and the snake responds to the server with the direction that corresponds to that value.

Conclusion

Hopefully this has been helpful in one way or another and helps to give some ideas on how you can create a high performance snake. (And I hope that I don’t shoot myself in the foot by sharing my strategies!)

Hope to see you at Battlesnake Victoria 2020!