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.
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!
> 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!
not exactly the same because it's not playing an established human vs. human game such as Battleship, but Core War [0] from 1984 is the earliest example of this idea that I'm aware of.
> At the beginning of a game, each battle program is loaded into memory at a random location, after which each program executes one instruction in turn. The goal of the game is to cause the processes of opposing programs to terminate (which happens if they execute an invalid instruction), leaving the victorious program in sole possession of the machine.
Battlecode [1] from MIT seems to be along similar lines as well
Corewar may be the first example of the game in its purest form, but earlier than that was Robotwar (first on the PLATO system in the 1970s then on the Apple ][ in 1981) which involved players writing simple programs to control robots in a BASIC like language. You could either compete against a friend or compete against a series of programs included with the game.
We (http://pr0gramm.com) had a multiplayer battleship[1] for our april's fools two days ago. All users were divided into a red and blue team and then voted for the next shot. For our april's fools in 2018 we did the same with connect 4[2].
The games itself are not that interesting (altough OP certainly disagrees), but the social dynamics, shitposts and memes that came out of this were fascinating.
StarCraft 2 has a pretty active version of this! I've always wanted to play around with it but I lost a lot of steam when I wanted to upstream some changes to the various libraries involved and my employer vetoed the idea.
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 :)
One of the first incantations of this idea that I encountered, when I had just started working at my first corporate job back in the day, was Robocode ( https://robocode.sourceforge.io/ ) - it was great fun, and I see it's still going.
Although there is no specific implementation for Battleship, but I believe that some users sometimes have the possibility to create and submit their own games.
I wanna say the Metropolis-Hastings algorithm is probably the best way to explore any probability distribution like this. The core algorithm is pretty similar to battleships -- pick a random point from a map, then explore neighbouring points, use the difference between predicted and measured results to update the map, and when bored do random restarts.
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.
I don’t understand the executing of entrusted code part. If the instructions are plain text, how could it even be a problem? The instruction FIRE(5,7) isn’t going to turn into a zero day exploit, right?
I think you are teetering on the edge of the rabbit hole of a domain specific language for the representation of board game rules. Unless you want to write a new emulator for each new multiplayer game, that's the hole you'll dive down. But once down there, you'll realize you're basically making a programming language with a board game theme, as any language sophisticated enough to represent most board games is destined to become a Turing tarpit. At that point the project has become self defeating, as you are now coding each new game in a programming language you invented to avoid coding each new game.
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.
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).
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.
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:
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.
European versions have this rule [1]. I wasn't aware that the US version allowed adjacent ship placement until I bought a commercial version for my kid last Christmas and started looking into strategies.
It's not weird. I played article version my whole life and never knew different ones existed. It could help you if you're lucky enough to hit it. But it also can help you if this is your last ship on the board, which happens quite often actually.
I don't know why it would be a rule but the one time I tried it, I got absolutely rekt and never did it again.
May have been because I put ALL my ships in one big blob, but typically people will fire at adjacent hits until they don't get any, so I think it's a terrible strategy anyway.
Not 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.
> 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.
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.
>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.
Readit News
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.
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!
> At the beginning of a game, each battle program is loaded into memory at a random location, after which each program executes one instruction in turn. The goal of the game is to cause the processes of opposing programs to terminate (which happens if they execute an invalid instruction), leaving the victorious program in sole possession of the machine.
Battlecode [1] from MIT seems to be along similar lines as well
0: https://en.wikipedia.org/wiki/Core_War
1: https://battlecode.org/
https://en.wikipedia.org/wiki/RobotWar
The games itself are not that interesting (altough OP certainly disagrees), but the social dynamics, shitposts and memes that came out of this were fascinating.
[1] https://vid.pr0gramm.com/2022/04/02/e9c168457179b582.mp4
[2] https://vid.pr0gramm.com/2018/04/01/fa0b52dacd80da53.mp4
https://sc2ai.net/
Did it while I was in university. I even won one of the categories one year.
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 :)
If there's another outcome I'm missing, I'd like to hear about it (stalemate?)
Who has a SaaS prototype for creating board game servers
Although there is no specific implementation for Battleship, but I believe that some users sometimes have the possibility to create and submit their own games.
Dead Comment
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.
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.
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
1: https://de.wikipedia.org/wiki/Schiffe_versenken#Vorbereitung
Also, the board game had a different ship length distribution; the board game is biased towards fewer, longer ships:
1x Len 5
1x Len 4
2x Len 3
1x Len 2
The length one ships in the article are weird, especially with the no adjacency rule they quickly rule out large sections of the board.
May have been because I put ALL my ships in one big blob, but typically people will fire at adjacent hits until they don't get any, so I think it's a terrible strategy anyway.
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.
https://www.youtube.com/watch?v=1hs451PfFzQ
Thanks!
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.
I'd also place my ships in the same places as the previous round.
Deleted Comment
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.