Chronicles of Team Pixel — Part Two

Nathan Mackenzie is a father, hobbyist, passionate full-stack developer, and Battlesnake enthusiast. This is part two of his two-part guest post about his experiences as a Battlesnake participant (part one is available here).

My Goals While Building The Pixelated Snake

  • Stay on the board
  • Eat Food
  • Defense

For this second part, I will discuss each of the steps above and how I accomplished them. Note: There are many ways to implement this, and I decided to recycle some code from Noah Spriggs snake and my original snake.

The pixelated snake source code is here if you want to follow along.

Goal: Stay on the Board

The easiest way I found to do this is to collect all possible moves that Pixelated could move to, ie: up, down, left, right.

Here is some pseudo code to find the available moves:

 # Find the neighbours around a specific coordinate (x,y)
def neighbours(coord):
board_width = 11
board_height = 11
# Create an empty array to store neighbours
neighbours = []
# Check to make sure the cells are actually on the board then add them to your array
if (x_value > 0):
neighbours.append((x_value-1, y_value))
if (x_value[0] < width-1):
neighbours.append((x_value+1, y_value))
if (y_value > 0):
neighbours.append((x_value, y_value-1))
if (y_value < height-1):
neighbours.append((x_value, y_value+1))
# Do one last check to see if any of these neighbours are in your snakes body
return neighbours

With this method in place, I could choose any one of these coordinates to move and they would be safe.

But wait! The response I need to give to the server is one of (“up”, “down”, “left”, “right”) How do I do that? Let’s create another method:

# Takes in a start (snakes head) and a goal (neighbour) and returns the direction
def direction(my_head, my_safe_neighbour):
x = neighbour_x_value — my_head_x_value
y = neighbour_y_value — my_head_y_value
if x == 1:
return ‘right’
elif x == -1:
return ‘left’
elif y == -1:
return ‘up’
elif y == 1:
return ‘down’

The above methods allowed Pixelated to stay on the game board and not run into his own body. If you have questions, head to the Battlesnake slack community.

Acceptable neighboring cells

Goal: Eat Food

Now that we could wander around the board (until we starved) Pixelated needed to find food and go eat it.

A simple way to accomplish this is with a pathfinding algorithm like “A*”. An excellent resource for learning this algorithm is from Stanford University Theory papers, specifically Amits A* pages. I won't go into detail about how the A* algorithm works, I’ll leave the pathfinding research to you.

I used A* because it returned the shortest path to food and I wanted Pixelated to get food quickly.

# Example of an astar call to find food if your health is less than 50
if my_health < 50:
path = (astar(my_head, food))

To recap what we have done so far:

  • We have logic to avoid going off the board and avoiding ourself.
  • We use A* to find food on the board.

Goal: Defense

Tail Chasing

The first defensive move in Battlesnake usually is the classic tail chase. When in doubt find your tail!

To accomplish this we use A* again and set the goal as our tail instead of food and presto, defensive maneuver complete.

Well, complete to a certain degree. In my case, I use it if there is no path to the food or my length is above a threshold.

# Example of an astar call if there is no path to food and your health is higher than 50
if my_health > 50 and not path_to_food:
path_to_tail = (astar(my_head, my_tail))

Avoid Other Snakes

Previous steps assume you are on the board by yourself cruising along and eating food — this is the bread and butter of Battlesnake.

However you cannot just aimlessly slither around the board because there are enemy snakes also on the board. There are many different ways to deal with this, and one is to add a third parameter to your neighbour call and filter out coordinates in enemy snakes as well.

This is the method I chose and it follows along with my map representation which I’ll cover next.

# Example of what my neighbours will look like after the map
def neighbours(coord, what_to_ignore):
# everything remains the same as before with the exception of the last check.
# Instead of just looking for our body or walls we also need to check for other snakes
Snake about to eat

Creating Our Internal Map

In just about every pathfinding paper they discuss map representation. Take a look at this grids / graphs write up its amazing!

  • grids are easy to use
  • they match exactly with a coordinate system

I liked all the examples I read, so I decided to use a grid to represent the game board.

# Quick way to create a grid initialized with all zeros
board = [[0] * board_height for _ in range(board_width)]
# This is the exact same as a nested for loop
# ie
for i in board_height:
for j in board_width:
# Do things

Excellent, we have a grid! Next, we need to decide how we will represent things on the board. I stuck to integers because of some calculations that I do however you can use whatever you like.

Example:

  • safe = 0
  • my_snake = 1
  • enemy_snake = 2
  • food = 3

With these values we can iterate over each enemy snake and mark the cells that match their bodies.

ie board[enemy_body[x]][enemy_body[y]] = 2

Once the grid is updated we can update our neighbours function to accept a new parameter

def neighbours(coord, grid, what_to_ignore ):
# Update the logic in here to ignore bad values if they match the grid
# Example filter method using lambda
# This may look intimidating but all its doing is iterating over our grid and checking that each neighbour isnt in our ignore list
result = filter(lambda p: (grid.get_cell(p) not in ignore_list), result)

Things are now starting to come together by creating the grid we have basically given our snake a brain that we can use to guide it.

Our basic survival instinct is now in place and we can start to focus on more defensive and aggressive logic.

Examples of defensive logic:

  • Checking ahead to see if we can eat safely
  • Finding an enemy tail to follow
  • Growing bigger than other snakes on the board so that we don't die from head to head collisions

Examples of aggressive logic:

  • Look for smaller snakes and eat them
  • Look for choke points to cut off other snakes

Further Optimizations:

There are currently a multitude of optimizations to make including:

  • Additional tie breakers for equal moves
  • Checking more moves ahead for enemy snakes (this was the reason for missing out on first place for 2019).
  • The way my map is setup Pixelated prioritizes kills without looking ahead to make sure its safe which lead to Pixelated’s demise in the final head to head.
  • Weighted grid optimizations.
Sample of a weighted grid. Source — https://www.redblobgames.com/pathfinding/a-star/introduction.html

Development Challenges

The Grid

  • I have gone through multiple iterations of the grid, and in some I had too much information and others I had too little.
  • Finding the right balance for your board representation will have dramatic effects on your snake's actions (I still need to improve this).
  • One example of this is how you are representing safe/unsafe areas.

Pathfinding

  • Pixelated A* has only been enhanced with a tiebreaker so that it will explore less of the grid for finding a path.
  • Finding the right decision in the tiebreaker case is a tough call because in some situations it will enhance pathfinding and others it won't.
  • A* isn't the only pathfinding algorithm, there are many to choose from.
  • Each pathfinding algorithm also has a subset of optimizations as well.

Edge Cases

  • There are so many more edge cases to worry about once you start playing against other snakes, don’t be fooled.
  • Sometimes a fix I implemented broke other logic and produced undesirable results.
  • You won't get them all. Try to deal with the most re-occurring edge cases and not the one-off ones.

Personal

I suffer from chronic pain, PTSD, and partial short term memory loss. Dealing with these on a daily basis is hard enough, Throwing a competition in the mix elevates the difficulty. Regardless, it may have taken me three years of attending to finally feel like I am ready to move up to the next bracket but I made it and I will be ready for Battlesnake 2020.

This is a list of the biggest hurdles I had, there are plenty more minor ones to work on but I felt for informational purposes these would be the ones to focus on.

Looking Back

I definitely made the right choice in taking a step back. Being the runner up allowed me to feel as though I was finally comprehending what I was doing. The event/sponsors and the team that put this all together are absolutely amazing. I can't wait for next year and I’ll be keeping my eyes peeled for similar events in Victoria. ( But we all know this one’s the best! )

Finally

I could not have achieved any of this if it wasn’t for: