文献

J-GLOBAL ID：202202222762493985   整理番号：22A0884778

将棋における状態空間数の上下界

Upper and lower bounds on the state-space complexity of Shogi

著者 (3件)： 都勇志 (名古屋大 大学院情報学研究科) ,  木谷裕紀 (九大 大学院経済学研究院) ,  小野廣隆 (名古屋大 大学院情報学研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2022  号： GI-47  ページ： Vol.2022-GI-47,No.14,1-7 (WEB ONLY)  発行年： 2022年03月11日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ゲームの難易比較やAIベンチマークの妥当性評価などのため,二人零和有限確定完全情報ゲームの「複雑さ」の計量が様々な形で研究されている.代表的な「複雑さ」の尺度の一つが状態空間数であり,これは初期局面から到達可能な局面数として定義されている.本研究では将棋の状態空間数の見積もりを行う.禁則ルールの多さなどから将棋の厳密な状態空間数を測ることは容易ではないが,2008年の篠田の研究により4.65×10⁶²と9.14×10⁶⁹の間の値を取ることがわかっている.本研究では将棋の状態空間数のより正確な評価を行い,2.45×10⁶⁴と6.78×10⁶⁹の間の値を取ることを示す.上界値の評価については持ち駒が少ないほど局面のパターンが増えることに注目した計量方法を提案する.下界については,篠田により提案された駒配置のテンプレートを改良し,これに基づく解析を行う.また将棋から派生したゲームである5五将棋についても状態空間数が13桁から20桁の間であることを示す.(著者抄録)

シソーラス用語： 娯楽 ,  空間 ,  *限界 ,  配置 ,  情報科学 ,  *ゼロ和ゲーム ,  *二人ゲーム
準シソーラス用語： ゲーム情報学 ,  コンピュータ将棋 ,  下界 ,  完全情報ゲーム ,  将棋 ,  上界 ,  状態空間 ,  複雑性

分類 (1件)： ゲーム理論  (KA03060T)

引用文献 (12件)：

• Chinchalkar, S.: An upper bound for the number of reachable positions, ICGA Journal, Vol. 19, No. 3, pp. 181-183 (1996).
• Gourion, D.: An upper bound for the number of chess diagrams without promotion, CoRR, Vol. abs/2112.09386 (2021).
• Microsoft: ゲームAIの難易度とは,https://news.microsoft.com/ja-jp/2019/08/22/190822-difficulty-of-game-ai/ (閲覧日:2022年2月21日) (2019).
• Park, D.: Space-state complexity of Korean chess and Chinese chess, arXiv preprint arXiv:1507.06401 (2015).
• Shannon, C. E.: XXII. Programming a computer for playing chess, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, Vol. 41, No. 314, pp. 256-275 (1950).

タイトルに関連する用語 (2件)： 将棋 ,  状態空間