The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Nous présentons des algorithmes de test en temps constant pour le shogi généralisé (échecs japonais), les échecs et le xiangqi (échecs chinois). Ces problèmes sont connus ou présumés EXPTIME-complet. Un algorithme de test (ou un testeur) pour une propriété accepte une entrée si elle possède la propriété, et la rejette avec une forte probabilité si elle est loin de posséder la propriété (par exemple, au moins 2/3) en lisant uniquement une partie constante de l'entrée. Une propriété est dite testable si un testeur existe. Étant donné n'importe quelle position sur un ⌊√n⌋×⌊√n⌋ planche avec O(n), les problèmes généralisés du shogi, des échecs et du xiangqi sont des problèmes déterminant la propriété selon laquelle « le joueur qui bouge en premier a une stratégie gagnante ». Nous proposons que cette propriété soit testable pour le shogi, les échecs et le xiangqi. Le testeur de shogi et le testeur de xiangqi ont une erreur unilatérale, mais étonnamment, le testeur d'échecs n'a aucune erreur. Au cours de la dernière décennie, de nombreux problèmes se sont révélés vérifiables, mais la plupart de ces problèmes appartiennent à NP. Il s'agit du premier résultat sur la testabilité en temps constant de EXPTIME-problèmes complets.
Hiro ITO
the University of Electro-Communications,CREST JST
Atsuki NAGAO
Ochanomizu University
Teagun PARK
E.K Soft Co., Ltd
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Hiro ITO, Atsuki NAGAO, Teagun PARK, "Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1126-1133, September 2019, doi: 10.1587/transfun.E102.A.1126.
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 ⌊√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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1126/_p
Copier
@ARTICLE{e102-a_9_1126,
author={Hiro ITO, Atsuki NAGAO, Teagun PARK, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable},
year={2019},
volume={E102-A},
number={9},
pages={1126-1133},
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 ⌊√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.},
keywords={},
doi={10.1587/transfun.E102.A.1126},
ISSN={1745-1337},
month={September},}
Copier
TY - JOUR
TI - Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1126
EP - 1133
AU - Hiro ITO
AU - Atsuki NAGAO
AU - Teagun PARK
PY - 2019
DO - 10.1587/transfun.E102.A.1126
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - 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.
ER -