Is it NP complete?

asked Dec 29 '10 at 07:51

yura's gravatar image

yura
1010364854

edited Jan 02 '11 at 13:15

Andrew%20Rosenberg's gravatar image

Andrew Rosenberg
170772338


One Answer:

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.

answered Dec 29 '10 at 11:41

Kevin%20Canini's gravatar image

Kevin Canini
126021330

edited Dec 29 '10 at 12:17

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
Your answer
toggle preview

powered by OSQA

User submitted content is under Creative Commons: Attribution - Share Alike; Other things copyright (C) 2010, MetaOptimize LLC.