The search functionality is under construction.

Author Search Result

[Author] Teagun PARK(1hit)

1-1hit
  • Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable

    Hiro ITO  Atsuki NAGAO  Teagun PARK  

     
    PAPER-Puzzles

      Vol:
    E102-A No:9
      Page(s):
    1126-1133

    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.