I’m going to do something a little different in this post, which is geared more towards grown-ups who like playing around with programming and recreational mathematics. Even so, there might be some good stuff here for kids who are comfortable with some programming basics. Instead of a problem set, I thought I’d tell you about a random bit of modeling I ended up doing over the holiday that you might have fun playing with too. One of the things I think is great about learning how to write code is that it gives you the tools to chase down lots of fun questions and see how different kinds of system work by building them and then changing things around. In this post, I’m going to tell you about my efforts this past week or so to learn some things about a system I bet you’re familiar with.
My daughter got a Battleship set for Christmas just a few days ago after learning how to play the game at after-school daycare. Before we got this for her for Christmas, I made up a bunch of paper-and-pencil versions we could use to play at home (You can download a PDF of these
here, if you like). Like any game, the finer points of strategy took some time to impart, and she’s still working out how to plan her missile shots to efficiently search the grid. The game also can take a fair bit of time (and a lot of disappointing missed shots) to complete, so like we’ve done with other games, I’ve occasionally introduced some changes to speed things up just a bit. These have included: (1) A smaller board (8x8 rather than 10x10), (2) 2 shots per turn rather than 1, (3) Different ship sizes. One of the nice things about the paper-and-pencil version is that you can invent whatever sizes and shapes of ships you want, which makes these changes very easy to implement.
Playing (and talking through) the game with her a bunch of times, the different formats we invented got me thinking about how this simple system works and what you, the player, might want to know about it. Board games as simple as this one are kind of fun to poke at this way because you can usually see your way to some aspects of the game’s structure by either writing some expressions that describe how the game works formally, or when all else fails, writing some code that helps you understand some aspect of the game.
For Battleship, I decided to tackle a straightforward question Blaise and I face every time we play: Where should you take your first shot? How does that depend on the size of the board and the ships that are available to place on the grid?
The answer certainly will depend on whatever biases human opponents have for placing ships on the grid. There are probably some general factors that come into play, like the fact that most people have a
left visual-field bias that affects a lot of different tasks. There are also probably lots of individual differences as well: Do you really like to put ships on the edges? Do you like to bunch everything up in one place? Do you hate/love using the corners? What these biases are could be it’s own fun problem to consider, but for now we’re going to act like they don’t exist. This way, we can start to develop a kind of simulation called a
Monte-Carlo model that will let us understand some things about Battleship and how to plan your first shot.
What is a Monte Carlo model? Basically, it’s a way of simulating a probabilistic system by making lots of random draws and keeping track of what happens each time. For example, suppose you have 10 coins you want to flip and you want to know how often you’ll get exactly 3 heads – that’s something you can work out analytically, but if you didn’t know how (or just didn’t want to), you could also just flip the 10 coins lots of times and see how often you got 3 heads. That latter approach is more or less what we’re doing in a Monte Carlo simulation: Given a random process, we “draw” an outcome and record what features of the outcome we care about so we can estimate properties of the system that we’re interested in. While this strategy has been around for a long time, the advent of computers capable of doing the random draws and multiple iterations for us meant that MC simulations became much more widely used in the mid 20th century. To my knowledge, a mathematician named
Stanislaw Ulam (who is a fascinating person to read about) is responsible for developing modern MC approaches, which he and others including John Von Neumann and Enrico Fermi used to examine issues in nuclear physics arising from the Manhattan Project. This was a case where they really didn’t know how to write down deterministic equations to explain the systems they cared about, so simulating them with random draws was about the only way forward.
OK, so how do we use these methods to talk about Battleship? First, let’s define what we want to know: Where should we take our first shot? I’m going to rephrase this as, “How likely is it that any given square will be occupied by a ship?” After all, if a square isn’t likely to be occupied, we wouldn’t want to waste time shooting at it. Second, let’s define how we think this system works in terms of a random process. Here are the rules I’ll use for our Battleship simulations:
1) There are five ships. One ships takes up 2 squares, two ships take up 3 squares, one ship takes up 4 squares, and one ship takes up 5 squares.
2) No square may be occupied by more than one ship (no overlap).
3) The ships are placed on a 10x10 board.
4) The ships are placed randomly by the opponent. For each ship, each legal ship position is equally likely to be selected.
Note: It’s really rule #2 that makes things a little tricky to compute deterministically, since the placing of one ship constrains the possible positions of the others.
So now what? The next step is to write code that allows us to randomly arrange the 5 ships for a single game and record where they were positioned. Here’s a picture showing you what a single game looks like using code that implements the four rules above.
Now that we can do this, we run that code thousands of times, keeping track of the ship positions for each simulation. When we’re done, we’ll count up how often each square was occupied across all of our thousands of random games. The result is a map of the game grid, with a number in each square telling us how often that square was occupied across the whole set of simulations. When I tried it out with 10,000 iterations, I got the following map:
What do we see? Well, it’s definitely a good idea to shoot for the center, but we can even say roughly how good an idea it is relative to other spots. For example, the center squares are occupied about 3 times more often than the corner squares! That’s not a bad thing to know about the game, and it all comes from the constraints placed on ship positions imposed by our rules.
My guess is that at this point this basically matches your intuitions about the game, so you may not be very impressed. Sure, we got some quantitative data about the relative merits of the center vs. the other locations, but how big a deal is that? Arguably, not much of a big deal, but the real fun starts by messing with those rules and seeing how things change. See, I wrote all my code so I can manipulate the size of the board, and the size and number of ships and do all this over again. Let’s see how the maps change when we use a smaller board (9 squares and then 8 squares).
The same overall structure, but the absolute numbers change a good bit (note that the ~3:1 ratio for center vs. corner is roughly preserved, though). What about changing the ships? Let’s see a version where we only have ships that are 4 squares long:
Now let’s compare that to what happens if our fleet is only made up of ships that are 6 squares long:
Check out that cross shape! The center isn't really favored any more than the arms of the plus sign - see if you can figure out why this changed the way it did intuitively.
There’s tons of other stuff you can do with this little game by simulating different scenarios, and these are nice ways to see how some candidate rule changes might make the game more or less fun. What if you introduce squares that can never be occupied? How about ships with different shapes? What if you make your game toroidal by letting ships “wrap around” the edges of the grid? Suppose we let the “no overlap” rule go? There are lots of possibilities to explore, and an MC simulation lets you quickly get some insight into how they work.
That’s the end of my grown-up post, and I hope you found it at least somewhat fun. I really think learning how to play with mathematical objects opens the door to lots of great ways to explore ordinary stuff, and hopefully this was a good example of why I think that’s fun to do. Please feel free to
play with the code yourself, and I’ll try to develop a few more posts about similar topics. Thanks for reading, and happy modeling!
