NOTE: This is Part 1 of a three-part series demonstrating how we might model the classic game Battleship as a C# program. You might want to use the sample project over on GitHub to follow along with this post. Also, check out my other posts in the Modeling Practice series!
In software development, often we programmers are asked to take large, complex issues and break them down into smaller, more manageable chunks in order to solve any given problem. I find that this, as with many things, becomes easier the more you practice it, and so this blog has a series of posts called Modeling Practice in which we take large, complex problems and model them into working software applications.
In my case, I love games, so each of the previous entrants in this series have been popular, classic games (Candy Land, Minesweeper, UNO). That tradition continues here, and this time the board game we'll be modeling is the classic naval battle game Battleship.
My boys (who I've written about before) are now old enough that they can play this game themselves, and so they've been killing hours trying to sink each other's ships.
That's the Modeling Practice we're going to do this time: we're going to model a game of Battleship from start to finish, including how our players will behave. So, let's get started!
What is Battleship?
For those of you who might not have played Battleship before, here's how it works. Each player gets a 10-by-10 grid on which to place five ships: the eponymous Battleship, as well as an Aircraft Carrier, a Cruiser, a Submarine, and a Destroyer. The ships have differing lengths, and larger ships can take more hits. Players cannot see the opposing player's game board.
Players also have a blank firing board from which they can call out shots. On each player's turn, they call out a panel (by using the panel coordinates, e.g. "A5" which means row A, column 5) on their opponent's board. The opponent will then tell them if that shot is a hit or a miss. If it's a hit, the player marks that panel with a red peg; if it is a miss, the player marks that panel with a white peg. It then becomes the other player's turn to call a shot.
When a ship is sunk, the player who owned that ship should call out what ship it was, so the other player can take note. Finally, when one player loses all five of his/her ships, that player loses.
The game itself was known at least as far back as the 1890s, but it wasn't until 1967 that Mattel produced the peg-and-board version that most people have seen today. It is that version (and its official rules) that we will use as part of our modeling practice.
Now, let's get started modeling! First, we need to figure out the components of the game.
Components of the Game
In order to play a game of Battleship, our system will need to be able to model the following components:
- Coordinates: The most basic unit in the game. Represents a row and column location where a shot can be fired (and where a ship may or may not exist).
- Panels: The individual pieces of the board that can be fired at.
- Game Board: The board on which players place their ships and their opponent's shots.
- Firing Board: The board on which players place their own shots and their results (hit or miss).
- Ships: The five kinds of ships that the game uses.
All of that is fine and good, but if our system expects to be able to actually play a game, we're going to have to figure out the strategy involved.
Potential Strategies
Here's a sample Battleship game board:
There are two different strategies we'll need to model:
- How to place the ships AND
- How to determine what shots to fire.
Fortunately (or maybe unfortunately) the first strategy is terribly simple: place the ships randomly. The reason is that since your opponent will be firing at random for much of the game, there's no real strategy needed here.
The real interesting strategy is this one: how can we know where to fire our shots so as to sink our opponent's ships as quickly as possible? One possibility is that, just like placing the ships randomly, we also just fire randomly. This will eventually sink all the opponent's ships, but there is also a better way, and it involves combining two distinct strategies.
First, when selecting where to fire a shot, we don't need to pick from every possible panel. Instead, we only need to pick from every other panel, like so:
Because the smallest ship in the game (the Destroyer) is still two panels long, this strategy ensures that we will eventually hit each ship at least once.
But what about when we actually score a hit? At that point, we should only target adjacent panels, so as to ensure that we will sink that ship:
These are called "searching" shots in my system, and we only stop doing searching shots when we sink a ship.
By using these two strategies in tandem, we ensure that we can sink the opponent's ships in the shortest possible time (without using something like a probability algorithm, which more advanced solvers would do).
Summary
Here's all of the strategies we've discovered so far:
- Placement of ships is random; no better strategy available.
- Shot selection is partly random (every other panel) until a hit is scored.
- Once a hit is scored, we use "searching" shots to eventually sink that ship.
- The game ends when one player has lost all their ships.
In the next part of this series, we will begin our implementation by defining the components for our game, including the players, ships, coordinates, and so on. We'll also set up a game to be played by having our players place their ships.
Matthew JonesDon't forget to check out the sample project over on GitHub!
Happy Modeling!
