Battleship is a game for two players. Each player has a 10×10 grid to place their ships. There are 5 different types of ships. The carrier, which is 5 squares long. The battleship, which is 4 squares long. The cruiser and submarine, both of which are 3 squares long. And the destroyer, which is just 2 squares long. Ships can be placed horizontally or vertically, but not diagonally.

You can’t see where your opponent put their ships. Players take turns picking a square on the opponent’s grid to shoot at. After each shot, you only find out if you missed or hit a ship. When you manage to hit all the squares of a ship, your opponent will tell you that their ship has sunk.

You don’t know where your opponent’s ships are, so you might wonder where to start with your first shot. Is there a good strategy or should you just shoot randomly? Well, there are 100 squares on the grid and only 17 of them contain a ship. So if you shoot randomly, without even paying attention to whether you hit or miss, on average you will sink all your opponent’s ships after around 95 shots. But your opponent will certainly do it faster, so we need to figure out a strategy.

We need to take advantage of the thing that we know after every shot if we hit a ship or missed. In a strategy called Hunt and Target, you start by shooting randomly. When you hit a ship, you know that one of the 4 squares around your hit also contains that ship. After another hit, you already know if the ship is placed horizontally or vertically. Keep shooting until you sink the ship. By using this strategy, you’ll on average sink all your opponent’s ships in around 66 shots.

But we can make it even better. The smallest ship in the game, Destroyer, occupies 2 squares. So that means you don’t have to shoot squares right next to each other. You can shoot every other square, like a checkerboard pattern. If you sink the Destroyer, the next smallest ship is 3 squares long. So then you only need to shoot every 3 squares. And once you’ve sunk all the ships that are 2 or 3 squares long, you can shoot every 4 squares. And if you know that your opponent only has a carrier left, you can shoot every 5 squares. By using this strategy, you’ll on average sink all your opponent’s ships in around 55 shots.

But we can create an even better strategy using probability. To make it simpler, let’s look at a 5×5 grid first. We know that there is a 3 square long submarine somewhere here. And these squares are empty. We want to figure out where to shoot next to have the best chance of hitting it.

We start with every square having a probability count of 0. The submarine can be placed here, so we add 1 to these 3 squares. It can be placed 1 square to the right, so we add 1 to these 3 squares. And we go through every possible position that the submarine can be placed in, and add 1 to the squares where it can fit. We pick the square with the highest probability and shoot it. If it’s a miss, we go through all possible submarine positions again, and update our probability map. If it’s a hit, we shoot the squares around to sink the ship. If the opponent has more ships, we calculate the probability maps for each ship and add them up. For example, these are the probability maps for destroyer, submarine, and carrier. After adding them, our overall probability map looks like this.

At the start of the game, when your opponent has all the ships, the probability map looks like this. More red squares mean there is a higher chance of finding a ship there. You begin by shooting somewhere in the middle. After each shot, you update the probability map based on what you’ve learned. When you hit a ship, you shoot around it to sink it. With this strategy, on average, you will sink all your opponent’s ships in only around 46 shots.