Battleship (Not the movie) - An analysis of strategies used to play the game | Hacker News Reader

Battleship (Not the movie) - An analysis of strategies used to play the game

datagenetics.com

9 pointssqueakynick5 comments

Very cool, but still some room for improvement. You can see at the very bottom that the algorithm doesn't know how many battleships there are in the game. Specifically, even though every other ship has been sunk, and it knows the battleship runs up/down, it still has non-zero probability for ships going off to the left. It should be able to rule those gray tiles out completely by that point.

Also this leaves open the question of how best to place ships to avoid being hit? :)

Actually it does take this into account (in a roundabout way). After two hits on the last ship it does know orientation of the ship. It gets this information by applying a massive weighting to the locations where the ship could be that pass through this location.

"and so hit squares are treated as unvisited space squares for deciding if a ship 'could' pass through this square, and then a heavy score weighting is granted to possible locations that pass through a point we know already know contains a hit."

You'll notice that as soon as it wings the ship and knows the orientation that it continues in that direction.

(I concede your point, however, that without this weighting the probability density would be the superposition of all possible locations of the ship independant of other information - that would be a much more complex calculation).

As to how best to place the ships, there is no correct answer, as those who study game theory will tell you. If you had a strategy, then if the opponent knew that there was this strategy, then he could foil you be firing into these locations first, but if you knew that he knew ... etc.

See this http://en.wikipedia.org/wiki/Nash_equilibrium

Well that last slide is just a hint that the algorithm isn't completely right yet. It is clear that every square to the left should be completely white because there is no chance of a ship being there.

A better way to calculate would be: given that a ship is here, what is the probability that other ships are in the other spaces. It's more complex but you can rule out a lot more spaces.

I'm aware of Nash equilibrium, I'm just curious about what it is for this game.

I get what you are saying, but you can only pick one square to fire on next. Knowing the exact probability of every square left (differnetiating between white and almost white), does not help you if, on each move, you take the square with the next highest probability.

If you have a bag containing 85 red balls, 10 yellow balls, 3 blue, and 2 black, and had to draw one and predict its color, are you going to change your answer about red even if you are told that someone stole one of the blue balls before you picked? :)

I think it will make a bigger difference in some circumstances. I guess the only way to resolve this is to run a few million simulations and see if the answers are different :)

Reply on news.ycombinator.com