Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable

Hiro ITO  Atsuki NAGAO  Teagun PARK  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1126-1133
Publication Date: 2019/09/01
Online ISSN: 1745-1337
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,  EXPTIME-complete,  one-sided-error,  

Full Text: PDF(1.1MB)>>
Buy this Article




Summary: 
We present constant-time testing algorithms for generalized shogi (Japanese chess), chess, and xiangqi (Chinese chess). These problems are known or believed to be EXPTIME-complete. 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 one-sided-error, but surprisingly, the chess tester has no-error. 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 constant-time testability of EXPTIME-complete problems.