Name
Abstract | ||
|---|---|---|
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 [root n] x [root 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1587/transfun.E102.A.1126 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
property testing, generalized shogi, generalized chess, generalized xiangqi, EXPTIME-complete, one-sided-error | Theoretical computer science,Mathematics,Calculus | Journal |
Volume | Issue | ISSN |
E102A | 9 | 0916-8508 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiro Ito | 1 | 290 | 39.95 |
| Atsuki Nagao | 2 | 2 | 3.78 |
| Teagun Park | 3 | 0 | 0.34 |