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

• Item type: SIG Technical Reports(1)
• 公開日: 2022-03-11
• タイトル: 将棋における状態空間数の上下界
• タイトル / 言語: en
• タイトル: Upper and lower bounds on the state-space complexity of Shogi
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 将棋と５五将棋
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学大学院情報学研究科
• 著者所属: 九州大学大学院経済学研究院
• 著者所属: 名古屋大学大学院情報学研究科
• 著者名: 都, 勇志; 木谷, 裕紀; 小野, 廣隆
• 著者名(英): Yuji, Miyako; Hironori, Kiya; Hirotaka, Ono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ゲームの難易比較や AI ベンチマークの妥当性評価などのため，二人零和有限確定完全情報ゲームの「複雑さ」の計量が様々な形で研究されている．代表的な「複雑さ」の尺度の一つが状態空間数であり，これは初期局面から到達可能な局面数として定義されている．本研究では将棋の状態空間数の見積もりを行う．禁則ルールの多さなどから将棋の厳密な状態空間数を測ることは容易ではないが，2008 年の篠田の研究により 4.65×1062 と 9.14×1069 の間の値を取ることがわかっている．本研究では将棋の状態空間数のより正確な評価を行い，2.45×1064 と 6.78×1069 の間の値を取ることを示す．上界値の評価については持ち駒が少ないほど局面のパターンが増えることに注目した計量方法を提案する．下界については，篠田により提案された駒配置のテンプレートを改良し，これに基づく解析を行う．また将棋から派生したゲームである 5 五将棋についても状態空間数が 13 桁から 20 桁の間であることを示す．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11362144
• 書誌情報: 研究報告ゲーム情報学（GI）; 巻 2022-GI-47, 号 14, p. 1-7, 発行日 2022-03-11
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8736
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会