LordoftheMorons posted...
Well generally for a game like Go or Chess you're not going to compute every possible remaining game state (that would take way too long), but you can use a number of different strategies to make good moves. Like, you could look a few moves into the future and choose the move that results in the best game state for you assuming your opponent plays optimally (minimax), or do a genetic algorithm where you "train" a computer with various sample games (this is what they did with IBM's Watson to train a computer to play Jeopardy).
Right, but this is different from a question of NP-completeness. When you take these shortcuts, you're not "solving" these games. You're getting a good approximation.
Physics simulations are NP complete if you do things properly, and yet a whole lot of videogames have physics simulations running at 60 FPS, because they're willing to make some approximations.
--
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