論文の概要: High-Precision Estimation of the State-Space Complexity of Shogi via the Monte Carlo Method

• arxiv url: http://arxiv.org/abs/2604.06189v1
• Date: Tue, 24 Feb 2026 08:16:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-04 02:32:13.807303
• Title: High-Precision Estimation of the State-Space Complexity of Shogi via the Monte Carlo Method
• Title（参考訳）: モンテカルロ法による正木状態空間の高精度推定
• Authors: Sotaro Ishii, Tetsuro Tanaka,
• Abstract要約: 本報告では,正木における到達可能な位置の数について,高精度な統計的推定を行う。 50億のポジションのサンプルから、正木における法的地位の数は6.55倍1068ドル、信任レベルは3ドルと見積もった。 また,この手法をMini Shogiに適用し,その複雑性を約2.38倍1018ドルとした。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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σ$ 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}$.
• Abstract（参考訳）: 前回の組合せ推定では5桁の差(10^{64}$から10^{69}$)を残している。 この大きなギャップは、多数の有効な掲示板構成の中の初期位置と法的に到達可能な職位を区別することの難しさから生じる。 本稿では,正木における到達可能な位置の数について,高精度な統計的推定を行う。 本手法では,モンテカルロサンプリングと,1つの初期位置に対する1つのターゲットの後方探索ではなく,「キングキングのみ」(KK)位置に対する逆探索を利用する新しい到達性試験を組み合わせる。 このアプローチは、到達不可能性を決定するための探索労力を大幅に削減する。 50億のポジションのサンプルから、正木における法的地位の数は6.55 \times 10^{68}$ (to three significant digits) と推定され、信頼度は3σ$である。 また,この手法をMini Shogiに適用し,その複雑性を約2.38 \times 10^{18}$とした。

関連論文リスト

• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。 関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。 また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
  論文  参考訳（メタデータ） (2025-01-22T16:30:58Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Estimating the number of reachable positions in Minishogi [0.0]
  著者らは、一様ランダムサンプリングを用いて候補位置を生成することにより、到達可能な位置の数を推定する。 実験の結果、到達可能なミニショギのポジションは約2.38時間1018ドルであることが判明した。
  論文  参考訳（メタデータ） (2024-08-29T06:20:12Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。 本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。 我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
  論文  参考訳（メタデータ） (2024-08-27T18:28:31Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。 使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。 我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
  論文  参考訳（メタデータ） (2023-06-29T14:57:56Z)
• Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus [48.34563955829649]
  本稿では,共同戦略の信頼区間を構築する戦略的な集中原理を提案する。 2人のプレイヤーによるゼロサムマルコフゲームの場合、戦略的なボーナスの凸性を利用して効率的なアルゴリズムを提案する。 すべてのアルゴリズムは、指定済みの戦略クラスである$Pi$を入力として取り、最良の戦略に近い戦略を$Pi$で出力することができる。
  論文  参考訳（メタデータ） (2022-06-01T00:18:15Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent [9.094186120476174]
  ゼロサムゲームのための後サンプリング強化学習(PSRL-ZSG) ゼロサムゲームのための後サンプリング強化学習(PSRL-ZSG)を提案する。
  論文  参考訳（メタデータ） (2021-09-08T02:05:40Z)
• Scalable estimation of pure multi-qubit states [0.0]
  帰納的$n$-qubit純状態推定法を提案する。 提案手法は,他の推定法と比較して,キュービット数のスケーリングに非常に適している。 提案手法をIBMの量子プロセッサの1つで実験的に実証した。
  論文  参考訳（メタデータ） (2021-07-12T19:02:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。