High-Precision Estimation of the State-Space Complexity of Shogi via the Monte Carlo Method

Computer Science > Artificial Intelligence [Submitted on 24 Feb 2026] High-Precision Estimation of the State-Space Complexity of Shogi via the Monte Carlo Method Sotaro Ishii, Tetsuro Tanaka Determining the state-space complexity of the game of Shogi (Japanese Chess) has been a challenging problem, with previous combinatorial estimates leaving a gap of five orders of magnitude (10^{64} to 10^{69}). This large gap arises from the difficulty of distinguishing Shogi positions legally reachable from the initial position among the vast number of valid board configurations. In this paper, we present a high-precision statistical estimation of the number of reachable positions in Shogi. Our method combines Monte Carlo sampling with a novel reachability test that utilizes a reverse search toward a set of "King-King only" (KK) positions, rather than a single-target backward search to the single initial position. This approach significantly reduces the search effort for determining unreachability. Based on a sample of 5 billion positions, we estimated the number of legal positions in Shogi to be 6.55 \times 10^{68} (to three significant digits) with a 3\sigma confidence level, substantially improving upon previously known bounds. We also applied this method to Mini Shogi, determining its complexity to be approximately 2.38 \times 10^{18}. Comments: Preprint submitted to IPSJ Journal of Information Processing Subjects: Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT) Cite as: arXiv:2604.06189 [cs.AI]   (or arXiv:2604.06189v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2604.06189 Focus to learn more Submission history From: Sotaro Ishii [view email] [v1] Tue, 24 Feb 2026 08:16:22 UTC (961 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.GT References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)