A Finite Automaton Approach to Combinatorial Games
Abstract
This study applies finite automata to the automatic solving of a variety of combinatorial games. For games whose positions and moves can be represented as regular languages and their operations, we design a two-stage automatic solving algorithm: first, construct a candidate finite automaton to determine the 𝒫- and 𝒩-positions, and then perform rigorous formal verification on this automaton; once verified, a complete solution of the game is obtained. For partizan octal games, we introduce a generalized misère quotient, overcoming the limitation that traditional theory applies only to impartial games. Using the above algorithm, we successfully solve the majority of two-digit partizan octal games, and based on these results, we propose a partizan version of Guy's conjecture. We also successfully solve a considerable number of partizan octal games under misère play, and give a conjecture on the structure of those games exhibiting ``algebraic periodicity'' among them. For Kotzig's nim, we resolve the most important related conjecture: we prove that the outcomes and SG values are periodic under both normal and misère play (including their partizan versions). Our algorithm successfully solves several small-scale cases, including misère play and partizan versions. This study pioneers a new theoretical tool and algorithmic paradigm for the automatic solving of combinatorial games, and has broad prospects for further extension and application in the field of combinatorial game theory.
Related
- Certificates for short extending words in a finite automaton
- A combinatorial approach to point-flat incidences over finite fields
- A Fast and High-Accuracy Finite-Time Sliding-Mode Algorithm for Computing Local Stackelberg Equilibria in Nonlinear Bilevel Games
- Risk-Averse Bayesian Games with an Unknown Type Distribution: Bayesian Learning, Equilibrium Analysis, and Finite-Sample Guarantees
- The smallest Mealy automaton of intermediate growth
BibTeX
@misc{liang2026finite,
title = {{A Finite Automaton Approach to Combinatorial Games}},
author = {Kai Liang},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.13273},
eprint = {2608.13273},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.13273},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Finite Automaton Approach to Combinatorial Games
AU - Kai Liang
PY - 2026
DA - 2026/08/29
PB - arXiv
DO - 10.48550/arxiv.2608.13273
UR - https://arxiv.org/abs/2608.13273
AB - This study applies finite automata to the automatic solving of a variety of combinatorial games. For games whose positions and moves can be represented as regular languages and their operations, we design a two-stage automatic solving algorithm: first, construct a candidate finite automaton to determine the 𝒫- and 𝒩-positions, and then perform rigorous formal verification on this automaton; once verified, a complete solution of the game is obtained. For partizan octal games, we introduce a generalized misère quotient, overcoming the limitation that traditional theory applies only to impartial games. Using the above algorithm, we successfully solve the majority of two-digit partizan octal games, and based on these results, we propose a partizan version of Guy's conjecture. We also successfully solve a considerable number of partizan octal games under misère play, and give a conjecture on the structure of those games exhibiting ``algebraic periodicity'' among them. For Kotzig's nim, we resolve the most important related conjecture: we prove that the outcomes and SG values are periodic under both normal and misère play (including their partizan versions). Our algorithm successfully solves several small-scale cases, including misère play and partizan versions. This study pioneers a new theoretical tool and algorithmic paradigm for the automatic solving of combinatorial games, and has broad prospects for further extension and application in the field of combinatorial game theory.
ER -