Battleship
nulliq.dev
nulliq.dev
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
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
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.
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.
I like it.
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:
[0]https://3dprint.com/wp-content/uploads/2016/01/Battleship.jp...
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.
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.
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.
Yet the next pick is a square next to the hit. Huh?
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!
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.
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.
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.
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.
Heh
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.
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.