The Battleship Bet

Will I Win This Wager?

I’m enjoying a meal with a friend in Atlanta. He looks at me with a twinkle in his eye.

“I have a winning strategy for Battleship.” he says. “I cheat.”

I raise an eyebrow and ask him for more details. He says that occasionally he secretly moves his ships on the board during the game.

For the few of you who may not know the rules of Battleship:

At the start of the game players secretly place five ships of different sizes on a 10x10 grid. They players then take turns calling out a grid coordinate, with the opponent saying whether it hits (marked with red peg) or misses (marked with a white peg). When all the spots of a ship are filled, you announce that it is sunk. First player to sink all their opponent’s ships wins the game.

I pressed my friend, and learn his cheating takes a very specific form:

• He keeps track of all the opponent guesses - misses as well as hits. On the image above, the player is only tracking hits on their lower grid. He tracks misses as well.

• When the opponent calls out a coordinate, he truthfully says whether it is a hit or a miss.

• Occasionally, as the mood strikes him, if a ship has not been hit, he moves it to a new position that the opponent has not yet targeted. This is why he tracks both hits and misses.

• Once one of his ships is hit, he doesn’t move it. It is locked into place.

Reaction 1: Sounds like a way to win!

My first reaction to his explanation, setting aside the moral implications, was that this was a devious approach. By tracking where your opponent already went, and pinning damage ships in place, the opponent would not know that you were moving your ships (unless they physically caught you). They couldn’t tell from in-game actions.

But then I thought about it again, and realized:

Reaction 2: This makes no difference

Moving ships that have not been hit to places that have not been targeted should have no effect on the game.

As an analogy, let’s say I’ve got a deck of cards. Each turn I draw a random card. If it’s the Ace of Spades, I win.

Let’s say you decide to ‘cheat’ to make it harder for me to win by secretly moving the Ace to a different position in the deck after each of my turns. Or maybe you just shuffle the deck.

Either way, this in no way impacts my chance of drawing the Ace.

This is related to one of my pet peeves - Blackjack players who think you messed up their game if you didn’t hit or stand when they thought you should.

For those of you that have not run into this type of lovely person before; If you’re playing blackjack and, for example, take a hit when you they think you should not, they berate you not because you are messing up your own chances to win, but because you’re messing up theirs. They claim that the card you took was ‘due’ for them or the dealer. Similarly, if you stand and don’t take a card when they think you should, then they or the dealer gets it instead, they will berate you for that.

This is, of course, poppycock. I have literally, because I am fun, gotten into arguments with people at the blackjack table over this. Every card is equally likely to be drawn from a shuffled deck. It doesn’t change your chances of winning or losing in any way because another player decides to hit or stand. Absolutely none.

Battleship is similar. Your chances of hitting a ship are random. So if the ship gets moved in between turns, it doesn’t make a difference. You still have the same chance at getting a hit.

My friend was cheating for nothing. I told him that, and tried to explain the math behind it, but he was adamant that his strategy will give him an edge.

And so, we set up the Battleship for Bourbon Bet. We will both be in Las Vegas for the Consumer Electronics Show in January, and we plan to have a series of Battleship games where he is allowed to use this method of cheating, while I will play by the rules.

Loser buys the winner a bourbon. Mainly because of the alliteration.

Battleship Strategy

After the bet is agreed to, I start thinking about strategies for Battleship, and doing a little research online. As expected, many before me have plumbed these depths.

Let’s take a look at some hunting strategies:

Completely Random

The completely naive strategy is just to randomly choose a target space each turn, regardless of what has happened before. This is obviously not a great strategy. Once you get a hit you have a huge piece of information that you should act on, leading us to…

Seek and Destroy

In this strategy you hunt randomly, but once you get a hit, you target left/right/up/down until you find the direction of the ship and completely sink it.

I would hazard a guess that this strategy is the one that most people use.

Polarity

Each ship in Battleship covers at least two spaces. This can help you narrow your search a bit.

Imagine that the grid is colored in like a black and white checkerboard. Every ship must be on at least one black square and one white square.

So you can restrict your selections to just one of the two colors. This isn’t a huge difference over a random Search and Destroy strategy, but it does help to optimize your search.

Heat Map

This is the most sophisticated strategy, and to take full advantage of it you would have to use a computer.

Imagine that at the start of the game you have a list of all the possible positions that your opponent could have chosen for their ships. I didn’t check the math, but this site claims there are about 30 trillion ways to place them.

So it’s a long list.

After every guess, whether it’s a hit or a miss, that rules out some number of possible ship locations.

For your next move you can look at all the remaining positions and determine the space that has a ship in the largest number of positions. That would then be your guess.

The result of that guess, then rules out more positions, and so on.

Each round, in essence you generate what is called a ‘heat map’ of possible ship locations and guess a space that is the ‘hottest’, and most likely to be part of a ship.

As an example, take a look at this position. Assume this is the entire board, and you’re just looking for a 3-square ship:

There are five possible places that the 3-square ship could be:

The ‘heat’ of each square is the number of ship positions that theoretically could be there. Here’s what that looks like:

The optimal strategy in this case is to pick one of the ‘2’ spaces. That scores a hit 40% of the time. The ‘1’ spaces are a hit 20% of the time.

As you can imagine, generating these heat maps in your head during an actual game is not really feasible.

However, we can boil it down into a heuristic, a rule of thumb. In general, the most open areas will have the highest heat values, and you should concentrate on spaces within the largest square that fits into that area.

You can see that with the areas above - the 8-space empty spot is the largest area, and the 2x2 square within there is the best place to target.

Reaction 3: Wait - Am I Wrong?

So how does my friend’s cheating method impact these strategies?

Completely Random: No Impact. This is equivalent to the ‘deck of cards’ metaphor I presented earlier

Seek and Destroy: No Impact. Since you can’t move a ship once it’s hit, this reverts back to Completely Random.

Polarity: No Impact. Since every ship must cover both a black and white square, you can’t reposition a ship to make this less likely to work.

Heat Map: Yes! Moving your ship actually does make this strategy less effective. If my friend has the situation at the top, then they can move their ship to the 3-square slot on the left, knowing that my strategy will be to aim at one of the ‘2-heat’ spaces on the right.

If the cheater is also keeping a heat map of their situation, they can move their ships to the locations with the lowest heat value. I believe that this makes the ‘heat map’ strategy actually less effective than the Polarity strategy under these conditions.

Doublethink

However, our bet is not being conducted under the conditions where I don’t know the other player is cheating. I do know that my friend is cheating in this manner, so how does that impact what I do?

If I just use my rule of thumb from the heat map strategy, that means if I am faced with the situation above, I should guess a space in the large area - 4 out of 5 times the final ship will be located there. But my friend knows that, so he will move the ship to the area on the left.

But if I know that he knows that, then I should definitely pick the area on the left, as that is the obvious move that he should make.

As you might guess, we are getting into a classic Yomi situation here, which gives me an excuse to include the classic Iocaine Powder scene from The Princess Bride.

The Wager

So where does that leave the wager? Am I behind the eight ball here?

I think I’ll be fine, for several reasons. First, I would hazard a guess that my friend is not going to use the Heat Map strategy. He strikes me as a Seek and Destroy type. If I just do a Polarity I should have a slight edge over a Seek and Destroy.

Second, he knows that I know that he’s moving the ships. So I expect that I can play a psychological warfare game with him, and make him second-guess whether he should move the ships at all, or just move them sparingly. This will minimize the advantage he gains over the Heat Map strategy.

So either way I think each game should be pretty darn close to a coin flip.

The last reason I’ll be fine: In the absolute worst case I will have had a fun time playing a game with my friend over a couple of bourbons, a privilege I am happy to pay for!

Setup Strategies

I haven’t even begun to explore setup strategies. Are you better off near the edge? Putting your ships far apart? Close together?

This is firmly in the realm of psychology of course, but I’m curious - do you have a favorite starting setup? Or any good Battleship stories in general? Let me know in the comments!