2
$\begingroup$

Consider a 10 x 10 Battleship grid that hides a single ship of length = 3. This ship can be placed vertically or horizontally in any of the 100 cells. The problem is to get the 10 x 10 probability matrix that maps the best cells to shoot (higher probability to hit the ship).

My first idea was to loop through each cell, and if the ship can be placed in that cell, increment this cell in the probability matrix. With the problem stated above, this approach gives a probability of 0.01 for each cell

Then i consider the following: if a generate all the possible board positions for this ship and perform a "intersection sum" of all these boards, i get a very different result from the method above. In the problem stated above, this method tells that the cells in the center are the best to shoot.

In the mathematical sense, what is the difference between these two methods? The image shows the heat map using the second method. Thanks!

heat map for ship of length 3

1 Answers 1

4

Your first method counts whether the ship can be placed in the square, but not the number of different ways it can be placed there. The ship of length 3 can be placed so as to cover any square, but there are only two ways to wedge it into the corner (one horizontal and one vertical) whereas there are six ways to get it to cover a square in the middle of the board (three each horizontal and vertical).

  • 3
    Note that there is some real game theory here. If your opponent knows your strategy, they will tend to place their ships in the safest places.2012-05-14