Battleship

Battleship is a classic two person game, originally played with pen and paper.

On a grid (typically 10 x 10), players ’hide’ ships of mixed length; horizontally or vertically (not diagonally) without any overlaps. The exact types and number of ships varies by rule, but for this posting, I’m using ships of lengths: 5, 4, 3, 3, 2 (which results in 17 possible targets out of the total of 100 squares).

Note: even though ships cannot overlap, there is nothing in the rules to say they cannot touch. (In fact, some players consider this a strategy to confuse an opponent by obfuscating the true layout of ships. If there are five ‘hits’ in a row, a naive player might consider this to be the successful destruction of an aircraft carrier of length 5, but actually it could be the sinking of a battleship of length 4, and part of a cruiser of length 3)

We’ll start with a description of the simplified method of play:

After each player has hidden his fleet, players alternate taking shots at each other by specifying the coordinates of the target location. After each shot, the opponent responds with either a call HIT! or MISS! indicating whether the target coordinates have hit part of a boat, or open water. An example of a game in progress is show on the left.

In these diagrams, misses are depicted by grey crosses and hits by red squares with grey crosses.

The first player to sink his opponent’s fleet (hitting every location covered with part of a boat) wins the game.

As expected, the results of firing random volleys produces very poor results. Games take a long time to complete, as the majority of squares have to be hit in order to ensure that all the ships are sunk.

A simple implementation of this refined strategy is to create a stack of potential targets. Initially, the computer is in Hunt mode, firing at random. Once a ship has been 'winged' then the computer switches to Target mode. After a hit, the four surrounding grid squares are added to a stack of 'potential' targets (or less than four if the cell was on an edge/corner).

Cells are only added if they have not already been visited (there is no point in re-visiting a cell if we already know that it is a Hit or Miss).

Once in Target mode the computer pops off the next potential target off the stack, fires a salvo at this location, acts on this (either adding more potential targets to the stack, or popping the next target location off the stack), until either all ships have been sunk, or there are no more potential targets on the stack, at which point it returns to Hunt mode and starts firing at random again looking for another ship.

Initially, the algorithm starts in Hunt mode, firing random shots. On turn #3 it has hit something and turns into Target mode. The four cardinal directions (We'll use N, S, E and W to describe direction), are all added to the stack of 'potential' locations as they are touching a know ship location. Going N for turn #4 has resulted in another successful hit, so the locations N, E and W of this new location are added to the 'potential' target stack (S is not added – that location has already been visited!).

Turn #5 (S of the first hit) is also a hit, so the surrounding squares not already visited are added to the end of the stack. Turn #6 and Turn #7 are misses.

Turn #9 and turn #10 see the computer testing and eliminating squares either side of the target, and turn #12 sees the discovery of a pixel to the side. You can see here why this dumb algorithm needed to perform this test; if it was simply looking for straight lines, it would have stopped searching downwards after the miss on turn #11 and then continued up one more square ontop to sink, what it thought, would be the the aircraft carrier at five units long.

We're now deep into the sinking this ship cluster.

But, to be sure, we need to visit every touching member around the edge of the a known hit.

Edge investigation continues, resulting in a new find on turn #21.

On turn #28, the last 'potential' target is pulled off the stack, drawing a miss. The algorithm will now return to Hunt mode and continue the random search.

No luck yet …

Success on turn #36! Returning to Target mode.

The cruiser has been sunk by turn #40, but the dumb algorithm does not know this, and needs to blindly continue walking around the edge … just to be sure.

Some of the edges have already been visited by this stage, so searching is faster.

The miss on turn #45 indicates the end of Target mode and we're back to random Hunt mode.

We've hit again on turn #49.

The grouping of the final two ships is such that finding the last few squares happens quickly (it's in a corner, so less to add to the stack, and they lay parallel, so share many of the same boundaries).

A count is kept of the number of hit pixels, and so on turn #53, when the last salvo brings the count to 17, the algorithm terminates immediately and it does not need to walk around the edges still on the 'potential' stack.

Because the minimum length of a ship is two units long, then we don't need to random search every location on the board. Even the shortest ship has to straddle two adjacent squares.

Imagine the board as a checker board, like the grid on the left. No matter how the two unit destroyer is placed on the grid it will cover always cover one white and one blue grid.

A mathematical term to describe this is Parity. This is just a fancy word of describing if the square would contain an odd or even number if labelled sequentially from 1 to 100

The blue squares on the grid are even parityand the white squares odd parity.

We can instruct our Hunt algorithm to only randomly fire into unknown locations with even parity. Even if we only ever fire at blue locations, we will at least hit every ship — it's impossible to place any ship so that it does not touch at least one blue square.

Once a target as been hit, and Target mode is activated, the 'parity' restriction is lifted enabling all potential targets to be investigated. If the algorithm returns to Hunt mode, again, the parity filter is enabled.

(The smarter readers will have realised that, once we've sunk the two unit destroyer, we can change the parity restriction to a larger spacing, and that's the prefect seque into the advanced implementation described further in this article, keep reading …)

The official rules of the game also state that you should let your opponent know if they have successfully SUNK any ship, so this third style message ”You have sunk my aircraft carrier” conveys much more information than just hit.

It tells you the length of the ship you have just hit, it tells you that you have hit all pixels of this ship, and it could, potentially, give you a new minimum size of ship you are searching for (for instance, if you have sunk all ships other than the aircraft carrier, then you know that this remaining ship is five units long and can adjust your random search according to skip the appropriate number of spaced when in hunt mode.

In the diagram to the left, SUNK entities are rendered in brown with white crosses.

In all these examples, shading is used to depict the probability. Dark colours represent high probabilty, and light colours represent low probability.

In this example, one shot has been fired, and we're looking for the aircraft carrier. It's less likely to be South (because it could not fit vertically, and so the only way it could overlap one of the cells to the South is if it layed horizontally). Similarly, it's less likely to be West. Probablities also fall off slightly towards the edges and corners as there are less ways to position the ship that covers these locations.

With two misses on the grid, it's less likely to be in the space between the two misses. It's also very unlikely to be on the top row to the left, as here it can only be placed vertically.

White squares represent zero probability, and by definition, any square that is a miss has zero probability.

In this configuration we can see a white square just to the left of the top miss. It is impossible for the aircraft carrier to pass through this square.

An example distribution with seven misses on the grid.

A ficticious board layout with lots of misses marked. Many of the locations are impossible to host the carrier. The darker the shading, the more possible ways that the carrier could use this square.

Another example with lots of misses.

With no information about the board, the algorithm selects one of the center squares. Because of the edge effect described earlier, the middle of the board will score higher than an edge or a corner.

Unfortunately, the first shot ends in a miss

With the knowledge of the first miss, the algorithm recalculates the probability density and selects the current highest scoring sell (or one of them, if there are more than one that share the same value).

This time, it's a hit

The four surrounding squares are all equal in probablity (this being a square close to the center, so still able to host part of an aircraft carrier in all directions), and the cell to the right is chosen.

Another hit

Now that there are two hits in a row, the highest probability targets are to either side of these two.

The shot to the right is a miss

Interestingly, at this point, it's just as likely that the two hits could be from two parallel up/down ships as one side to side, and in this implementation of the alogrithm if there is more than one location with the same probability, the next numeric one (starting from the top-left) is selected.

This is also a miss

Another miss. (Notice that the algoritm tested the top side this time, and the lower side previously, gaining knoweldge becasuse of a parity skip between it and the miss two to the left.

Now we pretty sure that we need to move left (since we know all ships are still in play), and the chances are very low that the soution is down/up/down ships.

Success, we've sunk our first ship. Since we receive indication that a ship is sunk, the algorithm does not heavily weight continuing further to the left. It will go there if needed, but based on the probability that another ship is in this space, not as a continuation of the current ship.

Hunting shot based on the probability of ships being in this location

More hunting shots.

And again.

Another hit.

Since long ships are still in play, it's slightly more likely that ships run up/down from this location (and slightly more likely down than up, since the aircraft carrier would not fit upwards).

Miss

Another ship sunk (and thus removed from the probability cloud).

Back to hunting.

Another hit.

Again, with the big ship still in play, it's slightly more likely that it ships run up/down.

Miss.

Miss. But again notice the skipped vertical parity as it tried the vertical space two up, not just one up.

Hit.

Another ship sunk.

Back to hunt mode.

Checking the larger white spaces.

Hit.

Checking to the side first, as the aircraft carrier is still out there, and can only run left-right from here.

Success in shrinking the destroyer. This is good fortune for us. The destroyer is length 2, and with this sunk, it only leaves the aircraft carrier, which is large, and harder to hide. With the removal of the destroyer there probability cloud will change considerably. There are not that many loations left where the aircraft carrier can be.

Large areas of the board are now white. The alogithm starts to search, initially, in the biggest area of possible space (highest probability, since there are many ways that the carrier could lay in this area).

Hit! It's only a few moves to victory from here.

Game Over!