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

arXiv: https://arxiv.org/abs/2604.06189 · HTML: https://mlsanity.com/paper/2604.06189/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 26 references that are in the map.
- First posted on arXiv 24 Feb 2026.

## Builds on (most cited first, 1 of 1)

- [An Upper Bound on the State-Space Complexity of Brandubh](https://mlsanity.com/paper/2106.05353/) (2021)

## Abstract (arXiv)

Determining the state-space complexity of Shogi (Japanese Chess) has been a challenging problem, with previous combinatorial estimates leaving a gap of five orders of magnitude (1064 to 1069). This gap arises from the difficulty of distinguishing positions reachable from the initial position among the vast number of board configurations. In this paper, we present a high-precision statistical estimate of the number of reachable Shogi positions. Here, a position consists of the side to move, the board configuration, and the pieces in hand, without move history, and positions related by exchanging the two players or by horizontal reflection of the board are counted once. Our method combines Monte Carlo sampling with a reachability test that performs reverse search toward the set of ``King-King only'' (KK) positions rather than toward the single initial position. Since every KK position and the initial position are mutually reachable, reaching any KK position proves reachability, and removing pieces from the board is a much simpler objective than reconstructing the initial position. Based on a sample of five billion positions, we estimate the number of such positions in Shogi to be 6.55 × 1068; both ends of the approximate 3σ confidence interval round to this value at three significant digits. We also applied this method to Mini Shogi, obtaining approximately 2.38 × 1018.