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.
Figures & tables
Figure 1: The initial position of Shogi
Figure 2: The initial position of Mini Shogi
Figure 3: Schematic of statistical estimation. In this study, the population P shown in the diagram is PK , and the target R consists of canonical reachable positions. The accepted sampled positions R are those with Xj=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, Prev1(p)={q} and Prev1(q)=∅ .
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 19: Move sequences for changing the side to move
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
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.
Benjamin Walker, Terry Lyons
Mathematical Institute, University of Oxford · Department of Mathematics, Imperial College London
Positional superko (PSK) forbids recreating any earlier whole-board position. It is part of the Chinese rules as written and of the rules used in computer Go. Yet almost all solved Go boards were computed under a simpler basic-ko rule set. PSK makes solving hard: legality depends on the whole game history, and this breaks the three tools that make solving tractable, namely transposition tables (the graph-history interaction problem), static life-and-death recognition, and safe move pruning. We present Sanko, a parallel depth-first proof-number solver that restores all three soundly. Its core is a cheap proof-transfer theorem: a stored proof stays valid on a new path unless a board that the proof's winner must create has already occurred. Sanko proves 5x5 Go in 16 minutes with six threads, where the previous state of the art needed 5.25 hours with six processes, and in about a minute and a half on one 192-thread machine. It also establishes the first PSK values of twenty-three further boards, eleven of which were unsolved under any rules. Superko changes game-theoretic values: 4x7, a full-board win under basic ko, is worth only 12 points under PSK, and we pinpoint the move at which the previously published optimal line fails. Unlike earlier solutions of empty Go boards, we release the solver source together with the command line and outcome of every run behind our values and measurements, so that all reported values can be reproduced.
Chess is a two player strategic game that is embedded in classical AI culture as it was once the frontier for intelligent behaviour. There was the silent assumption that the advent of computer engines that play better than the best humans will extinguish interest in the game. However, the opposite has come to pass, with a growing following for the game. A lot of the computational resources are now centered around training of players, where the engine output is just one aspect. Access to past games is also an essential part, both in knowing what games a specific player has played previously, and also which continuations at a certain position have led to victory more often for each of the two colour players. We present Chess_db a suite of logic programming tools that can effectively manipulate games both in memory and via creating back end databases. In particular, we provide versatile code that creates databases from PGN (portable game notation) game files and explore the suitability of open source key-value databases for storing position tables that provide near-instant access to information pertaining to substantially large number of games.
Nicos Angelopoulos, Jan Wielemaker
University College & Imperial College, London UK · University College & Imperial College London, UK · SWI-Prolog solutions +1