Comment Just to throw this out there (Score 5, Informative) 322
Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.
NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games. Additionally, you always have to generalize these games in order to make that claim. Since computational complexity is defined in terms of the length of the input, and certainly all of these games are being played on an input of fixed length.
However, there are effective approaches to solving NP-Hard problems. There are solvers for known NP-Hard problems. If you Google "sat solver" you'll find at least 5 that you can just download. SAT solvers are used in VLSI validation and other practical things. These solvers use heuristics to improve search performance, generally proposing answers and checking them (for NP-Complete problems).
Also, there are tons of games known to be NP or PSPACE complete. The reductions for those games are kind of a standard problem, since the AI community writes a bunch of these solvers.