5

In a game of battleship, both players play in a 10x10 grid and have the following ships:

  • 1 ship of length 5
  • 2 ships of length 4
  • 3 ships of length 3
  • 4 ships of length 2

The ships have to be placed so that adjacent to a ship is only water.

What are the best strategies to

  1. Place the ships
  2. Shoot other ships

Please also provide an explanation for your strategies.

TIA

3
  • 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
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
4

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
0

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/ enter image description here

He compares 4 algorithms, running each algorithm 100M games.

  1. Random is just a (bad) base line, see that it has a 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 small letters / different set of rules:

  1. Ships Can be placed next to each other.
  2. Opponent's feedback on each shot: HIT, MISS or SUNK.
New contributor
o2h2o is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
2
  • 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
    19 hours ago
  • 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
    15 hours ago
0

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.

New contributor
Louis Zhan is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

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.