Regarding finding Nash Equilibrium strategies: If we have a candidate mixed optimal strategy for one player, then any of the individual strategies in the other player's optimal counter strategy will have the same pay off. So, given a candidate mixed strategy for one player, we can search for a an optimal single (i.e. simple) counter-strategy for the other player and evaluate the candidate strategy based on how it performs against that optimized counter.
For the shooting strategy presented in the video there's basically a mix of eight strategies (for reflections and rotations), so it's probably practically feasible to just simulate it against a placement of ships, move one of the ships at random and try again over and over. (I think this is an example of simulated annealing.)
The thing is, I'm quite confident that the shooting strategy in the video is not particularly close to a NE since it predictably avoids the edges. And, when I try to come up with NE shooting strategies they tend start with something like "choose a random value from 0-5 then shoot all the cells where row+column is equal to that value mod 6 in a random order". That's already trillions of possible shooting sequences, so, while that kind of shooting approach can certainly be analyzed using combinatorics, it's impractical to directly simulate.
For Nash Equilibrium on setting side of things, it's pretty easy to come up with placement probabilities that make all cells except for the corners equally probable to hold each ship. A naive greedy approach like the one in the video won't provide any guidance about which of the 96 non-corner cells to start with in response. Searching for a good shooting response to that approach to ship placement (if there is one) will take more sophisticated thinking.
I definitely agree that my guessing strategy is not close to a Nash Equilibrium, although I don't think I had a great way of thinking about how to come up with one. I like your approach better.
For setting, I'm not actually sure that "equally likely to hold each ship" is actually optimal. I think another commenter might have pointed this out somewhere, but sinking time is generally lower for ships on the edges, so you probably do want to keep them slightly less likely to compensate for this. Even though I was running my placement algorithm against a greedy opponent, I do think that it was probably pretty close to optimal, partially because I think the focus on find time vs. sink time is fairly important to the analysis.
> ... For setting, I'm not actually sure that "equally likely to hold each ship" is actually optimal.... I think the focus on find time vs. sink time is fairly important to the analysis.
It may well be that it's best for the setter to optimize 'seek' for the short ships and 'sink' for the long ships. In your simulations, about 87% of the time, seeking time is determined by one of the short (length 2 or 3) ships. For the shorter ships, there is less edge effect, so the impact of making the distribution more even on sink times is smaller. Moreover, the longer seek times for those ships make even distribution more valuable for them.
For what it's worth, I have always played a version of battleship where the opponent calls out hit, miss, or sunk [ship]. But, in the copy of the rules that I found on-line:
It indicates that players have to call out which ship was hit when a ship is hit, not just when it is sunk. Depending on what the shooter knows about the setting strategy, that information could make the sinking process more efficient.
A fundamental thought that I ran into is that the goal of battleship is to sink the other fleet first. That's a bit different than trying to sink the other fleet in the fastest average time. There is obviously some overlap, but it really doesn't matter whether a player loses by one shot or by 100. There may be situations where it makes sense to do things that increase the expected average sinking time in exchange for increasing the probability of fast wins.
For example, suppose that our opponent gets lucky and hits our destroyer with the first shot, it might make sense to shoot a coarse 'seek' pattern and gamble on getting lucky to hit their destroyer while covering all the possible placements for length 3 ships on the map.
Evaluating that kind of thing is a bit of work since it's getting into distribution vs distribution stuff and involves speculating about the opponent's strategy to generate a distribution of finish times based on what ships have been hit or sunk. A reasonable first estimate is that, if there's a seek pattern for N target ships covering M targets then the probability of finding all the ships by the Xth shot goes roughly as X choose (N-1) and that sinking each ship of length L is equally likely to take L-1, L, L+1 or L+2 additional shots.
I was trying to figure out a good way to talk about opponent-dependent strategy, but I had trouble thinking of any concrete examples where you wouldn't just want to minimize expected turns. I like this approach with the coarseness of the seek pattern and would love to take a closer look at it at some point.
I was doing some more thinking about shooting strategies with the goal of coming up with reasonably simply shooting strategies that are difficult to counter. I had originally thought that starting with gaps of 3 and then splitting those into gaps of 1 was a good candidate, but it then realized that it's possible to place the destroyer and the two 3-length ships so that at least one of them will always get missed by the initial pass.
This led me to think about starting with shooting diagonals that leave gaps of 5, and then either splitting those gaps of 5 into gaps of 2 (if the initial pass was lucky enough to hit a the destroyer) or into gaps of 1 (if it was not.) Then it occurred to me that shooting for gaps of 2 might also make sense as a high-risk strategy: 2/3 of the time, the destroyer will get hit by a "gaps of 2" pattern that is guaranteed to find all the other ships, and, since that "gaps of 2" pattern has fewer shots than a "gaps of 1" pattern, it's going to have a faster average finishing time when it does hit the destroyer.
That led to an intriguing possibility for a somewhat interactive approach: Shoot out a diagonal, and then pick a gap to the next diagonal based on the game state. That decision can be informed by what ships (on both sides) have already been sunk, but it can also be informed by any patterns that we can find in the opponent's shooting patterns combined with our knowledge of our own ship placements. That kind of thing can - in principle - be endlessly complex, but something simplified like initially making a pass with gaps of 5 and then making a decision to leave gaps of 1 or 2 on the second pass based on what ships have already been might get a lot of the possible benefit.
I really like this idea, and am curious to see how it would do. I spent a while trying to think of good examples of high risk versus low risk strategies, and I wasn't able to come up with any good ones. Your strategy is also probably one that could be adapted based on how your opponent is doing. If you're ahead, you can afford to choose smaller gaps, but if you're behind, it may be better to choose larger ones in hopes of getting lucky.
> ... Uniform placement is suboptimal for the seeking phase, but it actually turns out to be very close to optimal for the sinking phase. ...
I'm not sure it's as easy for the bigger ship or multi-ship interaction, but it shouldn't be so hard to work things out for a simplified version of the game where it's just the destroyer.
A naive "every placement is equally likely" strategy for the destroyer gives each of the middle 64 squares a 4/180 chance of holding a destroyer, each of the 32 non-corner edge squares a 3/180 chance of holding a destroyer, and the corners each a 2/180 chance of holding a destroyer. We should expect a greedy shooting strategy to "seek" 32 shots in the middle until it runs out of 4/180 cells, then 16 shots along the edge and then the corners at the end.
To calculate the expected seek time we can split the placements into ones that are going to get hit by the middle sweep (128/180), ones that get hit by the edge sweep (48/180) and the lucky corner placements (4/180).
The expected seek time for middle sweep placements is (32+1)/2. Their expected sink time is (4+1)/2.
The expected seek time for edge sweep placements is 32+(16+1)/2. Their expected sink time is (3+1)/2.
The expected seek time for corner sweep placements is 32+16+(2+1)/2. Their expected sink time is (2+1)/2
That works out to an expected completion time of (1169/45) or roughly 25.98 turns.
A 'nice' way to make a placement strategy with a uniform distribution is to make "even" placements along the edges twice as likely as other placements like (A1-A2). The uniform nature of this kind of distribution means that any checkerboard shooting strategy will have an expected seek time of (50+1)/2=25.5 shots (non-checkerboard seeking will be slower). The expected sink time will vary a little based on where the initial hit is:
Corners (2 of 50 targets in the sweep) have an expected sink time of (2+1)/2=1.5
Middle shots (32 of 50 targets in the sweep) have an expected sink time of (4+1)/2=2.5
The remaining edge hits (16 of 50 targets in the sweep) have a 50% chance to get sunk in 1 shot (if the placement is "even") and a 50% chance of a sink time of 1+(2+1)/2=2.5. For a total expected sink time of 1.75.
So the expected sink time is 2.22. And the expected completion time is 27.72 turns, which is about 1.75 turns longer than the expected completion time against the naive placement strategy. The expected sink time does get shorter (from about 2.34 to 2.22) but that's more than offset by the increase in seek time.
As ships get larger, the variability in sink times is going to stay about the same, but the seek times get much shorter, so I would expect that using uniform density placement strategies will be less advantageous for them.
This is a great analysis. Thank you. It's nice to see that a pure mathematical approach gave about the same result as the computer optimization, and I think your approach provides much nicer intuition.
> ... 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.
I've been thinking about how to make strategies that aren't exploitable, and there's an obvious way to think about it: If, for a moment, we only concern ourselves with the "seek" phase of the game, then any shooting strategy that is not exploitable is going to be equally likely to hit every square on the grid (or at least equally likely to hit every "domino"). Similarly, a placing strategy that is not exploitable should have an equal likelihood of placing a boat in each cell.
As you observed, the length 3 and 4 ships can't cover the battlefield evenly. The length 3 ships must be less likely in at least 1 square, and the length 4 ship must be less likely in at least 4 cells. If we also require the placement strategy to be symmetric with respect to rotations and reflections, then both will have to have at least 4 cells that are less likely to have a boat.
It is possible to pick placement patterns for the battleship, the cruiser and the submarine so that their combined probability is uniform. Though, since it's more valuable to sink smaller ships, a countering shooting strategy would target the squares where the smaller ships are more likely first. I'm also not sure how much easier those placement patterns make it to sink ships.
> ... 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. ...
I think that your 'naive' greedy strategy does well in that regard. It seems like there are two ways that current shots can impact future situations: One is that the shooter wants to be in a good position to exploit a lucky hit on an early small ship. The other is that the shooter wants to be able to efficiently hunt for small ships in the endgame if they didn't get hit early.
For an example of "exploiting lucky hits from hitting a small ship early", compare two scenarios. One player starts by shooting A1, A3, B2, C1, A5, B4, C3, D2, E1 and then hits a destroyer on A7. Another shoots A3, B2, C1, A7, B6, C5, D4, E3, F2, and then hits a destroyer on G1. Both were lucky to hit a destroyer on their 10th shot, but the second player has covered twice as much of the grid. (The greedy strategy likes to place shots far apart, and should do pretty well in this sense.)
For an example of "efficiently hunting in the late game" let's compare a player who starts by shooting diagonals spaced 4 apart A1, B2, C3... J10 then A6, B7, C8 ...E10, then F1, G2 ... J5 with one that starts by shooting diagonals spaced 3 apart instead: A1, B2.. J10 and then A5, B6, C7 F10, then A9, B10, then E1, F2 ... and so on. Assuming neither player is lucky enough to hit the destroyer, the player that left gaps of an even length can't split them in half while the one that left odd lengths can. I may be missing something, but it seems like initially splitting with gaps of 3 has a significantly better worst case scenario than initially splitting with gaps of 4. That said, it's only the worst case scenario. I'm not sure which one will do better on average against naive ship placement or counter strategies.
To your first point, I agree that you can optimize the seeking phase by making the heatmap as uniform as possible. I unfortunately found when I did this that there are pretty significant penalties to the sinking phase if we're not careful. Uniform placement is suboptimal for the seeking phase, but it actually turns out to be very close to optimal for the sinking phase. A lot of the optimizations I had to do for ship placement were to make sure that I wasn't slowing down the seeking phase at the expense of the sinking phase.
As for your second point, I agree that the odd gap seems much better. I think this is a place where the greedy strategy "got lucky" in some sense. I'm sure that if we changed the board dimensions or the lengths of the ships, I'm guessing the greedy strategy would almost always give diagonal sequences of guesses, but we'd probably find plenty of examples that gave inconvenient gap sizes.
> ... we'd probably find plenty of examples that gave inconvenient gap sizes ...
I wouldn't be that surprised that on large grids, a greedy strategy would try to leave gaps that are 1 shorter than the length of the longest ship, but - in some sense - the Battleship grid is rather small. The carrier is pretty big compared to the size of the grid, so there are basically always edge effects in play for it. Even for the destroyer, where edge effects are really only one cell deep, about 1/3 of the grid is edge cells.
> ... Uniform placement is suboptimal for the seeking phase, but it actually turns out to be very close to optimal for the sinking phase. ...
I did wonder whether uncertainty about which ship was being sunk could help with that, but I'm not sure it can do that much - there's a consistent pattern that hits close to edges are going to be on ships that are parallel to the edge.
I tend to think that it makes sense to keep ships at least one cell apart because, if they're next to each other, then there's a pretty high chance of finding a one ship "for free" while sinking another.
Regarding the "Linear Algebra Approach", if you insist on having strategies that are symmetric with respect to reflections and rotations, then there is only one placement strategy for destroyers and aircraft carriers that provides for a uniform density. For the length 3 and length 4 ships, its possible to get a uniform density for most of the board by sacrificing some cells like the corners.
That said, it also seems like it's possible to do better than the uniform density placement strategies. If we consider a simplified version of the game with just the destroyer, a uniform density strategy would give an expected "seek" time of 25.5 turns, and an expected "sink" time of 1.5 turns. That does seem like an optimum seek time, but placing using uniform 100/196 of the time, placing off-uniform on the border 32/196 of time, and placing using a uniform cover of the central 64 squares 64/196 of the time should decrease the expected seek time by a little bit less than 1, but increase the expected sink time by more than 1.
It's worth noting that the symmetric uniform placement of destroyers means at least an expected 25.5 turn seek time and 1.5 turn expected sink time, and that random checkerboard shooting means at most an expected seek time of 25.5 turns and an expected sink time of under 2.5 (thanks to edges and corners) so those solutions are within 1 turn of equilibrium in the simplified game.
I think there are good reasons to keep ships at least one cell apart, but also fairly good reasons to put them next to each other at least some of the time. If we never put ships next to each other, then we save the guesser a lot of work after they sink a ship, since we can now eliminate a lot of squares. I reran my code for a European version of Battleship, where ships can’t touch, and the number of configurations drops from 30 billion to 3.8 billion. It’s possible that my intuition about putting them next to each other even more often is wrong, though.
What do you mean by the “only one placement strategy … that provides for a uniform density?” Any strategy that chooses uniformly from 50 disjoint destroyer locations or 20 disjoint carrier locations should accomplish this (along with any linear combinations of these).
These issues with seek versus sink time were a pretty big inspiration for my later strategies. I’m curious to see how close we can get to the theoretical optimal for the destroyer, which should be close to 25.5+2.5=28, but a little less because of reductions in sink time at the edges and corners.
Regarding keeping the ships separate: It might be treating the bow and heck differently than the side pieces, since the ends in the long dimension are more likely to get hit.
Approximating, once again, with a toy model, suppose that we're dealing with just a battleship and a destroyer. Roughly 2/3 of the time, the battleship will get hit first. Less than 1/4 of the time, the shooter will start by hitting an end of the battle ship and then walk along the length to sink it without hitting the bow or heck cell. So more than 3/4 of the time that the battle one of those cells gets hit while the battleship is being sunk. (With an efficient search pattern, it's pretty unlikely that those cells were already hit before.) Thus there's a better than 2/3*3/4*1/2 = 1/4 chance that the cell gets hit while the destroyer is still alive. If you knew that the opponent had a 1/4 probability of shooting a cell, would you put a ship there? No, we want cells that have a chance of getting hit of 1/100 (or less). Since we expect about 60 cells to be left when the battleship is getting sunk, I guess we want 1/60 or less, but that's still less than 1/4.
I think it works out to something like a 1/20 chance for the cells along the side of the battleship to get hit while the destroyer is still alive, which isn't quite as huge, but it's still bigger than 1/60.
There's a temptation to think something like "we have put the ships there sometimes to keep the shooter honest" but the shooter is already forced to shoot at those cells at a pretty high rate from needing to sink the ship.
> ... I reran my code for a European version of Battleship, where ships can’t touch, and the number of configurations drops from 30 billion to 3.8 billion. ...
It would probably take some work to optimize a shooting strategy against a "no touch" placing strategy, but, if you were so inclined, it seems like you do have most of the pieces in place to do some statistical testing on how quickly arrangements with various numbers of touching ships get sunk compared to ones without.
I may be mistaken, but I think there is some confusion of what probabilities are being compared. As you say, the squares at the end of the battleship have at least a 1/4 chance of getting guessed, but I don't think 1/60 is the number we should be comparing it to. Using the greedy strategy, an average game takes about 47 guesses, of which 30 are misses (since the ships cover 17 squares). This means that the chances of a random unoccupied square being guessed is about 30/(100-17) = 36%. I'd have to check to see how often the squares at the end of the battleship are guessed in other situations to see if we get that extra 11% somewhere, but it doesn't seem that crazy that a greedy strategy would still guess those squares a bit less.
I definitely want to do some work on whether ships should touch at some point. That was definitely at the top of my list for things that didn't end up making it into the video.
TL;DR: Based on a simplified model, and the dubious assumption that my math is accurate, it looks like always separating the ships may break even as a setting strategy compared to letting them touch, but that separating them some of the time (I.e. a mix of separating and not separating) should be better than either strategy individually. It also doesn't look like the advantage is more than half a turn on average.
This is a long comment. I'm going to work through a simplified example of how I think the impact of ships touching or not work.
Things are a little bit tricky because there are are guesses about optimal strategies without actually knowing what the optimal strategies are. I'm going to approximate optimal shooting with a checkerboard strategy. I know that checkerboard strategies aren't necessarily as strong as greedy strategies, but your testing shows that the expected time to finish for checkerboard is pretty close to the expected time for the greedy strategy, and checkerboard strategies are easier to deductively reason about. (Checkerboard shooting strategies also make the shooter pretty indifferent to what the placer's strategy is, which is something that we tend to see in Nash Equilibriums.) And, once again, I'm going to analyze a simplified version of battleship where it's only a destroyer (i.e. the 2) and the battleship (the 4). For now, I'm just going to assume that this simplified game will give some insight into multi-ship interactions.
Now, against just the battleship, there's a 'checkerboard' strategy where the shooter picks some value t from 0-3 at random, and then shoots at cells where (row+column)%4 = t. For example, if t=2, the shooter would pick from the remaining cells from (1,1),(1,5),(1,9),(2,4),(2,8),(3,3),(3,7),(4,2),(4,6),(4,10)...(10,4), and (10,8) at random with a uniform distribution. Hitting all 25 of those squares will not leave any spaces big enough to hold a battleship. So the setter can, at best, bring the expected seek time for the battleship up to 12.5 turns.
These 'just the battleship' cells are a subset of a checkerboard to find the destroyer. (For example, the t=0 squares, (1,3),(1,7),(2,2),(2,6),(2,10) and so on, would complete a checkerboard with the t=2 squares above.) So there is a greedy/checkerboard compromise strategy that does a sweep for the battleship first, and then, if it hasn't been lucky enough to find the destroyer, in that sweep, finishes out the checkerboard looking for the destroyer.
This is a pretty easy strategy to analyze: The initial sweep will cover exactly one cell that has a battleship on it. 50% of the time, it will also cover one cell that has a destroyer on it. (The other 50% of the time it will not hit the destroyer.) Since the cells are swept randomly, if the destroyer is covered by the initial sweep, the destroyer and the battleship are equally likely to get hit.
I'm also going to assume that sinking a ship involves, on average, 1.5 misses. So that the sink phase for a destroyer takes 2.5 turns and the sink phase for the battleship takes 4.5 turns. (In practice average sink times will be shorter due to stuff like hits on the edges or proximity to already hit cells but I'm pretty confident it's within half a turn of that for efficient seeking strategies.) I'm also going to use that number to estimate the chance of accidentally hitting adjacent ships. In other words, since there are 10 squares next to a battleship, I'm going to assume that if the destroyer and battleship are touching and the battleship gets hit first, then there's a (1.5/10)=15% chance that the destroyer gets hit "by accident" while the battleship gets sunk. And, if the two are touching and the destroyer gets hit first, there's a 1.5/6=25% chance that the
Another simplifying assumption that I'm going to make is that, out of the 100 cells on the board, 10 are next to the battleship and the destroyer covers 2 cells, so that the chance that the are touching for a random arrangement of the ships is roughly 2*10/100=1/5.
Now things can be split into scenarios with estimated likelihoods and expected times:
The destroyer gets hit first (1/4), is touching the battleship (1/5), and there's an accidental hit (1/4) has an estimated probability of (1/80) and an expected finishing time of (25/4) (seeking the destroyer) + 2.5 (sink the destroyer) + 4.5 (sink the battleship) =53/4=13.25
The destroyer gets hit first (1/4), and there's no accidental hit (19/20) has a probability of (19/80) and an expected finishing time of (75/4) (seeking the battleship) + 2.5 (sink the destroyer) + 4.5 (sink the battleship) = 101/4 = 25.75
The battleship gets hit first (3/4), and there's an accidental hit (3/100) has a probability of (9/400) and an expected finishing time of (25/4) (seeking the battleship) + 2.5 + 4.5 = 13.25
The battleship gets hit first (3/4), there's no accidental hit (97/100) has a probability of (291/400) and an expected sink time of (75/4)/2+(25+25/2)/2 (seeking the destroyer) + 2.5 + 4.5 = 279/8 = 34.875
This works out to an expected finishing time of 31.95 turns or so.
Now let's say that the setter separates the ships instead, so that there's no chance of accidental hits and the shooter adjusts by not sweeping areas next to the first shot ship. Then:
1/4 of the time the destroyer is hit first. The destroyer is so small that sinking it won't give any free hits on the rest of the sweep to find the battleship and the expected time to finish is (75/4)+2.5+4.5=25.75
and
3/4 of the time, the battleship is hit first. The battleship and surrounding area eliminate 1 shot from the first 3 shots from the second sweep. This gives an expected time to finish of (72/4)/2 + (25+22/2)/2+ 2.5 + 4.5 = 34
This works out to an expected finish time of roughly 31.94 turns or so. Up to the accuracy of my approximations and assumptions, I would say that that's the same.
However, if the shooter doesn't take advantage of the fact that the ships are separated, separating the ships does make sinking the fleet take half a turn longer on average. So, based on this model, it looks like it should be a mix of separating and not separating in the Nash Equilibrium strategy.
This is great work. Thank you for taking the time to write this out. Everything looks right to me. The only thing I can think of that might make a significant difference is that the squares off the ends of a ship are more likely to be guessed than the squares on the sides of the ship, so maybe this is justification for putting ships alongside one another more often than end to end.
I guess I'm confused about how you're differentiating between "letting them touch" and "separating them some of the time." Does "some of the time" mean that we are allowing them to touch, but less often than random placement would dictate?
I'm not sure that the simplified model represents the game with more ships accurately. TBH, I'm not all that confident in my calculations about the seek times either.
> ... Does "some of the time" mean that we are allowing them to touch, but less often than random placement would dictate? ...
Yes. ( In this estimate I was treating all adjacent squares the same, so It could also be something like touching on the sides is OK but touching on the ends is not. )
> ... What do you mean by the “only one placement strategy … that provides for a uniform density?” ...
I was mistaken. I though that the only way to get uniform density for the destroyers was to - effectively - divide the grid into 2x2 squares. I played around with pencil and paper after making that comment and realized that there are more options than that.
There are 180 ways to place a destroyer on the grid, that reduces to 25 if we require the placement strategy to share the symmetries of the square. It reduces to 10 degrees of freedom if we specify a particular placement density. And, there is exactly one placement strategy for destroyers that has the expected duration for the "sink" part of things maximized for every hit on the interior of the grid. It's actually pretty simple: The placements A1 A2, A3 A4, A5 A6, A7 A8, A9 A10, A10 B10, C10 D10, E10 F10, G10 H10, I10 J10, J9 J10, J7 J8, J5 J6, J3 J4, J1 J2, I1 J1, G1 H1, E1 F1, C1 D1, and A1 B1 are chosen with probability 1/100. Every other possible placement is chosen with probability 1/200. Then interior hits take 2.5 extra turns, edge hits take 1.75 extra turns and corner hits 1.5 extra turns for sinking. I think it ends up working out to 25.5+2.2= 27.7 expected turns to find and sink the destroyer.
I've done some math and sacrificing the corners to optimize sink times on the edges seems to do worse at 27.56 expected turns.
Cool video and nice research. You mentioned Nash Equilibrium above, but made it sound like that idea was a failure. But what you've done when "smoothing" the probabilities of tiles such that corners and sides match the centre is actually just finding the Nash Equlibrium.
Maybe you thought that Nash Equilibrium requires 1 single strategy but this is an example of a "mixed strategy" Nash Equilibrium, where the most optimal thing to play is actually randomly chosen from a specific probability distribution. This also happens in RPS, where the Nash Equilibrium is to play each move exactly 1/3 of the time, so that the opponent can't do any better against you (otherwise they could identify the move you favor more and counter that).
Thank you for bringing this up. I think the ship placement strategy I talked about is close to the mixed strategy equilibrium, although it doesn’t consider multiple-ship effects, like how often ships should be placed next to each other, which I think should matter.
Figuring out the Nash Equilibruim strategy for the guesser seemed a lot harder, since it would presumably also be a mixed strategy, and just running simulations using this strategy would be really difficult.
Regarding finding Nash Equilibrium strategies: If we have a candidate mixed optimal strategy for one player, then any of the individual strategies in the other player's optimal counter strategy will have the same pay off. So, given a candidate mixed strategy for one player, we can search for a an optimal single (i.e. simple) counter-strategy for the other player and evaluate the candidate strategy based on how it performs against that optimized counter.
For the shooting strategy presented in the video there's basically a mix of eight strategies (for reflections and rotations), so it's probably practically feasible to just simulate it against a placement of ships, move one of the ships at random and try again over and over. (I think this is an example of simulated annealing.)
The thing is, I'm quite confident that the shooting strategy in the video is not particularly close to a NE since it predictably avoids the edges. And, when I try to come up with NE shooting strategies they tend start with something like "choose a random value from 0-5 then shoot all the cells where row+column is equal to that value mod 6 in a random order". That's already trillions of possible shooting sequences, so, while that kind of shooting approach can certainly be analyzed using combinatorics, it's impractical to directly simulate.
For Nash Equilibrium on setting side of things, it's pretty easy to come up with placement probabilities that make all cells except for the corners equally probable to hold each ship. A naive greedy approach like the one in the video won't provide any guidance about which of the 96 non-corner cells to start with in response. Searching for a good shooting response to that approach to ship placement (if there is one) will take more sophisticated thinking.
I definitely agree that my guessing strategy is not close to a Nash Equilibrium, although I don't think I had a great way of thinking about how to come up with one. I like your approach better.
For setting, I'm not actually sure that "equally likely to hold each ship" is actually optimal. I think another commenter might have pointed this out somewhere, but sinking time is generally lower for ships on the edges, so you probably do want to keep them slightly less likely to compensate for this. Even though I was running my placement algorithm against a greedy opponent, I do think that it was probably pretty close to optimal, partially because I think the focus on find time vs. sink time is fairly important to the analysis.
> ... For setting, I'm not actually sure that "equally likely to hold each ship" is actually optimal.... I think the focus on find time vs. sink time is fairly important to the analysis.
It may well be that it's best for the setter to optimize 'seek' for the short ships and 'sink' for the long ships. In your simulations, about 87% of the time, seeking time is determined by one of the short (length 2 or 3) ships. For the shorter ships, there is less edge effect, so the impact of making the distribution more even on sink times is smaller. Moreover, the longer seek times for those ships make even distribution more valuable for them.
For what it's worth, I have always played a version of battleship where the opponent calls out hit, miss, or sunk [ship]. But, in the copy of the rules that I found on-line:
https://officialgamerules.org/wp-content/uploads/2025/02/battleship.pdf
It indicates that players have to call out which ship was hit when a ship is hit, not just when it is sunk. Depending on what the shooter knows about the setting strategy, that information could make the sinking process more efficient.
A fundamental thought that I ran into is that the goal of battleship is to sink the other fleet first. That's a bit different than trying to sink the other fleet in the fastest average time. There is obviously some overlap, but it really doesn't matter whether a player loses by one shot or by 100. There may be situations where it makes sense to do things that increase the expected average sinking time in exchange for increasing the probability of fast wins.
For example, suppose that our opponent gets lucky and hits our destroyer with the first shot, it might make sense to shoot a coarse 'seek' pattern and gamble on getting lucky to hit their destroyer while covering all the possible placements for length 3 ships on the map.
Evaluating that kind of thing is a bit of work since it's getting into distribution vs distribution stuff and involves speculating about the opponent's strategy to generate a distribution of finish times based on what ships have been hit or sunk. A reasonable first estimate is that, if there's a seek pattern for N target ships covering M targets then the probability of finding all the ships by the Xth shot goes roughly as X choose (N-1) and that sinking each ship of length L is equally likely to take L-1, L, L+1 or L+2 additional shots.
I was trying to figure out a good way to talk about opponent-dependent strategy, but I had trouble thinking of any concrete examples where you wouldn't just want to minimize expected turns. I like this approach with the coarseness of the seek pattern and would love to take a closer look at it at some point.
I was doing some more thinking about shooting strategies with the goal of coming up with reasonably simply shooting strategies that are difficult to counter. I had originally thought that starting with gaps of 3 and then splitting those into gaps of 1 was a good candidate, but it then realized that it's possible to place the destroyer and the two 3-length ships so that at least one of them will always get missed by the initial pass.
This led me to think about starting with shooting diagonals that leave gaps of 5, and then either splitting those gaps of 5 into gaps of 2 (if the initial pass was lucky enough to hit a the destroyer) or into gaps of 1 (if it was not.) Then it occurred to me that shooting for gaps of 2 might also make sense as a high-risk strategy: 2/3 of the time, the destroyer will get hit by a "gaps of 2" pattern that is guaranteed to find all the other ships, and, since that "gaps of 2" pattern has fewer shots than a "gaps of 1" pattern, it's going to have a faster average finishing time when it does hit the destroyer.
That led to an intriguing possibility for a somewhat interactive approach: Shoot out a diagonal, and then pick a gap to the next diagonal based on the game state. That decision can be informed by what ships (on both sides) have already been sunk, but it can also be informed by any patterns that we can find in the opponent's shooting patterns combined with our knowledge of our own ship placements. That kind of thing can - in principle - be endlessly complex, but something simplified like initially making a pass with gaps of 5 and then making a decision to leave gaps of 1 or 2 on the second pass based on what ships have already been might get a lot of the possible benefit.
I really like this idea, and am curious to see how it would do. I spent a while trying to think of good examples of high risk versus low risk strategies, and I wasn't able to come up with any good ones. Your strategy is also probably one that could be adapted based on how your opponent is doing. If you're ahead, you can afford to choose smaller gaps, but if you're behind, it may be better to choose larger ones in hopes of getting lucky.
> ... Uniform placement is suboptimal for the seeking phase, but it actually turns out to be very close to optimal for the sinking phase. ...
I'm not sure it's as easy for the bigger ship or multi-ship interaction, but it shouldn't be so hard to work things out for a simplified version of the game where it's just the destroyer.
A naive "every placement is equally likely" strategy for the destroyer gives each of the middle 64 squares a 4/180 chance of holding a destroyer, each of the 32 non-corner edge squares a 3/180 chance of holding a destroyer, and the corners each a 2/180 chance of holding a destroyer. We should expect a greedy shooting strategy to "seek" 32 shots in the middle until it runs out of 4/180 cells, then 16 shots along the edge and then the corners at the end.
To calculate the expected seek time we can split the placements into ones that are going to get hit by the middle sweep (128/180), ones that get hit by the edge sweep (48/180) and the lucky corner placements (4/180).
The expected seek time for middle sweep placements is (32+1)/2. Their expected sink time is (4+1)/2.
The expected seek time for edge sweep placements is 32+(16+1)/2. Their expected sink time is (3+1)/2.
The expected seek time for corner sweep placements is 32+16+(2+1)/2. Their expected sink time is (2+1)/2
That works out to an expected completion time of (1169/45) or roughly 25.98 turns.
A 'nice' way to make a placement strategy with a uniform distribution is to make "even" placements along the edges twice as likely as other placements like (A1-A2). The uniform nature of this kind of distribution means that any checkerboard shooting strategy will have an expected seek time of (50+1)/2=25.5 shots (non-checkerboard seeking will be slower). The expected sink time will vary a little based on where the initial hit is:
Corners (2 of 50 targets in the sweep) have an expected sink time of (2+1)/2=1.5
Middle shots (32 of 50 targets in the sweep) have an expected sink time of (4+1)/2=2.5
The remaining edge hits (16 of 50 targets in the sweep) have a 50% chance to get sunk in 1 shot (if the placement is "even") and a 50% chance of a sink time of 1+(2+1)/2=2.5. For a total expected sink time of 1.75.
So the expected sink time is 2.22. And the expected completion time is 27.72 turns, which is about 1.75 turns longer than the expected completion time against the naive placement strategy. The expected sink time does get shorter (from about 2.34 to 2.22) but that's more than offset by the increase in seek time.
As ships get larger, the variability in sink times is going to stay about the same, but the seek times get much shorter, so I would expect that using uniform density placement strategies will be less advantageous for them.
This is a great analysis. Thank you. It's nice to see that a pure mathematical approach gave about the same result as the computer optimization, and I think your approach provides much nicer intuition.
> ... 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.
I've been thinking about how to make strategies that aren't exploitable, and there's an obvious way to think about it: If, for a moment, we only concern ourselves with the "seek" phase of the game, then any shooting strategy that is not exploitable is going to be equally likely to hit every square on the grid (or at least equally likely to hit every "domino"). Similarly, a placing strategy that is not exploitable should have an equal likelihood of placing a boat in each cell.
As you observed, the length 3 and 4 ships can't cover the battlefield evenly. The length 3 ships must be less likely in at least 1 square, and the length 4 ship must be less likely in at least 4 cells. If we also require the placement strategy to be symmetric with respect to rotations and reflections, then both will have to have at least 4 cells that are less likely to have a boat.
It is possible to pick placement patterns for the battleship, the cruiser and the submarine so that their combined probability is uniform. Though, since it's more valuable to sink smaller ships, a countering shooting strategy would target the squares where the smaller ships are more likely first. I'm also not sure how much easier those placement patterns make it to sink ships.
> ... 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. ...
I think that your 'naive' greedy strategy does well in that regard. It seems like there are two ways that current shots can impact future situations: One is that the shooter wants to be in a good position to exploit a lucky hit on an early small ship. The other is that the shooter wants to be able to efficiently hunt for small ships in the endgame if they didn't get hit early.
For an example of "exploiting lucky hits from hitting a small ship early", compare two scenarios. One player starts by shooting A1, A3, B2, C1, A5, B4, C3, D2, E1 and then hits a destroyer on A7. Another shoots A3, B2, C1, A7, B6, C5, D4, E3, F2, and then hits a destroyer on G1. Both were lucky to hit a destroyer on their 10th shot, but the second player has covered twice as much of the grid. (The greedy strategy likes to place shots far apart, and should do pretty well in this sense.)
For an example of "efficiently hunting in the late game" let's compare a player who starts by shooting diagonals spaced 4 apart A1, B2, C3... J10 then A6, B7, C8 ...E10, then F1, G2 ... J5 with one that starts by shooting diagonals spaced 3 apart instead: A1, B2.. J10 and then A5, B6, C7 F10, then A9, B10, then E1, F2 ... and so on. Assuming neither player is lucky enough to hit the destroyer, the player that left gaps of an even length can't split them in half while the one that left odd lengths can. I may be missing something, but it seems like initially splitting with gaps of 3 has a significantly better worst case scenario than initially splitting with gaps of 4. That said, it's only the worst case scenario. I'm not sure which one will do better on average against naive ship placement or counter strategies.
To your first point, I agree that you can optimize the seeking phase by making the heatmap as uniform as possible. I unfortunately found when I did this that there are pretty significant penalties to the sinking phase if we're not careful. Uniform placement is suboptimal for the seeking phase, but it actually turns out to be very close to optimal for the sinking phase. A lot of the optimizations I had to do for ship placement were to make sure that I wasn't slowing down the seeking phase at the expense of the sinking phase.
As for your second point, I agree that the odd gap seems much better. I think this is a place where the greedy strategy "got lucky" in some sense. I'm sure that if we changed the board dimensions or the lengths of the ships, I'm guessing the greedy strategy would almost always give diagonal sequences of guesses, but we'd probably find plenty of examples that gave inconvenient gap sizes.
> ... we'd probably find plenty of examples that gave inconvenient gap sizes ...
I wouldn't be that surprised that on large grids, a greedy strategy would try to leave gaps that are 1 shorter than the length of the longest ship, but - in some sense - the Battleship grid is rather small. The carrier is pretty big compared to the size of the grid, so there are basically always edge effects in play for it. Even for the destroyer, where edge effects are really only one cell deep, about 1/3 of the grid is edge cells.
> ... Uniform placement is suboptimal for the seeking phase, but it actually turns out to be very close to optimal for the sinking phase. ...
I did wonder whether uncertainty about which ship was being sunk could help with that, but I'm not sure it can do that much - there's a consistent pattern that hits close to edges are going to be on ships that are parallel to the edge.
I tend to think that it makes sense to keep ships at least one cell apart because, if they're next to each other, then there's a pretty high chance of finding a one ship "for free" while sinking another.
Regarding the "Linear Algebra Approach", if you insist on having strategies that are symmetric with respect to reflections and rotations, then there is only one placement strategy for destroyers and aircraft carriers that provides for a uniform density. For the length 3 and length 4 ships, its possible to get a uniform density for most of the board by sacrificing some cells like the corners.
That said, it also seems like it's possible to do better than the uniform density placement strategies. If we consider a simplified version of the game with just the destroyer, a uniform density strategy would give an expected "seek" time of 25.5 turns, and an expected "sink" time of 1.5 turns. That does seem like an optimum seek time, but placing using uniform 100/196 of the time, placing off-uniform on the border 32/196 of time, and placing using a uniform cover of the central 64 squares 64/196 of the time should decrease the expected seek time by a little bit less than 1, but increase the expected sink time by more than 1.
It's worth noting that the symmetric uniform placement of destroyers means at least an expected 25.5 turn seek time and 1.5 turn expected sink time, and that random checkerboard shooting means at most an expected seek time of 25.5 turns and an expected sink time of under 2.5 (thanks to edges and corners) so those solutions are within 1 turn of equilibrium in the simplified game.
A lot of good ideas here. A few of my thoughts.
I think there are good reasons to keep ships at least one cell apart, but also fairly good reasons to put them next to each other at least some of the time. If we never put ships next to each other, then we save the guesser a lot of work after they sink a ship, since we can now eliminate a lot of squares. I reran my code for a European version of Battleship, where ships can’t touch, and the number of configurations drops from 30 billion to 3.8 billion. It’s possible that my intuition about putting them next to each other even more often is wrong, though.
What do you mean by the “only one placement strategy … that provides for a uniform density?” Any strategy that chooses uniformly from 50 disjoint destroyer locations or 20 disjoint carrier locations should accomplish this (along with any linear combinations of these).
These issues with seek versus sink time were a pretty big inspiration for my later strategies. I’m curious to see how close we can get to the theoretical optimal for the destroyer, which should be close to 25.5+2.5=28, but a little less because of reductions in sink time at the edges and corners.
Regarding keeping the ships separate: It might be treating the bow and heck differently than the side pieces, since the ends in the long dimension are more likely to get hit.
Approximating, once again, with a toy model, suppose that we're dealing with just a battleship and a destroyer. Roughly 2/3 of the time, the battleship will get hit first. Less than 1/4 of the time, the shooter will start by hitting an end of the battle ship and then walk along the length to sink it without hitting the bow or heck cell. So more than 3/4 of the time that the battle one of those cells gets hit while the battleship is being sunk. (With an efficient search pattern, it's pretty unlikely that those cells were already hit before.) Thus there's a better than 2/3*3/4*1/2 = 1/4 chance that the cell gets hit while the destroyer is still alive. If you knew that the opponent had a 1/4 probability of shooting a cell, would you put a ship there? No, we want cells that have a chance of getting hit of 1/100 (or less). Since we expect about 60 cells to be left when the battleship is getting sunk, I guess we want 1/60 or less, but that's still less than 1/4.
I think it works out to something like a 1/20 chance for the cells along the side of the battleship to get hit while the destroyer is still alive, which isn't quite as huge, but it's still bigger than 1/60.
There's a temptation to think something like "we have put the ships there sometimes to keep the shooter honest" but the shooter is already forced to shoot at those cells at a pretty high rate from needing to sink the ship.
> ... I reran my code for a European version of Battleship, where ships can’t touch, and the number of configurations drops from 30 billion to 3.8 billion. ...
It would probably take some work to optimize a shooting strategy against a "no touch" placing strategy, but, if you were so inclined, it seems like you do have most of the pieces in place to do some statistical testing on how quickly arrangements with various numbers of touching ships get sunk compared to ones without.
I may be mistaken, but I think there is some confusion of what probabilities are being compared. As you say, the squares at the end of the battleship have at least a 1/4 chance of getting guessed, but I don't think 1/60 is the number we should be comparing it to. Using the greedy strategy, an average game takes about 47 guesses, of which 30 are misses (since the ships cover 17 squares). This means that the chances of a random unoccupied square being guessed is about 30/(100-17) = 36%. I'd have to check to see how often the squares at the end of the battleship are guessed in other situations to see if we get that extra 11% somewhere, but it doesn't seem that crazy that a greedy strategy would still guess those squares a bit less.
I definitely want to do some work on whether ships should touch at some point. That was definitely at the top of my list for things that didn't end up making it into the video.
TL;DR: Based on a simplified model, and the dubious assumption that my math is accurate, it looks like always separating the ships may break even as a setting strategy compared to letting them touch, but that separating them some of the time (I.e. a mix of separating and not separating) should be better than either strategy individually. It also doesn't look like the advantage is more than half a turn on average.
This is a long comment. I'm going to work through a simplified example of how I think the impact of ships touching or not work.
Things are a little bit tricky because there are are guesses about optimal strategies without actually knowing what the optimal strategies are. I'm going to approximate optimal shooting with a checkerboard strategy. I know that checkerboard strategies aren't necessarily as strong as greedy strategies, but your testing shows that the expected time to finish for checkerboard is pretty close to the expected time for the greedy strategy, and checkerboard strategies are easier to deductively reason about. (Checkerboard shooting strategies also make the shooter pretty indifferent to what the placer's strategy is, which is something that we tend to see in Nash Equilibriums.) And, once again, I'm going to analyze a simplified version of battleship where it's only a destroyer (i.e. the 2) and the battleship (the 4). For now, I'm just going to assume that this simplified game will give some insight into multi-ship interactions.
Now, against just the battleship, there's a 'checkerboard' strategy where the shooter picks some value t from 0-3 at random, and then shoots at cells where (row+column)%4 = t. For example, if t=2, the shooter would pick from the remaining cells from (1,1),(1,5),(1,9),(2,4),(2,8),(3,3),(3,7),(4,2),(4,6),(4,10)...(10,4), and (10,8) at random with a uniform distribution. Hitting all 25 of those squares will not leave any spaces big enough to hold a battleship. So the setter can, at best, bring the expected seek time for the battleship up to 12.5 turns.
These 'just the battleship' cells are a subset of a checkerboard to find the destroyer. (For example, the t=0 squares, (1,3),(1,7),(2,2),(2,6),(2,10) and so on, would complete a checkerboard with the t=2 squares above.) So there is a greedy/checkerboard compromise strategy that does a sweep for the battleship first, and then, if it hasn't been lucky enough to find the destroyer, in that sweep, finishes out the checkerboard looking for the destroyer.
This is a pretty easy strategy to analyze: The initial sweep will cover exactly one cell that has a battleship on it. 50% of the time, it will also cover one cell that has a destroyer on it. (The other 50% of the time it will not hit the destroyer.) Since the cells are swept randomly, if the destroyer is covered by the initial sweep, the destroyer and the battleship are equally likely to get hit.
I'm also going to assume that sinking a ship involves, on average, 1.5 misses. So that the sink phase for a destroyer takes 2.5 turns and the sink phase for the battleship takes 4.5 turns. (In practice average sink times will be shorter due to stuff like hits on the edges or proximity to already hit cells but I'm pretty confident it's within half a turn of that for efficient seeking strategies.) I'm also going to use that number to estimate the chance of accidentally hitting adjacent ships. In other words, since there are 10 squares next to a battleship, I'm going to assume that if the destroyer and battleship are touching and the battleship gets hit first, then there's a (1.5/10)=15% chance that the destroyer gets hit "by accident" while the battleship gets sunk. And, if the two are touching and the destroyer gets hit first, there's a 1.5/6=25% chance that the
Another simplifying assumption that I'm going to make is that, out of the 100 cells on the board, 10 are next to the battleship and the destroyer covers 2 cells, so that the chance that the are touching for a random arrangement of the ships is roughly 2*10/100=1/5.
Now things can be split into scenarios with estimated likelihoods and expected times:
The destroyer gets hit first (1/4), is touching the battleship (1/5), and there's an accidental hit (1/4) has an estimated probability of (1/80) and an expected finishing time of (25/4) (seeking the destroyer) + 2.5 (sink the destroyer) + 4.5 (sink the battleship) =53/4=13.25
The destroyer gets hit first (1/4), and there's no accidental hit (19/20) has a probability of (19/80) and an expected finishing time of (75/4) (seeking the battleship) + 2.5 (sink the destroyer) + 4.5 (sink the battleship) = 101/4 = 25.75
The battleship gets hit first (3/4), and there's an accidental hit (3/100) has a probability of (9/400) and an expected finishing time of (25/4) (seeking the battleship) + 2.5 + 4.5 = 13.25
The battleship gets hit first (3/4), there's no accidental hit (97/100) has a probability of (291/400) and an expected sink time of (75/4)/2+(25+25/2)/2 (seeking the destroyer) + 2.5 + 4.5 = 279/8 = 34.875
This works out to an expected finishing time of 31.95 turns or so.
Now let's say that the setter separates the ships instead, so that there's no chance of accidental hits and the shooter adjusts by not sweeping areas next to the first shot ship. Then:
1/4 of the time the destroyer is hit first. The destroyer is so small that sinking it won't give any free hits on the rest of the sweep to find the battleship and the expected time to finish is (75/4)+2.5+4.5=25.75
and
3/4 of the time, the battleship is hit first. The battleship and surrounding area eliminate 1 shot from the first 3 shots from the second sweep. This gives an expected time to finish of (72/4)/2 + (25+22/2)/2+ 2.5 + 4.5 = 34
This works out to an expected finish time of roughly 31.94 turns or so. Up to the accuracy of my approximations and assumptions, I would say that that's the same.
However, if the shooter doesn't take advantage of the fact that the ships are separated, separating the ships does make sinking the fleet take half a turn longer on average. So, based on this model, it looks like it should be a mix of separating and not separating in the Nash Equilibrium strategy.
This is great work. Thank you for taking the time to write this out. Everything looks right to me. The only thing I can think of that might make a significant difference is that the squares off the ends of a ship are more likely to be guessed than the squares on the sides of the ship, so maybe this is justification for putting ships alongside one another more often than end to end.
I guess I'm confused about how you're differentiating between "letting them touch" and "separating them some of the time." Does "some of the time" mean that we are allowing them to touch, but less often than random placement would dictate?
> ... . Everything looks right to me. ...
I'm not sure that the simplified model represents the game with more ships accurately. TBH, I'm not all that confident in my calculations about the seek times either.
> ... Does "some of the time" mean that we are allowing them to touch, but less often than random placement would dictate? ...
Yes. ( In this estimate I was treating all adjacent squares the same, so It could also be something like touching on the sides is OK but touching on the ends is not. )
> ... What do you mean by the “only one placement strategy … that provides for a uniform density?” ...
I was mistaken. I though that the only way to get uniform density for the destroyers was to - effectively - divide the grid into 2x2 squares. I played around with pencil and paper after making that comment and realized that there are more options than that.
There are 180 ways to place a destroyer on the grid, that reduces to 25 if we require the placement strategy to share the symmetries of the square. It reduces to 10 degrees of freedom if we specify a particular placement density. And, there is exactly one placement strategy for destroyers that has the expected duration for the "sink" part of things maximized for every hit on the interior of the grid. It's actually pretty simple: The placements A1 A2, A3 A4, A5 A6, A7 A8, A9 A10, A10 B10, C10 D10, E10 F10, G10 H10, I10 J10, J9 J10, J7 J8, J5 J6, J3 J4, J1 J2, I1 J1, G1 H1, E1 F1, C1 D1, and A1 B1 are chosen with probability 1/100. Every other possible placement is chosen with probability 1/200. Then interior hits take 2.5 extra turns, edge hits take 1.75 extra turns and corner hits 1.5 extra turns for sinking. I think it ends up working out to 25.5+2.2= 27.7 expected turns to find and sink the destroyer.
I've done some math and sacrificing the corners to optimize sink times on the edges seems to do worse at 27.56 expected turns.
Cool video and nice research. You mentioned Nash Equilibrium above, but made it sound like that idea was a failure. But what you've done when "smoothing" the probabilities of tiles such that corners and sides match the centre is actually just finding the Nash Equlibrium.
Maybe you thought that Nash Equilibrium requires 1 single strategy but this is an example of a "mixed strategy" Nash Equilibrium, where the most optimal thing to play is actually randomly chosen from a specific probability distribution. This also happens in RPS, where the Nash Equilibrium is to play each move exactly 1/3 of the time, so that the opponent can't do any better against you (otherwise they could identify the move you favor more and counter that).
Thank you for bringing this up. I think the ship placement strategy I talked about is close to the mixed strategy equilibrium, although it doesn’t consider multiple-ship effects, like how often ships should be placed next to each other, which I think should matter.
Figuring out the Nash Equilibruim strategy for the guesser seemed a lot harder, since it would presumably also be a mixed strategy, and just running simulations using this strategy would be really difficult.