Slashdot Mirror
Pac-Man Is NP-Hard
MrSeb writes "An Italian researcher with a penchant for retro games — or perhaps just looking for an excuse to play games in the name of science! — has used computational complexity theory to decide, once and for all, just how hard video games are. In a truly epic undertaking, Giovanni Viglietta of the University of Pisa has worked out the theoretical difficulty of 13 old games, including Pac-Man, Doom, Lemmings, Prince of Persia, and Boulder Dash. Pac-Man, with its traversal of space, is NP-hard. Doom, on the other hand, is PSPACE-hard."
Yup, posted on /. a while back
http://games.slashdot.org/story/10/12/03/2237200/pac-mans-ghost-behavior-algorithms
--->
http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior
--->
http://home.comcast.net/~jpittman2/pacman/pacmandossier.html
I don't know what it is but reading about the internals of how games worked (algorithms, data structures, tricks, etc.) is neat.
http://web.mit.edu/newsoffice/2009/explainer-pnp.html
It means it isn't computationally solvable in linear time.
No, it can't be solved in POLYNOMIAL time. For instance, comparative sorting cannot be done in linear, yet is not NP-hard.
Something that is O(n^12387349892319348917359872394872328349872398723985729375982734598275) is in fact insanely hard, yet still not NP-hard.
WARNING! This girl exceeds the MAXIMUM SAFE standards established by the FDA for BRATTINESS
It is believed that P != NP, and if any problem that is NP-Hard (usually one just says NP-Complete) turns out to be solvable in polynomial time, then P = NP.
Roughly speaking, NP-hard (NP = non-polynomial) means that it scales non-polynomially fast ... e.g. if an algorithm is O(n^n) then it is NP-hard but if it is O(n^3) than it is only P-hard. By this definition, even O(n^lg(n)) is NP-hard and O(N^100) is "only" P-hard.
No, no, no, no. NP does not mean "non-polynomial". In fact, all "P" problems are also "NP". NP means "nondeterministic polynomial", i.e, polynomial in a non-deterministic machine (think a computer with an infinite number of CPUs). It is unlikely that they are "P" ("deterministic polynomial"), but it has not been proven either way. Also, a problem being NP-hard doesn't imply that it is NP. It actually may be harder than NP: in general, to say that a problem is X-hard means that there is no problem of class X that is "harder" than it.
For the precise definition of "harder", the wikipedia article http://en.wikipedia.org/wiki/P_versus_NP_problem is pretty good.
(Hmm. it seems I can't log in from the comment box...)
Mod parent down, please. The definition of NP above is circular -- if NP actually stood for non-polynomial, then P!=NP by definition. That would be begging the question.
Rather, NP means "nondeterministic polynomial time." It is the class of problems whose solutions can be verified in polynomial time. NP-hard are the "hardest" problems in this class. All algorithms known to solve problems in this class are super-polynomial. The question of "P==NP?" really amounts to "is there an undiscovered polynomial solution to every problem that we currently think is NP-hard?" or even more simply, "if a problem's solution can be verified in polynomial time, can the solution be discovered in polynomial time?"
tetris DS does get to the point where the piece lands nearly as soon as it appears
This behavior is called 20G, and it's also seen in "Death" mode of Tetris the Grand Master 2 and "Shirase" mode of Tetris the Grand Master 3.
however you can keep it from fixing to the stack by rotating it and wiggling it constantly.
This infinite spin behavior has become the standard since 2001, despite reviewers' assertions that "it actually breaks Tetris".