20
$\begingroup$

Mason likes the game Battleship, but he doesn't win much. However, Sherry, his opponent, is so confident in her skill and luck that she has agreed to let Mason have his five friends help him.

Sherry's method for placing her ships is completely random. Each side has 5 ships, and they reach the position below, where Mason has sunk all of Sherry's ships except for her Battleship, which is 4 units long.

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

Each of Mason's friends want to help, but they cannot seem to agree on the best move. Clair insists on F2, but Mike is sure about H2. Bartholomew recommends D8 and Jessica tells him to play G6. Lastly, Pat says to play D5.

Put his friends in order from "Best Advice" to "Worst Advice". Did one of them find the best move?

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ Nice to see a new game coming onto the site! I created a tag for battleship, since I don't think you have enough rep to create tags. $\endgroup$
    – Rand al'Thor
    Mar 24, 2015 at 21:39
  • 2
    $\begingroup$ @Micah The hits and misses are irrelevant to the puzzle. You can simply treat them all as "positions already tried that didn't hit the 4 space battleship". If anything, it's a distraction, which is why none of the answers discuss already hit ships. $\endgroup$
    – Adam Davis
    Mar 25, 2015 at 14:18
  • 1
    $\begingroup$ Having played lots of battleship, I can say the proposed method of solution to solve the puzzle is not correct. Psychology of the opponent is more reliable. $\endgroup$
    – Joshua
    Mar 25, 2015 at 16:01
  • 2
    $\begingroup$ @Joshua I think so too, so I included a phrase when I created the question to combat that: "Sherry's method for placing her ships is completely random." $\endgroup$
    – JLee
    Mar 25, 2015 at 16:14
  • $\begingroup$ @AdamDavis: While not a factor for this particular arrangement, hits and misses--and even the sequencing thereof--could be relevant if hits were not 100% accounted for by sunk ships; house rule variations could also play a role. For example, if one plays that a person is told "hit and sunk" without being told what was sunk, then the above map could have the battleship at b10-e10 (already sunk) and the carrier at a6-a10 (with one hit). $\endgroup$
    – supercat
    Mar 25, 2015 at 22:15

5 Answers 5

Reset to default
18
$\begingroup$

D5 covers 4 locations

D8 covers 3

F2 covers 2

H2 covers 1

G6 covers 0

E5 is the best; it covers 5 locations.

Improve this answer
$\endgroup$
15
  • 6
    $\begingroup$ This is clearly the right reasoning if your goal is to hit something next turn. It's less clear that it's correct if you have a different goal. e.g. it's easy to see that, except for G6, there isn't any difference between the options if your goal is "win four turns from now", since that requires a guess of the exact location of the battleship. (I also assume that all places for the battleship are equally likely) $\endgroup$
    – user1502
    Mar 25, 2015 at 2:20
  • 5
    $\begingroup$ What "best" means is rather vague; I thought it worth explicitly pointing out. It is not uncommon for people to mean "the play that gives me the best chance of winning", but do an analysis for something only loosely related to that goal, such as the odds of scoring a hit immediately. (also, conditional probability can be rather unintuitive; I wanted to just assume it works out the way we hope it would, and felt compelled to document the fact I assume) $\endgroup$
    – user1502
    Mar 25, 2015 at 2:27
  • 3
    $\begingroup$ @Hurkyl: Consider what happens if E5 does not result in a hit but a miss: You would have eliminated those 5 locations from future consideration. $\endgroup$
    – DevSolar
    Mar 25, 2015 at 12:02
  • 6
    $\begingroup$ I agree with Hurkyl. Consider this image where red=miss. Using the heuristic "play the move that covers the most ship locations," you would play at A. If you play at A, then it may take four moves worst case to locate the battleship. But if you don't play at A, there is a way to get a sure hit in three moves! (Can you see it?) It is not clear which move is better; presumably it depends on how close your opponent is to winning. $\endgroup$
    – Lopsy
    Mar 25, 2015 at 14:19
  • 1
    $\begingroup$ @Mooing Duck And thus was born the idea for your first question on the site. And I'm not being sarcastic. There aren't many Battleship questions, so you make one with that twist. I'd try to solve it. $\endgroup$
    – JLee
    Mar 25, 2015 at 19:02
22
$\begingroup$

The "best" move for this puzzle is the one most likely to hit the ship in one shot, as the puzzle doesn't allow for further follow up shots. There are 23 possible positions for that ship, and 68 spaces where a shot could be placed.

Due to the size of the ship and previously placed shots, we can find both where shots cannot possibly hit the ship, and places for shots which cover more than one position.

For instance, G6 cannot hit the ship because previous shots placed at G4, G7, F6, and I6 would have most certainly hit that ship given that the ship is four spaces long. So G6 could not result in a hit.

Taking F2 as an example, there are 5 spaces in a vertical column where shots have not previously been placed. A 4 length ship could exist in the four top spaces, or four bottom spaces, and F2 covers both possibilities. Thus, F2 would hit 2 out of those 21 possible ship positions, giving you a 8.7% chance of hitting the ship.

If we perform this analysis for every possible shot we can take, we can find how many positions each shot could cover:

Image of battleship board with each available space filled with the number of positions it covers

We find then that the best space for a shot which covers the most of the 21 available positions is E5, covering 5 positions, and having a 22% chance of hitting the ship. This is not among the suggestions the friends made, though. Their shots rank as follows, from best to worst:

Space   Positions    Probability
D5      4            17%
D8      3            13%
F2      2             8.7%
H2      1             4.3%
G6      0             0.0%

Once E5 is taken you've removed 5 possible locations, leaving 18 if it didn't hit the ship:

Image of battleship board with each available space filled with the number of positions it covers after another shot on E5

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ It's not clear if your first sentence is a definition of the word best, or if you're trying to assert something by it. $\endgroup$
    – user1502
    Mar 25, 2015 at 15:27
  • 2
    $\begingroup$ +1 Very well-explained. Hurkyl has brought up an excellent point though, in the comments of the accepted answer. Consider the usual case where your opponent cannot win within the next few moves. Then, it is likely that the "best" move would be based on a strategy that looks at, for example, the 3 shots that will cover the most squares. Sometimes the "best" single shot will be one of those 3, but not necessarily (consider Lopsy's image). $\endgroup$
    – JLee
    Mar 25, 2015 at 16:34
  • 1
    $\begingroup$ @Hurkyl I've altered the sentence to be more specific, and removed following irrelevant shots. Continuing the game was interesting to me, but ultimately irrelevant to the puzzle as presented and, as you suggested, muddied the definition of "best". $\endgroup$
    – Adam Davis
    Mar 25, 2015 at 17:48
  • 2
    $\begingroup$ @JLee You are right, thanks for pointing out the comments elsewhere. As the puzzle is presented considering only one move ahead (ie, each didn't suggest a sequence of moves, just one) then I'm taking the path where we assume he wants to maximize his possibility of finding the ship in only one move. As it turns out, the answer is still the same even if you look ahead for two additional moves, but since there's no upper limit to that analysis (do we look at the next 3, 5, or 10 best moves?) then it seems reasonable to address just the one move he is about to take. $\endgroup$
    – Adam Davis
    Mar 25, 2015 at 17:52
  • 1
    $\begingroup$ @Adam Davis Yes, all that sounds good, and it was my intention to consider the best single move when creating the puzzle, so I could have phrased the question better, avoiding the use of the word "best", but I just wanted to point out (after reading Hurkyl's comments) that the single-move solution wouldn't necessarily be the "best" move. $\endgroup$
    – JLee
    Mar 25, 2015 at 17:59
5
$\begingroup$

Based on the number of possible eliminations:

D8 covers 3 possible battleship locations (Bartholomew)

F2 covers 2 possible battleship locations, and also follows a more spread out pattern of ships (Clair)

D5 covers 2 possible battleship locations but leaves open a third, D6-D9 (Pat)

H2 covers 1 possible battleship location (Mike)

And Jessica is obviously on Sherry's team, since G6 covers 0 possible battleship locations.

Tip of the hat to @JonTheMon, I would have also recommended E5.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Did you get your D5 and D8 reversed? $\endgroup$
    – JonTheMon
    Mar 24, 2015 at 21:56
  • $\begingroup$ No. D8 does cover 3 possible locations. A8-D8, D5-D8, and D6-D10. I went back and forth on D8/F2 being number 2... $\endgroup$
    – Brian Robbins
    Mar 24, 2015 at 21:58
  • $\begingroup$ Ah, right, I see what you're getting at. $\endgroup$
    – JonTheMon
    Mar 24, 2015 at 21:59
3
$\begingroup$

Since some of the locations overlap, it may be better to look at how many squares can be eliminated by each guess. The end result will be somewhat different.

A miss on F2 eliminates the following other squares from contention: D2, E2, G2, and H2.

For H2, it doesn't eliminate any other squares

D8 also eliminates B8, C8, D6, D7, D9

G6 technically eliminates itself, but it already wasn't an option

D5, although it eliminates a lot of potential battleship positions, only actually takes 1 other spot out of the running - C2. All the other spots are still possible battleship locations in another configuration.

So by this metric, D8 is the best of the 5 guesses, potentially eliminating itself plus 5 other squares. That's followed by F2, then H2 and D5 tied, and G6 in last.

I'm interested to hear people's opinions on which of the two metrics are "best". To me, the potential flaw in looking at it from the number of ship locations that a spot is part of is that some spots are part of other potential locations too. So guessing D5 doesn't help you as much with regard to B5 because B5 could still be part of the ship.

Also, by this measure, E5 eliminates 4 additional spots - C5, E4, E6, E7, so not as good as D8.

Improve this answer
$\endgroup$
2
  • $\begingroup$ E5 is the better choice. $\endgroup$
    – Tony Ennis
    Mar 24, 2015 at 23:53
  • $\begingroup$ There's no point in eliminating squares. You're interested in eliminating positions the battleship can be in. The more positions it could hit the better--hence E5. $\endgroup$
    – Loren Pechtel
    Mar 25, 2015 at 3:34
3
$\begingroup$

I'd say the order from best to worst is

D5 - Covers a total of 3 placements and 9 spaces of the board where the ship could be. Also a slightly better shape (3 bars of a +)
D8 - Covers 2 placements and 8 spaces
F2 - 1 placement, 5 spaces
H2 - 1 placement, 4 spaces
G6 - There is no chance that the last ship is in this square, there is no segment going through this square that is 4 long.

And the best move I'd say is E5, since that hits up to 3 positions and gets 10 spaces of coverage.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.