Indoor, Outdoor & Kids' Trampolines

The Battleship Algorithm


Vsauce! Kevin here, in the control room of the USS
Pasadena — a Los Angeles Class nuclear-powered fast attack submarine. The Pasadena is over 100 meters long, has
a crew of nearly 130, and is propelled by a thermal-neutron reactor that generates 35,000
shaft horsepower. And it has a lot of buttons, so I’m gonna
push… this one. Hey. Don’t touch that. Or… anything. Right. I’m here with Petty Officer John Davis,
Machinist Mate Nuclear First Class and trained rescue diver with the United States Navy. I’m 100 meters deep in the Pacific Ocean
with an expert in thermodynamics, nuclear reactor technology, fluid dynamics, mathematics
and more. And we’re gonna tap that knowledge to get
to the bottom of a game that’s been a staple of kitchen tables for a century: Battleship. Battleship evolved from a pencil and paper
French game called L’Attaque, which eventually became Stratego. By the 1960s Milton Bradley developed the
classic 10 x 10 grid in which each player places 5 ships: a carrier that occupies 5
spaces, a battleship on 4, and a cruiser and submarine that are each on 3, and a destroyer
on 2. Ships can’t overlap, but they can touch. The actual gameplay is really simple: the
first player guesses a location on the grid — say, C4 — and the second player says whether
that shot hit one of their ships or missed entirely. If it’s a miss, then we both mark our grids
with a white peg. If it’s a hit, then we’ll mark it with a
red one. The object is to hit each location on all
5 ships and sink them. And it seems like there’s really no perfect
way to start. We’ve got 100 possibilities, and all of
them equally valid. With 17 possible hits, our first random shot
is going to hit about 1 in 5 times. So… I’ll start. F7. Miss. Random guesses in Battleship are just a massive
exercise in probability, and a simulation by Nick Berry of DataGenetics showed that
using this random system means over 99% of games will require at least 78 shots. Uhh. E7. Miss. Playing totally randomly would be really,
really inefficient, and unless both players are choosing all shots randomly, you’d lose
almost every time. And real randomness is actually pretty, pretty
hard. Research as early as the 1930s showed that
humans aren’t capable of generating a random number sequence, and modern research in economics
shows that decision-making is incredibly difficult when we have to try to make sense of randomness. A3. Miss. Computers are a lot better at handling randomness. But pure randomness just isn’t optimal here. The way most people play Battleship is a blend…
first, they shoot randomly until they get a hit, and then they go up, down, left and
right around that hit to find the next part of the ship. D5. Ugh. Hit! That’s what Berry calls the “Hunt and
Target” method. You start by randomly firing shots, and then
work around your hits to sink ships. By repeating that strategy, the average game
will take about 65 shots. That’s better than random, but it’s not
great. H8. Miss. The next level strategy is what’s called
“Parity,” where you recognize that the board of 100 spaces is actually no more than
50. Because the smallest ship has to occupy at
least 2 spaces, we can think of the Battleship board like a checkerboard of alternating colors. We can “Hunt” on just one color, and then
“Target” when we get a hit. D6. Hit… and sunk. Battleship’s smallest unit is 2, so once
the Destroyer has been sunk — like you just did — then that expands to 3, then 4 and
5. Hunt and Target with Parity improves our average
number of moves nearer to 60, so it’s a little better. But still not optimal. Uhh. B2. Miss. We can employ a rough algorithm in our minds
that takes into account both the board and whether ships of a certain length are likely
to be in a certain position on that board. G9. Uhh. Miss! A computer can do this perfectly judging the
probability of a given ship’s length being placed in the leftover spaces on the board. This will change with every single move and
will create a sort of heat map that suggests where we should guess next. I’m gonna guess. next… D4. Hit! You’ll start the game with no information
at all, so the best option is to shoot near the center and adjust from there. Guess, recalibrate, repeat, each time refining
your probability based on the layout of spaces left and the length of the ships you haven’t
sunk. A9. Hit! We can’t do this as fast or as perfectly
as a computer, but we can generate a pretty good approximation in our minds. As we play each game of Battleship, we’re
employing a probability density function and refining an algorithm in our brains with every
move. Statistically, there’s a massive payoff
to this approach: It drops the number of shots required into the 30s or 40s, with Berry finding
that all 100 million games he simulated were completed by about 65 moves. C4. Hit. That’s how so much of practical math, science
and engineering works. We make an approximation, and then hone in
on the details the best we can considering all the variables, unknowns, and randomness
— and then put it together with constant adjustments to make something complex function
flawlessly. B9. Ugh. Hit. It’s a constant process. But whether you’re optimizing the probability
behind a 50-year-old board game or navigating one of the most advanced naval vessels ever
created… today we have an opportunity to learn, refine, and evolve faster than ever
before. Wait. Did you say, B4? Uhhh.. yeah? Hit… and you sunk my submarine. W..wait. Not… Not this submarine? … No. Okay. Good. And as always — thanks for watching! To check out more videos like this go to sailorvs.com. Did I say it right? I said it right, right? Okay cool. Phew! And it’s got a lot of buttons. So I’m gonna touch this one. Please don’t touch that! Uh. Right. Or anything. Sorry. Nuclear. I’m such an idiot. Okay yeah! If you like it — I like it!

Reader Comments

  1. 0:41 excuse me but that's a tardis console i'm seeing here

    I KNEW IT! THE US GOVERNMENT IS HIDING THE ARTRONS FROM US!

  2. Very sadly Nick currently has cancer and it doesn't sound too good. I highly recommend everyone take a look at the huge treasure chest of blog posts he has created over the years. There really are some brilliant insights and captivating explanations there. http://datagenetics.com/blog/june12019/index.html

  3. I prefer to put my submarine on my copy of the opponent's grid, and if the opponents ship is in front of my sub, save that attack for last.

  4. My grandparents used to have an OLD copy. Of course, pegs were missing, so we had a limit to how many shots could be taken.

    Also, one of the subs was missing a peg, so I'd always cheat and put it at an angle.

  5. I usually walk my shots diagonally from A1 to J10 and J1to A10 but I do it randomly meanign i go across that whole diagonal but i don't do it in order (partly cause if do ppl BLATANTLY cheat at this game and move their ships)

  6. I've got a feeling this Battleships was staged. That's disgusting.

    I'm gonna go and watch some wrestling instead.

  7. My shoots aren't random. Example of my strategy:
    Shoot A1
    Shoot A5
    Shoot A9
    Next line
    Shoot B2
    Shoot B6
    Shoot B10
    Next line. . .
    And after the whole plane
    Shoot A3
    Shoot A7
    And so on
    When I hit a target, I'm trying to destroy it and back to strategy

  8. 0:15 that dented pipe on the right worries me…

    EDIT: when i place ships i follow such a strict pattern that most people can't guess right. i place my smallest ships in opposite corners and my largest ship vertically at one of the thirds. the other ships go horizontally in contact with the top and bottom of the large ship.

  9. What about rather than the checkerboard you divide it in 3rds given that there is only one ship that is a 2 it would seem to be considerably better than simply dividing the board with. 2/3 chance of hitting the destroyer.

  10. I found that the best spots to start are the four spaces that are one diagonal block away from the corners.
    Like if corner is C, O is a case, X is where you hit
    CO OC
    OX XO

    etc

  11. These videos are the kind that I enjoy the most. Only in our generation could a person make a living by playing goofy games, putting videos of it on YouTube, and then get invited to play those goofy games on a freakin' submarine.

  12. thats cool but, you seriously went on a nuclear sub just to talk about battleship? why not go on a battleship and do that? also I bet you couldn't really talk about the sub as it would be classified

  13. Very entertaining but almost no strategic information that goes beyond very vague descriptions. I'd like to know a lot more about the maths.

  14. I remember one Battleships incident when I was 8-9 years old at school. If it was bad weather outside at lunchtime obviously we didnt get sent outside to play, we got to stay inside, and one of the things people did to pass the time was battleships. Each player would get a sheet of a4 paper, fold it in half for privacy, draw two ten by ten squares, then on the 'home' board draw ships and play a regular game of battleships.
    Well, there was this one girl and one boy playing each other. Except, this game lasted *ages*. As in, more and more spectators (including myself) gathered round the pair of them like fans watching their football team. But this game was different.
    The boy had come up with a sneaky way to ensure victory. It may be called 'cheating' nowadays, but back then, whenever we played there was no restriction on how many or how big the ships could be. Monstrous 8*2 dreadnoughts were common, as was filling the board with so many cruisers it was actually easier to hit than miss. What HE did however, was put NO ships in the sea. He could not lose. You have to score the 'final hit' to win, so there was no way his opponent could win.
    Looking at her board though, she could not lose either. She drew lots of pretty waves, fish, and sea gulls all over her 'sea', but not a single warship. So the pair of them kept shouting out random letters and numbers, not knowing that whatever they said, the answer was always 'miss'…..

  15. For all those who see this and think "hey, I should join the Navy's nuclear program", trust me, you don't want to, ask any other navy vets and they'll say the same.

  16. ME-kevin goes in to the nuclear powered submarine wow i am going to learn something.
    Kevin – nah i am just playing battleships
    ME-still learned something (strategy skills)

  17. 3:06 its not smart to go up and then down, you get much better chances if you try left or rigth after up

  18. Why not start with the algorithm to find the largest ship first and then hone in on smaller ships, in hopes that you'd still get lucky and hit the smaller ships along the way.

    I'd like to see a comparison of going for the largest ships first versus the smallest ships first.

  19. Carrier(5) Battleship(4) Destroyer(3) Submarine(3) Patrol Boat(2). You couldn't even get the ships right. Also, if you hit a ship you get another shot till you miss. Yeah, Im a stickler for details.

  20. Initially, instead of guessing randomly, one can create virtual clusters of say 3 by 3 and keep guessing points in clusters. This may help because ships have good size as compared to the board. Once hit, then one can guess around it to sink. Also, once you get 2 points hit, you can know orientation of ship to sink it. So usually people may avoid aligning ships at border as it limits orientation.

  21. If you want to learn how the optimal strategy actually works, here's a python implementation of the code: https://github.com/DataSnaek/battleships_ai

  22. Thank you captain obvious. I always have even when I was little cut the odds in half from doing a checker board. Once you know for sure the 2 hit ship is destroyed then you can space out your shots more by 2 instead of one. Also set the little one across from a 3 or 4 so they hit it once hopefully go across sink a smaller one and they think it was a bigger ship and odds are they wont shoot right next to it.

  23. Friend of mine is a naval history enthusiast, specialised on WWI British destroyer fleets. Checking the specs of a VW class destroyer, he came across engine details for engine horse power and shaft horsepower…..he regretted trying to use Google to find out the difference….

  24. I have an electronic battleship game, the boards still exist but the computer announces hits and misses and you can play against the computer. The most interesting thing about it is the advanced weapons extension it has.

    In addition to your regular cannon each ship (besides the destroyer/”special operations craft”) has additional features. These features each take a turn to use.

    – All ships (including the destroyer) have an unlimited supply of anti-aircraft "missiles" to target enemy fighter planes. This acts exactly like your regular cannon but only for planes.
    – Your aircraft carrier starts out carrying 2 fighter planes. If the part of the carrier the fighter is on is hit before it is launched, the fighter is destroyed. Fighters do not care if the carrier is destroyed after they launch.
    – Fighters take 1 turn to move and perform one of two search patterns at it's location, "plus" or "x". It will then openly report the locations of enemies it spots. On the first turn it finds enemies, it will immediately launch missiles at ALL enemy locations it found. After that it can only scout. Can only be shot down with anti-aircraft "missiles"
    – The battleship comes equiped with 1 "tomahawk missile". This missile will target a 3×3 area.
    – The "light missile cruiser" has 2 (I forget the name) missiles. These target a 1×3 area either vertically or horizontally
    – The "fast attack sub" has two functions. The first is 2 torpedoes that enter from one of the edges of the board and travel either a column or a row and will hit the first thing it comes in contact with.
    – The second function of the sub is the "sonar scan". This looks at a 3×3 area and will report whether a craft exists in that area, but not how many or where.

    This extension really brings about multiple layers of strategy to the game which makes it more interesting for me.

Leave a Reply

Your email address will not be published. Required fields are marked *