One of the great things about working on version 1 of a project is that you can learn from version 0. However, step 0 is still to do the design work.

Let's going to start with a short discussion of the features that we want to keep in mind as we design, because they will affect a number of design decisions that we make.

Key Features

We'll keep our discussion fairly high level here, but we can get into more detail as we get closer to writing code.

• Battleship Gameplay
• Game Modes / Rule Tweaks
• Spectators / Replays
• Chat
• Quick Play / Invite Links
• User Accounts

Battleship Gameplay

Rather obviously, the goal is for people to be able to play Battleship. We use the standard rules^[1], so games have two players, players have two boards and 5 ships, gameplay bounces from player to player, etc.

Game Modes / Rule Tweaks

There exists a variation of Battleship in which players fire salvos instead of single shots. We want to be able to accomodate this rule tweak and potentially other rule tweaks in the future, so we need to abstract somewhat over the rules of the game.

Spectators / Replays

In real life, people can crowd around the physical game and watch the battle unfold. The internet-enabled analog to that is spectators. This requires a log of all game events in a form that can be used to replay events up to arbitrary game state.

Chat

While we don't need to embed a full featured chat client, being able to echange messages with your opponents without any other setup is something that we think will likely make the Questionable Battleship experience nicer as a whole.

Quick Play / Invite Links

The ability to hit the ground running and just pull up to a game and play is invaluable. Anything we do to streamline that process is a step in the right direction, and this should help. We want Quick Play to be a way for anyone to quickly drop into a game, and we want people to be able to use invite links to quickly join games without any fuss.

It might be possible to extend this concept to queueing to play against another random player or a computer player.

User Accounts

No one asked for them, but User Accounts make it easier to organize and present potential features down the line.

Designing the backend server

The ultimate goal is to play Battleship, so our primary focus is going to be on the representation and manipulation of game state. The other features we discussed may help guide some of our decisions, but they aren't our end goal. So there are at least three things we have to do:

1. Represent game state
2. Store game state
3. Represent server state

We're fortunate enough here to have Version 0 to interrogate. We can learn quite a bit about how many design decisions panned out as the project progressed. In our discussions of how we plan to accomplish these goals, we'll occasionally look in the direction of the original Questionable Battleship server and what it has to teach us.

Today we'll talk about representing game state.

Representing Game State

Games of Battleship seem fairly simple, so we don't expect to have some gargantuan and excessively complicated game state. We don't have quests like Skyrim or consequences to choices like in some RPGs, and we certainly don't have to deal with the open-world that games like Minecraft have to.

We'll start at the top level and work our way down, noting our assumptions as we catch them. We'll almost certainly have to come back later, but but most of the things we have to add or tweak later should have little to do with the completeness our coverage of the state of the game.

Game :: (
    player_1,
    player_2
)

Games have two players

We can all imagine how N-way Battleship might get interesting, especially when Game Modes come into play, but we'll leave that for another day. For now, we'll design with more vanilla tweaks in mind.

Unlike other boards games like Monopoly or Risk, Battleship does not have a shared playing field. Instead, players each have a play area upon which ships are placed and a tracking area.

Game :: (
    player_1,
    player_2,
    board_1,
    board_2,
    tracking_1,
    tracking_2,
    ship_...,
    ....
)

Players each have a single play area (Board) and a single tracking area (Tracking)

We could probably make this flat representation work, but it seems like more trouble than it's worth. Recall that one of our goals is to be able to tweak the way the game works, and this suddenly seems like a terrible idea: Even the smallest change may require that everything else change as well.

Let's break things down a bit then:

Game :: (
    player_1 :: Player,
    player_2 :: Player
)

Player :: (
    board :: Board,
    tracking :: Tracking,
)

Board :: (
    ships :: [Ship]
)

This is still incomplete, but it's far easier to understand. Games have two players, players have a board and something for tracking, and boards have ships. This also neatly captures ownership relationships, and it'll hopefully help us limit the scope of any tweaks we may have to make.

We still don't know what Tracking is. From a game perspective, it's the tracking grid that players use to track the results of the shots that they've made. In that case, there's relatively little to it: Where a shot was, and what the result was.

Tracking :: (
    shots :: [ Shot ]
)

Result = Hit | Miss | Sink Ship

Shot :: (
    x :: Int,
    y :: Int,
    result :: Result
)

Players play on discrete two-dimensional boards

Tracking only displays shot results

Shots either hit a ship, miss all ships, or sink a ship

There's room here to add more things to Tracking, but the general spirit is to record the shots that a player has made at their opponent's ships.

So let's talk about Boards and Ships.

In standard Battleship, boards are squares with 10 cells on each side for a total of 100 cells. Five ships are placed onto each player's board, and they may not intersect.

A ship's position can be described completely by a starting location, a length, and a direction.

Board :: (
    ships :: [ Ship ]
)

Direction = Up | Right | Down | Left

Ship :: (
    x :: Int,
    y :: Int,
    length :: Int,
    direction :: Direction
)

Ships can neither intersect nor extend beyond the boundaries of the board.

Shots fired by the opposing player will either hit a ship or miss all ships. These shots and their results are part of the state of the game, and must be recorded. While it's possible for us to simply keep a complete game log that we can use to replay the game to any point and determine the current state in that fashion, that doesn't feel like an optimal solution.

One way to think about the problem is to note that shots in standard Battleship are unordered: There is no distinction between shooting cell A4 and then cell G6, and shooting cell G6 and then cell A4. Therefore, as long as our chosen strategy allows us to reconstruct the end result of all shots taken, it is acceptable.

We can additionally extend the concept of ownership to shots, or rather their results: recording the shots that hit is the responsibility of the victim. For classic Battleship, that means that ships track the shots that hit them, and the board tracks the shots that miss the ships, or alternatively, the shots that hit the board.

Because the positions of all ships relative to the board is simple to calculate, it is sufficient for ships to record shot positions relative to themselves.

Board :: (
    ships :: [ Ship ],
    misses :: [ Shot ]
)

Direction = Up | Right | Down | Left

Ship :: (
    x :: Int,
    y :: Int,
    length :: Int,
    direction :: Direction,
    hits :: [ Int ]
)

Result = Hit | Miss | Sink Ship

Shot :: (
    x :: Int,
    y :: Int,
    result :: Result
)

Shots that missed all ships and shots that hit a ship form a disjoint partition of all shots fired upon a board.

Putting everything together, our representation of Battleship state is as follows:

Game :: (
    player_1 :: Player,
    player_2 :: Player
)

Player :: (
    board :: Board,
    tracking :: Tracking,
)

Board :: (
    ships :: [ Ship ],
    misses :: [ Shot ]
)

Direction = Up | Right | Down | Left

Ship :: (
    x :: Int,
    y :: Int,
    length :: Int,
    direction :: Direction,
    hits :: [ Int ]
)

Result = Hit | Miss | Sink Ship

Shot :: (
    x :: Int,
    y :: Int,
    result :: Result
)

Tracking :: (
    shots :: [ Shot ]
)

I've proposed something slightly shady here: hits :: [ Int ] from Ship. It is the responsibility of ships to record shots that hit them, and there are a few approaches we can take:

• Keep a list of all ship segments that have been hit
• Keep a list of all ship segments that have not been hit
• Keep a list of the state of every ship segment

I don't yet see any particularly compelling reasons to rule out any of these representations, but if we recall that ships "own" shots in our model, it makes some sense to keep a list of ship segments that have been hit. So for now, we will represent the state of the ship as a list of unique indices, representing the segments that have been hit. This representation makes it easy to tell when a ship sinks: when all of a ship's segments have been hit, it sinks.

I see a little bit of redundancy here:

Board :: (
    ships :: [ Ship ],
    misses :: [ Shot ]
)

Result = Hit | Miss | Sink Ship

Shot :: (
    x :: Int,
    y :: Int,
    result :: Result
)

We already know that all of the shots recorded by the Board are misses, so we don't need the result field of Shots.

Board :: (
    ships :: [ Ship ],
    misses :: [ (x :: Int, y :: Int) ]
)

This works, but makes my skin crawl a little. Coordinate pairs are great, but they aren't treated like pairs anywhere, really. Let's fix that by adding the appropriate data abstraction:

Point :: (
    x :: Int,
    y :: Int
)

Then our representation becomes:

Game :: (
    player_1 :: Player,
    player_2 :: Player
)

Player :: (
    board :: Board,
    tracking :: Tracking,
)

Point :: (
    x :: Int,
    y :: Int
)

Board :: (
    ships :: [ Ship ],
    misses :: [ Point ]
)

Direction = Up | Right | Down | Left

Ship :: (
    location :: Point,
    length :: Int,
    direction :: Direction,
    hits :: [ Int ]
)

Result = Hit | Miss | Sink Ship

Shot :: (
    location :: Point,
    result :: Result
)

Tracking :: (
    shots :: [ Shot ]
)

We can revisit this in the future when necessary, but this looks like something we can work with.

Let's take a moment to talk about strategies for representing board state.

From a programming perspective, it's fairly natural to think of a board as a two-dimensional array. It makes sense to model a two-dimensional grid of cells in the real world with a two-dimensional grid of cells in a program. This approach has the added benefit of being easy to think about and easy to implement. It also tends to perform well, because array lookups are fast. However, when we're doing small lookups in response to player actions, we're unlikely to notice the speed difference unless the server is under heavy load.

The original Questionable Battleship doesn't do this, but the singleplayer proof of concept (PoC) that came before it did. State was represented in a cell-oriented fashion: It concerned itself with the owner of each and every cell on the board, and used those relationships to delegate handling shots. While this seems somewhat elegant, it does lead to a couple of questions with unsatisfying answers.

1. Who owns empty cells?
   In a standard game of Battleship, 83 of the 100 cells on each board are unowned. It's not a good idea to delegate the shot to no one, because then the player never gets feedback about their shot. The PoC solved this problem by assigning every unowned cell to a special type of ship: Open Sea. An Open Sea ship is one cell long and always reported that the shot missed. This feels like a bit of a hack, as it abuses the representation to provide "correct" behavior.
2. How much of this space do we actually need?
   In standard Battleship, there are only 17 cells taken up by ships. Further, most games don't end up covering every single cell in artillery shells. It seems like a potential waste of space to unconditionally dole out memory for so many cells that likely won't ever be touched; especially in a server that may have to serve many concurrent games. Simulations run by DataGenetics indicate that if players adhere to a hunt-then-sink strategy, games tend to touch fewer than 70 cells, and players using better strategies will touch even fewer cells! This probably doesn't matter too much in the grand scheme of things, but it leaves a bad taste in my mouth.

However, we can think of boards more generally as a set of cells identified by integer coordinates, and there is another way of representing sets: the characteristic function.

In a nutshell, the characteristic function of a set is a way to query membership of an element in a set. A black box, if you will, that answers one question and one question only: "Is this element in the set?"

Where B is the set being queried

Characteristic functions are interesting to think about. I'm rather partial to the following example, which implements a set.

If you'll allow me to drop into Python for a moment, consider the following:

def set():
    def nil(query):
        return false
    return nil

def set_add(set, element):
    def contains(query):
        if query == element:
            return true
        else:
            return set(query)
    return contains

def set_remove(set, element):
    def does_not_contain(query):
        if query == element:
            return false
        else:
            return set(query)
    return does_not_contain

A trivial example:

s = set()
# s = {}

s = set_add(3)
s = set_add(5)
s = set_add(7)
# s = {3, 5, 7}

if s(2): print("Set contains 2") # False
if s(3): print("Set contains 3") # True

s = set_remove(3)
# s = {5, 7}

if s(2): print("Set contains 2") # False
if s(3): print("Set contains 3") # False

If you think about it for a little while, you can see why this behaves like a set. It's not exactly computationally efficient, but it works. set() creates an empty set, set_add(element) adds a layer that encodes the presence of element in the set, and set_remove(element) adds a layer that encodes the absence of element in the set! This is a somewhat extreme example, completely foregoing explicit storage in favor of function closures, but it does a marvelous job of getting the point across.

You can see where I'm going with this: We can get away without an actual board in our representation if we keep, in any form, enough data to construct a characteristic function for our boards. This is what the original Questionable Battleship server did, and we plan to stick with that approach.

That's all I can think of with regards to representing game state for now. We'll leave the discussions of storing game state and representing server state for the future.

---

1. The Milton Bradley rules for Battleship ↩︎