|
Is it NP complete? |
|
I thought this was a joke until I Googled it and discovered you're probably talking about the game Battleship (e.g., see http://www.xs4all.nl/~barend/). Anyway, the game is a simple type of partially-observable Markov decision process (POMDP) with a finite number of moves and deterministic transition function (but only partially observed state), so yes, there is a theoretically optimal strategy. But computing it is even harder than NP-complete for general POMDPs, if I recall correctly. This one intuitively seems like it shouldn't be terribly hard. Thanks, yes you are right it is Battleship, its my translation issue.
(Dec 29 '10 at 12:00)
yura
Even though this is off-topic, I find the connection between battleship and POMDPs interesting. I think battleship as a process is pretty boring, since knowing where one ship is tells you nothing apart from "no other ship is here", and the misses essentially just give you information that rules out the larger ships, and there is no way of knowing where the little one- or two-block ships are apart from trying the whole board out. On the other hand, trying the whole board requires a linear number of moves.
(Dec 29 '10 at 19:15)
Alexandre Passos ♦
Try the latest abstruse goose and you will find that tinsel is np- hard. Just a Christmas Joke :) http://abstrusegoose.com/330
(Dec 30 '10 at 01:59)
Leon Palafox
In general POMDPs are EXP-TIME, so you recall correctly (assuming I do! :) I think a few people have looked at deterministic transition functions but I can't recall any off the top of my head.
(Dec 30 '10 at 06:37)
Noel Welsh
|
