Odds of never missing in a game of Battleship

17 hits wins at Battleship. My mate and I were arguing which would be harder, never missing a single hit at Battleship (going 17 for 17) or winning the lottery. What are the odds of never missing your opponent at Battleship?

I'll take a whack at this, see if any of this math stuff is sinking in....

I think if you worded the question as "randomly selecting numbers" and never missing, it could be figured as (17/100)*(16/99)*(15/98)...etc and so on (assuming there's 100 spots, I can't remember for sure). The problem I have is Battleship is a strategy game, where if you get one hit, instead of selecting a random # out of the 99 left, you'd typically select only one number out of the 1-4 remaining spots adjacent to that hit. When it comes to figuring THAT mess out, or how you'd incorporate the fact that it may be a 2 hit PT boat or a 5 hit Carrier, I'm beyond out of my league.

I'd be interested if ME, Crystal, Wiz, Miplet, DG, or any other of our math genius' had an answer for this one.

Assume that your strategy is to hit a ship and then attempt to sink the ship.

Your odds of hitting the first ship is indeed 17/100. At that point, you usually have 4 choices as to which direction to go. But if the hit is on an edge, then you could have only 3 or 2 directions to go. And at the same time, if your hit is on the middle of the ship then you are only in 2 directions.

My ball park guess is about 1 million to one.

Face has the right formula - for completely blind / random hits.
It works out to 0.000000000000000000150372890040097 or 1 in 6,650,134,872,937,200,000.
Note that this is NOT an exact number. Excel rounded it.

One you start to consider strategy and edges, man it gets complex.

Quote: boymimbo

Assume that your strategy is to hit a ship and then attempt to sink the ship.

Your odds of hitting the first ship is indeed 17/100. At that point, you usually have 4 choices as to which direction to go. But if the hit is on an edge, then you could have only 3 or 2 directions to go. And at the same time, if your hit is on the middle of the ship then you are only in 2 directions.

My ball park guess is about 1 million to one.

The way I remember Battleship being played, if you had 17 rounds available, you did not get to fire one, see whether it hit a ship or not, and then fire again. You had to fire all 17 rounds and were told how many, if any, were hits -- you weren't even told which shots were hits. Am I remembering that correctly? If so, then the likelihood of the initial 17 rounds (with no feedback yet) hitting the exact 17 spots that contained ship parts would be the extremely low figure already quoted. (Haven't calculated it myself.)

Ten months ago, I made this post about Battleship in a thread discussing whether video poker games are all dealt randomly. I noted that my experience with an early version of video Battleship led to my continuing suspicion (justified or not) about the trustworthiness of video craps that I had seen in a tribal casino. That suspicion seems quite relevant these days in light of the various BLR/on-line craps threads.

I don't have much.

I looked at placing the single largest boat (5 hits). It has 120 ways to place it randomly on the board. If the placement is completely random, then the best first move is to select one of the four most inner squares. If that hits, then randomly select up/down/left/right. If that hits, then select the opposite direction. If that hits, the last two selections are 50/50. If you continue to hit spots and always make the best choice, then the probability of sinking the large boat with the first 5 hits is 1 in 1680.

Interesting question, but one that you will likely not get an answer to.

Quote: Doc

The way I remember Battleship being played, if you had 17 rounds available, you did not get to fire one, see whether it hit a ship or not, and then fire again. You had to fire all 17 rounds and were told how many, if any, were hits -- you weren't even told which shots were hits. Am I remembering that correctly? If so, then the likelihood of the initial 17 rounds (with no feedback yet) hitting the exact 17 spots that contained ship parts would be the extremely low figure already quoted. (Haven't calculated it myself.)

That's a good point - the rules really determine everything. I haven't played Battleship in ages, but I'm sure I remember having red pegs and white pegs and knowing whether a shot was a hit or miss after making it. "You sunk my Battleship!"

Computing the odds of an intelligent player (the hypothetical perfect logician) under that scenario is difficult, not only because of the choices available to the player but because of the strategy that may be used by the opponent. For example, I used to T two of my ships together. In other words, you can't assume the ships are placed randomly because that may not be optimal if the opponent is attempting to maximize your number of shots (which they are). So then you're into game theory...

Or, you could be playing against an alien intelligence. I have no idea what the odds of winning are there...

The rules as I remember them were that you got feedback on every shot. Call a position, and you got "miss, hit, sunk." You were NOT told what type of ship you hit or sunk.

Quote: MathExtremist

That's a good point - the rules really determine everything. I haven't played Battleship in ages, but I'm sure I remember having red pegs and white pegs and knowing whether a shot was a hit or miss after making it. "You sunk my Battleship!"

It's a very simple game:

You call out a square by using its coordinates. If you hit, you place a red peg on your board and, if memory serves, you keep going until you miss; your opponent places a red peg on the ship hit. If you miss, you place a white peg on your board and your turn is over; the opponent palces a white peg where the shot missed. Each ship is sunk when all the squares it occupies are hit. The first player to sink all the opponent's ships wins.

The problem, as usual, is the honesty of the players. I did know people who'd cheat at Battleship, Mastermind and Go Fish.

There are two ways I remember playing it. According to the official battleship rules from my trusted game downstairs:

Quote: Hasbro

It's a hit!

If you call out a shot location that is occupied by a ship on your opponent's ocean grid, your shot is a hit! Your opponent tells you which ship you have which ship you have hit (destroyer, submarine, etc.). Record your hit by placing a red peg in the corresponding target hole on your target grid.".

You get one shot per turn.

I've played two variants:

(1) you are not told what ship you hit, and/or
(2) after a hit, you are allowed to continue selection until you get a miss.

Quote: Nareed

The problem, as usual, is the honesty of the players. I did know people who'd cheat at Battleship, Mastermind and Go Fish.

[goad]Did they believe in God?[/goad]

I guess the rules you remember are likely dependent upon where/how you learned the game. My older brother and I were taught Battleship by our father, and we used quadrille paper ("graph" paper with 1/4" blocks). Each player drew two game box outlines and positioned our "ships" in one of them. The other box was for marking where we fired shots at the other player's ships.

In our game, I think there were five ships, with lengths ranging from one to five blocks. Each player had as many shots on a turn as he had un-hit blocks on his own ships, so the first player's initial volley was 15 shots. We marked the shots we took on the "opponent" game box, numbering them with the round number -- 1s for the first volley, 2s for the second, etc. After the first player fired a volley, the other player reported how many hits there were on each of his ships, then he fired his volley.

Under those rules, you could track were your full volley was aimed and which ships were hit, but you didn't know which shots hit which ship. You had to analyze the hits from each volley to try to figure out where the opponent's ships were positioned.

I remember my younger brother having a toy-store version of the game with pegs or markers or something. I don't remember the rules of that game, but I probably knew them back then. Later, I saw ads for an electronic version of the game, but I never saw it outside of a box. Maybe that was during the era when one of my kids might have played.

I do remember we laughed at the picture on the outside of the box for one of those games. It showed two boys playing the game, with one of them calling out the location of a shot. The other boy responded, "It's a hit!" (This seems to support the idea of immediate feedback, unlike the game my father taught us.) The amusing thing was you could see the board with the ship locations, and the co-ordinates for that shot did not hit any ship. Whoever did the cover graphics apparently did not understand the game!

deleted

deleted

There's Battleships the Movie coming out soon. Sigh.

The standard version I played was with 1 battleship (4 squares long) 2 Cruisers (3 squares), 3 Destroyers (2 squares) and 4 Submarines (1 square each). Turns were strictly you go/I go (Ugo-Igo).

I know of one variant where each ship had at least one gun placement and you got as many shots as gun placements, much as Doc describes.

Another was that all shots were fired in Salvo's of three, which had to be in a line. Again you'd be told number of hits and if you sank anything.

All ships had to have a clear space all the way around them (no touching, even diagonally)... this will reduce your number of shots and chances of hitting a perfect score of all hits no missed.

Battleships : Galaxies has also been released as a major revamping of the game. It has some of the hidden features of the original, but much more tactical in nature from what I've heard.

Quote: Ibeatyouraces

Strategy aside, cant you determine the odds of 17 straight hit as if you were betting a 17 out of 17 pick in keno with it having 100 numbers? Sure playing the game is different, but were talking about 17 random picks hitting.

This is what Face and DJTeddyBear calculated earlier. About 1 in 6.65 quintillion.

Quote: Ibeatyouraces

If you pick A1. you MUST chose B1 or A2. You cant keep both as a miss.

Again, it depends upon which rules for Battleship you are following. In the version I was taught by my father back in the early '50s, as described above, the smallest ship only covered one box. It would be possible to have that ship in position A1 and nothing in B1 or A2. If the rules you are considering only have ships larger than that, then I agree completely.

I think your "easier way" might be close. However (per the rules of my father's version of the game) I could have my 2-block ship end-to-end with my 3-block ship in the same position as your 5-block ship, or my 1-block and 3-block ships touching and in the same position as your 4-block ship. Thus, there are ways to cover the exact same coordinates without having the exact same ship layout. This might not work with other versions of the game -- I don't remember the ship sizes in those games.

deleted

The two versions I remember (I think both are in the original rules) are:
(a) Players alternate taking one shot at a time;
(b) "Salvo Battleship" - each player takes a number of shots equal to the number of ships the other player has remaining; each hit must have its ship identified (e.g. "B-6 was a hit on my submarine").

Thinking about this some more.

If you just consider all of the ways that each boat can be placed on the board independently, which would include overlapping boats, we can overestimate the number of unique boat placement patterns:

boat	size	unique placements
aircraft carrier	5	120
battleship	4	140
submarine	3	160
destroyer	3	160
patrol boat	2	180

The total number of possible placements (including overlapping boats for ease of calculation) = 120*140*160*160*180 / 2 = 38,707,200,000. I'm dividing by two because we don't care if the submarine and the destroyer are swapped.

I have also already determined that once you place the aircraft carrier, there are, on average, 120 places to put the battleship. So this reduces the total possibilities to an upper limit of 33,177,600,000 (120*120*160*160*180 / 2).

Without additional strategy, such as selecting spots adjacent to hits, the worst possible odds of hitting all 17 with 17 picks is 1 in 33,177,600,000. I think there's a chance that using perfect strategy could get the odds better than the powerball.

There are possible hits. So, one the first draw, the odds of a hit are 17/100.

At that point, you have a 1/5 chance that it's the battleship, a 1/5 chance that it's a destroyer, a 2/5 chance that it's a sub or frigate, and 1/5 chance that it's a tugboat.

-If it's a tugboat, you have a 1/4 chance that your next shot will be the hit sinking the ship.

-If it's a submarine or frigate, you first have a 2/3 chance that the ship is on an edge and therefore a 1/4 chance that your next shot will be a hit. After the 2nd hit, you have a 1/2 chance that your next shot will sink the ship. On the other hand, if you are the 1/3 middle shop, you have a 50% shot that the next shot will be a hit and another 50% shot that you will sink the ship.

-For a destroyer, 1/2 chance that the ship hit on an end.
-For a battleship, 2/5 chance that the ship hit is on an end.

So for the first ship hit, 17% chance of hitting, (20% * 25%) + 40% * ((2/3 * 1/4 * 1/2) + (1/3 * 1/2 * 1/2)) + 20% * ((1/2 * 1/4 * 1/2 * 1/2) + (1/2 * 1/2 * 1/2)) + 20% * ((2/5 * 1/4 * 1/2 * 1/2 * 1/2) + (3/5 * 1/2 * 1/2 * 1/2 * 1/2))

This gives me a (17% * .157917)= .026846 chance of sinking my first ship without any misses. This is ignoring any boundary conditions (the fact that the ship is bordering an edge or another ship).

After the 1st ship is sunk I'll have a 20% chance of 15/98, 40% of 14/97, 20% of 13/96, and 20% of 12/95 left.
Add it all together and the odds of a 2nd hit on my second ship is .140691 * .026846 = .003777

After two ships, the odds of sinking two ships in a row is about .000596 (using .157917) as a factor.

So, after all of this I'm going to revise the odds to about 10,000,000 to 1.

Battleships where you can place ships adjacent is like 6:5 Blackjack. Sure it looks like the same game, but it just isn't :)

Quote: roony672

17 hits wins at Battleship. My mate and I were arguing which would be harder, never missing a single hit at Battleship (going 17 for 17) or winning the lottery. What are the odds of never missing your opponent at Battleship?

There is not enough information provided.
1. Will the placer of the batlleships be done at random? Or will the placer try and make it difficult?
2. Will the shooter have to announce all 17 shots at once, or shoot one at a time? If all 17 at once I am sure there is someone who can figure it out.
If not, then strategy in both placing the ships and shooting at them will make the answer unsolvable.

Quick math would say this is very similar to keno.

20 out of 20 out of 80 = 3.5 billion billion to 1.

I asked my unix box for the answer.

[2.20-/softdev/source] > bc
scale=99
a=(1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17)
a
355687428096000
b=(18*19*20*21*22*23*24*25*26*27*28*29*30*31*32*33*34*35*36*37*38*39*40)
c=(41*42*43*44*45*46*47*48*49*50*51*52*53*54*55*56*57*58*59*60)
d=(61*62*63*64*65*66*67*68*69*70*71*72*73*74*75*76*77*78*79*80)
e=(81*82*83*84*85*86*87*88*89*90*91*92*93*94*95*96*97*98*99*100)
f=b*c*d*e
f
26238266543048976361450768383434109693249889888956583299647758123055\
09774584920717887341946885961783168463991997208555683840000000000000\
00000000
g=f/a
g
73767764813906413749646930628844166943344564493281739236205759727834\
2511784732494558114871608611228852372373504000000000000000000.000000\
00000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000


and without division
scale=99

b=(2*19*2*21*2*23*2*25*2*27*2*29*2*31*2*33*2*35*6*37*38*39*10)
c=(41*42*43*44*45*46*47*48*49*10*51*52*53*54*55*56*57*58*59*10)
d=(61*62*63*64*65*66*67*68*69*10*71*72*73*74*75*76*77*78*79*10)
e=(81*82*83*84*85*86*87*88*89*90*91*92*93*94*95*96*97*98*99*100)
b
10834710698718466560000
c
339944897204613461881314754560000
d
153590673962987334080971304140800000
e
1303995018204712451095685346159820800000
f=b*c*d*e
f
73767764813906413749646930628844166943344564493281739236205759727834\
2511784732494558114871608611228852372373504000000000000000000

NEVER GOING TO HAPPEN.............