The Linear Theory of Battleship
Recently I set out to hold a Battleship programming tournament here among some of the undergraduates. Naturally, I myself wanted to win. So, I got to thinking about the game, and developed what I like to call “the linear theory of battleship”. A demonstration of the fruits of my efforts can be found here. Below, my aim is to guide you through how I developed this theory, as an exercise in using physics to solve an interesting unknown problem. This is one of the things I really love about physics, the fact that obtaining an education in physics is essentially an education in reasoning and thinking through complicated problems, along with an honestly short list of tips and tricks that have proven successful for tackling a wide range of problems. So, how do we develop the linear theory of battleship? First we need to quantify what we know, and what we want to know.
So, how does one win Battleship? Since the game is about sinking your
opponents ships before they can sink yours, it would seem that a good
strategy would be to try to maximize your probability of getting a hit
every turn. Or, if we knew the probabilities of there being a hit on
every square, we could guess each square with that probability, to keep
things a little random. So, let’s try to represent what we are after. We
are after a whole set of numbers
Alright, we seem to have a goal in mind, now we need to quantify what we
have to work with. Minimally, we should try to measure the probabilities
for the ships to be on each square given a random board configuration.
Let’s codify that information in another matrix
First of all, lets look at the sum of all of the ship probabilities, so
that we have the probability of getting a hit on any square for any ship
given a random board configuration, or in our new parlance
shouldn’t be too surprising. Notice first that we can see that my statistics are fairly good, because our probabilities look more or less smooth, as they ought to be, and show nice left/right up/down symmetry, which it ought to have. But as you’ll notice, on the whole there is greater probability to get a hit near the center of the board than near the edges, an especially low probability of getting a hit in the corners. Why is that? Well, there are a lot more ways to lay down a ship such that there is a hit in a center square than there are ways to lay a ship so that it gives a hit in a corner. In fact, for a particular ship there are only two ways to lay it so that it registers a hit in the corner. But, for a particular square in the center, for the Carrier for example there are 5 different ways to lay it horizontally to register a hit, and 5 ways to lay it vertically, or 10 ways total. Neat. We see entropy in action.
Next let’s look just at the Carrier:
Woah. This time the center is very heavily favored versus the edges. This reflects the fact that the Carrier is a large ship, occupying 5 spaces, basically no matter how you lay it, it is going to have a part that lies near the center.
Now for the Battleship:
This is interesting. This time, the most probable squares are not the center ones, but the not quite center ones. Why is that? Well, we saw that for the Carrier, the probability of finding it in the center was very large, and so respectfully, our battleship cannot be in the center as often, as a lot of the time it would collide with the Carrier. Now, this is not because I lay down the Carrier first, my board generation algorithm assigns all of the boards at once, and just weeds out invalid ones, this is a real entropic effect. So here we begin to see some interesting Ship-Ship interactions in our probability distributions. But notice again that on the whole, the battleship should also be found near the center as it is also a large ship.
Sub / Destroyer
Next let’s look at the sub / destroyer. First thing to note is that our plot should be the same for both of these ships as they are both the same length.
Here we see an even more pronounced effect near the center. The Subs and Destroyers are ‘pushed’ out of the center because the Carriers and Battleships like to be there. This is a sort of entropic repulsion.
Finally, let’s look at the patrol boat:
The patrol boat is a tiny ship. At only two squares long, it can fit in just about anywhere, and so we see it being strongly affected by the affection the other ships have for the center. Neat stuff. So, we’ve experimentally measured where we are likely to find all of the battleship ships if we have a completely random board configuration. Already we could use this to make our game play a little more effective, but I think we can do better.
In fact, as a game of battleship unfolds, we learn a good deal of
information about the board. In fact on every turn we get a great deal
of information about a particular spot on the board, our guess. Can we
incorporate this information into our theory of battleship? Of course we
can, but first we need to come up with a good way to represent this
information. I suggest we invent another matrix! Let’s call this one
Alright if we decide to go with my silly way of codifying the
information, at this point we have two pieces of data,
That is a picture of
That is a picture of
In the end, this is exactly what I did. I had my computer create billions of different battleship boards, and figure out what the proper values of B and W should be for every square of the matrix. I put all of those results together in a way that I hope is easy to explore up at the Fancy Battleship Results Page, where you are free to explore all of the results yourself. In fact, the way it’s set up, you can even use the Superduper Results Page as a sort of Battleship Cheat Sheet. Have it open while you play a game of battleship, and it will show you the probabilities associated with all of the squares, helping you make your next guess. I’ve used the page while playing a few games of battleship online, and have had some success, winning 9 of the 10 games I played against the computer player. Of course, this linear theory isn’t everything…
Why Linear isn’t everything
But at the end of the day, we’ve made a pretty glaring assumption about the game of battleship, namely that all of the information on the board adds in a linear way. Another way to say that is that in our theory of battleship, we have a principle of superposition. Another way to say that is that in this theory, what you think is happening in a particular square is just the sum of the results from all of the squares, independent of one another. Another way to say that is to show it with another picture. Consider the following:
Here, I’ve specified a bunch of misses, and am asking for the probability of there being a Carrier on all of the positions of the board. If you look in the center of that cluster of misses, especially in the inner left of the bunch, you’ll see that the linear theory tells me that there is a small but finite chance that the Carrier is located on those squares. But if you stop to look at the board a little bit, you’ll notice that I’ve arranged the misses such that there is a large swatch of squares in the center of the cluster where the Carrier is strictly forbidden. There is no way it can fit such that it touches a lot of those central squares. This is an example of the failure of the linear model. All the linear model knows is that in the spots nearby misses there is a lower probability of the ship being there, but what it doesn’t know to do is look at the arrangement of misses and check to see whether there is any possible way the ship can fit. This is a nonlinear effect, involving information at more than one square at a time. It is these kinds of effects that this theory will miss, but as you’ll notice, it still does pretty well. Even though it reports a finite positive probability of the Carrier being inside the cluster, the value it reports is a very small one, about 1 percent at most. So the linear theory will have corrections at the 1 percent level or so, but that’s pretty good if you ask me.
And so it is. I’ve tried to develop a linear theory for the game Battleship, and display the results in a Handy Dandy Data Explorer. I encourage you to play around with the website, use it to win games of Battleship, and in the comments, point out interesting effects, things you think I’ve missed, or ideas for how to come up with linear theories of other things.Tweet