4 ms·
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, "h
by cmeacham98 5y ago
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.
- driscoll42 5y agoAgreed, while I understand he used random maps to generate the heatmap. Using the distributions from actual games would likely be far more useful.
- SV_BubbleTime 5y agoI look forward to the Recaptcha “Play this game of Battleship”.
- Shared404 5y agoA variation on https://xkcd.com/810/ https://xkcd.com/810/ except instead creating bots that play like humans! I like it.
- colordrops 5y agoIt'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.
- greenbay20 5y agoWould be interesting to analyze what ship-placement strategy/distribution makes the opponent indifferent in terms of which cell to shot.
- IIAOPSW 5y agoThe 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.
- kevinwang 5y agoTo 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).
- IIAOPSW 5y ago...I've implemented the fictitious play algorithm before. I should have caught that!
- cmeacham98 5y agoFor 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.
- Etherlord87 5y agoAlso 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.