14
Meet Searchy, the Battlesnake powered by Algolia Search
Since I started working at Algolia, I see search everywhere. Naturally, when trying my hand at building a Battlesnake, my first thought was "can I build a snake powered by search?" So, I played mad scientist and built a Battlesnake that uses an Algolia Search index to hunt for food on the board. Her name is Searchy.
The API latency is perfectly fine and she's actually ranked on a couple of leader boards. Here's how I did it.
If you're not familiar with Battlesnake, it's a competitive programming game. Battlesnake builders write code against the pre-defined API and deploy it to an endpoint. The Battlesnake game servers use that endpoint to control the snakes in real time as they attempt to find food, avoid other Battlesnakes, and stay alive as long as possible.
Just like any other microservice, competitors can use whatever language and tech stack they want behind the API, as long it can respond with "up", "down", "left", or "right" within the service level agreement (SLA) response time of the API (typically 500ms).
The most obvious technology to use here is machine learning. Train an algorithm on a pile of games, let it learn the best moves, and set it loose to compete against other snakes. But I started thinking about old school chess programs. Back before the advent of machine learning, the way you built an engine to play chess (or really any turn-based game) was by using tree traversal. Basically, map out all of the possible board representations and then find the best one based on the current board.
I thought perhaps I could do the same for Battlesnake -- generate a collection of boards centered around my snake's head and then traverse them to find the best move based on the current board state received via the API.
For a chess engine, you always start from the same initial position and games proceed proceed from there with openings, middle games, and end games.
For Battlesnake, your snake can start anywhere on the board (which can be of a variable size) and there's really no relation from one board to the next. So I thought it might be better to treat my boards more like radar, with my snake's head at the center and a representation of the surrounding squares to determine where to move next.
Rather than traversing a tree, I could put all of these boards into an Algolia index, then use the search API to quickly find the current board and identify the best next move for Searchy.
Why did tree traversal fall out of favor in the first place? Well, things can quickly get out of hand depending on how far out you want to search. There's about 36 moves per position in one move of a game of chess. There's 400 positions possible after each player's first move, 200,000 after two moves, and nearly 120 million after just three.
The same holds true with Battlesnake. Every square at any time could be empty, contain part of a snake, a wall, or a piece of food. That means if my board snapshot was a three by three grid, there could be 4^9 different combinations (262,144). A five by five grid take us to 4^25, or 1.1 quadrillion combinations. Obviously, this isn't tenable.
So I aimed a bit lower. What if I just represented various combinations of food? Now my boards were base-2 (food or empty) instead of base-4. This reduced the number of combinations significantly! A 3x3 board was now only 512 combinations and a 5x5 grid a reasonable (relatively speaking) 33.5 million. Half of that, actually, if I assume the snake's head is always the center square.
You can find my approach in this github repo. The board generators are written in Python and live in the utilities directory. Running utilities/make_food_plays.py generates all the possible positions for food in a 5x5 matrix (about 16.7 million of them). It then weights the possible moves on each board based on food proximity and how much food is in each quadrant.
for loc, value in enumerate(board):
if value == 'O':
x_diff = loc % board_size
y_diff = loc // board_size
x_weight = head - abs(x_diff - head)
y_weight = head - abs(y_diff - head)
# left
if x_diff < head:
preferred["left"] += 1 + x_weight + y_weight
# right
if x_diff > head:
preferred["right"] += 1 + x_weight + y_weight
# down
if y_diff < head:
preferred["down"] += 1 + x_weight + y_weight
# up
if y_diff > head:
preferred["up"] += 1 + x_weight + y_weight
best_move_score = max(preferred, key=preferred.get)Finally, it creates JSON records of all the boards and uses the Algolia Python client to import the records into an Algolia index.
def update_index(plays: str, index: str = ''):
# Create the index
print("Updating index {}".format(index))
client = SearchClient.create(os.getenv('APP_ID'), os.getenv('API_KEY'))
index = client.init_index(index)
index.clear_objects()
index.save_objects(plays)Once the boards are loaded into an index, I don't have to run this utility again. Searchy makes all game time decisions against the index.
Searchy is built using the Python Starter Snake as a foundation. At game time, I do some quick collision evaluations in server_logic.py, then build a string representing a 5x5 field around her head. I use this string to query the Algolia index in find_boards.py to get the best moves from the list of possible boards. All the "smarts" are in the board generator, so I can work to constantly improve Searchy's vision without putting more drag on these real time queries.
Even at a more reasonable 16.7 million records, using Algolia this way is still suboptimal. This is because I'm treating Algolia more like a database than a search index, bypassing most of the features that make it so powerful. Algolia is designed from the ground up for lightning-fast type-as-you-go, predictive, interactive search. Every aspect of the search engine design leans into this, from prefix matching to how we scale our indices.
Maintaining a large index designed for incredibly fast, as-you-type search is costly. And it's mostly wasted when I'm simply retrieving a complete record (the board) every time.
So at the end of the day, I'm basically towing a trailer with a sports car. You can do it, but it's not the best tool for the job or the best use of your money.
And yet... it works pretty beautifully! Searchy has a consistent latency of about 250ms, well below the required 500ms of the API, and even without much logic around avoiding other snakes, she has maintained a 25% win rate for months. By offloading board decisions to Algolia, I've reduced the amount of real-time code I need to maintain and moved decision making to the asynchronous board generation process.
There's nothing more satisfying than an exercise in stunt coding that creates something surprisingly viable!
I have lots of ideas on where to take Searchy next. I could improve her vision by doing a coarse grain search by averaging food in each quadrant of the board. I'd also like to create a second index for collision detection so everything is pulled via queries, but I'm trying to thoughtful about my number of records/queries.
Obviously the whole thing is a little silly, but I can but feel there are some interesting things around faceting the index to pick strategies, or using geosearch instead of text search that could really make this approach shine.
For now, I'm mostly impressed I can query the result from 16.7 million record Algolia index via API in < 250ms
14