mizer, chess on an 8x8 board is not an NP-complete problem, it is O(1). For a very very large value of O(1), of course. :-)

Even if you turned chess into a parametric problem, let's say as CHESS(n) with an n times n board and specific rules to fill the base lines with new pieces, you'd still have to prove that it is a) in NP and b) NP-hard before you can safely claim that it is NP-complete. The actual decision problem would be something like figuring out whether White has a forced win.

At first I thought that to prove a) it would be sufficient to show that the maximum number of moves in a game is polynomially bounded, which I thought was easy thanks to the 50 move rule: 50 * (max. number of captures + max. number of pawn moves) yields a polynomial. But there are two problems: For one, no player is actually required to invoke the 50 move rule. He could invoke it when he sees he's going to be checkmated, but if a pawn moves or pieces are captured in the meantime, the counter is reset to zero. And most importantly, to solve CHESS(n) it is not enough to find a position where Black is checkmate. You have to show that the sequence of moves leading up to it is forced, i.e. in case of any other move, White has an equally short or shorter mate! But the non-deterministic Turing machine, which has simply been described as the "luckiest possible guesser" cannot just guess whether a move is forced, because it needs to know ALL subsequent lines to do that, not just any winning line. This leads me to believe that CHESS(n) would more probably be in EXPTIME.

a6?, a5?

But let's not get too excited about the perfect anti-computer strategy. This is not John Connor in the future about to smash skynet.

This is a game played back in 2003, when the early hunter-killers had rubber skin. We spotted them easy.

GMs would not get such an easy ride against modern chess engines. The programmers watched games like this and adjusted, tinkered, fiddled. They changed the engine's opening books, upgraded their understanding of closed positions, introduced the ability to make speculative sacrifices to open a position up to tactics. He doesn't feel pity or remorse. And he absolutely will not stop, ever, until you are dead.

If Fritz X3D could have spoken in 2003, he might have said, in an Austrian Governor monotone "I'll be back".

Bravo, Kasparov!! Kasparov must have smiled at this computer because it resigns. Naturally, it is not premature. Kasparov creates powerful pressure on the Queen side.

<Lefthandsketch> Yeah, it is very interesting. I want to mention to you: Crafty (Computer) vs Hikaru Nakamura - ICC Blitz 2007 with five underpromotions and mate with six knights.

It is awesome, <Lefthandsketch>, right?

More likely Fritz's operators decided that they had seen enough and resigned on behalf of the computer.

White King represents the British investigator Ichabod Crane. Six Black Knights represent the six headless horsemen in the scary town of Sleepy Hollow, England. LOL

That's what I wrote in the game between Crafty (White) and Hikaru Nakamura (Black) - a hilarious commentary.