Hacker News Reader

Comment by cmeacham98 | Hacker News Reader

A key point of this seems to be assuming that the other players place their ships at random, which obviously isn't true when humans are playing. For example, "hiding" a ship on the edge is super common behavior from people I've played against, despite the author's heatmap suggesting edges are one of the _least_ likely places.

View on HN

The discrepancy is probably explainable by game theory. There is some set of strategies, defined by the distribution you use to place your own ships and the distribution for picking guesses at enemy positions. If we start from the naive assumption of a uniform distribution for both, this strategy is exploitable using exactly the heatmap from the article. So next we can iterate, assume that the opposing player is using the heatmap from the article, and generate a new distribution of ship placements designed to be unlikely to be picked. From there we get a new heatmap, which can be iterated again in the same manner until eventual reaching convergence with the Nash Eq. I wonder what the Nash Eq of Battleship is and how similar it is to observed real player strategies.

For placement, I am fairly confident the best possible strategy will be one in which every tile has a uniform chance of being chosen for a ship. Any other strategy will result in the opponent being able to gain an advantage by preferring certain tiles when firing, and thus the equilibrium and best strategy will be one where that cannot happen.

However, I am also fairly certain that human players, especially those playing a casual iMessage battleships game, do a very bad job of following this strategy.

To be nitpicky, the process you described won't necessarily reach a Nash, as it may cycle. But if each player best-responds against the average of all opponent strategies so far, then said average strategies will converge to a Nash (fictitious play).

...I've implemented the fictitious play algorithm before. I should have caught that!

Agreed, while I understand he used random maps to generate the heatmap. Using the distributions from actual games would likely be far more useful.

I look forward to the Recaptcha “Play this game of Battleship”.

A variation on https://xkcd.com/810/ except instead creating bots that play like humans!

I like it.

In reality bots would probably post the same few comments over and over, with random synonyms substituted.

That's maybe the most wholesome xkcd I've seen.

Would be interesting to analyze what ship-placement strategy/distribution makes the opponent indifferent in terms of which cell to shot.

It's similar to rock-paper-scissors in this respect. Humans play in patterns rather than randomly, so you can actually win if you can predict the pattern.

Also when you destroy a ship hidden in a corner, you only get to exclude half of usual surrounding tiles (since ships can't connect). So long ships of lengths 4, and 3 are best to be placed on edges, because they're going to be hit sooner rather than later anyway, while small ships can try dodge late-game shots.

Edit: just realized a lot of commenters here played a version where the ships can touch. My reasoning above won't apply in such case.

Reply on news.ycombinator.com