firebotslash posted...
So is it trying to say like, there's so many different possibilities for moves that Mario/Zelda/etc could make that a computer would have extreme difficulty determining which moves are necessary to complete the game?
(as opposed to a game like Chess or something, where computers have essentially mastered the game)
Not quite.
Chess is actually a fairly hard problem, in that let's say you went up to a 9x9 board and added more pieces (two on each side). Now the amount of computation time a computer needs would go waaaaaaaay up, because the number of possible optimal moves just went waaaaaay up.
NP is measuring a more general "how much more computation would we need to do if you made this game slightly longer?"
Which...isn't actually very useful in the case of games. It's useful when we're talking about how much more computation you need to handle a database with 1000 people in it compared to a database with 2000 people in it, though.
--
Cats land on their feet. Toast lands peanut butter side down. A cat with toast strapped to its back will hover above the ground in a state of quantum indecision