arxiv: 2604.06189 · v1 · submitted 2026-02-24 · 💻 cs.AI · cs.GT

Recognition: no theorem link

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

Sotaro Ishii , Tetsuro Tanaka

Authors on Pith no claims yet

Pith reviewed 2026-05-15 20:17 UTC · model grok-4.3

classification 💻 cs.AI cs.GT

keywords Shogistate-space complexityMonte Carlo samplingreachability testlegal positionsgame complexityMini ShogiKing-King positions

0 comments

The pith

Monte Carlo sampling with reverse reachability testing estimates 6.55 × 10^68 legal Shogi positions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks a precise count of reachable board positions in Shogi, a game whose legal configurations had previously been bounded only between 10^64 and 10^69. It replaces exhaustive enumeration or single-target backward search with Monte Carlo sampling of five billion random positions, each tested for reachability by a reverse search that terminates at simplified King-King configurations. The resulting point estimate of 6.55 × 10^68, reported to three significant figures with 3σ , narrows the uncertainty by several orders of magnitude and is accompanied by a parallel estimate of 2.38 × 10^18 for the smaller Mini Shogi variant. A sympathetic reader would care because an accurate state-space size directly informs the computational resources needed for perfect play, heuristic evaluation depth, and cross-game complexity comparisons.

Core claim

By drawing five billion positions uniformly from the space of valid Shogi boards and classifying each as reachable or unreachable via reverse search to the set of King-King only positions, the authors obtain a statistical estimate that the number of positions reachable from the initial setup is 6.55 × 10^68 (three significant digits, 3σ). The same procedure applied to Mini Shogi yields approximately 2.38 × 10^18 reachable positions.

What carries the argument

Monte Carlo sampling paired with reverse search toward the set of King-King only positions, which replaces a single-target backward search and thereby reduces the effort required to certify unreachability.

If this is right

The five-order-of-magnitude gap in prior bounds is replaced by a single value known to three significant figures.
Shogi can now be compared quantitatively with Chess (approximately 10^47) and Go (approximately 10^170) on the same scale of state-space size.
The identical sampling-plus-reverse-search pipeline produces a concrete complexity figure for Mini Shogi.
The method demonstrates that Monte Carlo estimation becomes practical once an efficient reachability oracle is available.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the same oracle can be adapted to other drop-move games, state-space estimates for those games could be obtained at comparable cost.
The reported confidence interval supplies a concrete target variance that future sampling campaigns could aim to reduce by increasing sample size or variance-reduction techniques.
A verified count of reachable positions supplies an upper bound on the memory footprint required by any exhaustive retrograde-analysis solver for Shogi endgames.

Load-bearing premise

The reverse search from sampled positions to King-King configurations classifies reachability from the true initial position without systematic false positives or negatives.

What would settle it

Discovery of even one position that the reverse-search procedure labels unreachable yet can be shown by forward play to be reachable from the initial setup (or vice versa) would invalidate the classification step and therefore the numerical estimate.

Figures

Figures reproduced from arXiv: 2604.06189 by Sotaro Ishii, Tetsuro Tanaka.

**Figure 13.** Figure 13: Positions p such that Prev1(p) ̸= ∅ ∧ Prev2(p) = ∅ making the right figure an illegal position. Although this example was artificially constructed, among the examples of positions p satisfying Previ(p) ̸= ∅ ∧ Previ+1(p) = ∅ (i ≥ 1) discovered in our experiments, many were related to an ignored check as in [PITH_FULL_IMAGE:figures/full_fig_p009_13.png] view at source ↗

read the original abstract

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}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper's new Monte Carlo estimate puts Shogi reachable positions at 6.55 × 10^68, improving on prior bounds, though the reachability oracle lacks reported validation.

read the letter

This paper's key result is a Monte Carlo estimate of the reachable state space in Shogi at 6.55 × 10^68 to three significant digits, drawn from 5 billion samples. The novelty is in the reachability test: instead of searching back to the initial position, they search to the set of King-King only positions. That change makes it feasible to classify enough samples to close the previous five-order gap between 10^64 and 10^69. The work does a good job of making the computation practical and reporting a usable number for game developers and theorists. Extending the method to Mini Shogi gives a concrete smaller case at 2.38 × 10^18, which helps show the approach scales. The soft spot is the unverified accuracy of the KK reverse search classifier. If it has systematic errors in labeling reachable positions, the sampled fraction shifts and the total estimate is off. The abstract mentions no explicit checks against known positions, no error rate on Mini Shogi, and no variance formula, so the 3σ claim rests on the assumption that the oracle is unbiased. That is the load-bearing part. This is for people who need numerical bounds on Shogi complexity rather than theoretical breakthroughs. A reader working on game AI or state-space analysis would find the number and the method worth looking at. It deserves serious peer review because the sample is large and the idea is new, even if more supporting evidence on the oracle would be needed in revision.

Referee Report

2 major / 1 minor

Summary. The paper claims a Monte Carlo estimate of Shogi's reachable positions at 6.55 × 10^68 (three significant digits, 3σ) from 5 billion samples, using reverse search from sampled boards to the set of King-King only (KK) positions as the reachability oracle; the same method yields 2.38 × 10^18 for Mini Shogi, narrowing the prior 10^64–10^69 gap.

Significance. If the KK classifier is unbiased, the result supplies the first three-digit numerical value for Shogi state-space size and demonstrates a scalable sampling technique that could be applied to other large games; the 5-billion-sample size and explicit Mini-Shogi cross-check are concrete strengths supporting reproducibility.

major comments (2)

[Methods (reachability oracle)] The central scaling step (observed reachable fraction × total valid boards) rests on the unvalidated assumption that the KK-reverse search produces no systematic false positives or negatives; no error-rate measurement, exhaustive enumeration on known Mini-Shogi positions, or comparison against direct backward search from the initial position is reported.
[Results (confidence level)] No explicit formula for the reported variance, standard error, or 3σ interval derivation appears; the 5-billion-sample size is large enough for three-digit precision only if the binomial proportion variance and any sampling bias from the KK oracle are quantified.

minor comments (1)

[Abstract] The abstract states the Mini-Shogi result but does not indicate whether the same KK classifier was validated there or whether known exact counts for Mini Shogi were used as a sanity check.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. We address the major comments point by point below and will incorporate revisions to improve the clarity and rigor of the manuscript.

read point-by-point responses

Referee: [Methods (reachability oracle)] The central scaling step (observed reachable fraction × total valid boards) rests on the unvalidated assumption that the KK-reverse search produces no systematic false positives or negatives; no error-rate measurement, exhaustive enumeration on known Mini-Shogi positions, or comparison against direct backward search from the initial position is reported.

Authors: We acknowledge that the manuscript does not include explicit validation of the KK-reverse search oracle. To address this, we will add a new subsection in the Methods section providing an error-rate analysis. Specifically, we will perform exhaustive enumeration on Mini-Shogi positions to measure false positive and negative rates, and compare against direct backward search from the initial position on a representative sample of boards. This will confirm the reliability of the oracle for the scaling step. revision: yes
Referee: [Results (confidence level)] No explicit formula for the reported variance, standard error, or 3σ interval derivation appears; the 5-billion-sample size is large enough for three-digit precision only if the binomial proportion variance and any sampling bias from the KK oracle are quantified.

Authors: We agree that the statistical derivation should be made explicit. In the revised version, we will include the formula for the binomial proportion variance, the standard error calculation, and the exact method used to derive the 3σ confidence interval. We will also quantify and discuss any potential sampling bias introduced by the KK oracle, ensuring that the three-digit precision is justified by the 5-billion-sample size. revision: yes

Circularity Check

0 steps flagged

No circularity: direct Monte Carlo proportion scaled by total configurations

full rationale

The derivation consists of sampling 5 billion board configurations, applying an external computational oracle (reverse search to KK-only positions) to label each as reachable or unreachable, then scaling the observed reachable fraction by the total number of valid board configurations. No equation in the paper reduces the final estimate to a fitted parameter, self-referential definition, or prior self-citation; the KK oracle is presented as a novel but independent procedure whose correctness is an external assumption rather than a derived result. No self-citation load-bearing step, no renaming of known results, and no ansatz smuggling appear in the central claim. The method is a standard statistical estimator against an external classifier and remains self-contained.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The claim rests on the law of large numbers for Monte Carlo convergence and on the unproven equivalence between reachability to KK positions and reachability from the initial position.

free parameters (1)

Monte Carlo sample size
5 billion positions chosen to achieve three-significant-digit precision; the exact count is a design parameter that directly controls reported uncertainty.

axioms (1)

standard math Law of large numbers guarantees convergence of sample proportion to true reachability probability
Invoked implicitly to justify reporting 6.55 × 10^68 from finite samples.

invented entities (1)

King-King only (KK) position set no independent evidence
purpose: Target set for reverse reachability search that reduces computational cost compared with single-target backward search
Newly defined collection of positions used as the termination condition for the reachability test.

pith-pipeline@v0.9.0 · 5510 in / 1403 out tokens · 57408 ms · 2026-05-15T20:17:55.719259+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

PhD thesis, Maastricht University, 1994

Louis Victor Allis.Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Maastricht University, 1994

work page 1994
[2]

Retrograde analysis of certain endgames.ICGA Jour- nal, 9(3):131–139, 1986

Ken Thompson. Retrograde analysis of certain endgames.ICGA Jour- nal, 9(3):131–139, 1986

work page 1986
[3]

Heule and L.J.M

M.J.H. Heule and L.J.M. Rothkrantz. Solving games: Dependence of applicable solving procedures.Science of Computer Programming, 67(1):105–124, 2007

work page 2007
[4]

Claude E. Shannon. Programming a computer for playing chess. Philosophical Magazine, Ser.7, 41(314), 1950

work page 1950
[5]

A knowledge-based approach of connect-four

Louis Victor Allis. A knowledge-based approach of connect-four. Master’s thesis, Vrije University, 1988

work page 1988
[6]

An upper bound for the number of reachable positions.ICGA Journal, 19:181–183, 1996

Shirish Chinchalkar. An upper bound for the number of reachable positions.ICGA Journal, 19:181–183, 1996

work page 1996
[7]

Combinatorics of go

John Tromp and Gunnar Farneb ¨ack. Combinatorics of go. In Computers and Games, pages 84–99, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.https://doi.org/10.1007/ 978-3-540-75538-8_8

work page 2007
[8]

Analysis of the number of piece placements innmen’s morris.IPSJ SIG Technical Report: Game Informatics (GI), 2020-GI-43(8), 2020

Dan Takeda and Kunihito Hoki. Analysis of the number of piece placements innmen’s morris.IPSJ SIG Technical Report: Game Informatics (GI), 2020-GI-43(8), 2020. [In Japanese]

work page 2020
[9]

Crandall

Kiernan Compy, Alana Evey, Hunter McCullough, Lindsay Allen, and Aaron S. Crandall. An upper bound on the state-space complexity of brandubh. In2020 IEEE Conference on Games (CoG), pages 519– 525, 2020

work page 2020
[10]

The number of the legal positions in shogi

Masato Shinoda. The number of the legal positions in shogi. InPro- ceedings of the Game Programming Workshop 2008, volume 2008, pages 116–119, 2008. [In Japanese]

work page 2008
[11]

Upper and lower bounds on the state-space complexity of shogi.IPSJ SIG Technical Report: Game Informatics (GI), 2022-GI-47(14), 2022

Yuji Miyako, Hiroki Kiya, and Hirotaka Ono. Upper and lower bounds on the state-space complexity of shogi.IPSJ SIG Technical Report: Game Informatics (GI), 2022-GI-47(14), 2022. [In Japanese]

work page 2022
[12]

Chesspositionranking.https://github.com/ tromp/ChessPositionRanking, 2021

John Tromp. Chesspositionranking.https://github.com/ tromp/ChessPositionRanking, 2021. [Online; accessed 2026-02-17]

work page 2021
[13]

Shogi Tengokusha, 1997

Isao Umebayashi.Shogi Around the World: From Antiquity to the Present. Shogi Tengokusha, 1997. [In Japanese]

work page 1997
[14]

Rules of play.https://www.shogi

Japan Shogi Association. Rules of play.https://www.shogi. or.jp/match/taikyoku_rules/. [In Japanese, Online; ac- cessed 2026-02-17]

work page 2026
[15]

Adjustment of game balance in min- ishogi by adding new rules.IPSJ SIG Technical Report, 2023-GI- 50(No.4), 2023

Kazushi Mizuta and Takeshi Ito. Adjustment of game balance in min- ishogi by adding new rules.IPSJ SIG Technical Report, 2023-GI- 50(No.4), 2023. [In Japanese]

work page 2023
[16]

CRC Press, 1998

Donald L Kreher and Douglas R Stinson.Combinatorial Algorithms: Generation, Enumeration, and Search. CRC Press, 1998

work page 1998
[17]

A comparison of greedy search algorithms.Proceedings of the International Sympo- sium on Combinatorial Search, 1(1):129–136, Aug

Christopher Wilt, Jordan Thayer, and Wheeler Ruml. A comparison of greedy search algorithms.Proceedings of the International Sympo- sium on Combinatorial Search, 1(1):129–136, Aug. 2010

work page 2010
[18]

mov- able region

yaneurao/yaneuraou: Yaneuraou is the world’s strongest shogi en- gine(ai player) , wcsc29 1st winner , educational and usi compliant engine.https://github.com/yaneurao/YaneuraOu. [On- line; accessed 2026-02-17]. Appendix A.1 Mutual Reachability Between the Initial Position and KK Positions In this section, we prove that any KK position and the initial pos...

work page 2026
[19]

Therefore, we can construct a move sequence (hereafter C3) in which Black returns to the original square in 3 moves within the movable region, as shown in the left ofFig. A·1. Similarly, we can construct a move sequence (hereafterC 2) in which White returns to the original square in 2 moves. By having Black playC 3 and White playC 2, the side to move swit...

work page