Imperfect Information RFC -- Battlesnake Flashlight Tag

[coreyja]

The purpose of this document is to propose a new feature to Battlesnake, and allow it to be played as an imperfect information game.

The proposed new game type involved allowing Snakes too ONLY see things within 5 game spaces from the head of their snake.
The working title for this game mode is “Flashlight Tag”

Background

Perfect vs Imperfect Information

Battlesnake has historically been a “perfect” information game. This means that each snake has the full information about the game state. Each player knows where each snake is, where the food is and where any hazard squares might be.

This makes Battlesnake easy to understand as you get started!

But for developers looking for an additional challenge, an “imperfect” information game mode opens up new ideas and possibilities.
If your snake is only able to see a few squares around its head, new strategies are expected to be explored!

Stateful Snakes

In particular, the Battlesnake Team believes an imperfect information game mode will encourage more “stateful” snakes, that remember information from one turn to the next.

In “traditional” perfect information Battlesnake, you can be very competitive without storing any state from turn to turn, since each turn you get the full information of the game board.

The introduction of an imperfect information game mode seems like it will increase the advantage of being able to store state between turns.

Battlesnake is all about teaching developers valuable skills while they build snakes, and high performance ‘local state’ is an awesome thing we can help developers gain exposure too.

Examples

Yannik and others from University of Hannover have been working on an imperfect information game mode for use in their AI classes!

You can see an example game played with one such imperfect information game mode

Technical Background

The Battlesnake rules repo is open source and available at
https://github.com/BattlesnakeOfficial/rules

The rules repo currently has two constructs to create different game types: ‘rulesets’ and ‘maps’

Examples of rulesets include: standard, wrapped and constrictor

And Examples of maps include: arcade_maze, solo_maze, and snail_mode

Rulesets

Rulesets change base behavior of the game. For example standard defines how snakes move and eliminations are done, this is the traditional Ruleset Battlesnake ruleset.
wrapped changes us the original rules by allowing snakes to leave the board on one side, and appear on the other! In standard this would lead to an elimination from hitting a wall

And constrictor changes the base rules my making it so snakes grow each turn, and their tail never move from their original square.

Maps

Maps on the other hand don’t affect the base rules of the game, but allow developers to create unique experiences on top of the rulesets.

For example the arcade_maze map typically is played with the wrapped ruleset, and has an arcade game inspired ‘maze’ for the snakes to battle it out in.

The solo_maze and snail_mode maps add some extra complexity.
One thing the Map interface allows you to do is decide the position of all food and hazards on the game board.

solo_maze uses this to a build a maze of hazards, with a food as the goal. When the snake reaches this food the map “increases in size”, a new map is generated by placing hazards on the board and a new goal food is placed.

snail_mode uses the hazards to create deadly “snail tails” behind snakes. When a snake leaves a space the snail_mode map replaces its tail with a hazard that stacks in damage. Over time this “slime” trail fades away, and this is also controlled by the snail_mode map

board Viewer

The board is responsible for showing games to developers in the UI: https://github.com/BattlesnakeOfficial/board

board currently has NO knowledge of any of the modeling we just talked about. It does NOT know about the different maps or rules specifically.
Instead the server sends it a copy of the game board for each frame, with all the information on the board. This is similar to the information sent to each snake.

This approach keeps the board decoupled from the engine, and allows adding game modes without requiring changes to the board.

Proposal

I propose that we introduce a new construct to allow the creation of new imperfect information game modes.

In addition to rulesets and maps, this RFC proposes adding filters.

filters would NOT be able to affect the game state as the rules repo sees it, but WOULD be able to alter the board state before they are sent to snakes.
And the filter would be applied to each snake individually, so that the filter could craft custom responses for each snake.

In Psuedo-Code the existing process looks something like this for an individual turn

previous_state = ...current game board...

// Allow the map to make changes before sending requests to snakes
board_state = map.preupdate_board(previous_state)

// Gather the moves for all snakes
// This pseudo-code ignores all timing concerns
chosen_moves = []
for snake in snakes:
  move = request_move_for_snake(snake, board_state)
  chosen_moves << move

// Evaluate the moves for the given rules
board_state = ruleset.evaluate_moves(board_state, chosen_moves)

// Give maps a chance to update the board after evaluating moves
board_state = maps.postupdate_board(board_state)

In the new version I propose a solution that looks like this

previous_state = ...current game board...

// Allow the map to make changes before sending requests to snakes
board_state = map.preupdate_board(previous_state)

// Gather the moves for all snakes
// This pseudo-code ignores all timing concerns
chosen_moves = []
for snake in snakes:
  filtered_board = filter.filter_for_snake(snake, board_state)
  move = request_move_for_snake(snake, filtered_board)
  chosen_moves << move

// Evaluate the moves for the given rules
board_state = ruleset.evaluate_moves(board_state, chosen_moves)

// Give maps a chance to update the board after evaluating moves
board_state = maps.postupdate_board(board_state)

The difference is the body of the for loop

  filtered_board = filter.filter_for_snake(snake, board_state)
  move = request_move_for_snake(snake, filtered_board)
  chosen_moves << move

Now we call filter.filter_for_snake for each snake before making requests.
This allows custom filters to be applied to each snake, which should enable the “flashlight tag” game mode

Adding a new construct for the filter allows the existing ruleset and map constructs to remain unchanged!

Snake Request Changes

The shape of the JSON sent to snakes MAY change in this RFC.

We propose that filters are allowed to REMOVE information from the requests, but NOT add new fields or information. It is likely this requirement will not be able to be enforced in code, but will remain a social construct.

Some of the information we expect filters to remove are:

• Snake Lengths
• Position of Hazards
• Position of Food
• Position of Snake Body Pieces (including head positions)
• Number of snakes currently alive

Its important to note that with the removal of snake body pieces, there is NO guarantee that snake body pieces are contiguous or that the number of snake body pieces equals the full length of the snake

Filters shall NOT remove “metadata” information about the game. This includes the ruleset, map and any filter modes that may be active.

board changes

We want to be able to ‘see’ what each snake can see while replaying the games.
And we would like to do that without requiring the board repo to be aware of the specific rules of the filters.

To do this I propose we make the rules repo in charge of deciding how to render any new ‘additions’.

I propose we add a new ‘ui_additions’ object that a filter can create. These ui_additions should be for things that do not affect gameplay, but add extra information to the board.

At a minimum filters should be able to create ui_additions, but I think it’s reasonable to allow maps and rulesets to do the same!

The board repo uses SVG to render the board, so I propose the ui_addition object closely match SVG elements. For the initial implementation of this game mode, I think only a single ‘type’ of ui_addition is needed, but we should expect to expand this in the future.

We need a ui_addition that maps to a cell of the board. The basic shape could look something like this

{
	type: 'cell',
	x: Int,
	y: Int,
	color: RGBA value,
}

This would allow us to draw cells for what each snake can see, similar to how the games look in the examples!

Alternatives Considered

Adding a Ruleset

In some sense it would be ideal to allow adding a “flashlight_tag” game mode, without adding any new concepts to the Battlesnake game.

One way to accomplish this would be to define ”flashlight_tag” as a ruleset!

rulesets are the lowest level concept here, and as such have the most ‘power’ to control the board state.

However, rulesets are NOT positioned in a place to create different experiences for each snake.
And with the current state of the rules code, a ruleset is NOT responsible for actually sending requests to snakes.

For a flashlight_tag to be written as a ruleset we’d need to refactor the rules and create a tighter coupling between a Ruleset and how requests are sent to snakes.

Another big downside to this approach is that it doesn’t allow easy ‘stacking. For example it’s reasonable to want to play “flashlight_tag” with either the standard ruleset or the wrapped ruleset. It would be unfortunate if we needed to create a “flashlight_tag_standard” and “flashlight_tag_wrapped” rulesets to accomplish this goal.

Adding a new Map

Trying to slot this into a Map has some of the same drawbacks a ‘ruleset’ does, and a map is more limited in its control of the board state.

Maps don’t provide a way to customize the requests sent to each snake, which is a core requirement of this proposal.

And again it would be ideal to be able to ‘stack’ different filters on top of different maps, without needing to duplicate large amount of logic

Having the board calculate the view too

We could have the Rules repo know how to draw the UI on its own, without adding any new information to the wire protocol.
But this requires the board repo also knowing the rules of the filter, and reduces the decoupling between board and rules that we have today

[ymahlau]

Thanks for the awesome RFC Corey! I have two additional thoughts to be considered:

1. I believe currently neither board nor Food struct saves the information, how long ago a food has spawned. If you want to make food visible in the first turn when it spawns and invisible afterwards, i would propose the following change:
   Add a 'spawn_turn' or 'data' attribute to the Point struct, which stores this information. This attribute would not be forwarded in a json to snakes, but could be used by the filter.

2. I am not very knowledgeable of the rules repo, so please correct me if I am wrong: The filter would operate on the board Struct of the rules Repo. This board state does not have the information of snake color etc., so creating a ui_addition with an RGB color for each snake would not work right? Maybe the ui_addition could be linked to a snake_id and then the renderer could lookup the specific RGB color / mix multiple colors if multiple snakes can see the same cell.

Best
Yannik

[coreyja]

Ahh thanks for these call outs @ymahlau, I definitely hadn't dug deep into the code path to catch either of those! I like your suggestions too!

1. This definitely reminds me of the TTL additions we wanted to add to hazards and food in a future battlesnake edition. I wonder if we either want to wait on adding this until we have it first class for snakes to see too? Or on the other hand this could be a building block to adding it to the snake responses too. Context: https://github.com/orgs/BattlesnakeOfficial/discussions/227
2. Great call out! Ya I like your idea of potentially having a snakeId that links up with the snake, but will also look into if it seems reasonable to make this info available to maps/filters!

Thanks for all you comments Yannik! Excited to get started on this game mode!

[bvanvugt]

This is great Corey! At first glance I would really like to find a way to roll out Filters as a sort of property of Maps, rather than in addition to. Maps are very much the goal, and ideally we deprecate rulesets.

Maybe it's as simple as giving Maps the filter function you propose as an API call that can manipulate BoardStates before they get sent to specific snakes. To start, we could limit input and output to valid BoardStates, and then the Map could only use the BoardState Editor interface to manipulate state for each snake -- this comes with added protections of not having to worry about the filter func breaking the JSON format, since it doesn't actually operate on the raw data.

filtered_board = *map*.filter_for_snake(snake, board_state)
move = request_move_for_snake(snake, filtered_board)
chosen_moves << move

I also like the idea of Maps being able to draw on the board arbitrarily! Maybe rather than ui_additions this takes the form of annotations. Maps can attach annotations to any board state, they aren't sent to snakes but they are shared with the board. Board can then provide a toggle setting to Display Map Annotations. Thoughts?

[coreyja]

At first glance I would really like to find a way to roll out Filters as a sort of property of Maps, rather than in addition to.

The reason I proposed a new concept is that it feels nice to allow Filters and Maps to be layered.
But thinking about it more if we wanted to really lean into Maps, a Filtered+ArcadeMaze wouldn't be that hard to write 🤔 But would probably limit having a Filter being something someone in the UI someone could toggle/pick independent of a Map

I don't have a huge preference! But it does feel to me that the existing maps and a 'filter' don't conceptually share a ton in common. So depending on how "first level" we want to make filters, I might lean towards them being their own entity.

Map could only use the BoardState Editor interface to manipulate state for each snake

I really like using the existing Editor interface for the filter functions! Makes sense to re-use that, and as you said should make it more robust to breakages

ideally we deprecate rulesets

I always forgot if the goal for maps was to layer on top of, or replace rulesets, so thanks for the reminder!

[coreyja]

Maps can attach annotations to any board state, they aren't sent to snakes but they are shared with the board. Board can then provide a toggle setting to Display Map Annotations. Thoughts?

Love annotations! Much better than the name I came up with! Also having a toggle for them is great 💯

[rob-odwyer]

Love this idea - particularly because I've always wanted there to be some kind of "game mode" that forces you to keep state. Otherwise, Battlesnake doesn't really push you into learning about databases - which is kind of a pity since they tend to be a major component of most software development work.

I agree with Brad's thought that, at least at first, maybe this is best implemented as an optional maps hook. Even if it might make sense to eventually separate them out, there's a lot of plumbing required to get a new game setting end to end - e.g. in the play UI, play database, engine API, engine workers, rules, etc.

Another unfortunate gotcha here is that the engine codebase has a mix of representations of the board state, depending on which step of playing a game it's in. The code that makes requests to snake servers uses one type, and the rules code uses another. The game logic converts to the rules BoardState after making the requests, then applies the rules, then converts back before storing the next frame in the database. I don't think this is insurmountable, but it is the reason why I never got around to implementing the PreUpdateBoard map hook. 😬
You can look at the GameTick function in engine to see what I mean. I'm sure it's possible to do this, but some refactoring might be needed. Or maybe we just convert between the two representations twice on every turn 🙈