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

Sotaro Ishii; Tetsuro Tanaka

cs.AIFeb 24, 2026

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

Authors: Sotaro Ishii, Tetsuro Tanaka

Organizations: Graduate School of Arts and Sciences, The University of Tokyo · Information Technology Center, The University of Tokyo

Abstract

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 ( $10^{64}$ to $10^{69}$ ). 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 \times 10^{68}$ ; 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 \times 10^{18}$ .

Figures & tables

Figure 2: The initial position of Mini Shogi

Figure 3: Schematic of statistical estimation. In this study, the population $\mathcal{P}$ shown in the diagram is $\mathcal{P}_{K}$ , and the target $\mathcal{R}$ consists of canonical reachable positions. The accepted sampled positions $R$ are those with $X_{j}=1$ ; all sampled positions in $S$ contribute to the denominator.

(0,0)	(1,0)	(2,0)	(3,0)	(4,0)	(5,0)	(6,0)	(7,0)	(8,0)
(0,1)	(1,1)	(2,1)	(3,1)	(4,1)	(5,1)	(6,1)	(7,1)	(8,1)
(0,2)	(1,2)	(2,2)	(3,2)	(4,2)	(5,2)	(6,2)	(7,2)	(8,2)
(0,3)	(1,3)	(2,3)	(3,3)	(4,3)	(5,3)	(6,3)	(7,3)	(8,3)
(0,4)	(1,4)	(2,4)	(3,4)	(4,4)	(5,4)	(6,4)	(7,4)	(8,4)
(0,5)	(1,5)	(2,5)	(3,5)	(4,5)	(5,5)	(6,5)	(7,5)	(8,5)
(0,6)	(1,6)	(2,6)	(3,6)	(4,6)	(5,6)	(6,6)	(7,6)	(8,6)

Figure 4: Coordinates

(x,y)

on the board

Figure 5: The final position of Game 4 of the 2nd Den-O Sen.

Figure 6: K-canonical positions and non-K-canonical positions

Figure 7: A non-canonical position. Both Kings are on the 5th file, the mirror axis, so the order is determined by the Golds. Reflection moves Black’s Golds from 1a and 3f to 9a and 7f, which gives a smaller representation. This position also violates the Two Pawns rule (Black’s Pawns on 9d and 9i).

Figure 8: A position violating a local rule. It is Black’s turn, but White’s King on 9f is in check from Black’s Lance on 9h.

Figure 9: A KK position. Only the two non-adjacent Kings remain on the board; all 38 non-King pieces are in hand. This example assigns all of them to Black, but the KK target set allows any distribution between the two players.

Figure 10: A reachable position that is difficult to prove

Figure 11: Positions with no legal one-ply predecessor, all with Black to move. In (a) and (b), every possible reconstruction of White’s last move leaves Black’s King already in check before that move. In (c), the only possible last move is an illegal Pawn-drop mate at 5h. In (d), neither of White’s pieces on the board (the King on 1i and the Horse on 9i) has a possible origin square, and neither could have been dropped.

Figure 12: Position $p$ (left) has position $q$ (right) as its only one-ply predecessor, obtained by undoing White’s Tokin move from 8e to 8f. In $q$ , the Dragon on 9f could not legally have moved from either 8f or 8g. Thus, $\mathrm{Prev}_{1}(p)=\{q\}$ and $\mathrm{Prev}_{1}(q)=\emptyset$ .

Figure 13: Mini Shogi positions determined to be reachable

Figure 14: Shogi positions determined to be reachable

Figure 15: A Mini Shogi position where 8 plies could be traced back. Arrows indicate the move sequence in the actual game.

Figure 16: A Shogi position where 3 plies could be traced back. Arrows indicate the move sequence in the actual game.

Figure 17: Path length $L$ and number of expanded nodes $E$ for 10,000 reachable Shogi positions. The red line is the reference line $E=L$ .

Figure 18: Path length $L$ and number of expanded nodes $E$ for 10,000 reachable Mini Shogi positions. The red line is the reference line $E=L$ .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 20: An example of transferring a piece in hand from Black to White in a KK position

\Unicode ”0026”17P-7f	\Unicode ”0026”16R-3b	\Unicode ”0026”17Bx3c=	\Unicode ”0026”16Rx3c
\Unicode ”0026”17R-3h	\Unicode ”0026”16Rx3g=	\Unicode ”0026”17Rx3g	\Unicode ”0026”16+Bx9i
\Unicode ”0026”17Rx3a=	\Unicode ”0026”16+Bx8i	\Unicode ”0026”17Rx2a=	\Unicode ”0026”16+Bx6g
\Unicode ”0026”17Rx2c=	\Unicode ”0026”16+Bx7f	\Unicode ”0026”17Rx1c=	\Unicode ”0026”16+Bx8g
\Unicode ”0026”17Rx4c=	\Unicode ”0026”16Lx1g=	\Unicode ”0026”17Lx1g	\Unicode ”0026”16+Bx9g
\Unicode ”0026”17Rx5c=	\Unicode ”0026”16K-4b	\Unicode ”0026”17Rx6c=	\Unicode ”0026”16+Bx7i
\Unicode ”0026”17Rx7c=	\Unicode ”0026”16+Bx5g	\Unicode ”0026”17Rx7a=	\Unicode ”0026”16+Bx3i

Appendix

Table 3: An example of a move sequence from the initial position to a KK position

Chess-World-Model: A 10M-Game Benchmark for Exact State Tracking from Chess Move Sequences
May 28, 2026Benjamin Walker, Terry LyonsRecurrent Neural Networks State Tracking
Mathematical Institute, University of Oxford · Department of Mathematics, Imperial College London
Solving Go under Positional Superko: Sound Proof Transfer and New Board Values
Oct 21, 2026Sami Kharma, Florian Schintke
Zuse Institute Berlin Berlin, Germany
Chess_db: A framework for working with large chess game datasets
Jul 23, 2026Nicos Angelopoulos, Jan WielemakerLogic Programming Chess
University College & Imperial College, London UK · University College & Imperial College London, UK · SWI-Prolog solutions +1

May 28, 2026J/K move · Enter open · S save

Chess-World-Model: A 10M-Game Benchmark for Exact State Tracking from Chess Move Sequences

Benjamin Walker, Terry Lyons

Mathematical Institute, University of Oxford · Department of Mathematics, Imperial College London

Recurrent Neural Networks State Tracking Chess World Model Evaluation

Open paper AskPDF arXiv

World models require state tracking, which is the ability to maintain a correct latent state across action sequences. Existing benchmarks are often synthetic or language-based, limiting their value as tests of structured state updates in realistic domains. We introduce Chess-World-Model, a large-scale state-tracking benchmark built from 10 million real chess games, where models predict the exact board state reached after a sequence of legal moves. Alongside a held-out real-game split, we include an out-of-distribution split from uniformly random legal play, which tests whether models learn the transition rules rather than shortcuts from common human positions. Prior theoretical and empirical work has shown that Transformers struggle to state-track, while input-dependent linear RNNs require expressive state-transition matrices to do so. We therefore benchmark a causal Transformer, block-diagonal SLiCE, Mamba-3, and Gated DeltaNet with negative eigenvalues under a matched interface and training protocol. The recurrent models strongly outperform the Transformer at 3 and 8 million parameters. Real-game performance saturates above 18 million parameters, but the random-uniform split remains discriminative up to 40 million, exposing failures otherwise hidden by scale. Additionally, ablations show that less expressive state-transition mechanisms reduce performance on the out-of-distribution split for all three recurrent models. Together, these results establish Chess-World-Model as a practical large-scale benchmark for state tracking that exposes failures model scale would otherwise conceal.

Abstract

Explore similar work

Chess-World-Model: A 10M-Game Benchmark for Exact State Tracking from Chess Move Sequences

Solving Go under Positional Superko: Sound Proof Transfer and New Board Values

Chess_db: A framework for working with large chess game datasets