Generalized shogi and chess are constant-time testable
Hiro Ito, Teagun Park, Atsuki Nagao · 2015
We present constant-time testing algorithms for the generalized shogi (Japanese chess) and chess. These problems are known to be EXPTIME-complete. A testing algorithm (or a tester) for a property accepts an input if it has the property and rejects it if it's far from having the property in high probability (e.g., at least 2/3) by reading only a constant part of the input. A property is said to be testable if there is a tester. The generalized shogi (and chess) problem is, given any position on √n x √n board with O(n) pieces, for testing the property “the player who moves first has a winning strategy.” We present that this property is testable for both shogi and chess. The shogi tester is one-sidederror and the chess tester is surprisingly no-error! In the last decade, many problems have been found to be testable. However, almost all of such problems are in class NP. This is the first result on constant-time testability of EXPTIME-complete problems.