Introduction
I played a lot of Battleship when I was a kid. It’s a simple game, but one with potentially very complex optimal playing strategy. Recently I encountered a variant of the game that Milton Bradley released in 2008 (now owned by Hasbro), using a hexagonal grid instead of the usual square 10×10 grid. The motivation for this post is to compare the original and updated versions, demonstrating just how unfair the new version of the game might be.
Original Battleship
In both versions of the game, two players each place their own ships on a grid of cells hidden from view of the other player. Players then alternate turns guessing cell locations, trying to hit and “sink” the other player’s ships. The following figure shows an example of one player’s deployment in the original game; there are 5 ships of various lengths: a carrier (5 cells), battleship (4 cells), submarine (3 cells), cruiser (3 cells), and destroyer (2 cells).
Original Battleship grid for a single player with example deployment of ships.
A natural question to ask is, in how many possible ways can a player deploy his ships? This is a known problem that has been solved many times before… but usually with special-purpose code implementing a backtracking search enumerating individual deployments.
Instead, we can re-use the implementation of Knuth’s “Dancing Links” (DLX) algorithm by casting the problem as an instance of a generalized exact cover (more on the generalization shortly). Recall that an exact cover problem is a matrix of 0s and 1s, with a solution consisting of a subset of rows of the matrix containing exactly one 1 in each column.
To count Battleship deployments, very similar to counting Kanoodle puzzle solutions, there are two “kinds” of columns in our matrix: one column for each of the 5 ships, and one column for each of the 100 cells in the 10×10 grid. Each row of the matrix represents a possible placement of one of the ships, with a single 1 in the corresponding “ship” column, and additional 1s in the corresponding occupied “cell” columns. The resulting matrix has 105 columns and 760 rows, corresponding to placing each of the carrier, battleship, submarine, cruiser, and destroyer in 120, 140, 160, 160, and 180 ways, respectively.
However, unlike the Kanoodle puzzle, we don’t want an exact cover here, since that would effectively require that our 5 ships cover all 100 cells of the grid! Instead, we want a “generalized” cover, in which some of the columns of the matrix are “optional” (Knuth calls them “secondary”), and may be covered at most once instead of exactly once. In this case, the 5 ship columns are required/primary (we must use all of the ships), and the 100 cell columns are optional/secondary (we don’t have to cover every cell, but the ships can’t overlap, either).
Putting this all together, the following Python code specifies the details of the original Battleship game:
- The board, specified as the coordinates of each of the cells in the 10×10 grid.
- The size and shape of the 5 ship pieces, each in a default position and orientation.
- The 4 possible rotations (in 90-degree increments) of each piece.
import numpy as np
def matrix_powers(R, n):
"""Return [R^1, R^2, ..., R^n]."""
result = []
a = np.array(R)
for k in range(n):
result.append(a)
a = a.dot(R)
return result
class Battleship:
def __init__(self):
self.board = {(x, y) for x in range(10) for y in range(10)}
self.pieces = {'Carrier': {(x, 0) for x in range(5)},
'Battleship': {(x, 0) for x in range(4)},
'Submarine': {(x, 0) for x in range(3)},
'Cruiser': {(x, 0) for x in range(3)},
'Destroyer': {(x, 0) for x in range(2)}}
self.rotations = matrix_powers(((0, -1), (1, 0)), 4)
Given such a specification of the details of the game, the following method constructs a sparse representation of the corresponding generalized exact cover matrix, by considering every possible ship piece, in every possible orientation, in every possible position on the board:
def cover(self):
"""Return (pairs, optional_columns) for exact cover problem."""
# Enumerate all possible placements/rotations of pieces.
rows = set()
for name, piece in self.pieces.items():
for R in self.rotations:
for offset in self.board:
occupied = {tuple(R.dot(x) + offset) for x in piece}
if occupied <= self.board:
rows.add((name, tuple(sorted(occupied))))
# Convert placements to (row,col) pairs and optional column indices.
cols = dict(enumerate(self.pieces))
cols.update(enumerate(self.board, len(self.pieces)))
cols = {v: k for k, v in cols.items()}
pairs = []
for i, row in enumerate(rows):
name, occupied = row
pairs.append((i, cols[name]))
for x in occupied:
pairs.append((i, cols[x]))
return (pairs, list(range(len(self.pieces), len(cols))))
Plugging this into the C++ implementation of DLX (all of this code is available in the usual location here), we find, about 15 minutes later, that there are over 30 billion ways– 30,093,975,536, to be exact– for either player to place his 5 ships on the board in the original Battleship game.
Hexagonal Battleship
In the 2008 version of the game, there are several changes, as shown in the figure below. Most immediately obvious is that the grid is no longer square, but hexagonal. Also, some grid cells are “islands” (shown in brown) on which ships cannot be placed. There are still 5 ships (shown in gray), but they have changed shape somewhat, no longer confined to straight lines of cells.
Finally, and most importantly, the two players each deploy their ships on two different “halves” of the board, with the “Blue” player’s ships on the top half, and the “Green” player’s ships on the bottom half. (The figure shows a typical view of the board from Blue’s perspective.)
Hexagonal Battleship grid for both players (Blue and Green), with islands (brown) and example deployment of Blue’s ships (gray).
Closer inspection of the board shows that the Blue and Green halves are almost symmetric… but not quite. Each half has 79 grid cells on which to deploy ships (I’m guessing this explains the missing cell at bottom center), and 4 of the 5 islands in each half are exactly opposite their counterparts in the other half… but not everything lines up exactly. This strongly suggests that one half allows more possible ship deployments than the other (can you guess which just by looking?), which in turn suggests that that player has at least a slight advantage in the game.
Hexagonal coordinates
We can count possible ship deployments in the same way, using the same code, as in the original game described above. The only catch is the hexagonal arrangement of grid cells. To handle this, we just need a coordinate system for specifying cell locations that may at first seem unnecessarily complicated: let’s view our two-dimensional grid as being embedded in three dimensions.
Specifically, consider the points with integer coordinates in the plane . Imagine viewing this plane in two dimensions by looking down along the plane’s normal vector toward the origin. The points in this plane with integer coordinates form a triangular lattice; they are the centers of each hexagonal grid cell. In the figure above, each hexagonal grid cell is shown with the coordinates of its center point, with the origin at the center of the board.
This is a handy representation, since these points form a vector space (more precisely, a module), where translations (i.e., moving ships from their “default” location to somewhere on the board) and rotations (i.e., orientations of ships) correspond to vector addition and matrix multiplication, respectively.
The following Python code uses these hexagonal coordinates to define the board, ship pieces, and 6 possible rotations for either the Blue (is_upper=True) or Green (is_upper=False) player in the 2008 version of Battleship:
class HexBattleship(Battleship):
def __init__(self, is_upper=True):
if is_upper:
islands = {(-5, 4, 1), (-1, 3, -2), (-1, 7, -6), (4, 2, -6),
(5, -1, -4)}
else:
islands = {(-5, 1, 4), (-1, -6, 7), (-1, -2, 3), (2, -1, -1),
(4, -6, 2)}
self.board = {(x, y, -x - y)
for x in range(-7, 8)
for y in range(max(-7 - x, -7) + 1 - abs(np.sign(x)),
min(7 - x, 7) + 1)
if (6 * y >= -3 * x + x % 4) == is_upper and
not (x, y, -x - y) in islands}
self.pieces = {'Carrier': {(x, 0, -x) for x in range(3)} |
{(x, -1, -x + 1) for x in range(1, 3)},
'Battleship': {(x, 0, -x) for x in range(4)},
'Submarine': {(x, 0, -x) for x in range(3)},
'Destroyer': {(x, 0, -x) for x in range(2)},
'Weapons': {(0, 0, 0), (1, 0, -1), (0, 1, -1)}}
self.rotations = matrix_powers(((0, -1, 0), (0, 0, -1), (-1, 0, 0)), 6)
Running DLX again on each of the resulting matrices, the upper Blue board allows 17,290,404,311 possible deployments, while the lower Green board allows 21,625,126,041– over 25% more than Blue! So it seems like it would be a definite advantage to play Green.
Finally, one minor mathematical aside: note that the 60-degree rotation in the above code is specified by the matrix
This is convenient, since just like the 90-degree rotations in two dimensions in the original game, the effect is a simple cyclic permutation (and negation) of coordinates, which we could implement more directly without the matrix multiplication if desired.
However, this is cheating somewhat, since is not actually a proper rotation! Its determinant is -1; the “real” matrix rotating vectors by 60 degrees about the axis is
It’s an exercise for the reader to see why the simpler form of still works.
References:
- Knuth, D., Dancing Links, Millenial Perspectives in Computer Science, 2000, p. 187-214 (arXiv)