Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Pac-Man Proved NP-Hard

technologyreview.com

Post reply on HN
Print view View original

11–20 of 21 posts

Re: Pac-Man Proved NP-Hard

#11

Post by joshAg »

lkozma wrote: post #7
joshAg wrote: post #6

I 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…

Perfect thanks! not obscure at all; i did the inverse of the transform i was supposed to do.

Now it's clearer why he used a form of Pacman where pacman could only visit each node once, and why it's not as trivial as i made it seem.

Re: Pac-Man Proved NP-Hard

#12

Post by joshAg »

adgar wrote: post #10
lkozma wrote: post #7

Earlier quoted context omitted.

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.

that would be an awesome entry into a rube goldberg contest...

Re: Pac-Man Proved NP-Hard

#13

Post by Cushman »

icepotato wrote: post #9
Retric wrote: post #4

Earlier quoted context omitted.

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 w…

Why try so hard? Just make a UMS map that implements Tic-Tac-Toe. StarCraft: solved!

Re: Pac-Man Proved NP-Hard

#14

Post by rictic »

icepotato wrote: post #9
Retric wrote: post #4

Earlier quoted context omitted.

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 w…

It is also possible that on any legally-sized starcraft map the number of nodes in the graph would be so small that the solution would be trivial.

But at the same time it's fascinating that they were able to embed this sub-problem within a starcraft scenario, such that any optimal player would have to solve this NP-hard problem. This sort of argument is a classic in the field, and always fun to read.

Re: Pac-Man Proved NP-Hard

#15

Post by NHQ »

Pretty neat. Is this rating based purely on the game's principles, or does the AI algorithms use--for controlling the Ghosts, or creating the stages--have a bearing on the Game's hardness/completeness?

Re: Pac-Man Proved NP-Hard

#16

Post by sukuriant »

Retric wrote: post #4
Sniffnoy wrote: post #2

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

No it doesn't. NP-Hard just states that it's NP-Complete + Polynomial Turing Time reducible to H.

NP-Complete just means that a correct solution can be evaluated in polynomial time by a deterministic Turing machine. It says nothing of the number of solutions that exist.

Re: Pac-Man Proved NP-Hard

#17

Post by adgar »

joshAg wrote: post #12
adgar wrote: post #10

Earlier quoted context omitted.

To explain it even easier: every integer addition problem can be transformed into a TSP problem, but not vice-versa.

that would be an awesome entry into a rube goldberg contest...

Basic start to a rigorous solution:

Input: A, B : integers

Output: directed graph G(V, E, w) (V = vertices, E = edges, w = weight fn)

V = {c1, c2, c3}

E = {(c1, c2), (c2, c3), (c3, c1)}

w(c1, c2) = A

w(c2, c3) = B

w(c3, c1) = 0

shortest tour is the only valid tour whose length is clearly A + B.

Re: Pac-Man Proved NP-Hard

#18

Post by blauwbilgorgel »

To rank the complexity of a game, as it relates to the user, couldn't you:

Record 1 hour of input in a string. Run a block level compression algo on it, and order the compressed strings on size?

Wouldn't that give a measure of the amount of input required by the game, coupled with how much of that input repeats/has simple patterns?

Re: Pac-Man Proved NP-Hard

#19

Post by argv_empty »

sukuriant wrote: post #16
Retric wrote: post #4

Earlier quoted context omitted.

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.

No it doesn't. NP-Hard just states that it's NP-Complete + Polynomial Turing Time reducible to H. NP-Complete just means that a correct solution can be evaluated in polynomial time by a deterministic Turing machine. It says nothing of the number of solutions that exist.

You've got this a little backwards. Being in NP means a correct solution can be checked by a deterministic TM in polynomial time. A problem is NP-hard if any problem in NP is polynomial time Turing reducible to it. NP-complete problems are those that are NP-hard and in NP (an NP-hard problem need not be NP-complete).

Re: Pac-Man Proved NP-Hard

#20

Post by kd0amg »

Retric wrote: post #4
Sniffnoy wrote: post #2

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

Packman's scoring is based on collecting items and is not time dependent.

The author does not bring completion time into this at all. He reduces (a still NP-complete subset of) Hamiltonicity to the question of whether a Pac-Man level can be completed without dying.

Post reply on HN