The Linear Theory of Battleship(thevirtuosi.blogspot.com)
thevirtuosi.blogspot.com
The Linear Theory of Battleship
http://thevirtuosi.blogspot.com/2011/10/linear-theory-of-battleship.html
26 comments
From the point of view of game theory, this is not an optimal strategy since it merely invites the opponent to place more ships on corners and edges. It might work well against a computer opponent, but a human will adapt quickly. The concepts that need to be taken into consideration are randomized strategies and Nash equilibria.
This is a search game. If your opponent constrains himself to a small subset of legal positions to avoid detection, your strategy is working, not failing.
Think about it this way: Suppose we are playing battleship on a board with one patrol boat and five squares in a line. There are only five possible places to put a patrol boat on this board. The three middle squares are equally likely to be chosen by a random arrangement, so we might as well choose the middle square for an opening move.
This is where this falls down. Since I know it's optimal for you to choose one of those three middle squares, I do not want any boat configuration that covers two of them, so I will always pick either the far left patrol boat or the far right patrol boat.
Except if I always pick the far left or right, why would you ever pick middle to start? You wouldn't. Finding an equilibrium to these games is hard, but I'd guess a 50/50 mixed strategy of placing a boat either on the extreme right or extreme left and a 50/50 guessing strategy of B1 or D1 would be a Nash Equilibrium of this game. And the boat arrangement would look nothing like what you'd expect from a random arrangement, in fact there'd be a giant black probability square right in the middle of the board.
This is where this falls down. Since I know it's optimal for you to choose one of those three middle squares, I do not want any boat configuration that covers two of them, so I will always pick either the far left patrol boat or the far right patrol boat.
Except if I always pick the far left or right, why would you ever pick middle to start? You wouldn't. Finding an equilibrium to these games is hard, but I'd guess a 50/50 mixed strategy of placing a boat either on the extreme right or extreme left and a 50/50 guessing strategy of B1 or D1 would be a Nash Equilibrium of this game. And the boat arrangement would look nothing like what you'd expect from a random arrangement, in fact there'd be a giant black probability square right in the middle of the board.
I like your simplified model, and I know random strategies are sometimes helpful. My point was that random strategies are not always helpful.
I worry people don't believe this, so let me use a silly outlandish example to prove my point.
Here's a game: Suppose we have a countably infinite number of boxes, all numbered. You pick one to hide under, and I have to find you by looking under boxes which I choose, one at a time. I get to look at as many boxes as I like until I find you or get tired and go home.
Under box 1 is famed astronomer Neil deGrasse Tyson, who was spying on you with his (perhaps magical) telescope all morning. He will gladly tell me where you hid.
I now announce my strategy for this game, namely, to pick Box 1 and ask Tyson how to win.
Will you now respond with the original, "From the point of view of game theory, this is not an optimal strategy since it merely invites the opponent to avoid box 1. ..."?
The point of this silly example game is that randomized strategies aren't necessarily helpful for certain classes of games where one strategy gives you disproportionate information about the state of the game.
Guess my number games and battleship games risk being very similar to my extreme illustrative example, but I'll admit I don't know how much.
Bottom line: I just resent the insistence that good game theorists dogmatically REQUIRE randomness in all competitive situations. This is not necessarily the case.
I worry people don't believe this, so let me use a silly outlandish example to prove my point.
Here's a game: Suppose we have a countably infinite number of boxes, all numbered. You pick one to hide under, and I have to find you by looking under boxes which I choose, one at a time. I get to look at as many boxes as I like until I find you or get tired and go home.
Under box 1 is famed astronomer Neil deGrasse Tyson, who was spying on you with his (perhaps magical) telescope all morning. He will gladly tell me where you hid.
I now announce my strategy for this game, namely, to pick Box 1 and ask Tyson how to win.
Will you now respond with the original, "From the point of view of game theory, this is not an optimal strategy since it merely invites the opponent to avoid box 1. ..."?
The point of this silly example game is that randomized strategies aren't necessarily helpful for certain classes of games where one strategy gives you disproportionate information about the state of the game.
Guess my number games and battleship games risk being very similar to my extreme illustrative example, but I'll admit I don't know how much.
Bottom line: I just resent the insistence that good game theorists dogmatically REQUIRE randomness in all competitive situations. This is not necessarily the case.
In my experience mixed strategies are very important to pushing the boundaries of game theory but are rarely important in applying it (I come from business/economics so that biases the kinds of models that are useful). For example, when we think about how to optimally design an executive compensation contract the resulting equilibrium usually has no randomness at all or at least the actors are not playing a mixed strategy. The executive knows what "effort" level she will exert and the compensation committee knows what it will pay her (not in absolute dollar terms but in terms of an explicit contract). The only mixing example I can think of is that Soccer goalies appear to be mixing with which direction they dive and kickers kick http://www2.owen.vanderbilt.edu/mike.shor/courses/game-theor... although I think duopoly product competition is often viewed that way (not competing on price or production size but whether to launch a new product)
Obviously, if there is a single move that wins you the game every time - being able to consult the oracle, in your example - then this pure strategy is dominant, and no mixed strategy is called for.
http://en.wikipedia.org/wiki/Pure_strategy#Pure_and_mixed_st... http://en.wikipedia.org/wiki/Strategic_dominance
It is obvious that if there is a dominant pure strategy, then that is the strategy to play, and there is no need for a mixed strategy.
Anyone with elementary game theory knows this, and, really, no 'good game theorist' is going to 'dogmatically' assert otherwise.
http://en.wikipedia.org/wiki/Pure_strategy#Pure_and_mixed_st... http://en.wikipedia.org/wiki/Strategic_dominance
It is obvious that if there is a dominant pure strategy, then that is the strategy to play, and there is no need for a mixed strategy.
Anyone with elementary game theory knows this, and, really, no 'good game theorist' is going to 'dogmatically' assert otherwise.
[deleted]
No, it is not. I have not tried proving it, but I would think the winning strategy is not "to avoid detection", but to "make it as hard as possible to detect your smallest ships".
I tend to place the large ships as close together as rules allow, in order to leave as much freedom to place the smaller ships. Something like (if ships can lie along a border; periods are squares where no ship can lie):
I tend to place the large ships as close together as rules allow, in order to leave as much freedom to place the smaller ships. Something like (if ships can lie along a border; periods are squares where no ship can lie):
#####.####
..........
###.###..
........Clarification: apparently, I tend to play a different game than what this text is about. The game I know forbids placing ships so that they touch (sometimes allowing corner touches). With those rules, finding a large ship can rule out lots of spaces from the search space. For example, a 5x1 ship has up to 16 bordering squares.
The way that I read the term "randomized strategies" in the original comment is that you opponent sometimes uses the clustering approach, and sometimes doesn't. Your search algorithm doesn't know whether the opponent has chosen to cluster or not. Or to partially cluster. And this decision will likely change each time the game is played.
There's only so much you can do to combat human trickery and for the most part you only have the option to be "reactive" instead of "proactive" on moves because if a human can read the algorithm (Open Source) they can device ways around it.
My personal experience working with Battleship AI is to play the highest probability. As a human your best option is to place ships closer to the middle and not on edges because of how a person reacts when hitting a ship.
Once a person "hits" the ship they know only that they've made a hit, not what they hit or whether they landed on the middle/side etc. By placing ships along the borders you're essentially reducing the problem space for them to guess. When you ship is in the middle-ish areas the player has a 25-50% chance of hitting the next square of the ship depending on what location they hit at. When your ship is in the corner or side there is only 2 or 3 options before they begin their guessing... (I hope that makes sense)
The AI that the author has presented is ideal for reducing the problem space that exists on the board by segmenting the possible locations that the ship will fit in. Once the problem space is small enough it makes it easy to pick out where ships are hiding.
My personal experience working with Battleship AI is to play the highest probability. As a human your best option is to place ships closer to the middle and not on edges because of how a person reacts when hitting a ship.
Once a person "hits" the ship they know only that they've made a hit, not what they hit or whether they landed on the middle/side etc. By placing ships along the borders you're essentially reducing the problem space for them to guess. When you ship is in the middle-ish areas the player has a 25-50% chance of hitting the next square of the ship depending on what location they hit at. When your ship is in the corner or side there is only 2 or 3 options before they begin their guessing... (I hope that makes sense)
The AI that the author has presented is ideal for reducing the problem space that exists on the board by segmenting the possible locations that the ship will fit in. Once the problem space is small enough it makes it easy to pick out where ships are hiding.
He's only solving the simpler version of the game, as popularized by Milton Bradley. In the prewar original, you get three simultaneous shots per turn and you get told how many of your shots hit but not which ones.
I'd be more interested to see optimal play solved for that version.
I'd be more interested to see optimal play solved for that version.
"In fact, I wrote a little code to generate random Battleship boards, and counted where each of the ships appeared."
A knowledgeable opponent will have a tendency to place ships such that they're not touching each other, else the second ship might be hit while trying to sink the first ship.
A full analysis of the problem would also generate optimized search patterns, and explore possible countermeasures.
It's also not clear whether to dedicate your turns to sinking ships that have been hit, or searching for new ships. If and when turns can accomplish both, an advantage is gained.
Another interesting aspect would be to look a dataset of ship placement and search strategies from human games.
A knowledgeable opponent will have a tendency to place ships such that they're not touching each other, else the second ship might be hit while trying to sink the first ship.
A full analysis of the problem would also generate optimized search patterns, and explore possible countermeasures.
It's also not clear whether to dedicate your turns to sinking ships that have been hit, or searching for new ships. If and when turns can accomplish both, an advantage is gained.
Another interesting aspect would be to look a dataset of ship placement and search strategies from human games.
>"Here, I've specified a bunch of misses, and am asking for the probability of there being a Carrier on all of the positions of the board"
What first caught my attention was that there were four squares between the missed shots, which cannot contain a carrier and thus should be black.
However, upon further examination, it occurred to me that the squares under the misses should also be black.
I will add that anyone who has actually played battleship even casually knows that placing one or more ships in the corners is a good defensive strategy because shots placed in the corner return the least amount of information to your opponent regardless of whether they hit or miss.
Finally, I was somewhat surprised by the lack of a search strategy which recognized the makeup of the opponents fleet. By eliminating spaces in groups of three, one gains information about the location of 80% of the opponents fleet (i.e. sub, cruiser, battleship, and carrier) while still having a reasonable chance of finding the PT boat - and certainly a better chance than the haphazard pattern shown in the diagram.
What first caught my attention was that there were four squares between the missed shots, which cannot contain a carrier and thus should be black.
However, upon further examination, it occurred to me that the squares under the misses should also be black.
I will add that anyone who has actually played battleship even casually knows that placing one or more ships in the corners is a good defensive strategy because shots placed in the corner return the least amount of information to your opponent regardless of whether they hit or miss.
Finally, I was somewhat surprised by the lack of a search strategy which recognized the makeup of the opponents fleet. By eliminating spaces in groups of three, one gains information about the location of 80% of the opponents fleet (i.e. sub, cruiser, battleship, and carrier) while still having a reasonable chance of finding the PT boat - and certainly a better chance than the haphazard pattern shown in the diagram.
About a year ago now I finished writing some cheap code that implemented basically what he details in the blog. (My blog links the code on github: http://pro-graham.com/) I wrote it for a small AI class project building on something a friend and I did two years previously. You can play the Java Applet here: http://pro-graham.com/Battleship/Battleship.html
Essentially it weighs the board and creates what I called a Probability Map to determine where ships lie. My tests gave the computer ~48% win rate against myself and ~60% against random friends. Its accuracy is double that of a random shooting AI.
I can go into more details about the advantages and disadvantages of the algorithm here if there's any interest. I'd have posted it a couple months ago when I published it had I known there was interest in such a project...
Essentially it weighs the board and creates what I called a Probability Map to determine where ships lie. My tests gave the computer ~48% win rate against myself and ~60% against random friends. Its accuracy is double that of a random shooting AI.
I can go into more details about the advantages and disadvantages of the algorithm here if there's any interest. I'd have posted it a couple months ago when I published it had I known there was interest in such a project...
This sounds like a perfect problem for Bayesian nets.
IIRC, Bayes prof was very similar to the concept of the game, by throwing pebbles on a table and trying to predict where they land.
IIRC, Bayes prof was very similar to the concept of the game, by throwing pebbles on a table and trying to predict where they land.
Similar research paper, veering off into FFTs and genetic algorithms:
http://www.cores2.com/files/FinalResearchPaper.pdf
Another page:
http://blog.codeus.net/a-lost-battleship-ai-and-probability-...
Both have source code.
http://www.cores2.com/files/FinalResearchPaper.pdf
Another page:
http://blog.codeus.net/a-lost-battleship-ai-and-probability-...
Both have source code.
When he lays out his random boards, it seems like he's always doing it from biggest ship to smallest, which has an effect on the probation distributions. To get better probabilities I think he should place them in a random order.
"Now, this is not because I lay down the Carrier first, my board generation algorithm assigns all of the boards at once, and just weeds out invalid ones, this is a real entropic effect."
Oops, missed that part. Thanks.
OP specifically says he does not favor large ships.
Whoo! Anyone interested in an algorithmic game competition?
I've always wanted starcraft to be scriptable so it would be code vs code instead of twitch vs twitch. But that is a big first step. So maybe some battleship?
I've always wanted starcraft to be scriptable so it would be code vs code instead of twitch vs twitch. But that is a big first step. So maybe some battleship?
[deleted]