The Linear Theory of Battleship

http://thevirtuosi.blogspot.com/2011/10/linear-theory-of-battleship.html

by ColinWright • 15 years ago

87 23 15 years ago

thevirtuosi.blogspot.com

zeteo2• 15 years ago

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.

Triumvark2• 15 years ago

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.

timdellinger2• 15 years ago

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.

zeteo2• 15 years ago

http://en.wikipedia.org/wiki/Pure_strategy#Pure_and_mixed_st...

danteembermage2• 15 years ago

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.

Someone2• 15 years ago

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):

    #####.####
    ..........
    ###.###..
    ........

TheCapn2• 15 years ago

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.

ximeng• 15 years ago

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.

MrVitaliy• 15 years ago

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.

timdellinger2• 15 years ago

"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.

waqf• 15 years ago

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.

brudgers• 15 years ago

>"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.

andrewflnr2• 15 years ago

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.

mturmon• 15 years ago

OP specifically says he does not favor large ships.

ajanuary• 15 years ago

"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."

andrewflnr2• 15 years ago

Oops, missed that part. Thanks.

TheCapn2• 15 years ago

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...

joshu• 15 years ago

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?

baltoo• 15 years ago

http://eis.ucsc.edu/StarCraftAICompetition

The Linear Theory of Battleship

Related Stories