Massive Archive of Games

[xtagon]

Introduction

The Battlesnake engine runs a lot of games -- too many to keep around forever in a permeant archive, I'd imagine! But how many games can be stored?

My first snake logged the full turn request for every game that it was in, and stored each game's history in a database. I wanted to have a history that I could review, run analytics and stats, copy key board positions to test cases, etc. - as I'm sure many snake developers do, in one form or another.

This grew into tens of gigabytes in no time, and I eventually stopped keeping them around permanently. To be fair, my serialization technique could have been improved. With smarter serialization of games, it is feasible to keep a pretty large archive, especially for a single snake (one developer).

In addition, it would be amazing if this could scale to all of Battlesnake, and not just individual developers archives like mine. At one point there was a machine learning dataset for a year's worth of games--how cool would it be to have more datasets like that?

This lead me down a rabbit-hole of figuring out how the store Battlesnake games the most compactly, and I think it can be done.

Overview

A game of Battlesnake can be represented as:

• An identifier for the ruleset and ruleset version (so that the game may be reproduced exactly according to that version of the rules)
• The size of the game board
• Any specific configuration that was used in starting the game besides just the ruleset and board size (if that game mode has any extra parameters when the game started)
• A starting position (snake start positions + initial food positions)
• A stream of deltas that change the game's state at each turn

This is theoretically enough to reproduce the end position and outcome of the game as well as any turns in between, without having to store intermediate state such as full snake bodies for every turn.

For the turn deltas, the move decision for each player must be tracked as well as the new food spawns for that turn as decided by the game engine. Food spawning is random and cannot be determined based on the first turn + snake moves alone (but food eating can).

This is much, much less data to store than full game positions. (How much less exactly depends on how the game progresses, how many turns, number of players, how many are eliminated at each turn, coord size, etc.--I have run some estimates months ago but lost the notes)

Moves

A game move has four variants (Up, Down, Left, or Right) which is only 2 bits of information. In this way, 4 moves can fit into a single byte/octet.

Initially it will be required to store 1 move per snake per turn, but as the game progresses it may be possible to compact it even more by excluding moves for snakes who are eliminated.

To illustrate how this can be done, consider this JavaScript function which will take 4 moves as ints in the range of 0-3 and return an int between 0-255 holding those 4 moves in one byte using bitwise operations:

function encodeQuad(a, b, c, d) {
    return [d, c, b, a].map((x, i) => ((x % 4) << (2 * i))).reduce((acc, x) => acc | x);
}

Because things are done in sets of 4, and using bitwise logic, a proper implementation could do this quicker using SIMD instructions, which operate on groups of values in parallel.

Snake and Food Coordinates

Boards in Battlesnake are typically quite small (standard sizes are 7x7, 11x11, and 19x19 with arena and tournament size usually being 11x11) but it is still possible to have very large board sizes in custom games and in alternative game modes such as Royale.

So for standard (small) board sizes, it may be possible to reduce the number of bits required to represent coordinates for snake and food positions, but there would still need to be a way to represent those larger game boards.

Deltas other than moves and food spawns

In some rulesets, such as Royale, there may be chance events other than food spawning. For example, in Royale mode the hazard zone closes in from a random direction which is only known at the turn on which it happens.

Reproducibility and Integrity

Because the rules of Battlesnake change periodically, this changes how a delta-based representation of a game history might look. So a key part of this storage method would be reproducibility and integrity (need to be able to load an old game, even if the ruleset has changed, and it will be the same as when it was serialized).

Battlesnake rules already have a permanent history recorded in the form of git history. Consider a world in which many of those versions are compiled (either retroactively, or automatically for future versions) into standalone binaries, each one with an incrementing identifier. These could be in Golang or WebAssembly or anything else, as long as they share a standard interface. It is highly likely that there would be multiple languages used over the years by the Battlesnake engine, if we're talking long term.

To store a large archive of games, each ruleset version would be stored separately, to be used to load past games. Remember, this is long-term cold storage, so loading games wouldn't be frequent, it would likely be done in batches for efforts such as analytics or machine learning.

Games could also store a CRC or small hash for validation against a ruleset.

Ruleset Semantic Versioning

Versioning rulesets semantically would mean that fewer ruleset binaries would need to be archived, because a new version only needs to be stored if it is incompatible. Not all version updates will be incompatible. For example, if you were to change the spawn rate, that would be intrinsically reflected in newly serialized games because spawning food at a specific position is a stored event/delta, not a "chance" of spawning food. So in that case, the old version will be compatible.

[xtagon]

I am changing this from Feature Request to Other Ideas, really I just want to see what other people think about it. This would be a big undertaking, but if people think it's worth it, I would like to explore it further. I already have some working proof of concepts for parts of this.

[bvanvugt]

We've always loved this idea!

Conceptually, the major concern is that by releasing a dataset we'd end up with a large amount of ML Battlesnakes that all behave identically -- and, more importantly, that variance in strategy across the community would dramatically decrease. Thinking about the problem from the ground up has historically been one of the best ways to find new competitive advantages, and strategic variance across the community is a clear strength.

I also think that's not a blocker to us doing this, just an aspect that requires careful consideration.

Re: Data Compression

We've thought about this a lot! Currently games are stored as full JSON, similar to what gets sent via API. This is obviously a scaling problem that we're, honestly, always bumping up against ;)

But as you say, we can get things pretty tight with the following changes:

• Store turns as moves, instead of full states
• Strict ruleset versioning and history (already in place)
• Deterministic RNG for food spawn, etc.

The last one is something we'd like to tackle soon'ish -- it would be generally useful in a few other contexts as well (challenges, game rematches, etc).

[InterestingBrainPoops]

the deterministic RNG would have effects further than the storage or replaying of boards, because tree snakes could use the seed along with the correct rng algorithm to finally take into account food spawns

[coreyja]

because tree snakes could use the seed along with the correct rng algorithm to finally take into account food spawns

This is interesting! I kinda like NOT being able to do this in actual game play, cause I think the randomness of food spawns in part of the 'fun' of the game.
But I could see this being very useful for game replay and analysis type of things

So maybe the seed used is NOT something that is included in the payloads that are sent to snakes during the game, but could be retrieved after a game to aid in analysis?

[xtagon]

@InterestingBrainPoops Snakes do not have access to the seed, that would make it exploitable. What I'm suggesting is not to make the seed public, and not to store the seed itself in the stored games, but for the game rules to account for randomness by storing the effects that were decided. So for example if the RNG spawned food at (x, y) on turn t, that information would be stored in the game archive structure.

[InterestingBrainPoops]

@InterestingBrainPoops Snakes do not have access to the seed, that would make it exploitable. What I'm suggesting is not to make the seed public, and not to store the seed itself in the stored games, but for the game rules to account for randomness by storing the effects that were decided. So for example if the RNG spawned food at (x, y) on turn t, that information would be stored in the game archive structure.

So the foods themselves would be stored in the delta?

[xtagon]

So the foods themselves would be stored in the delta?

The events/deltas would be stored. So when a new food is spawned, that is an event that is stored. You wouldn't need to store all food positions for all turns.