5

In the game of Battleship what are the best strategies to

  1. Place the ships
  2. Shoot other ships

Please also provide an explanation for your strategies. TIA

The rules are:

  • Both players place their ships on a 10x10 grid.
  • Ships have to be placed so that adjacent to a ship is only water.
  • Opponent's feedback on each shot is one of three : HIT, MISS or SUNK.
  • Each player have the following ships:
    • 1 ship of length 5
    • 2 ships of length 4
    • 3 ships of length 3
    • 4 ships of length 2
4
  • 4
    Is that standard? The Milton Bradley version has five ships total - one 5, one 4, two 3s, and one 2 Oct 2 at 14:31
  • You are right, I changed my question
    – Philip F.
    Oct 2 at 14:35
  • "The ships have to be placed so that adjacent to a ship is only water." Is this actually a rule in the paper version? That greatly limits the number of arrangements of a fleet. Or was it only that the ships couldn't overlap the same location?
    – ryanyuyu
    Oct 5 at 16:39
  • 1
    From what I understand, variants of the game differ in two aspects: (1) either ships can or can not be adjacent to each other, and (2) the amount of ships from each length.
    – Cohensius
    Oct 27 at 6:30
7

The strategy for placing follows from the optimal strategy for shooting, so let's start with shooting.

To shoot, do the following:

  1. Start in a random part of the board. Go to step 2.

  2. Check every N squares from where you started, where N is the smallest opponent ship remaining (N = 2 to start). If you already have an established search grid in another part of the board, you should use the same search grid in this part of the board. You should explore in a random direction each time you expand your search grid. If you don't hit, stay on step 2. If you do hit, go to step 3.

  3. Check the squares adjacent to the one you hit. Once you discover the direction of a ship, keep checking in that direction until you sink a ship. Once you sink a ship, go back to step 1. Note that there is a rare case where two ships can be parallel, so if you have two hits with misses on either side, check the other direction.

For example, with N = 3, you are trying to sweep a pattern like this:

X . . X . . X
. X . . X . .
. . X . . X .
X . . X . . X
. X . . X . .
. . X . . X .

This is the sparsest pattern (fewest number of total guesses) that is guaranteed to find all of their ships.

Given this, the best thing you can do when placing your ships is at random such that no two ships are touching (some variants of Battleship have this prohibited in the rules, but even if it is allowed, you shouldn't do it). The problem with ships touching each other is that when the opponent hits one of your ships, they will be checking around that hit to find the rest of the ship, and thus may find your abutting ship by accident.

Other advice for ship placement is only helpful if the opponent is searching sub-optimally, but here it is nonetheless:

  1. Place your ships far apart; in particular, make sure your three smallest ships are far apart. The simpler version of the systematic search involves starting in one area of the board and sweeping from there without ever resetting (a player would go from step 3 back to step 2 rather than to step 1). By placing your ships far apart you can nearly guarantee your opponent will have to search most of the board. Having the small ships far apart is particularly important to exploiting this behavior because sinking the small ships are the biggest boon to a searcher (once you have sunk all the ships of a certain size, you can increase the N of your search grid).

  2. Avoid the corner around 1A. Humans are bad at picking at random, so the 1A corner is the most likely place people will start searching.

  3. Put ships in a mixture of along the edges of the board and in the middle. Again exploiting the fact that humans are bad at picking at random, and will likely be exploring in a particular direction, either towards the edge or towards the middle, but not both.

  4. Put your ships in such a way that minimizes the number of diagonals that they share. This way, you maximize your chances of the opponent missing one of your ships if they try to do a wide sweep (such as N = 4) to start, requiring them to go over the entire board again. See below for an example, where the same ship placement of three small ships guarantees that at least one ship will be missed by an N = 4 sweep (@ = unhit ship, # = sunk ship, X = miss).

      1 2 3 4 5 6
     1 # # . . X . 
     2 . X . . @ X
     3 . . X . @ .
     4 . @ @ X . . 
     5 X . . . X .
     6 . X . . . X
    
       1 2 3 4 5 6
     1 # # . . . X 
     2 . . X . @ .
     3 . . . X @ .
     4 X @ @ . X . 
     5 . X . . . X
     6 . . X . . .
    
       1 2 3 4 5 6
     1 @ @ X . . . 
     2 . . . X # .
     3 X . . . # .
     4 . # # . . X 
     5 . . X . . .
     6 . . . X . .
    
15
  • 2
    The random walk feels correct to be as an answer, but it's not obvious why the step size should be the smallest ship remaining. It feels to me there's some value in going to a larger value because you could find a length-4 or length-5 ship quicker which then rules out a larger number of other potential squares, can you can always go back and "fill in the gaps" afterwards to find the length-2 ships. Oct 2 at 21:08
  • 3
    Agree with @PhilipKendall, There is a chance that you will hit all the 2-size ships before shooting all the N=2 places. For example, you can start with N=4: X . . . X if after that you still did not find all the 2-size ships, then fill the gaps: X . X . X
    – Cohensius
    Oct 3 at 7:25
  • 3
    @Zags's strategy minimize the number of shoots in the worst case scenario. However I think that there are better strategies to minimize the average case scenario.
    – Cohensius
    Oct 3 at 7:29
  • 1
    @Zags, The ships have to be placed so that adjacent to a ship is only water. So this part is redundant: "the best thing you can do when placing your ships is at random such that no two ships are touching. The problem with ships touching each other is that when the opponent hits one of your ships, they will be checking around that hit to find the rest of the ship, and thus may find your abutting ship by accident."
    – Cohensius
    Oct 3 at 7:32
  • 2
    I'm almost interested enough in this problem to start writing some simulations, but I've also got a bunch of IRL stuff going on, so... Oct 4 at 17:09
3

A strong algorithm for a slightly different set of rules:

Ships Can be placed next to each other.


DataGenetics wrote a fun piece about solving Battleship a few years ago. If their algorithm isn't optimal, it's at least extremely close. The author combined the concept of parity with probability density functions. That is, you only have to fire at every i'th square of the grid, where i depends on the size of the smallest ship. And as the number of shots increases, some spots are more likely to contain ships than others depending on how many rotation and translation-configurations of a certain ship is possible considering the space that is left.

I think it would be interesting to attempt to optimize fleet layout against their strategy. Maybe it's possible to lay out the ships in such a way that the probability density function gives the least amount of information for the maximum amount of rounds?

https://www.datagenetics.com/blog/december32011/

The paper compares 4 algorithms, running each algorithm 100M games.

  1. Random is just a (bad) base line, see that it has a probability of 17/100 to shot all the 100 places.
  2. No parity also called Hunt/Target plays random until it hits, then shoot next to hits.
  3. Parity do the same as #2 but also use Parity (as in the answer of @Zags (N = 2 to start))
  4. New algorithm is the winner and it shots in the following manner:

calculate the most probably location to fire at next based on a superposition of all possible locations the enemy ships could be in.

The following graph display number of turns distribution, we can see that in most games, the New algorithm sunk the opponent's ships in 30 to 60 turns. enter image description here

5
  • Could you put more details of the strategies into your answer so users don't have to visit the site to understand it. All answers should be self contained so if the link you use breaks the answer is still valid.
    – Joe W
    Oct 15 at 11:44
  • I independently found that article and didn't make reference to it because it has a number of flaws. Most importantly, their implementation of the "parity" strategy doesn't take into account whether or not a ship is sunk, and therefore wastes an incredible number of moves surrounding sunk ships with hits (and consequently ranks very poorly given this). Additionally, their proposed "new algorithm" requires a statistical analysis that cannot be reasonably performed by a human.
    – Zags
    Oct 15 at 15:09
  • @Zags, the flaw you are talking about is a matter of different rule set: The paper uses: "Ships Can be placed next to each other" While the OP ask about: "adjacent to a ship is only water."
    – Cohensius
    Oct 26 at 8:00
  • 1
    @Cohensius The article assumes ships can be placed adjacent. If that rule changes the analysis substantially, then the article is even less relevant to this question.
    – Zags
    Oct 26 at 14:56
  • 1
    @Zags, agreed, I think I should edit the answer to highlight the different set of rules. Never the less, the algorithms that the paper use are still valid (with a minor fix).
    – Cohensius
    Oct 27 at 6:12
3

I would say the optimal strategy for shooting is aiming to destroy the largest ships first in order to cover as much as the board as fast as possible. I would suggest starting out with a gap of 4 and move down as you sink the larger ships.

Below is an example of starting out with a gap of 3 between shots and filling it in later with a gap of 1 between shots.

X . . . X . .
. X . . . X .
. . X . . . X
. . . X . . .
X . . . X . .
. X . . . X .

X . O . X . O
. X . O . X .
O . X . O . X
. O . X . O .
X . O . X . O
. X . O . X .

I suggest this for several reasons.

  • You still have the possibility of hitting and sinking the smaller ships
  • If you start on the opposite side of the board from their ships you will waste a lot of time
  • You will cover the board much faster.
  • Starting by blocks of 4 lets you cover the entire board quickly and then come back and finish the board by filling in the gaps to rule out 5 positions with a single hit

Note: I am not suggesting where to start on the board, just the pattern to follow.

2
  • 1
    This strategy is easily defeated by placing your ships on different diagonals, especially if you have four 2-length ships as is in the question. Clever placement will guarantee that you will miss at least one small ship on your initial pass, requiring you to fill in all the rest of the board. Conversely, trying to find all the 2-length ships initially gets you to the point where you can safely increase the size of your search grid faster.
    – Zags
    Oct 5 at 15:34
  • @Zags sure it isn't perfect but yours has its flaws as well
    – Joe W
    Oct 5 at 16:56
-1

How to Win at battleships

There are two repeating phases in the game: Hunt and Kill.

In the Hunt phase you are trying to find ships. Since all ships occupy at least two contiguous squares, you only need to fire at every other square. If it was a checkerboard, you'd only fire on the red squares and not black, for example. Once you score a hit, go to the kill phase.

Kill phase obviously results in trying to figure out which way the ship points and where the ends are. In this case you fire immediately adjacent to the hit location. The rest you can figure out.

You can save some time by knowing which ships are still out there. If you have found the destroyer, you don't need to sample every other square, but rather every third, as the smallest ship will span at least three adjacent squares.

I'd start randomly firing off shots, but don't hunt in adjacent squares. Then you can fill in holes later after sinking a few ships and knowing which ones are still out there.

TL,DR; Every other square to find ships, then sink them.

1
  • This answer repeat @o2h2o answer. Also the link you provided is summarizing of the link provided by o2h2o answer. Both explain the work done by Nick Berry from DataGenetics.
    – Cohensius
    Oct 26 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.