Is there a rule to have a better chance for winning battleship?

Question

The game Battleship is played with a 10 by 10 field. There are ships in different sizes.

• one 5 sizer
• one 4 sizer
• two 3 sizer
• one 2 sizer

Is there a rule to have a higher chance hitting the other ships?

Answer 1

Interesting question!

I don't know if you can come up with an analytical answer, but you could definitely get estimate of the probability that a particular element (Letter and number combo) of the board will contain a "hit" (i.e., some part of a ship).

Here's an approach that would allow you to get this answer for each turn of the game all in one fell swoop:

1. Write a program that will pick a random point on the board (for the location of the end of the vessel), a random vessel, and a random orientation (North, South, East, West) and then try to place the vessel on the board.
2. If the placement is valid, remove the vessel from the list and record which cells (letter x number) contain that vessel.
3. Repeat Steps 1 and 2 until you are out of vessels.
4. Store the board configuration as a matrix with (0) for "does not contain part of a vessel" and (1) for "contains part of a vessel".
5. Repeat steps 1 - 4 a lot of times (say 1k - 5k), saving each board configuration matrix.

Once you have this, you can ask questions such as this:

1. First move: Add up all the matrices (element-wise) and divide by the number of matrices. The resulting matrix will tell you the probability of getting a "hit" at that location.
2. On subsequent moves, filter the matrices so that they have vessels where you have confirmed hits and don't have vessels where you have confirmed misses. Re-calculate the probability as in (1) but with the filtered set. This will approximate the probability of getting a hit on each cell given what you know already from previous turns.

Of course, your opponent might get a little suspicious when you keep checking a computer, but I'm guessing one could run the simulations a ton of times, store the data as a small iPhone app, and then you'd be in business.

Have fun!

PS: One caveat is that this assumes people place boats randomly. I'm guessing people actually have some strategy sometimes (maximize spread, make unexpected shapes on board, etc) but perhaps the variety of strategies effectively reduces to random choice when you consider all possible strategies. Also, as you collect more information, only some strategies will be consistent with the information you are collecting, so it may partially adjust for this anyway.