用蒙特卡洛方法精确估算将棋状态空间复杂度，结果达6.55×10⁶⁸。
High-Precision Estimation of the State-Space Complexity of Shogi via the Monte Carlo Method
- 通过反向搜索至多个‘将-将’位置，提升可到达性判断效率。
- 基于50亿样本估算将棋合法局面数为6.55×10⁶⁸，误差小于3σ。
- 方法适用于小型将棋，复杂度约为2.38×10¹⁸，适合博弈研究者参考。
确定将棋（日本象棋）的状态空间复杂度一直是个难题，以往的组合估算存在五数量级的差距（10⁶⁴至10⁶⁹）。这一巨大差距源于在海量有效棋盘配置中难以区分从初始位置合法可达的局势。本文提出一种高精度统计估计方法，结合蒙特卡洛采样与新颖的可到达性测试：采用反向搜索至一组“将-将”（KK）位置，而非单一目标回溯初始位置，显著降低判定不可达性的搜索开销。基于50亿个样本，我们估得将棋合法局面数为6.55×10⁶⁸（三位有效数字），置信度达3σ，远优于此前已知边界。该方法亦应用于小型将棋，测得其复杂度约为2.38×10¹⁸。
原文摘要 · Abstract (English)
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σ$ 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}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。