Battleship

In the game Battleship, what's the optimal way to choose targets in order to find the enemy ships fastest?

Not sure it is optimal, but I would go for spreading my shots so that the biggest ship could not escape, so in diagonal lines 4 apart (assuming the biggest ship is 5 long). If I was lucky enough to get smaller ships before I got it then that is even better. there may be a psychological way which takes into account where people are likely to put ships.

If I got the largest ship using the above method I suppose I would then close in on the next largest ship and so on.

Originally posted by deriver69
Not sure it is optimal, but I would go for spreading my shots so that the biggest ship could not escape, so in diagonal lines 4 apart (assuming the biggest ship is 5 long). If I was lucky enough to get smaller ships before I got it then that is even better. there may be a psychological way which takes into account where people are likely to put ships.

I ...[text shortened]... ship using the above method I suppose I would then close in on the next largest ship and so on.

I'd have to disagree and say go for the smaller ships first in a similar fashion, but also taking into account the corners and middle first. In that way, you don't have to retrace your steps looking for the 2-hit destroyer.

A lot depends on how long the longest ship is. To find every ship may require in its worse case every other square to be marked off. Each targetted square must therefore be part of a checkerboard pattern. I would still start off by spacing these further out then close in though hoping to get that 2 square one luckily.

I don't know if my strategy is optimal but I like to start near a corner and start playing Knight moves each time... 😛 It seems to do a decent job

this is a very interesting question... i haven't done much in terms of mathematics or trial and error concerning this problem, but i wanted to pose some ideas for consideration:

1) the strategy employed should work well against the common strategies and inherent "randomness" used in application of defensive placement of ships. what i mean here is that the strategy should work well both against spaced out ship placement, in all four quadrants, and against clustered ship placement in one particular area. This would seem to suggest some sort of mirroring idea whereby you don't lean towards one section of the board over another (i.e. first shot in top right quadrant, second a reflection to the lower left, next upper left and last lower right, for example.)

2) of course after getting a hit, one must attempt to sink that ship since the squares surrounding the initial hit will very likely result in a hit. this may even uncover additional ships if ships are clustered

3) the average length of a ship in the game of battleship is (2 + 3 + 3 + 4 + 5) / 5 = 3.4 squares. this should be taken into account when placing subsequent "random" shots in a particular zone... i would space shots in such a way that they were 3 squares apart or 4 squares apart from a miss.

4) placement of ships along the edges is a common theme in defensive battleship play and perhaps these squares should be weighted more highly as likely places to find a ship?

5) .. much more game theoretic and optimizational ideas than i have probably even thought would be worth considering. questions must be answered such as "is each square on the board as likely to contain a ship as other squares?" "if i sink a ship, is it more likely that a ship would be nearby such as to conceal its position, or far away?" etc.

very interesting question!

Originally posted by deriver69
A lot depends on how long the longest ship is. To find every ship may require in its worse case every other square to be marked off. Each targetted square must therefore be part of a checkerboard pattern. I would still start off by spacing these further out then close in though hoping to get that 2 square one luckily.

this seems like it would be a sound strategy, if used in tandem with the mirroring idea i just mentioned... perhaps imagine a checkerboard lattice on the board, and fill it in using spaces from one of each quadrant, and then filling in 4x4 checkers before doing the interior 2x2 spaces? and hope to get lucky with the smaller ships? would be great to see some mathematics, given particular assumptions about ship placement (such as each square is equally likely to contain a boat as any other square... what is optimal then?)

Originally posted by Aetherael
this seems like it would be a sound strategy, if used in tandem with the mirroring idea i just mentioned... perhaps imagine a checkerboard lattice on the board, and fill it in using spaces from one of each quadrant, and then filling in 4x4 checkers before doing the interior 2x2 spaces? and hope to get lucky with the smaller ships? would be great to see s ...[text shortened]... as each square is equally likely to contain a boat as any other square... what is optimal then?)

It seems like a sound strategy, but the question posed is "what's the optimal way to choose targets in order to find the enemy ships fastest?"

The optimal way would have to be:

a. fastest
b. find ALL ships
c. repeatable results using the same method

The solution fails if you can not find all ships, and leaving it to luck to find the small ships would negate the optimization of the process.

This is why I mentioned going to every other square. In this way, nothing is left to luck.

Battleship being 10X10 square, there are 10 columns and 10 rows (think of it as an Excel grid, columns being letters, rows being numbers.) Means 100 possible squares. 17 occupied with ships. Even if you sink the first 4 ships in your first 15 guesses, that still leaves you with 2 in a possible 85 squares (assuming that the placement of the other ships do no negate squares by blocking off one empty square)

Choosing any squares with the permutations of (A,odd) (B,even) (C,odd) (D,even) etc. or vice versa randomly will reduce your chances available choices to 50. Now you are looking for 8 or 9 hits in 50 (8 or 9, because skipping every other square will cut the hits in half). Much better chances.

Also, once you get one hit, continue with the same process of every other square around that hit, (unless the 4 largest ships are sunk already) because the best bet is that you hit one of the larger ships any way and you want to find out what direction it is pointing in, vertical or horizontal. Once that is determined, you can fill in the blanks.

So, the maximum guesses we need are 50 plus 3 (3 misses trying to find the direction of the Destroyer, 2 hit ship).

Since, in the beginning, unless you have prior knowledge or suspicions of how your opponent will place them, each square is equally as likely as containing a ship. Skipping every other space randomly, until ships are known, is the fastest way to garuntee that all ships are found and is easily repeated.

Now, whether or not you win, is a different question. Luck is a huge factor, especially if both opponents employ the same strategy.🙂

Originally posted by brobluto
It seems like a sound strategy, but the question posed is "what's the optimal way to choose targets in order to find the enemy ships fastest?"

The optimal way would have to be:

a. fastest
b. find ALL ships
c. repeatable results using the same method

The solution fails if you can not find all ships, and leaving it to luck to find the small ships ...[text shortened]... ent question. Luck is a huge factor, especially if both opponents employ the same strategy.🙂

the only issue i have with this is that there will be many many games in which this method will require going to completion to find all of the ships... imagine a spread of ships all over the board - you would likely have to complete your entire algorithm for the average case where ships are as likely to be in the top left as they are to be in the bottom right quadrant of the board.

if we still use the "every other spot" lattice idea, but choose an algorithm that spreads out your selections in terms of choosing a coordinate from a spread out area around the board will likely improve our odds over the long run.

edit: i just understood what you meant by (A, odd) (B, even) etc. and i completely agree. i might suggest choosing each column to be either an even or an odd, and then making sure to spread out your choices as much as possible: i.e. - (B2, E5, H6, I3.. etc.) would be preferable to (A1, B2, C1, D2, E1, ... ) and moving in a "top down" fashion.

last note is that i think it's actually an interesting statement that "without any other knowledge, each square is equally likely to contain a ship as any other" and i would tend to disagree. true randomness is actually quite difficult for humans to "replicate" ... if you ask a person to "randomly" generate a list of heads and tails as if they were flipping a coin 100 times, people very rarely account for proper strings of heads and tails, often create an unintended pattern, and almost always choose 50 heads and 50 tails though that wasn't part of the exercise.

in other words, human beings like patterns. and symmetry. i think centralized squares, or perhaps squares within a circular band AROUND the center, but have no statistical evidence to back up my theory. in fact, some would likely choose squares along the perimeter as a defense tactic AGAINST this intuited "natural" inclination of the attacker towards the central squares. food for thought.

Originally posted by brobluto
It seems like a sound strategy, but the question posed is "what's the optimal way to choose targets in order to find the enemy ships fastest?"

The optimal way would have to be:

a. fastest
b. find ALL ships
c. repeatable results using the same method

The solution fails if you can not find all ships, and leaving it to luck to find the small ships ...[text shortened]... ent question. Luck is a huge factor, especially if both opponents employ the same strategy.🙂

Your objection to forementioned approach (checkerboard corners of a 5x5 square) is that it leaves alot to luck.

I don't see how your method is different. You immedeately start filling in the complete checkerboard pattern.

Your method works or course, but the first method has a built in chance of finding the 2-length ship with only 25 + 3 shots.

With luck, the first method is faster. Without luck it is just as good as your method.

and after posting that ridiculously long message, another thing occurred to me...

would it still be optimal to look at every other square after you've eliminated the destroyer? surely the checkerboard pattern could be beaten by an "every three" method by the same logic that now our smallest ship is of length 3?

i think maybe the pattern with which one should attack may more optimally be based on the average length of the ships still yet to be found... and clearly as you blow up the larger ships, your focus should get smaller and smaller (at first, on average the ships are of length 3.4.. but after blowing up the carrier, the average length of the ships is only 3. and removing the battleship makes the average ship length even smaller)

just an idea

A strategy:

The trickiest ships to find are obviiusly the 2 square and the 3 square.

Begin by hitting every 6th square. eg A2, A8, G2, G8

If you get lucky and hit the 2 square ship you convert this to an 'every third sq strategy' if not revert to the 'every second sq strategy'

Originally posted by Aetherael
and after posting that ridiculously long message, another thing occurred to me...

would it still be optimal to look at every other square after you've eliminated the destroyer? surely the checkerboard pattern could be beaten by an "every three" method by the same logic that now our smallest ship is of length 3?

i think maybe the pattern with which o ...[text shortened]... y 3. and removing the battleship makes the average ship length even smaller)

just an idea

You are correct. But the method would not take into account the average of the ships, but the smallest ship left.

every second square at the beginning
Once the Destroyer is found, every 3rd
Once the 2 3-shot ships are found, every 4th etc.


Every sixth is a strategy, but unless you hit the Destroyer by luck, you will have to double up with shots next to each other, thereby wasting moves.

Originally posted by strokem1
I don't know if my strategy is optimal but I like to start near a corner and start playing Knight moves each time... 😛 It seems to do a decent job

That would work but only until you have to go back over territory you've already covered. Then it becomes inefficient because you'll be hitting squares horizontally or vertically adjacent to other squares.

I like the checkerboard pattern. I don't think it matters what order you choose the squares as long as you stick to the checkerboard.

Last time I played, I placed the 5 space long aircraft carrier on an angle so that it went diagonal (4 holes sideways and 3 holes vertical). I won. My sister freaked! We haven't played since. Good old Pythagorus.