odds/probability of identical board setup in Battleship
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 4
 Joined: Mon Nov 05, 2012 6:30 pm UTC
odds/probability of identical board setup in Battleship
Hello, numbers gods.
I need someone to calculate the odds of two people (in this scenario they are drunk, though I don't know that matters for the math) setting up exactly identical Battleship game boards with no foreknowledge of their opponent's tactics. And you know, obviously without cheating.
This really happened to me back in 2006. Once I figured it out I won, but the real winning can happen today with your help! Please explain your answer. I'd figure all this out myself if I a) had the game to go from and b) more than an elementary grasp of mathematics.
Please and thank you!
<3 Adeleine
P.S. Extra points for converting odds to probability. Cheers!
I need someone to calculate the odds of two people (in this scenario they are drunk, though I don't know that matters for the math) setting up exactly identical Battleship game boards with no foreknowledge of their opponent's tactics. And you know, obviously without cheating.
This really happened to me back in 2006. Once I figured it out I won, but the real winning can happen today with your help! Please explain your answer. I'd figure all this out myself if I a) had the game to go from and b) more than an elementary grasp of mathematics.
Please and thank you!
<3 Adeleine
P.S. Extra points for converting odds to probability. Cheers!

 Posts: 4
 Joined: Mon Nov 05, 2012 6:30 pm UTC
Re: odds/probability of identical board setup in Battleship
...
Last edited by sweetadeleiiine on Fri Nov 09, 2012 4:27 pm UTC, edited 1 time in total.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
What is the size of a standard battleship board? What are the ship sizes?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: odds/probability of identical board setup in Battleship
A battleship board is 10x10, and the lengths of the five ships are 5/4/3/3/2 and can be arranged either horizontally or vertically. (One of the 3 ships is a submarine and the other a destroyer  I would presume that the OP considers them to be indistinguishable.)
 dudiobugtron
 Posts: 1098
 Joined: Mon Jul 30, 2012 9:14 am UTC
 Location: The Outlier
Re: odds/probability of identical board setup in Battleship
Assuming the ships can overlap (which I know they can't) would make the problem much easier.
There are 120 ways to arrange the carrier, 140 ways to arrange the battleship, 160 ways to arrange the submarine and the destroyer, and 180 to arrange the crappy little tug boat.
So the chance would be one in 120*140*160*160*180
= 1 in 77,414,400,000
= 1 in 80 billion approx
(Or a 0.0000000000129% chance)
Mirrored setups count as different in this case as well. Also this counts the submarine and destroyer as distinct; just (approximately) halve it if they're not.
This assumes there can be overlaps. (Like this)
The actual probability will be lower (higher!) than this, since there cant be overlaps, but because there are a large number of cases I am daunted by the task! It would probably be easier to write a computer program which generates them all, then then count them.

Of course, especially since they are both drunk, the coincidence was likely due to both players using the same 'amazingseeming' setup strategy...
There are 120 ways to arrange the carrier, 140 ways to arrange the battleship, 160 ways to arrange the submarine and the destroyer, and 180 to arrange the crappy little tug boat.
So the chance would be one in 120*140*160*160*180
= 1 in 77,414,400,000
= 1 in 80 billion approx
(Or a 0.0000000000129% chance)
Mirrored setups count as different in this case as well. Also this counts the submarine and destroyer as distinct; just (approximately) halve it if they're not.
This assumes there can be overlaps. (Like this)
The actual probability will be lower (higher!) than this, since there cant be overlaps, but because there are a large number of cases I am daunted by the task! It would probably be easier to write a computer program which generates them all, then then count them.

Of course, especially since they are both drunk, the coincidence was likely due to both players using the same 'amazingseeming' setup strategy...
Re: odds/probability of identical board setup in Battleship
It is a very, very small probability, given that the two people are selecting the positions of the ships uniformly at random.
The probability of two battleship configurations chosen uniformly at random being identical is 1/c, where c is the number of possible battleship configurations.
Calculating c is rather tricky, because the possible position of the ships depends on the position of the other ships. I think perhaps it would be simplest to write a computer program to do this one.
/me opens IDLE
The probability of two battleship configurations chosen uniformly at random being identical is 1/c, where c is the number of possible battleship configurations.
Calculating c is rather tricky, because the possible position of the ships depends on the position of the other ships. I think perhaps it would be simplest to write a computer program to do this one.
/me opens IDLE
Blue, blue, blue
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
Yes, it was easiest to write a computer program... were people really thinking of solving it any other way??
And then
This is assuming that the two length 3 are different. If they're the same, then its half that. So, if you pick a setup, then I have a 1 in 103860 chance of picking the same setup. Its a 1/103860 chance for that to happen.
You'd have to play 71990 times for that it to be more likely than not that it happens. That's a lot of battleship.
Edit: the program logic looks good, but I'd appreciate some confirmation... pls? Seems quite a bit lower than I'd've guessed.
Edit2: if you think about it, a ship has four orientations (heading north, south, east or west), which would make the total number of placements
32 * 103860 = 3323520.
Code: Select all
class Ship(object):
""" where a ship is, its length and how its oriented."""
def __init__(self, x, y, length, orientation):
self.x = x
self.y = y
self.length = length
self.orientation = orientation
def occupies(self):
"""work out all the places the ship takes up"""
if self.orientation == 'h':
return set( [ (self.x + i, self.y) for i in range(self.length) ])
elif self.orientation == 'v':
return set( [ (self.x, self.y + i) for i in range(self.length) ])
class Board(object):
""" keeps track of vacant positions, and placed ships"""
def __init__(self):
self.vacant = set([ (x, y) for x in range(10) for y in range(10)])
self.ships = []
def possibleplacements(self, length):
"""Given a length, returns a set of all ships with that length that
can be placed."""
places = []
for (x, y) in self.vacant:
hship = Ship(x, y, length, 'h')
vship = Ship(x, y, length, 'v')
if hship.occupies() <= self.vacant:
places.append(hship)
if vship.occupies() <= self.vacant:
places.append(vship)
return set(places)
def placeship(self, ship):
"""places a ship and updates .vacant"""
self.ships.append(ship)
self.vacant.difference(ship.occupies())
def popship(self):
"""removes last placed ship and updates .vacant"""
ship = self.ships.pop()
self.vacant.union(ship.occupies())
def howmanysetups( shiplengths = [2, 3, 3, 4, 5], thisboard = Board() ):
"""how many ways can ships with shiplenghts be placed on thisboard"""
if len(shiplengths) == 1:
return len( thisboard.possibleplacements(shiplengths[0]) )
else:
thislength = shiplengths.pop()
setups = 0
for ship in thisboard.possibleplacements(thislength):
thisboard.placeship(ship)
setups += howmanysetups( shiplengths, thisboard )
thisboard.popship()
return setups
And then
Code: Select all
>>> battleship.howmanysetups()
103860
This is assuming that the two length 3 are different. If they're the same, then its half that. So, if you pick a setup, then I have a 1 in 103860 chance of picking the same setup. Its a 1/103860 chance for that to happen.
You'd have to play 71990 times for that it to be more likely than not that it happens. That's a lot of battleship.
Edit: the program logic looks good, but I'd appreciate some confirmation... pls? Seems quite a bit lower than I'd've guessed.
Edit2: if you think about it, a ship has four orientations (heading north, south, east or west), which would make the total number of placements
32 * 103860 = 3323520.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 phlip
 Restorer of Worlds
 Posts: 7542
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: odds/probability of identical board setup in Battleship
I suppose that's something that would need clarification from the OP:
If you take a setup, pick up the two threelength boats and swap them over, does that count as the same setup?
If you take a setup, pick up one of the boats, spin it around through 180 degrees, and put it back where it was but facing the other way, does that count as the same setup?
I've seen this game played both with and without a rule that two ships cannot be neighbouring  ie that there must be a buffer of empty spaces around each ship. Are you playing with this rule? If so, can two ships be touching each other on a corner, ie occupying squares that neighbour each other diagonally? Or is that out too?
If you take a setup, pick up the two threelength boats and swap them over, does that count as the same setup?
If you take a setup, pick up one of the boats, spin it around through 180 degrees, and put it back where it was but facing the other way, does that count as the same setup?
I've seen this game played both with and without a rule that two ships cannot be neighbouring  ie that there must be a buffer of empty spaces around each ship. Are you playing with this rule? If so, can two ships be touching each other on a corner, ie occupying squares that neighbour each other diagonally? Or is that out too?
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 gmalivuk
 GNU Terry Pratchett
 Posts: 25740
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: odds/probability of identical board setup in Battleship
I would assume that the important sense of "same setup" is that the same grid squares are hits in both setups.
 eta oin shrdlu
 Posts: 449
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: odds/probability of identical board setup in Battleship
This is clearly way too low. For a trivial lower bound, consider just placements in which each ship is oriented horizontally in its own row. There are then 10!/5! choices of rows for the ships, and 6*7*8*8*9 ways to place the five ships in their rows, for a lower bound of 731566080. (Divide by 2 if the two length3 ships are indistinguishable.)jestingrabbit wrote:
This is assuming that the two length 3 are different. If they're the same, then its half that. So, if you pick a setup, then I have a 1 in 103860 chance of picking the same setup. Its a 1/103860 chance for that to happen.
You'd have to play 71990 times for that it to be more likely than not that it happens. That's a lot of battleship.
Edit: the program logic looks good, but I'd appreciate some confirmation... pls? Seems quite a bit lower than I'd've guessed.
Edit2: if you think about it, a ship has four orientations (heading north, south, east or west), which would make the total number of placements
32 * 103860 = 3323520.
A substantially better lower bound comes by just bounding the number of placements each previouslyplaced ship can eliminate. An alreadyplaced ship of length m can eliminate at most (n+1)(m+1)2 of the 20(10n+1) placements for a ship of length n. Placing the ships in order 5, 4, 3, 3, 2, then, there are 120 placements for the 5; at least 14028=112 for the 4; at least 1602218=120 for the first 3; at least 160221814=106 for the second 3; and 18016131010=131 for the 2. So this gives a lower bound 120*112*120*106*131=22395340800 (again assuming all ships distinguishable).
Note that both of these lower bounds are on ship configurations, not just on filled grid squares; there are obviously some sets of grid squares which can be covered in multiple ways by the given ships, but these are relatively rare and so won't affect the order of magnitude of the bounds.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
Yeah, that code is wrong. This is better, but I'm not sure if its right yet.
I've set it running, its not finished yet. Its also going to be wildly slow because its all sets...
Code: Select all
class Ship(object):
""" where a ship is, its length and how its oriented."""
def __init__(self, x, y, length, orientation):
self.x = x
self.y = y
self.length = length
self.orientation = orientation
def occupies(self):
"""work out all the places the ship takes up"""
if self.orientation == 'h':
return [ (self.x + i, self.y) for i in range(self.length) ]
elif self.orientation == 'v':
return [ (self.x, self.y + i) for i in range(self.length) ]
def otherend(self):
if self.orientation == 'h':
return ( self.x + self.length  1 , self.y )
else:
return ( self.x , self.y + self.length  1 )
def shipclash( tryship , placedship ):
if tryship.orientation == placedship.orientation:
orientation = tryship.orientation
if orientation == 'h' and tryship.y == placedship.y:
if tryship.otherend()[0] < placedship.x or \
placedship.otherend()[0] < tryship.x:
return False, tryship.x + 1
else:
return True, placedship.otherend()[0] + 1
elif orientation == 'v' and tryship.x == placedship.x:
if tryship.otherend()[1] < placedship.y or \
placedship.otherend()[1] < tryship.y:
return False, tryship.y + 1
else:
return True, placedship.otherend()[1] + 1
else:
if orientation == 'h':
return False, tryship.x + 1
else:
return False, tryship.y + 1
else:
tryorientation = tryship.orientation
if tryorientation == 'h':
if placedship.y <= tryship.y <= placedship.otherend()[1] and \
tryship.x <= placedship.x <= tryship.otherend()[0]:
return True, placedship.x + 1
else:
return False, tryship.x + 1
elif tryorientation == 'v':
if placedship.x <= tryship.x <= placedship.otherend()[0] and \
tryship.y <= placedship.y <= tryship.otherend()[1]:
return True, placedship.y + 1
else:
return False, tryship.y + 1
def howmanysetups( unplacedlengths = [5, 4, 3, 3, 2], placedships = [] ):
"""how many ways can ships with shiplenghts be placed on thisboard"""
if unplacedlengths == []:
return 1
elif placedships == [] and unplacedlengths[0] == 5:
length = unplacedlengths[0]
otherlengths = unplacedlengths[1:]
setups = 0
orientation = 'h'
for x in range(3):
for y in range(5):
ship = Ship(x, y, length, orientation)
setups += howmanysetups(otherlengths, [ship])
print setups
return setups
else:
length = unplacedlengths[0]
otherlengths = unplacedlengths[1:]
setups = 0
orientation = 'h'
y = 0
while y < 10:
x = 0
while x < 10  length + 1:
ship = Ship(x, y, length, orientation)
newx = x + 1
flag = False
for s in placedships:
flag, newx = shipclash(ship, s)
if flag:
break
if not flag:
setups += howmanysetups(otherlengths, placedships+[ship])
x = newx
y += 1
orientation = 'v'
x = 0
while x < 10:
y = 0
while y < 10  length + 1:
ship = Ship(x, y, length, orientation)
newy = y + 1
flag = False
for s in placedships:
flag, newy = shipclash(ship, s)
if flag:
break
if not flag:
setups += howmanysetups(otherlengths, placedships+[ship])
y = newy
x += 1
if len(placedships)< 3:
print setups
return setups
I've set it running, its not finished yet. Its also going to be wildly slow because its all sets...
Last edited by jestingrabbit on Thu Nov 08, 2012 12:01 pm UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Xanthir
 My HERO!!!
 Posts: 5203
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: odds/probability of identical board setup in Battleship
gmalivuk wrote:I would assume that the important sense of "same setup" is that the same grid squares are hits in both setups.
This is a different condition than what everyone has been operating on, assuming normal Battleship rules, because, for example, a patrol boat + submarine endtoend looks the same as the battleship.
It offers up potential for interesting optimizations to the search algorithm, though  you can encode a given setup as a 100bit bitfield, or stash it in a 128bit integer.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
I've completely rewritten my code and I'm estimating that its going to take hours to execute. I doubt that that other stuff will finish before the obama administration and possibly not before the heat death of the universe. It was bad code I tells ya, bad. Here's some better code, but its still not great.
There's superfluous prints in there just so that you know something is happening. But, its 20s between prints, or so, and there are about 15 * 140 prints, which makes it a bit less than half a day to finish. When it does, you have to multiply the result by 8.
Edit: looks like the answer is going to be less than 37 billion.
Edit2: a fifth of the way through, its looking to be less than 30 billion.
Code: Select all
class Ship(object):
""" where a ship is, its length and how its oriented."""
def __init__(self, x, y, length, orientation):
self.x = x
self.y = y
self.length = length
self.orientation = orientation
def occupies(self):
"""work out all the places the ship takes up"""
if self.orientation == 'h':
return [ (self.x + i, self.y) for i in range(self.length) ]
elif self.orientation == 'v':
return [ (self.x, self.y + i) for i in range(self.length) ]
def otherend(self):
if self.orientation == 'h':
return ( self.x + self.length  1 , self.y )
else:
return ( self.x , self.y + self.length  1 )
def shipclash( tryship , placedship ):
if tryship.orientation == placedship.orientation:
orientation = tryship.orientation
if orientation == 'h' and tryship.y == placedship.y:
if tryship.otherend()[0] < placedship.x or \
placedship.otherend()[0] < tryship.x:
return False, tryship.x + 1
else:
return True, placedship.otherend()[0] + 1
elif orientation == 'v' and tryship.x == placedship.x:
if tryship.otherend()[1] < placedship.y or \
placedship.otherend()[1] < tryship.y:
return False, tryship.y + 1
else:
return True, placedship.otherend()[1] + 1
else:
if orientation == 'h':
return False, tryship.x + 1
else:
return False, tryship.y + 1
else:
tryorientation = tryship.orientation
if tryorientation == 'h':
if placedship.y <= tryship.y <= placedship.otherend()[1] and \
tryship.x <= placedship.x <= tryship.otherend()[0]:
return True, placedship.x + 1
else:
return False, tryship.x + 1
elif tryorientation == 'v':
if placedship.x <= tryship.x <= placedship.otherend()[0] and \
tryship.y <= placedship.y <= tryship.otherend()[1]:
return True, placedship.y + 1
else:
return False, tryship.y + 1
def howmanysetups( unplacedlengths = [5, 4, 3, 3, 2], placedships = [] ):
"""how many ways can ships with shiplenghts be placed on thisboard"""
if unplacedlengths == []:
return 1
elif placedships == []:
length = unplacedlengths[0]
otherlengths = unplacedlengths[1:]
setups = 0
orientation = 'h'
for x in range(3):
for y in range(5):
ship = Ship(x, y, length, orientation)
setups += howmanysetups(otherlengths, [ship])
print setups
return 8*setups
else:
length = unplacedlengths[0]
otherlengths = unplacedlengths[1:]
setups = 0
orientation = 'h'
y = 0
while y < 10:
x = 0
while x < 10  length + 1:
ship = Ship(x, y, length, orientation)
newx = x + 1
flag = False
for s in placedships:
flag, newx = shipclash(ship, s)
if flag:
break
if not flag:
setups += howmanysetups(otherlengths, placedships+[ship])
x = newx
y += 1
orientation = 'v'
x = 0
while x < 10:
y = 0
while y < 10  length + 1:
ship = Ship(x, y, length, orientation)
newy = y + 1
flag = False
for s in placedships:
flag, newy = shipclash(ship, s)
if flag:
break
if not flag:
setups += howmanysetups(otherlengths, placedships+[ship])
y = newy
x += 1
if len(placedships)< 3:
print setups
return setups
There's superfluous prints in there just so that you know something is happening. But, its 20s between prints, or so, and there are about 15 * 140 prints, which makes it a bit less than half a day to finish. When it does, you have to multiply the result by 8.
Edit: looks like the answer is going to be less than 37 billion.
Edit2: a fifth of the way through, its looking to be less than 30 billion.
Last edited by jestingrabbit on Thu Nov 08, 2012 12:04 pm UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: odds/probability of identical board setup in Battleship
From the german Wikipedia page "Schiffe_versenken" (I'm not allowed to post links yet):
Translation:
For a game with 1 ship of length 5, 2 ships of length 4, 3 ships of length 3, 4 ships of lenth 2 there are exactly 26509655816984 different setups.
Game rules: 10x10 board, no ships may touch each other
The probability for two setups to be exactly the same is then 1 : 26509655816984
Edit: corrected result, thanks jaap!
Bei einem Spiel mit einem Schiff der Länge 5, zwei Schiffen der Länge 4, drei Schiffen der Länge 3 und vier Schiffen der Länge 2 gibt es genau 26.509.655.816.984 (also ungefähr 26,5 Billionen) Möglichkeiten, die Schiffe aufzustellen.
Translation:
For a game with 1 ship of length 5, 2 ships of length 4, 3 ships of length 3, 4 ships of lenth 2 there are exactly 26509655816984 different setups.
Game rules: 10x10 board, no ships may touch each other
The probability for two setups to be exactly the same is then 1 : 26509655816984
Edit: corrected result, thanks jaap!
Last edited by csiko on Thu Nov 08, 2012 11:23 am UTC, edited 1 time in total.
Re: odds/probability of identical board setup in Battleship
csiko wrote:For a game with 1 ship of length 5, 2 ships of length 4, 3 ships of length 3, 4 ships of lenth 2 there are exactly 26509655816984 different setups.
The probability for two setups to be exactly the same is then 1 : 702761851534953628502856256
No, the probability that the second person will choose the the same setup as the first will then be 1/26509655816984. Yours is the probability that two people both randomly choose the particular setup I'm thinking of right now.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
From the rather bizarrely existent battleship wikia,
http://battleship.wikia.com/wiki/Battle ... %29#Trivia
there's an unsourced claim that there are 1,925,751,392 different configurations, with indistinguishable length 3s. That seems low. It would mean that 1/20 or so of the placements with possible overlap (ie 120*140*160*160*180/2 = 38707200000) have no overlap.
Currently, my code is saying that its more like two fifths that have no overlap, and that if you place the 5 along the top row, flush with the corner, and the 4 in the same row next to it, you have 2,713,430 configurations for the 3, 3 and 2, but if you move the 4 over one spot, you end up with 2,711,216 configurations. If someone could just check those two things it would be some sort of confirmation that my code is logically correct.
http://battleship.wikia.com/wiki/Battle ... %29#Trivia
there's an unsourced claim that there are 1,925,751,392 different configurations, with indistinguishable length 3s. That seems low. It would mean that 1/20 or so of the placements with possible overlap (ie 120*140*160*160*180/2 = 38707200000) have no overlap.
Currently, my code is saying that its more like two fifths that have no overlap, and that if you place the 5 along the top row, flush with the corner, and the 4 in the same row next to it, you have 2,713,430 configurations for the 3, 3 and 2, but if you move the 4 over one spot, you end up with 2,711,216 configurations. If someone could just check those two things it would be some sort of confirmation that my code is logically correct.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: odds/probability of identical board setup in Battleship
jestingrabbit wrote:From the rather bizarrely existent battleship wikia,
http://battleship.wikia.com/wiki/Battle ... %29#Trivia
there's an unsourced claim that there are 1,925,751,392 different configurations, with indistinguishable length 3s. That seems low.
The source for that may be one of the answers to this mathoverflow post (which includes Haskell source code).
Further answers can be found in the table found here, which also has the (same?) Haskell source code.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
jaap wrote:jestingrabbit wrote:From the rather bizarrely existent battleship wikia,
http://battleship.wikia.com/wiki/Battle ... %29#Trivia
there's an unsourced claim that there are 1,925,751,392 different configurations, with indistinguishable length 3s. That seems low.
The source for that may be one of the answers to this mathoverflow post (which includes Haskell source code).
Further answers can be found in the table found here, which also has the (same?) Haskell source code.
That's a lot of code in a language I'm not really familiar with, and eta oin shrdlu provides a transparent refutation of its conclusion.
What's more, the second number there is wrong. Placing a 2, there are 8 ways to put it in a corner which blocks 4 moves, 28 ways to place it along a side which blocks 5, 32 ways to place it perpendicular to a side which blocks 6 moves, and 112 ways to play in the middle that each block 7 moves ie there are (8*176 + 28 * 175 + 32 * 174 + 112 * 173)/2 = 15626 ways to place 2 indistinguishable 2s, and the page says there are 13952. That's a big discrepancy on a small problem...
I've got about an hour left on my program, and I'd estimate that its going to come up with a value near 30 billion for distinct length 3s.
Last edited by jestingrabbit on Thu Nov 08, 2012 11:27 am UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
And my code just finished, and its given the answer as
30,093,975,536
for distinct 3s. A lot more than the 2 billion that the mathoverflow suggests, but it seems like I can't downvote until I've got a certain amount of ewang over there, and I can't even work out how to comment lemmings' post.
I also get
which agrees with my by hand calculation.
30,093,975,536
for distinct 3s. A lot more than the 2 billion that the mathoverflow suggests, but it seems like I can't downvote until I've got a certain amount of ewang over there, and I can't even work out how to comment lemmings' post.
I also get
Code: Select all
>>> battleships2.howmanysetups( [2, 2], [] )
<snip>
31252
which agrees with my by hand calculation.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: odds/probability of identical board setup in Battleship
jestingrabbit wrote:And my code just finished, and its given the answer as
30,093,975,536
for distinct 3s.
My program confirms your answer.
C# Code:
Spoiler:
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
And I expect that yours took minutes to execute rather than hours
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: odds/probability of identical board setup in Battleship
jestingrabbit wrote:And I expect that yours took minutes to execute rather than hours :oops:
About 3 minutes on a highend pc.
 dudiobugtron
 Posts: 1098
 Joined: Mon Jul 30, 2012 9:14 am UTC
 Location: The Outlier
Re: odds/probability of identical board setup in Battleship
sweetadeleiiine wrote:Hello, numbers gods.
I need someone to calculate the odds of two people (in this scenario they are drunk, though I don't know that matters for the math) setting up exactly identical Battleship game boards with no foreknowledge of their opponent's tactics. And you know, obviously without cheating.
This really happened to me back in 2006. Once I figured it out I won, but the real winning can happen today with your help! Please explain your answer. I'd figure all this out myself if I a) had the game to go from and b) more than an elementary grasp of mathematics.
Please and thank you!
<3 Adeleine
P.S. Extra points for converting odds to probability. Cheers!
@OP: In case you missed it in all the conversation, the answer to your question is:
Odds of two people choosing the same setup:
1 in 30,093,975,536
(or 1 in 30 billion.)
Probability of this happening:
0.00000000332 % (3sf)
Credit goes to jestingrabbit and jaap.
Re: odds/probability of identical board setup in Battleship
I wrote a different program to solve this problem, and got the following results:
Note that ships of the same length are considered to be equal, so here the result for the standard number of ships (1,2,1,1) is half what we calculated before.
Code: Select all
Ships : Patterns
2 3 4 5

0 0 0 0 : 1
0 0 0 1 : 120
0 0 1 0 : 140
0 0 1 1 : 14400
0 1 0 0 : 160
0 1 0 1 : 17040
0 1 1 0 : 20336
0 1 1 1 : 1850736
0 2 0 0 : 11884
0 2 0 1 : 1119936
0 2 1 0 : 1367720
0 2 1 1 : 109786464
1 0 0 0 : 180
1 0 0 1 : 19840
1 0 1 0 : 23532
1 0 1 1 : 2216256
1 1 0 0 : 27336
1 1 0 1 : 2667272
1 1 1 0 : 3237624
1 1 1 1 : 269056552
1 2 0 0 : 1924020
1 2 0 1 : 165673320
1 2 1 0 : 205885084
1 2 1 1 : 15046987768
2 0 0 0 : 15626
2 0 0 1 : 1579056
2 0 1 0 : 1904748
2 0 1 1 : 163929000
2 1 0 0 : 2249848
2 1 0 1 : 200730096
2 1 1 0 : 247911400
2 1 1 1 : 18772683816
2 2 0 0 : 149875428
2 2 0 1 : 11767281448
2 2 1 0 : 14886380364
2 2 1 1 : 988321903552
Note that ships of the same length are considered to be equal, so here the result for the standard number of ships (1,2,1,1) is half what we calculated before.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
I think I worked out what's going on with the "erroneous" numbers that are floating around.
If the ruleset forces that ships not collide and not be adjacent, neither horizontally vertically nor diagonally, then for the problem of placing two ships that are distinguishable I get
which is what the table says. So, those other numbers are, I expect, right, but for a different set of rules.
If the ruleset forces that ships not collide and not be adjacent, neither horizontally vertically nor diagonally, then for the problem of placing two ships that are distinguishable I get
Code: Select all
>>> battleship.howmanysetups([2, 2], thisboard = battleship.Board(nodiagonaladjacency = True) )
27904
>>> 27904/2
13952.0
which is what the table says. So, those other numbers are, I expect, right, but for a different set of rules.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 4
 Joined: Mon Nov 05, 2012 6:30 pm UTC
Re: odds/probability of identical board setup in Battleship
Wow. I thought I was subscribed to this topic but I guess not. Thanks so much y'all!
Just to clarify, the setups were exactly the same, and we did not use the original rules.
We placed some ships directly next to each other if we wanted to, and we did all manner of placements except diagonal and there was no overlapping.
When I say we had identical setups, the ships that both contain three 'hits' cannot be the same. Our setups were in complete correspondence ship by ship, grid point by grid point.
So, what is the number based on this?
Pardon my html; I'm feeling frisky.
all appreciation!
Adeleine
Just to clarify, the setups were exactly the same, and we did not use the original rules.
We placed some ships directly next to each other if we wanted to, and we did all manner of placements except diagonal and there was no overlapping.
When I say we had identical setups, the ships that both contain three 'hits' cannot be the same. Our setups were in complete correspondence ship by ship, grid point by grid point.
So, what is the number based on this?
Pardon my html; I'm feeling frisky.
all appreciation!
Adeleine
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
sweetadeleiiine wrote:So, what is the number based on this?
That would be 30,093,975,536 and the probability is 1/30,093,975,536 for this event to occur.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: odds/probability of identical board setup in Battleship
jestingrabbit wrote:sweetadeleiiine wrote:So, what is the number based on this?
That would be 30,093,975,536 and the probability is 1/30,093,975,536 for this event to occur.
Errrm, that would be assuming that we choose Battleship setups uniformly, and I suspect we don't at all.
Re: odds/probability of identical board setup in Battleship
Tirian wrote:jestingrabbit wrote:sweetadeleiiine wrote:So, what is the number based on this?
That would be 30,093,975,536 and the probability is 1/30,093,975,536 for this event to occur.
Errrm, that would be assuming that we choose Battleship setups uniformly, and I suspect we don't at all.
Sure but what other assumption are you going to make? Anything else would need to be based on data which we don't really have.
double epsilon = .0000001;
Re: odds/probability of identical board setup in Battleship
Dason wrote:Tirian wrote:jestingrabbit wrote:sweetadeleiiine wrote:So, what is the number based on this?
That would be 30,093,975,536 and the probability is 1/30,093,975,536 for this event to occur.
Errrm, that would be assuming that we choose Battleship setups uniformly, and I suspect we don't at all.
Sure but what other assumption are you going to make? Anything else would need to be based on data which we don't really have.
I conjecture 1/30,093,975,536 is a lower bound on the probability. Humans tend to share specific tendencies when making "random" decisions. Even though we don't know what those specific tendencies are, I don't think it's at all a stretch to say that a human is more likely to set a board identical to one created by another human than to set a board identical to one of the 30 Billion possible board selected uniformly at random.
Blue, blue, blue
Re: odds/probability of identical board setup in Battleship
Dason wrote:Sure but what other assumption are you going to make? Anything else would need to be based on data which we don't really have.
I think we need to be upfront when our assumptions are so naive that they cause us to call into question the validity of the conclusion. And the fact is that amateur Battleships players (even sober ones) are typically reluctant to make ships adjacent. On the face, this strikes me as a rational decision  when someone hits your cruiser and shifts to a strategy of sinking it, the regret that would come from having another ship hit would be substantial AFAICT. (Indeed, when I read the official rules, I was surprised to see that you have to tell your opponent not just "hit" but which ship was hit.)
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: odds/probability of identical board setup in Battleship
I wouldn't know about that. One person might consider it prudent to place some ships adjacent for one reason or another: to leave more areas "bare", to go against the expectations of someone such as yourself, to make a pretty picture with the ships etc.
Also, the game can be played with a few pieces of paper and some pens. So to speak of official rules is kinda crazy imo. People agree their rules however they like. Should the number of shots per turn be 1, 3, or related to the number of surviving ships? If some shots hit, do you have to tell which ones? Are all the ships "straight" or can you agree on non straight ships (there is an indian variant with a 6 square, t shaped carrier). This is all up for grabs, and apart from single square ships making the game pointless, I think they all make for playable games. Acting like the "official" rules, made up by a corporation, through who knows what process, is absurd.
Also, the game can be played with a few pieces of paper and some pens. So to speak of official rules is kinda crazy imo. People agree their rules however they like. Should the number of shots per turn be 1, 3, or related to the number of surviving ships? If some shots hit, do you have to tell which ones? Are all the ships "straight" or can you agree on non straight ships (there is an indian variant with a 6 square, t shaped carrier). This is all up for grabs, and apart from single square ships making the game pointless, I think they all make for playable games. Acting like the "official" rules, made up by a corporation, through who knows what process, is absurd.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 dudiobugtron
 Posts: 1098
 Joined: Mon Jul 30, 2012 9:14 am UTC
 Location: The Outlier
Re: odds/probability of identical board setup in Battleship
undecim wrote:I conjecture 1/30,093,975,536 is a lower bound on the probability. Humans tend to share specific tendencies when making "random" decisions. Even though we don't know what those specific tendencies are, I don't think it's at all a stretch to say that a human is more likely to set a board identical to one created by another human than to set a board identical to one of the 30 Billion possible board selected uniformly at random.
Depending on the players, you could certainly get two people who had a lower chance than 1/30,093,975,536, if they were biased towards different types of setup. But overall you are likely right.
Re: odds/probability of identical board setup in Battleship
dudiobugtron wrote:undecim wrote:I conjecture 1/30,093,975,536 is a lower bound on the probability. Humans tend to share specific tendencies when making "random" decisions. Even though we don't know what those specific tendencies are, I don't think it's at all a stretch to say that a human is more likely to set a board identical to one created by another human than to set a board identical to one of the 30 Billion possible board selected uniformly at random.
Depending on the players, you could certainly get two people who had a lower chance than 1/30,093,975,536, if they were biased towards different types of setup. But overall you are likely right.
Agreed  for example, if one player always sets up his aircraft carrier along the top edge, while the other always puts it on the bottom edge.
On the other hand, two people in the same situation, who have probably, if not played each other, at least played in the same community of players, are likely to have similar ideas about the game  for example, whether targeting the main diagonal is stronger or weaker than other moves  which will tend to influence their patterns.
On the gripping hand, while, taken as an isolated incident observed by happenstance, my happening to pick out a pair of people playing battleships with identical layouts would be one chance in thirtybillion, this isn't the event we're discussing here  the actual event is that an xkcd forumposter had a sufficiently surprising event happen to them six years ago that they wanted to know just how unlikely it was. I would not be at all surprised to learn that more than thirty billion games of Battleships (with the 5,4,3,3,2 fleets on a 10*10 grid, ships unable to lie diagonally) have been played by now, so the surprise, if any, comes from it having been reported here specifically rather than elsewhere or not at all.
 gmalivuk
 GNU Terry Pratchett
 Posts: 25740
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: odds/probability of identical board setup in Battleship
Except that it is also an officially trademarked game sold by a particular company along with a particular set of rules. This isn't changed by your ability to play penandpaper variants of the game.jestingrabbit wrote:Also, the game can be played with a few pieces of paper and some pens. So to speak of official rules is kinda crazy imo.
Re: odds/probability of identical board setup in Battleship
Wow~ It's the first time going to this forum~
I have the same results as jestingrabbit~
This is actually part of my thesis (which I chose back in 2010) and I was trying to find a formula for the patterns~
Though my code is quite long and takes a few minutes to calculate~
I'm using C++ cause it's the only programming language I know~
I can post the source code after I'm done with my thesis~
I have the same results as jestingrabbit~
This is actually part of my thesis (which I chose back in 2010) and I was trying to find a formula for the patterns~
Though my code is quite long and takes a few minutes to calculate~
I'm using C++ cause it's the only programming language I know~
I can post the source code after I'm done with my thesis~

 Posts: 4
 Joined: Mon Nov 05, 2012 6:30 pm UTC
Re: odds/probability of identical board setup in Battleship
rmsgrey
I like what you say. more, por favor!
chibichen
yes please all
I like what you say. more, por favor!
chibichen
yes please all
Who is online
Users browsing this forum: No registered users and 16 guests