3 ms·
Small but relevant nitpick: Generalized chess is EXPEPACE-complete. Standard chess has an 8x8 grid with a finite number of states. In theory, chess is solvable
by mikejb 8y ago
Small but relevant nitpick:
Generalized chess is EXPEPACE-complete. Standard chess has an 8x8 grid with a finite number of states. In theory, chess is solvable in constant time (because you can provide a finite lookup table).
- FartyMcFarter 8y agoIf I understand correctly it's only exptime-complete if you allow an exponential number of moves? If you only allow a polynomial number of moves then it's PSPACE-complete. But yes good point about specific board sizes :)