Battleship

My first video is finally up! You can find here. I’m thrilled to finally be on YouTube.

This post has some more thorough explanations of things that I couldn’t cover in the video, although I realize it’s a bit scattered. I’ll update this page as I think of some more things.

I spent a lot of time trying to figure out the topic for my first video. My list of video ideas already numbers in the triple digits, although most of these will never see the light of day. I ultimately decided to focus my first few videos on boardgames, hoping that the animations would be simpler, and the math would be more straightforward, since I could generate the data myself. It turned out that I was very wrong on that second point.

Battleship specifically combined a few nice things. First, it’s the right level of complexity for an early video: complicated enough that it’s worth thinking about, but simple enough that it’s possible to cover pretty much the whole game with a few hundred lines of code and a 20-minute video.

Second, it seems like a topic that people want to see. There are already several successful videos covering Battleship, and while some of them are quite good, they all leave clear gaps on how their strategies can be implemented in practice. The videos all seemed to be based on this page on DataGenetics, which does a good job of summarizing some strategies but is light on implementation details.

A favorite example of this becoming a problem was in the most popular Battleship video on YouTube. They mention a version of the heatmap strategy, saying “we can employ a rough algorithm in our minds,” but then refusing to elaborate on what our minds are actually doing.

I’m hoping that this is a place where my channel can add some value. I have the time and the background to code some of these things up myself, making it easier to answer questions that might not be answered elsewhere.

The Approach

My original goal for this video was to come up with something close to a Nash equilibrium strategy for Battleship: strategies for both the placer and the guesser that are as good as possible against each other. The thought was that I would go back and forth, coming up with a good guessing strategy, then a placing strategy that would make the guessing strategy fail, and then a guessing strategy that would be immune to this, and so on.

There were two main problems with this. First, these are complicated strategies. Both the placer and the guesser would have to employ random strategies (if your opponent knows your first guess is always E5, they’ll never put a ship there, so you have to sometimes guess less likely squares to avoid this). Actually coming up with these strategies is hard even with a computer, and then trying to distill them into advice that human players could feasibly follow seemed like too difficult of a task.

The other issue is that the things that I put in the video ended up being a lot more difficult than I expected. There were plenty of times that I expected an approach to work on the first try but instead needed to spend weeks experimenting to get anything to work. I don’t think I can match a lot of the other Battleship videos on production quality, but I’m pretty sure that this is the most comprehensive Battleship strategy guide on the internet, and I’m hoping that people find it useful.

The Greedy Guessing Strategy

The core of this video comes from the greedy guessing strategy, which is based on the counterintuitive idea that random ship placements lead to non-uniform square probabilities. I spent a while trying to rigorize why we should even care about this idea. After all, players aren’t placing their ships uniformly at random, and they certainly aren’t choosing entire configurations uniformly at random. So why make the randomness assumption at all?

The first reason is something that I briefly mentioned in the video. If we have no information about what our opponent is doing, that’s sort of like imposing a uniform prior on possible things they could do. If we assume that all squares are equally likely, then we are implicitly assuming that the placer is trying harder to put their ships in the corners of the board, since that is what would need to happen in order to see the same square probabilities across the board.

There’s another reason, which is still largely intuition-based, that I think applies more near the end of the game. As the game goes on, the decisions that you’re making become more specific, and more tied to the exact collection of squares that have been guessed so far. It’s easy to imagine an opponent who tries to put their ships in the corners, but it’s hard to imagine one who specifically tried to make it more likely to put their cruiser horizontally rather than their cruiser or battleship vertically through B7 when you have a hit there but misses at B5, B9, and E7. As the scenarios get more specific, it’s harder to imagine that your opponent planned for them.

“Find Mode” and “Sink Mode”

Even though they didn’t make it into the video, a lot of the insights I found about the game came from dividing it into two phases: find mode and sink mode. In find mode, every ship has either not been hit, or is completely sunk, so our focus is to find the next ship. In sink mode, we have at least one ship that is partially sunk, so our goal is usually to sink that ship before moving on. There are technically a few cases where the greedy strategy will continue searching for ships, even when one is partially sunk, but this is rare, and there are other good reasons to try to break things down this way. I mention these two modes now because they are useful for a few things later on.

The Implementation

Part of the reason why there isn’t a lot of good information out there about our greedy strategy is that it takes a lot of work to simulate even a single game. Given a position on a board, you need to check all 30 billion possible configurations (technically only 15 billion, since every position has a similar position with the submarine and cruiser switched) to see how many of them are compatible with the information you have so far.

Once there are a few pegs on the board, this gets a lot easier: you can just check which positions for the submarine and cruiser are compatible with the given pegs. For each of those positions, you can check which positions for the carrier are compatible, and for each of those, you can check which positions for the battleship, and then the destroyer, are compatible. The number of things that you have to check goes down quickly, but at the beginning of the game, it’s still 15 billion.

Just simulating a single game this way could take hours, even on my pretty solid desktop, but there are thankfully some nice simplifications that we can do. One thing that saves us is that the positions that take the longest to check (the ones at the beginning of the game) are also the ones that show up the most often. If I run 10,000 simulations, then every single one of them will start with an empty board, about 8,000 will start with a miss at E5, and about 2,000 will start with a hit at E5. If we just cache the decision that we make in each position, then we avoid having to duplicate the most time-consuming steps. This allowed me to run my 10,000 simulations in about a day.

A few things on this: this is part of the reason why I gave up on coming up with a good randomized strategy. It will take much longer to build up the cache if we aren’t making the same decision every time that we see a position. Second, this is also why the hunt-target histogram looks so much smoother than the other ones in my video. I was able to run a million hunt-target simulations in much less time than the 10,000 simulations for the variants of the greedy method. It also brings up some important points about the information that we get during the game.

Information in Battleship

We essentially get four types of information during the guessing phase of the game:

1. Hit: there is a ship at that location

2. Miss: there is not a ship at that location

3. Sunk [SHIP]: that ship is entirely contained in the hits you’ve gotten so far

4. Sunk [SHIP]: that ship must go through the square you just hit

1 and 2 are extremely important. 3 is somewhat helpful, and 4 is helpful only in very specific cases where two multiple ships are next to each other.

My original greedy strategy only took 1 and 2 into account, but I ended up needing to add 3 to get the placing strategy to work. I only added 4 after the video was already filmed, and thankfully, it turned out not to make much of a difference. Here are the average turn counts for 10,000 simulations for each version of the strategy:

Info used    Average turns
12           46.94
123          44.71
1234         44.69

That’s not a statistically significant difference between the last two, and I suspect that if I ran enough trials, including 4 would improve the results slightly, but this confirms that 4 is not really contributing much here.

Flaws in the Strategy

There are a few problems with the greedy strategy. One is that it is exploitable. If your opponent knows that you’ll start the game in the middle, they will be able to win pretty easily by putting ships in the corners. The main way around this is to use a randomized guessing strategy, but this didn’t seem worth doing for reasons I mentioned above.

The other big problem problem with the greedy strategy is that it is, well, greedy. It doesn’t consider how earlier moves will affect later ones. It turns out, though, that actually finding a way to improve on this is easier said than done.

The Checkerboard

One thing that I thought would improve things quickly is the checkerboard strategy. This is mentioned in a few other videos on Battleship, and seems like a pretty straightforward win. The idea is this: every ship has length at least 2. This means that if you’re careful, you only need to check half of the squares on the board in order to guarantee that you find every ship. Specifically, you can color the board like a checkerboard, and then target only the dark squares.

A major concern with the greedy strategy is that it doesn’t think ahead to how the current move will affect the rest of the game, and the parity issue addressed by the checkerboard is one place where the greedy strategy fails. The greedy strategy will sometimes get stuck in cases where it has to make a bunch of guesses right next to each other because it made incompatible choices in different sections of the board. A properly implemented checkerboard strategy should never take more than about 65 moves, since it should find all of the ships in no more than 50, but the greedy strategy will take longer than this reasonably often.

I had actually already animated and recorded a scene on improving the greedy strategy using the checkerboard. The idea is this: when you’re in find mode, ignore the light squares on the checkerboard, and greedily choose the most likely dark square. When you’re in sink mode, just choose the most likely square.

There’s just one problem with the checkerboard strategy: it doesn’t work. I mean, it does. It’s a huge improvement compared to randomly guessing, or even when added to the hunt and target strategy. But the greedy strategy is so optimized that the checkerboard does more to prevent good guesses than to help future guesses. The greedy strategy used in the video took 44.7 guesses on average, while adding the checkerboard approach actually increased it to 45.4.

I put in a few more attempts to try to get this to work. I figured that the checkerboard might be most helpful at the beginning, organizing the guesses early on so that we wouldn’t have to waste turns later. At the end, the checkerboard might just be getting in the way of much more likely guesses when there are only a few places that ships can go. I tried an approach where we use the checkerboard strategy for some number of turns at the beginning, and switch to full greedy after that. Here are the results. Checkerboard[n] refers to n moves of checkerboard strategy, followed by regular greedy for the rest of the game.

Strategy          Average Turns
Greedy            44.71
Checkerboard      45.39
Checkerboard15    44.91
Checkerboard20    44.91
Checkerboard25    44.93
Checkerboard30    45.01
Checkerboard40    45.11
Checkerboard50    45.41

Still nothing that can match the original greedy strategy, let alone beat it. I guess I’m glad I checked that before releasing the video.

Multiplayer Strategies

The whole video basically assumes that Battleship is two 1-player games rather than a 2-player game. While we have to think about how our opponent places their ships when we guess and vice versa, we’re basically just trying to guess as quickly as possible, without having to consider that there is another person guessing at the same time. In a lot of games, there are specific things you have to think about when you’re ahead or behind. If a basketball team is behind at the end of the game, they are likely to commit a lot of fouls. This is a terrible strategy for most of the game, and most of the time, it causes them to lose by more than if they didn’t do it, but when you’re behind, it makes it better to play high-risk, high-reward strategies that wouldn’t be worth it otherwise. Are there cases in a Battleship game where you should change your approach if you’re ahead or behind?

I strongly suspect that there are cases like this, although I haven’t been able to come up with any concrete examples yet. I’m looking for an example where either

1. A player who is behind will make a move that will make them use more turns on average, but if it works, will allow them to finish in less than a certain number of turns and win the game.

2. A player who is ahead will make a move that will make them use more turns on average, but is guaranteed to take at most a certain number of turns, guaranteeing that the other player can’t finish in time.

I’m sure there are other possible examples of two player strategies like this, but I expect that the easiest examples to come up with would take one of these two forms. Either way, I doubt that tailoring your strategy to whether you are ahead or behind makes as much of a difference in Battleship as in a lot of other games.

Placement Strategy

While it accounted for relatively little of the video, the placement strategy took the vast majority of my time, and ultimately led to some long delays for the video. I was hoping that this would be the main thing that my video would contribute, since the greedy guessing strategy already exists in various places online, even if there isn’t a really thorough explanation anywhere else.

By the end, I was pretty convinced that random ship placement is actually fairly close to optimal when it comes to placing ships in a way that can’t be exploited by a good guesser. Negative results aren’t as fun to put in a video, but this is pretty interesting in and of itself.

I had to speed through it in the video, but I want to be a bit more clear about what I was trying to do in this section. As I mentioned in the video, there’s a pretty good way to beat the greedy strategy, or any deterministic strategy, but just not putting your ships where your opponent is guessing. But that’s not really what we want from our ship placement strategy. We want a strategy that works against any opponent, including one who knows the strategy that we’re using.

For the entire ship placement section of the video, every time I said “greedy strategy”, I meant “greedy strategy for this specific ship placement strategy”. For whatever ship placement strategy we were using, the greedy strategy would calculate the most likely square to contain a ship under that strategy and then pick the most likely one. The greedy strategy isn’t completely optimal, but I suspect that it’s close enough to optimal that if a ship placement strategy forces more guesses against a greedy strategy, it’s probably hard to exploit in general.

The Linear Algebra Approach

I had originally planned to take a linear algebra approach to ship placement. This was going to be the most “pure math” part of the video. There are 180 places for a destroyer to go on a battleship board (10x9 horizontal, and 9x10 vertical). There are 160 for the cruiser and submarine, 140 for the battleship, and 120 for the carrier. If you randomly place a destroyer by assigning probabilities to each of the 180 locations, then you can use that to figure out the probabilities of the destroyer landing on any square.

In some sense, the “problem” with random ship placement was that assigning equal probabilities to the 180 destroyer locations led to unequal probabilities for the 100 squares. So can we assign probabilities to the 180 locations so that the 100 squares become equally likely? This can be written as a system of equations with 100 equations and 180 variables, plus a constraint that the variables are probabilities and therefore must be at least 0 and sum to 1. There are more variables than equations, so if we add some extra constraints, it seems like we should be able to get a nice solution for this.

This turns out not to work, though. The destroyer and carrier both produce systems with infinitely many solutions, while the other ships produce systems with none. While it may seem strange at first that it only works for the shortest and longest ships in the game, there’s actually a pretty nice reason for this: the lengths of those ships (2 and 5) are both divisors of the length of the board (10).

Essentially, what happens is this. Just find a way to put 50 destroyers on the board together. The easiest way is just to do 10 rows of 5 horizontally, or 10 columns of 5 vertically. Then, you can just place a destroyer in any of those 50 locations with probability 1/50. This will give every square a 1/50 chance of being covered. You can do the same thing with 20 carriers. The infinitely many solutions come from the fact that you can take linear combinations of any of these arrangements.

While it’s not obvious that there shouldn’t be any solutions for the submarine and cruiser, it’s pretty clear that you at least can’t use the above method, since it’s impossible to cover 100 squares with ships of length 3. The fact that it doesn’t work for the length 4 battleship, however, actually brings up a cool math problem. 10 isn’t divisible by 4, but 100 is, so it seems like we should be able to come up with a way to arrange 25 battleships on the board and do the same thing. There’s actually a nice classic proof for why we can’t.

It involves, funnily enough, a checkerboard, but not quite the same one we used before. We make a checkerboard pattern out of 2x2 blocks instead of 1x1 blocks. Wherever we place a battleship on this board, it will always cover 2 dark squares and 2 light squares. However, the board has 52 dark squares and only 48 light squares. Since there are 48 light squares and 2 per battleship, this means we can only fit 24 battleships on the board. Indeed, it turns out that any way we can possibly fit 24 battleships on the board will have to leave 4 dark squares uncovered.

But back to the original problem. Even if we try to find approximate solutions to our systems of equations for each ship, it leaves open some major issues. It specifically comes down to the difference between the find and sink phases of the game. If we choose the destroyer location randomly from 50 non-overlapping locations, then this turns out to be theoretically optimal for taking as many turns as possible to find, on average. However, we can always sink the ship in just one additional turn, because once we’ve found the ship, we know which of the 50 locations we’ve hit, and then we know where the other half of the ship is. In general, the linear algebra approach is good for lengthening the find phase of the game, but possibly at the expense of the sink phase.

So our linear algebra approach doesn’t really work, since it can lead to solutions that are not great in practice. What if we instead just try to maximize the total turns to find and sink directly?

The Expected Turns Approach

Instead, we’ll try to just maximize the expected number of turns needed to find and sink each ship. We’ll still go one ship at a time, since finding a probability distribution over all 30 billion configurations is a bit too complicated. For each ship, we’ll place the ship at random over all possible locations, and then we’ll use a greedy guessing strategy that’s aware of the placement probabilities to try to find and sink just that one ship. If we change the probabilities, we can see if the 1-ship greedy guessing strategy takes more or less time to sink the ship on average. Since there are only 120-180 places where the ship can go, we can just check the number of turns needed to sink the ship in every possible location every time we change the probabilities.

I wrote an optimizer that goes through all pairs of ship locations, and tries to increase the probability of putting the ship in one location, and similarly lowers the probability of putting the ship in the other location. If this increases the expected number of turns to find the ship, we keep the new probabilities and keep going. Running this for each ship leads to increases of about 1-2 turns per ship. We can then sample random ship configurations by just choosing a location for each ship at random from our updated probability distribution, and throwing out any samples with overlapping ships.

But then something strange happened. Even though the single ship find-and-sink times increased by 1-2 turns per ship, the total number of turns actually went down when the greedy guessing strategy was run on 5 ships. For a while, I assumed that there was just a bug in my code (and for some of that time, there was), but I ultimately realized it was something else: the same find vs. sink issue that came up in the linear algebra approach.

Basically, finding and sinking look different when you go from one ship to 5. The number of turns from the 5 sink phases roughly add, but the number of turns from the 5 find phases don’t. This is because the same turn can be used to try to find multiple ships. Your first turn of the game contributes toward the find phase for all 5 ships. After you sink your first ship, each turn contributes to 4 different find phases, and so on. Each turn in the sink phase usually only contributes toward one ship.

So when we run the optimizer for each ship, we are essentially trying to maximize the number of turns in 5 find phases plus 5 sink phases, when we really have 1 find phase and 5 sink phases. The optimizer did a great job of increasing the number of turns in each find phase, but the number of turns in the sink phases actually went down slightly. This worked for individual ships, but when we combined them, the loss from all of our sink phases added up and cancelled out any gains we got from the find phase.

So I changed my optimizer. In an attempt to weigh the sink phase properly, I tried to maximize (1/5 * find_turns + sink_turns) for each ship, instead of the (find_turns + sink_turns) that we had before. This did slightly better, but still didn’t show a meaningful improvement.

The next attempt involved the observation that not all ships are created equal. In some sense, adding a turn to the find time only actually affects the final result of the game if the ship you’re trying to find is your last ship. Finding your first ship a turn earlier doesn’t really help you unless you also find your last ship a turn earlier. Because of this, smaller ships, which are harder to find, will contribute more to the total length of the find phase. Specifically, I ran 1000 game simulations using the greedy strategy to get the percentage of the time where each ship was found last:

Length   Ship       % Time Last
2        Destroyer          49%
3        Cruiser            19%
3        Submarine          19%
4        Battleship        8.5%
5        Carrier           4.5%

This is sort of interesting information in its own right, but it also suggests a modification to our optimizer. Instead of maximizing (1/5 * find_turns + sink_turns) , we maximize (.49 * find_turns + sink_turns) for the destroyer, (.19 find_turns + sink_turns) for the cruiser and submarine, and so on, so that we’re weighing the find turns appropriately for each ship. Finding the carrier faster probably doesn’t matter much, since you’ll probably still be looking for other ships anyway, but finding the destroyer faster matters a lot, since there’s basically a 50/50 chance that it will be the last thing keeping you from winning the game.

Unfortunately, this didn’t improve things enough either, so I had to get back to the real problem that I had been avoiding. Up to this point, I had only been considering hits and misses when thinking about a board state (1 and 2 from the section above about information in Battleship games). These are the easiest things to think about, because the only things you need to keep track of are the red and white pegs currently on the board. If you want to properly use information about sunk ships, you have to know not only what the board looks like now, but what the board looked like when each ship was sunk. I had been hoping to avoid thinking about this, because it would require a rewrite of a lot of my code for choosing guesses with the greedy strategy.

But I had gotten to a point where I was completely stuck on half of my video. No matter what I did, I couldn’t get any improvement on random ship placement, and ignoring information about sinking ships seemed to be the next big thing to try. The problem with not using sunk ship information was that any time you sunk a ship other than the carrier, there was a decent chance that the greedy strategy would just keep guessing in that direction. This didn’t have that much of an impact on the success of the algorithm (it ended up adding about 2 turns on average), but those extra turns came in exactly the worst places.

When we calculated the expected number of turns to find and sink the destroyer, we were doing it in a game that only included a destroyer. When the destroyer was sunk, the counter stopped. But in the actual games we were playing, there would often be a few extra guesses after sinking the destroyer that would occur almost any time the destroyer wasn’t sunk last. Those guesses weren’t accounted for by the optimizer.

I finally rewrote the code to add information type 3 (the sunk ship must be included in the red pegs from the time it was declared sunk) and it immediately fixed the problem. We still only got a benefit of about half a turn, but we finally found a way to get our improved placement strategy to do something productive.

On probabilities of adjacent ships

Now, this approach to trying to place ships one at a time was only supposed to be my first attempt at an improved placement strategy. Because it took so long, I didn’t get the chance to try anything else, but I think there’s still a decent amount of improvement that can be made from considering interactions between multiple ships. Specifically, I strongly suspect that it’s better to put ships next to each other more often than pure randomness would suggest.

In addition to avoiding guesses near the edges of the board, the greedy strategy also avoids guessing near ships that have already been sunk. The sunk ship essentially acts like another wall, reducing the number of ways that other ships could go through the adjacent squares. Just as we were able to slow down a greedy guesser by putting more ships in the corners, I suspect that we could produce a similar improvement by putting more ships next to each other, but I guess I’ll have to save that for another time.

Final takeaways

I learned a lot from making this video, both on Battleship and otherwise. Animating took a lot more time than I expected, but editing took a lot less. I was not expecting the math to be the bottleneck here, but I guess this is what I get for trying to do original research for my first video. Granted, one of my goals for this channel was to show what it’s like to do math in the real world, and my many hacks and failed attempts are probably more representative than a perfectly clean video would have been.

With that said, I’m excited for my next video to be a bit more straightforward. I’m tackling another board game that also has relatively interaction between the players. The math is already done, so I’m expecting this video to come out a lot faster, and to have significantly fewer last-minute changes and cuts.