odds/probability of identical board setup in Battleship

[sweetadeleiiine]

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!

[sweetadeleiiine]

...

[jestingrabbit]

What is the size of a standard battleship board? What are the ship sizes?

[Tirian]

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]

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 'amazing-seeming' setup strategy...

[undecim]

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

[jestingrabbit]

Yes, it was easiest to write a computer program... were people really thinking of solving it any other way??

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.

[phlip]

I suppose that's something that would need clarification from the OP:
If you take a setup, pick up the two three-length 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?

[gmalivuk]

I would assume that the important sense of "same setup" is that the same grid squares are hits in both setups.

[eta oin shrdlu]

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.

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 length-3 ships are indistinguishable.)

A substantially better lower bound comes by just bounding the number of placements each previously-placed ship can eliminate. An already-placed ship of length m can eliminate at most (n+1)(m+1)-2 of the 20(10-n+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 140-28=112 for the 4; at least 160-22-18=120 for the first 3; at least 160-22-18-14=106 for the second 3; and 180-16-13-10-10=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]

Yeah, that code is wrong. This is better, but I'm not sure if its right yet.

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...

[Xanthir]

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 end-to-end 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 100-bit bitfield, or stash it in a 128-bit integer.

[jestingrabbit]

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.

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.

[csiko]

From the german Wikipedia page "Schiffe_versenken" (I'm not allowed to post links yet):

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!

[jaap]

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]

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.

[jaap]

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]

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.

[jestingrabbit]

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 e-wang 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.

[jaap]

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:

Code: Select all

using System;
using System.Collections.Generic;

namespace test4
{
   class BShip
   {
      class BPat
      {
         private readonly long mask1;
         private readonly long mask2;

         public BPat(long m1, long m2)
         {
            mask1 = m1;
            mask2 = m2;
         }
         public bool canMerge(long m1, long m2)
         {
            return (m1 & mask1) == 0 && (m2 & mask2) == 0;
         }
         public void mergeWith(ref long m1, ref long m2)
         {
            m1 |= mask1;
            m2 |= mask2;
         }
      }


      static private readonly IList<BPat>[] ship = new List<BPat>[5];
     
      static void Main()
      {
         for( int ln = 2; ln<=5; ln++ )
         {
            IList<BPat> list = new List<BPat>();
            // by symmetry, we can restrict the len5 ship to being vertical and in the top left quarter of the field.
            int mxx = ln == 5 ? 5 : 10;
            int mxy = ln == 5 ? 3 : 10;
            for (int x = 0; x < mxx; x++)
            {
               for (int y = 0; y < mxy; y++)
               {
                  placeShip(list, ln, x, y, 0, 1);
                  if( ln!=5) placeShip(list, ln, x, y, 1, 0);
               }
            }
            ship[5-ln] = list;
         }
         ship[4] = ship[3];   // extra len 3 ship
         ship[3] = ship[2];
         long  count = search(0, 0L, 0L);
         // 8 symmetries
         Console.WriteLine(count * 8);
      }
      static long search(int depth, long m1, long m2)
      {
         if (depth == 5) return 1;
         long count = 0;
         foreach (BPat p in ship[depth])
         {
            if( depth == 0 ) Console.WriteLine(count);
            if( p.canMerge(m1,m2))
            {
               long oldm1 = m1, oldm2 = m2;
               p.mergeWith(ref m1,ref m2);
               count += search(depth + 1, m1, m2);
               m1 = oldm1;
               m2 = oldm2;
            }
         }
         return count;
      }

      static void placeShip(IList<BPat> list, int ln, int x, int y, int dx, int dy)
      {
         if (x + dx*(ln-1) >= 10 || y + dy*(ln-1) >= 10) return;
         int loc = 10*y + x;
         long m1 = 0, m2 = 0;
         for (int i = 0; i < ln; i++)
         {
            if (loc >= 50) m2 |= 1L << (loc - 50);
            else m1 |= 1L << loc;
            loc += 10*dy + dx;
         }
         BPat p = new BPat(m1, m2);
         list.Add(p);
      }
   }
}

[jestingrabbit]

And I expect that yours took minutes to execute rather than hours

[jaap]

And I expect that yours took minutes to execute rather than hours :oops:

About 3 minutes on a high-end pc.

[dudiobugtron]

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.

[jaap]

I wrote a different program to solve this problem, and got the following results:

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]

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

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.

[sweetadeleiiine]

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

[jestingrabbit]

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.

[Tirian]

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.

[Dason]

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.

[undecim]

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.

[Tirian]

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]

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.

[dudiobugtron]

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.

[rmsgrey]

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 thirty-billion, this isn't the event we're discussing here - the actual event is that an xkcd forum-poster 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]

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.

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 pen-and-paper variants of the game.

[ChibiChen]

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~

[sweetadeleiiine]

rmsgrey

I like what you say. more, por favor!

chibichen

yes please all