Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It only takes a minute to sign up.
Sign up to join this community
In the game of Battleship what are the best strategies to
Please also provide an explanation for your strategies. TIA
The rules are:
The strategy for placing follows from the optimal strategy for shooting, so let's start with shooting.
To shoot, do the following:
Start in a random part of the board. Go to step 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.
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:
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).
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.
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.
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 . .
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.
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.
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.
Note: I am not suggesting where to start on the board, just the pattern to follow.
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.
