Pac-Man Proved NP-Hard
technologyreview.com
Pac-Man Proved NP-Hard
1–10 of 21 posts
Re: Pac-Man Proved NP-Hard
#2This could use a better title; the noteworthy thing here is not that Pac-Man is NP-Hard, but that this guy has covered the computational complexity of a whole bunch of games at once.
Re: Pac-Man Proved NP-Hard
#3[deleted]
Re: Pac-Man Proved NP-Hard
#4This could use a better title; the noteworthy thing here is not that Pac-Man is NP-Hard, but that this guy has covered the computational complexity of a whole bunch of games at once.
He also changed basic game mechanics to make it NP-Hard. Packman's scoring is based on collecting items and is not time dependent. So there are effectively unlimited games that all share a perfect score unlike the traveling salesman which has a single optimal solution. To make it NP-Hard requires one way paths though the maze.
Re: Pac-Man Proved NP-Hard
#5"We assume full configurability of the amount of ghosts and ghost houses, speeds, and the durations of Chase, Scatter, and Frightened modes"... "The game alternates between Chase and Scatter mode fast enough, so that each ghost reverses direction after covering only one tile. "
I'm sorry, but this is a sick and twisted version of Pac Man.
Re: Pac-Man Proved NP-Hard
#6I have to be missing something here. Isn't it obvious that any discrete, single use, path location traversal can be transformed into the tsp by making every point on the path a node connected to it's nearest neighbors? Is the newsworthy point that some games do not require every point to be visited?
Re: Pac-Man Proved NP-Hard
#7I have to be missing something here. Isn't it obvious that any discrete, single use, path location traversal can be transformed into the tsp by making every point on the path a node connected to it's nearest neighbors? Is the newsworthy point that some games do not require every point to be visited?
Say you want to prove your problem A is NP-hard and you know already that problem B is NP-hard. The fact that you can transform every instance of A to an instance of B does not prove anything, because it could be that you only create instances in a subset of B that are easy.
To prove that A is NP-hard, you have to do the opposite. Show how you transform every instance of B into an instance of A, so that a solution of A implies a solution of B. Then if you had a solver for A, you could use it to solve B, which is impossible unless P=NP (since B is known to be NP-hard). In this case, you have to transform TSP to Pac-Man, not the other way around. Some technicalities aside (which are important, nevertheless), this is how hardness proofs go, sorry if it was a bit obscure.
Re: Pac-Man Proved NP-Hard
#8On a tangential note, HNers might be interested in the annual Ms Pacman vs Ghosts competition: http://www.pacman-vs-ghosts.net/
Entrants are required to write a controller for Ms Pacman or the ghosts using at least one computational intelligence technique. Entries are played against each other in a tournament.
It's a great way to get some experience with stuff like neural nets, evolutionary algorithms and so forth.
Re: Pac-Man Proved NP-Hard
#9This could use a better title; the noteworthy thing here is not that Pac-Man is NP-Hard, but that this guy has covered the computational complexity of a whole bunch of games at once.
He also changed basic game mechanics to make it NP-Hard. Packman's scoring is based on collecting items and is not time dependent. So there are effectively unlimited games that all share a perfect score unlike the traveling salesman which has a single optimal solution. To make it NP-Hard requires one way paths though the maze.
same with starcraft:
"Suppose the two players have
bases on diff erent islands, player B has a strong ground army but no income and no way to reach player A, while player A has no units and needs exactly x resources to train an army and barely defeat B. Player A starts with just enough resources to train a worker. In yet another un-
reachable island, there are n locations, each of which has a main building of A (to which workers must bring the resources they collect) and x=n resources. There is also a worker in each location, but it is "trapped" behind some resource batches, and cannot reach the main building. On each path connecting two locations, there is a turret (or other static defence) of B, positioned in such a way that a lone worker traversing the path isbound to be killed, but if two workers traverse it, exactly one survives.
B hopes for a draw, while A has only one strategy: Train a worker at some location, collect the resources, thus setting the second worker free, traverse a path with both workers to reach another location, and repeat.
A cannot waste resources into training more than one worker, and can win if and only if the (planar) graph of locations has a Hamiltonian path."
which raises the question - what is a game? is it the collection of all possible permutations of states allowed by the rules, as in the Pac-Man generalization or this extremely weird corner case SC scenario that requires extended amounts of sub-optimal play? If I -can- construct such a bizarre and entrenched StarCraft position, is it part of "the game", or is it a weird theoretical custom map whose sole purpose is proving starcraft is np-hard to "solve"
Re: Pac-Man Proved NP-Hard
#10I have to be missing something here. Isn't it obvious that any discrete, single use, path location traversal can be transformed into the tsp by making every point on the path a node connected to it's nearest neighbors? Is the newsworthy point that some games do not require every point to be visited?
Say you want to prove your problem A is NP-hard and you know already that problem B is NP-hard. The fact that you can transform every instance of A to an instance of B does not prove anything, because it could be that you only create instances in a subset of B that are easy. To prove that A is NP-hard, you have to do the opposite. Show how you transform every instance of B into an instance of A, so that a solution of…
To explain it even easier: every integer addition problem can be transformed into a TSP problem, but not vice-versa.