3
$\begingroup$

Mason is improving at the game Battleship. He's got this current game in the bag, or so he thinks.

His opponent is Richard, whose method for placing his ships is completely random. Each side has 5 ships, and they reach the position below, where it is Mason's turn and Mason has sunk all of Richard's ships except for his Carrier, which is 5 units long. Richard has sunk only 2 of Mason's ships.

The board is 10x10, and all ships must be fully on the board and placed either horizontally or vertically. The green H's represent ships that Mason has already sunk. The red M's represent his misses.

enter image description here

For the question, you can assume that Mason will win.

If Mason plays optimally, in how many moves can he guarantee victory? Also, can you explain your answer so that the vast majority of those reading it will understand it?

$\endgroup$
5
$\begingroup$

The max I've found is winning within

8 shots:

There are only 4 "spots" where the ship could be:

B3-B8 (6 spots)
E1-E8 (8 spots)
H4-H8 (5 spots)
A4-J4 (10 spots)

The highest concentration of spots is at E4, so check that.
If hit, you know it's along col-4 or row-E, so I would first check if it extends downward (F4). If hit, then we have at most 4 more shots (total 6).
If F4 is a miss, then I would check E5, since if it is horizontal, that's a guaranteed hit (Leftmost would be E1-E5, rightmost would be E4-E8). After that, it's up to 4 more moves (total 6).
If that is a miss, the only spot left is A4-E4, 4 more shots, 7 total.

If E4 is a miss, I would go H4 next. It hits 2 full spots where the ship could be (F4-J4, H4-H8). If it's a hit, spend a shot to figure out vert/horz, then 4 more to finish, total 7.

If H4 is a miss, the last place to be is at B3-B8. That will take up to 6 shots, 8 total.

$\endgroup$
  • $\begingroup$ Both of you have great answers. +1 for both of you. Since he was first and thoroughly answered the question, I will accept this answer. $\endgroup$ – JLee Mar 30 '15 at 20:09
  • $\begingroup$ I've added the hidden since that's a fair request. Honestly, you should mark the answer that makes the most sense to you. I like Reticality's diagrams, but not his logic flow. Ian is explicit for the full number of shots, whereas I give a slightly broader strategy and assume that the user can finish off a ship. $\endgroup$ – JonTheMon Mar 30 '15 at 20:09
4
$\begingroup$

The answer:

In the worst case, 8.
This has a $\frac1{13}$ chance of happening with my strategy. My strategy overall (Where $m$ is the moves it takes):
$$\ \\\begin{align}P(m<5)&=\ \ 0\\P(m=5)&=\frac1{13}\\P(m=6)&=\frac5{13}\\P(m=7)&=\frac6{13}\\P(m=8)&=\frac1{13}\\P(m>8)&=\ \ 0\end{align}$$

First you want to ignore the spaces who have less than 5 spaces above/below and left/right. After all, if there aren't 5 spaces, how is there going to be a 5 unit long battleship?

Battleships_possible

Then, you want to hit the intersections of those pathways where the battleship could be to see which line the battleship is in, in this order, stopping when you hit a battleship:

Move_here

(Numbers in brackets denote moves taken to win)

If you hit 1 (E4):

- Go for E5.
- - If it hits, you are sure it is in the row E. Use this process of elimination:
- - - Go for E3, E2 and E1 until you miss or win.
- - - Go for E6, E7 and E8 until you win. (Maximum 6 turns)
- - If it misses, you are sure the ship is in the 4 column.
- - - Go for D4, C4, B4 and A4 until you miss or win.
- - - Go for F4, G4, H4 and I4 until you win.

If you hit 2 (B4):

- Part of the battleship is B4 to B7 (As all other rows and the 4 column are blocked off with the new knowledge that E4 is a miss)
- Go for B3.
- - If it hits, you won. (6)
- - Else B8 then you won. (7)

If you hit 3 (H4):

- Go for H5 (To check if the ship is the H row or the 4 column).
- - If you hit, the battleship is H4 to H8. (7)
- - If you don't, the battleship is F4 to J4 (8)

$\endgroup$
  • $\begingroup$ Generally Battleship coordinates are expressed as letter number, like E1 instead of (1, E). $\endgroup$ – Joe Z. Mar 30 '15 at 19:23
3
$\begingroup$

He is guaranteed victory in

8 moves. There are 8 possible scenarios, with shot totals of 5, 6, 6, 7, 6, 7, 7, 8. They are all described below.

Since the carrier has not yet been hit, we know that it must be in one of the spaces that are at least 5 squares long.

His first shot $S_1$ is:

E4
This overlaps with a carrier sitting vertically somewhere in the range A4-I4 or horizontally somewhere in the range E1-E8.

If it's a hit, his second shot $S_{2,1}$ is:

E5
A hit on E5 means that the carrier is positioned horizontally. His next shots extend to the right starting with E6.
If his next three shots all hit, he has sunk the carrier using 5 shots.
If one of his shots to the right misses, he begins shooting left starting with E3. The carrier will have been sunk using 6 shots.

If $S_{2,1}$ is a miss, his third shot $S_{3,1}$ is:

D4 and then continuing up the grid.
A miss on E5 means the carrier is vertical.
If these four vertical shots all hit, the carrier has been sunk using 6 shots.
If one of the shots misses, he fires at F4 and continues downwards until the carrier is sunk in a total of 7 shots.

In the event that $S_1$ misses, his second shot $S_{2,2}$ will be:

B4
In the event of a hit, we know the carrier is horizontal. If it were vertical, $S_1$ would have also hit the carrier. 4 more shots to the right will sink the carrier in 6 shots.
If the final shot misses, one shot fired at B3 sinks the carrier bringing our total to 7 shots.

In the event that $S_{2,2}$ also misses, his third shot $S_{3,2}$ will be guaranteed to hit at:

H4
Here, we might be hitting a vertical carrier (F4-J4) or a horizontal carrier (H4-H8).
Testing H5 $S_4$ will determine the orientation.
If $S_4$ is a hit, three more shots at H5-H8 will sink the carrier in a total of 7 shots.
If $S_4$ is a miss, we know the carrier is positioned vertically. The carrier will be sunk by the remaining shots F4, G4, I4, J4; a total of 8 shots.

$\endgroup$

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.