
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Generalized Shogi, Chess, and Xiangqi are ConstantTime Testable
Hiro ITO Atsuki NAGAO Teagun PARK
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E102A
No.9
pp.11261133 Publication Date: 2019/09/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E102.A.1126
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Puzzles Keyword: property testing, generalized shogi, generalized chess, generalized xiangqi, EXPTIMEcomplete, onesidederror,
Full Text: PDF(1.1MB)>>
Summary:
We present constanttime testing algorithms for generalized shogi (Japanese chess), chess, and xiangqi (Chinese chess). These problems are known or believed to be EXPTIMEcomplete. A testing algorithm (or a tester) for a property accepts an input if it has the property, and rejects it with high probability if it is far from having the property (e.g., at least 2/3) by reading only a constant part of the input. A property is said to be testable if a tester exists. Given any position on a ⌊√n⌋×⌊√n⌋ board with O(n) pieces, the generalized shogi, chess, and xiangqi problem are problems determining the property that “the player who moves first has a winning strategy.” We propose that this property is testable for shogi, chess, and xiangqi. The shogi tester and xiangqi tester have a onesidederror, but surprisingly, the chess tester has noerror. Over the last decade, many problems have been revealed to be testable, but most of such problems belong to NP. This is the first result on the constanttime testability of EXPTIMEcomplete problems.

