[HN Gopher] Battleship
___________________________________________________________________
Battleship
Author : signa11
Score : 108 points
Date : 2022-04-02 20:58 UTC (2 hours ago)
(HTM) web link (www.nulliq.dev)
(TXT) w3m dump (www.nulliq.dev)
| drekipus wrote:
| This 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 wrote:
| About 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!
| onionisafruit wrote:
| I worked on something like that for a while that I never
| finished. One of the stumbling blocks was executing untrusted
| code. I settled on having players either connect via websocket
| or receiving webhooks and having to respond in a given time
| frame.
| debbiedowner wrote:
| I participated in a "ruby fight club" like this a few years ago
| hosted by grouper: https://github.com/Grouper/battleship
| Carbocarde wrote:
| I actually started working on that with some of my friends,
| here's a link: https://github.com/Carbocarde/games
|
| We were planning on eventually making it into a website and
| doing a leaderboard.
|
| The program works by having agents that write to stdout and a
| game that reads from stdin. That way we can kinda avoid some of
| the security issues around running untrusted code.
|
| Still has a lot of work to be done before it's ready to
| simulate battleship :)
| aleksiy123 wrote:
| There is a snake version of this called Battlesnake
| https://play.battlesnake.com/
|
| Did it while I was in university. I even won one of the
| categories one year.
| driscoll42 wrote:
| There's a decent blog article here with some more strategies for
| Battleship:
| https://datagenetics.com/blog/december32011/index.html
| moffkalast wrote:
| > Optimal Sunk-cost Strategy
|
| Heh
| WalterBright wrote:
| Stratego 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 wrote:
| Hiding the flag near the frontlines is my Stratego strategy, no
| one ever suspects it
| funkattack wrote:
| The most important rule is rule number 4. Ships have to be placed
| bevor the first shot.
| dmurray wrote:
| > 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.
| WalterBright wrote:
| I 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.
| Carbocarde wrote:
| Definitely 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]
| cmeacham98 wrote:
| 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.
| greenbay20 wrote:
| Would be interesting to analyze what ship-placement
| strategy/distribution makes the opponent indifferent in terms
| of which cell to shot.
| colordrops wrote:
| 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.
| driscoll42 wrote:
| Agreed, 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 wrote:
| I look forward to the Recaptcha "Play this game of
| Battleship".
| Shared404 wrote:
| A variation on https://xkcd.com/810/ except instead
| creating bots that play like humans!
|
| I like it.
| servytor wrote:
| "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 wrote:
| Author 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 wrote:
| This 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
| _pastel wrote:
| Note 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.
| cochleari_major wrote:
| Reminds me of a fun video about speedrunning a battleship
| minigame in some Zelda title:
|
| https://www.youtube.com/watch?v=1hs451PfFzQ
| Waterluvian wrote:
| I 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.
| schoen wrote:
| Is 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 wrote:
| This 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
| jtokoph wrote:
| I love how the game came without the labels pre-attached.
| Gone are the days of "some assembly required".
| dylan604 wrote:
| Of 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.jp...
| Gare wrote:
| MB version appears to allow it, and I recall playing it like
| you did.
___________________________________________________________________
(page generated 2022-04-02 23:00 UTC)