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.
I work in America, so my employer owns my entire being. Specifically, in order to commit to open source, do any independent project, etc, I need to get permission from my employer that it doesn't compete with them and that they are willing to relinquish the copyright/IP rights.
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?
In a game of battleship it’s a human player who would write down the text, correct? But that doesn’t matter at all. It seems to me it could be a very simple text protocol with literally zero chance of binary execution exploits
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.
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?
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.
"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?
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.
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.
At 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.
The 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.
If 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.
There'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.
The 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?
There are a few gyms for 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.
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.
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.
Interesting. 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.
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.