La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable Le Shogi, les échecs et le Xiangqi généralisés sont testables en temps constant

Hiro ITO, Atsuki NAGAO, Teagun PARK

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1126-1133
Date de publication
2019/09/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E102.A.1126
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Casse-têtes

Auteurs

Hiro ITO
  the University of Electro-Communications,CREST JST
Atsuki NAGAO
  Ochanomizu University
Teagun PARK
  E.K Soft Co., Ltd

Mots-clés

Table des matières