著者

都 勇志 木谷 裕紀 小野 廣隆

雑誌

研究報告ゲーム情報学(GI) (ISSN:21888736)

巻号頁・発行日

vol.2022-GI-47, no.14, pp.1-7, 2022-03-11

---

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