Researchers narrow the gap on how many chess positions exist in Shogi — a problem unsolved for decades

A team used statistical sampling rather than brute-force calculation to estimate the total number of legally reachable positions in Shogi (Japanese chess), shrinking a five-order-of-magnitude uncertainty down to a single number: roughly 6.55 × 10^68 positions. This matters because state-space complexity is the basic measurement that tells you how hard a game is for AI systems to learn — tighter estimates mean AI researchers can actually predict what it will take to master a game.

For decades, researchers could only say Shogi's state-space complexity fell somewhere between 10^64 and 10^69 — a gap so wide it made planning AI approaches to the game nearly impossible. This paper closes that gap to a single estimate with statistical confidence, which means AI teams can now calibrate training requirements, model size, and computational cost against a known target instead of a range that spans five orders of magnitude. The methodological win here is also portable: the reverse-search technique works on other combinatorial games where forward-search from a starting position is computationally intractable, so this will likely get copied.