6 ms·
Battleship
- moffkalast 5y ago> Optimal Sunk-cost Strategy Heh
- funkattack 5y agoThe most important rule is rule number 4. Ships have to be placed bevor the first shot.
- frosted-flakes 5y agoThat kind of goes without saying, no?
- dmurray 5y ago> With this heatmap, the center 4 squares are the best place for your first shot Surely the right strategy is some kind of mixed strategy. If you always go for the centre squares on your first shot, your opponent can exploit this by not placing ships there.
- Carbocarde 5y agoDefinitely in a real game against a human you would want to adjust the weighting based on historical game data. When I'm playing games against my friends, I treat the solver like an advisor. So sometimes I ignore what the solver says and instead choose from only edge squares.
- deleted 5y ago[deleted]
- WalterBright 5y agoI had good success by firing at the places the opponent's ships weren't at in the last round. I'd also place my ships in the same places as the previous round.
- cmeacham98 5y agoA 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.
- 5y ago
- servytor 5y ago"We already know the squares surrounding our hit are eliminated, so let’s pick the next square by only looking at the probability scores for the squares that weren’t already eliminated." Yet the next pick is a square next to the hit. Huh?
- Carbocarde 5y agoAuthor here. Yeah that graphic is a little confusing. Since we have a 3x3 area of squares that are already accounted for by the current hit, we only focus on expanding that 3x3 area into a 3x4 or 4x3 area by shooting adjacent squares. We're expanding the 3x3 to 4x3, so we only focus on the delta between the 3x3 and 4x3 area (hence highlighting the edges of the 3x3 area). Once we decide which direction would result in the most potential ships being eliminated, we shoot in that direction. Hope this helps!
- YossarianFrPrez 5y agoThis reminds me that Dr. Todd Gureckis, a researcher at NYU, has some work looking at inferring which hypothesis-testing strategies people are using as they play (a version of) battleship. The three strategies he and his colleagues identify are a 'naive' or 'positive-testing strategy', an 'label entropy reduction strategy' and an 'information gain' strategy. The work is described in "A preference for the unpredictable over the informative during self-directed learning." It is an interesting paper. If you are interested in this post, you might like it: https://escholarship.org/content/qt0059t11p/qt0059t11p.pdf https://escholarship.org/content/qt0059t11p/qt0059t11p.pdf
- kqr 5y agoThis was interesting and highlighted some distinctions between strategies that I hadn't explicitly considered before. Thanks for sharing!
- Waterluvian 5y agoI really want to build some sort of learning algorithm that plays a game. And just run that game on a screen in my room and normal speed for years, slowly watching it get better. A game like Battleship definitely seems like the right idea.
- ghaff 5y agohttps://towardsdatascience.com/an-artificial-intelligence-learns-to-play-battleship-ebd2cf9adb01 https://towardsdatascience.com/an-artificial-intelligence-le... There save also been a fair number of papers on the topic. It’s mostly focused on reinforcement earning which has been interesting for games if less so elsewhere.
- Waterluvian 5y agoThanks for the link!
- schoen 5y agoIs the "no ships adjacent to other ships" rule part of the original commercial Battleship game? When I played it with my family, we didn't follow that rule, and so there was considerable scope for ambiguity about whether nearby hits were part of the same ship or not.
- whitexn--g28h 5y agoThis is the commercial version I remember which has less ships, a smaller board and no adjacency rules https://www.hasbro.com/common/instruct/battleship.pdf https://www.hasbro.com/common/instruct/battleship.pdf
- jtokoph 5y agoI love how the game came without the labels pre-attached. Gone are the days of "some assembly required".
- dylan604 5y agoOf all of the assembly required, I wonder why just this one sticker on the outside. The interior had insert cards/stickers for the ocean and other inserts in the lid to look like HUD console or something [0]. So why not make thos assembly required too? [0]https://3dprint.com/wp-content/uploads/2016/01/Battleship.jpg https://3dprint.com/wp-content/uploads/2016/01/Battleship.jp...
- frosted-flakes 5y agoNot really. My young cousins got a battleship ge very similar to this as a Christmas gift last year, stickers not yet applied.
- Gare 5y agoMB version appears to allow it, and I recall playing it like you did.
- whiskyant 5y agoNope, don't think any commercial version has that rule. Seems like a house rule or a misunderstanding of the official ruleset.
- drekipus 5y agoThis reminds me of a project idea I had... I was thinking of setting up a small server that can emulate some up multiplayer games, such as battleship, connect 4, even perhaps monopoly. Then people submit code, or connect their machines to it, and it becomes "battle of the algorithms". You'd have to register an algorithm name / version, and compete a few times against other algorithms, to be placed on the leaderboard for that game*. Each game could just be stored as plaintext, so it would be easy to replay each move and visualise it on the website. I haven't yet begun creating it, but it'd be great to see how your algorithm would work against another; You'd also have to consider how to place your ships as well. (probably sticking them in the corners could be easily dealt with, right? Looking at this algorithm it seems like it's pretty optimal, I don't think there's much else that could be done with Battleships. Playing with other human players would be a different outcome.. * I would only really expect algorithms work per game, not across games.
- hntcz 5y agoAbout 20 years ago when I was a teenager Microsoft did this in my country with rock-paper-scissors. XML-RPC-based web services were new at the time and they promoted it this way. You hosted your own web service and they called it to play, I think 10 or 20 games against each opponent in your group. Obviously you can't get an edge against someone playing completely randomly but they placed a bunch of simpler bots in the groups that you could detect (e.g, always playing a pattern). Group winners made it to the final. It was awesome, thanks for reminding me of that memory!
- mormegil 5y ago> you can't get an edge against someone playing completely randomly Sure, random choice is not only a Nash equilibrium, it even has a fixed expected value without regard to the other player's strategy, _but_ that is only in the basic two-player game. If you have a tournament and some players use other strategies, you can get better score against them by a non-random strategy, meaning you can beat the random strategy in the global tournament. But it also means someone can defeat you! Which means RPS tournaments are interesting even if the game seemed almost trivial!
- 5y ago
- driscoll42 5y agoThere's a decent blog article here with some more strategies for Battleship: https://datagenetics.com/blog/december32011/index.html https://datagenetics.com/blog/december32011/index.html
- kqr 5y agoI thought this was going to be that article! It's a classic.
- cochleari_major 5y agoReminds me of a fun video about speedrunning a battleship minigame in some Zelda title: https://www.youtube.com/watch?v=1hs451PfFzQ https://www.youtube.com/watch?v=1hs451PfFzQ
- NaturalPhallacy 5y agoThis was way more interesting than the OP lol Thanks!
- WalterBright 5y agoStratego is another simple, deterministic game, but picking a successful strategy is far from simple. I played it a lot as a kid, and came up with a strategy that beat everyone I played against 100%. I never let on what it was, to their frustration :-) Risk was good, but I disliked the randomness of it. There wasn't a whole lot of strategy to it, being way too much dependent on the roll of the dice.
- HideousKojima 5y agoHiding the flag near the frontlines is my Stratego strategy, no one ever suspects it
- ghaff 5y agoNot the first time maybe. But if you play with the same people they obviously learn it and it’s probably not a great location for a variety of other reasons.
- nosefrog 5y agoWhat's your strategy? :-)
- WalterBright 5y agoI'm not that easy!
- _pastel 5y agoNote that greedy probability maximization or information gain are not quite optimal. Not without some kind of search or tiling heuristics. For example, suppose you've eliminated all the other ships and are only looking for the 2-ship. If you overlay a checkerboard, it's best to only shoot on squares corresponding to a single color on the checkerboard. This guarantees you won't waste shots adjacent to previous misses once the search area fills up.
- Imnimo 5y ago>Information gain can be combined with the Naive Strategy in order to calculate both the probability of a hit, along with the value that hit would provide (how many possible positions it would eliminate). Isn't this missing the other half? It seems to me that the information you expect to gain depends on both the information you would gain from a hit AND the information you would gain from a miss, weighted by the likelihood of those outcomes.
- CSMastermind 5y agoThere's a popular battleship clone called Fleet Battle with a large active player base. There's a few different strategies and shot patterns that top players use but none of them shoots directly in the middle to start the game. That game does have slightly different rules with a different board size, different ship shapes, and it allows you to place ships adjacent to each other. I'm not sure how much that would make a different in the approach but it would be interesting to see how those aspects change the analysis and compare them to what we observe in real human players.
- mixedmath 5y agoAs an aside (if the author happens to read this), I would happily subscribe to an RSS or atom feed for this site, but I don't see one.
- oneoff786 5y agoIf you like battleship, check out captain sonar. A real time, 4v4 (possibly with fewer), submarine vs submarine board game that’s sort of like battleship with movement. Real time as in you can make moves as fast as your team can execute them. But at the cost of giving information that signals your location.
- jonbaer 5y agoThere are a few gyms for battleship, https://github.com/thomashirtz/gym-battleship https://github.com/thomashirtz/gym-battleship ... some variations I would like to see involve a much bigger grid (100x100) and moving ships along axis @ various rates ... but then you would get a different game I guess.
- rahimiali 5y agoThe strategy is a greedy one. You're maximizing the one-step-ahead information gain. But this can end you in a spot where two steps ahead, you're only left with low information-gain moves, or at least, lower than you would have if you had planned better. Why not unroll the search a few more iterations and pick the move that maximizes average information gain k steps ahead?
- Andrew_nenakhov 5y agoThe real winning strategy in playing battleship is to minimize wasted spaces when ships are hit, then relying on luck to hide the last 1 square ones in a big free space in the middle. Basically, put all big ships on the edges, this way when they are hit you lose far less squares than if it is in the middle. For example, with 4 square ship you lose 10 squares of it is in the corner, and 18 if it is in the middle. Make all big ships squares overlap as much as possible, they are a liability anyway, and win with your randomly placed 1sq ones.
- GnarfGnarf 5y agoInteresting. I did a similar analysis when I wrote Battleship in assembler for a 32K card computer in 1972. Input was through the maintenance panel toggle switches.
- nojvek 5y agoAt UNSW where I did my bachelors, Many of my courses had a battle of algorithms as assignments. One was building a Lego mindstorms robot that would fight other robots. Or follow black tape on white board to traverse a maze. Other assignments would involve bots that would play yahtzee, connect four, chess and other games. I spent so much time on these assignments trying to win that I gave only the basic effort needed to pass on other assignments. At one point I stayed up 48 hours straight to gain an extra 1% advantage by rewriting all my java code in c++ so I could traverse more possible scenarios. Fun days.