How are games like chess provably harder than NP?
The fault lies in this statement:


  So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win.


The second sentence might be right, but it might not.  Perhaps there is a cleverer, faster way that the verifier can check a certificate, or a cleverer format for the certificate that makes it easy to check.  How do we know that's impossible?  We don't.  That would need proof.

The argument has made an assumption about how a verifier "would have to" behave, without substantiating or proving that assumption.  This is basically an argument from failure of creativity: "I can't think of any other strategy a verifier could plausibly use, so there must not exist any valid strategy".  Needless to say, this is not a persuasive form of argument.



For instance, let me give you an example.  Suppose we replace "generalized chess" by "generalized tic-tac-toe", which works as follows: we have a nxn game board, and the first person to get three in a row wins.  Try working through the same argument.  It's tempting to draw the same conclusion, that generalized tic-tac-toe is NP-hard.  But there are reasons to doubt that conclusion: for instance, this form of generalized tic-tac-toe is always a first-player win when you start from the empty board, for all $n&gt;3$.

There are better examples.  In particular, there are games where there are in fact polynomial-time algorithms to play optimally, but the algorithm/strategy is not at all obvious, and if you weren't already aware of it, you might be inclined to be persuaded by the above reasoning that the game is NP-hard.  Examples include Nim, Brussels Sprouts, and Wythoff's game.  This illustrates that the line of reasoning can't possibly be right -- it leads you to draw conclusions that are false.