BattleSnake2019 - Part 2 Implementation

For this portion I will discuss each of the steps above and how I accomplished those Note - There are many was to implement this I decided to recycle some code from Noah Spriggs snake and my original snake I worked with.

Pixelated repository

Stay on the board

  • The easiest way I found to do this and by far the best way Is to collect all possible moves that Pixelated could move too. Eg ( up, down, left, right )
  • Here is an altered example to find the neighbours with comments and some sudo code:
  # 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? Yep lets create another method like the one below # 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 were the base foundation for Pixelator to stay on the game board and not run into his own body. Of course there are other pieces but for learning purposes Ill leave that to you! Again any questions head to the BattleSnake slack community.

Safe moves

Eat food

  • Now that we could wander around the board randomly and not die (well at least until we starved) Pixelated needed a way to find food and go eat
  • Easiest method and most used is a path-finding algorithm like A_Star.
  • An excellent resource for this is and the documentation that I used to learn about these algorithms is from Stanford University Theory papers specifically Amits A* pages
  • I wont go into detail about the A* algorithm, Ill leave the path-finding research to you
  • For my purposes I did use the A* because it returns the shortest path and Pixelated needed to get to the food fast
  # 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 implemented logic to avoid going off the board and avoiding ourself -> found a way to find food on the board.

Some kind of defense (aka 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 our A* and set the goal as our tail instead of food and presto defensive maneuver complete
  • Well to a certain degree In my case I use it if there is no path to the food or my length is above a thresh-hold
  # 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 a board by yourself cruising along, This step is the bread and butter of BattleSnake
  • You cannot just aimlessly slither around the board. Well you could but probably not ideal
  • There are many different ways to deal with this one would be 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 Ill 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

Creating our map

  • In just about every path-finding paper they discuss map representation
  • Take a look at this grids / graphs write up its amazing
  • 9/10 times a grid is used for a couple of reasons
    • grids are easy to use
    • they match exactly with a coordinate system
  • So like all the examples I have read 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 value we can iterate over each enemy and mark the cells that match their bodies as 2 Pixelated as 1 etc.. 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

Snake about to eat

Our basic survival instinct is now in place and we can focus on either more defense or aggressiveness.

More defensive logic

  • Additional defense that Pixelated uses is:
    • 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

Assertive moves

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

Optimizations

  • There are currently a multitude of optimizations to make including additional tie breakers for paths
  • Checking ahead more currently only implemented for eating
    • 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 Pixelateds demise in the final head to head
  • Grid optimizations - Again have a read through here.

Grid example

Challenges - development

THE GRID

  • I have gone through multiple iterations of the grid in some I had too much information and others I had to little.
  • Finding the right balance for your map representation will be night and day in your snakes actions ( I still need to improve this. )
  • An example would be 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 balance in the tiebreaker is a tough call because in some situations it will enhance path-finding and other it wont
  • A* isn't the only one path-finding there are many to choose from
  • Each path-finding algorithm also has a subset of optimizations as well

Edge cases

  • There are so many and even more pop up when you match up on a board with other snakes
  • Some fixes I have implemented broke other logic and produced undesirable results.
  • You wont get them all try to deal with the most reoccurring ones 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 there 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 BattlseSnake 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 cant wait for next year and I'll be keeping my eyes peeled for similar events in Victoria. ( But we all know this ones the best! )

Finally

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