将棋の実現可能局面数の推計

2024年11月15日の情報処理学会ゲームプログラミングワークショップ2024で利用したスライドを再編集したものです。
同一のスライドを https://github.com/u-tokyo-gps-tanaka-lab/shogilib でも公開しています。

Transcript

1. 将棋の実現可能局⾯数の推計 Statistical estimation of the number of legal positions in Shogi ⽯井颯太郎, ⽥中哲朗 (東京⼤学) GPW2024 2024年 11⽉ 15⽇ ⽯井颯太郎, ⽥中哲朗. “将棋の実現可能局⾯数の推定.” ゲームプログラミングワークショップ2024論⽂集, pp. 150-157, 情報処理学会, 2024.
2. 本発表の要約 課題 将棋の状態数に関して, 既知の上下界はギャップが⼤きい. → 将棋の状態数を⾼い精度で正確に推定したい. 提案⼿法 • 将棋の合法局⾯ (=実現可能局⾯) の判定⼿法を開発した. • 同アルゴリズムを⽤いて, 将棋の状態数を推計した. 結果 約   個という有効数字3桁の推計値を得た. 2
3. 本研究で発⾒した合法な局⾯の例 どちらも 初期局⾯から到達可能 ※なぜそう分かるかは後述 3
4. 研究背景 状態数 (実現可能局⾯数, 状態空間複雑性) … ゲームの規模を特徴づける量の1つ • ゲームの規模それ⾃体が興味の対象になる • ゲームの解決可能性を測るための⽬安になる → 様々なゲームに対して, 状態数の計算が試みられてきた 〈参考 : “ゲームの解決” の種類〉 弱解決 = 初期局⾯のゲーム値も, その証明に必要な各局⾯での最善⼿も判明している 強解決 = 初期局⾯から到達可能な全局⾯に対して, ゲーム値と最善⼿が判明している 4
5. 状態数計算の難しさ 局⾯だけを⾒て, それが初⼿から到達可能か (合法か) 判定することが難 しいゲームは, 状態数の計算も難しい傾向にある. 将棋において, 到達可能性の判定が難しい要因: • 王⼿の放置が禁⽌されている • パスが禁⽌されている • 打ち歩詰めが禁⽌されている 5
6. 禁則事項を破らない駒配置を 厳密に数え上げることで, 上界・下界が計 算されている • (篠⽥, 2008) • (都 et al, 2022) ➜ しかし, 上下界の⼤きなギャップは未解決のまま. (到達可能性のチェックが 難しいため) 先⾏研究 … 将棋の状態数 6
7. 本研究での状態の定義 先⾏研究と共通 • 千⽇⼿・連続王⼿の回数は考慮しない • 先⼿番の局⾯のみを考慮 先⾏研究との違い 左右反転して同⼀となる2つの局⾯を同⼀視 (※将棋ではどの駒の動きも左右対称なため, 左右反転した局⾯を元 と同⼀とみなすのが⾃然.) 7
8. 本研究の⼿法 ※本研究では (50億標本) とした. 統計的推計により, 将棋の状態数を⾼い精度で求める 8
9. 1. 標本局⾯集合 の⽣成 2. 合法な標本局⾯集合 の検出 3. ⺟⽐率の区間推定 ※2. の実⾏の際に, 局⾯の合法性判定アルゴリズムが必要 推計の流れ Python実装: https://github.com/u-tokyo-gps-tanaka-lab/shogilib C++実装: https://github.com/u-tokyo-gps-tanaka-lab/YaneuraOu 9
10. ⼿法 > ① 標本局⾯集団の⽣成 1. 王将以外の駒種に対して「盤上／駒台に 駒 p が各何枚あるか」のパター ンを⽣成 2. 各パターンに当てはまる駒配置を求める 3. 求めた駒配置に整数を重複なく割り当てる → 該当する駒配置 (擬合法局⾯) の総数 = ≒ 約 個 [*] [*] 厳密には 80, 880, 932, 079, 767, 835, 177, 773, 204, 009, 328, 769, 812, 438, 521, 503, 800, 714, 936, 366, 945, 233, 084, 532 個 10
11. ⼿法 > ① 標本局⾯集団の⽣成 • 反則（⼆歩・⾏きどころのない駒・王⼿放置）も含めて⽣成 ◦ 反則局⾯は合法性チェックの際に除去 ◦ 左右対称性や反則をある程度考慮しての⽣成は, 実装が煩雑 ▪ 本研究では実装の容易さを重視して, 王2枚の左右対称性のみを考慮 して⽣成 • を実際に⽣成するのではなく, 事前に計算したテーブルを⽤いて, ある整 数と1対1対応する局⾯を導く ◦ 変換⼿法の詳細は予稿を参照 11
12. ⼿法 > ① 標本局⾯集団の⽣成 区間 内の整数を1つ⽣成する事は, 対応する局⾯を1つ⽣ 成する事と等価 ➜ この区間内の⼀様乱数を50億個⽣成し, 対応する局⾯に変換 ➜ 変換した50億局⾯を標本として, 合法局⾯の割合を調べる. 12
13. ⼿法 > ② 標本中の合法局⾯を⾒つける 擬合法局⾯の組から, 2段階に分けて⾮合法局⾯を取り除く A. 盤⾯を⾒ただけで分かる反則局⾯を除去 ◦ ⼆歩, ⾏き所のない駒, 王⼿放置 ◦ ここで左右の対称性のチェックも⾏う B. 反則ではないが, 初⼿から到達できない局⾯を除去 ◦ ここで合法性判定アルゴリズムが必要. 最も難しい ➜ 取り除かれずに残った局⾯が, 合法局⾯となる. 13
14. ⼿法 > ② 標本中の合法局⾯を⾒つける 擬合法局⾯の組から, 2段階に分けて⾮合法局⾯を取り除く A. 盤⾯を⾒ただけで分かる反則局⾯を除去 ◦ ⼆歩, ⾏き所のない駒, 王⼿放置 ◦ ここで左右の対称性のチェックも⾏う B. 反則ではないが, 初⼿から到達できない局⾯を除去 ◦ ここで合法性判定アルゴリズムが必要. 最も難しい ➜ 取り除かれずに残った局⾯が, 合法局⾯となる. 14
15. 左右の対称性のチェック 左右反転すると, 辞書式順序が元 の局⾯より⼩さくなる局⾯を除く. • 通過: 49億4506万3843個 ◦ 50億標本の 98.9% • 排除: 5493万6157個 15
16. ⼆歩・⾏き所のない駒を含む局⾯の排除 盤⾯を⾒れば判定可能 • 通過: 1億8722万0063個 ◦ 50億標本の 3.74% • 排除: 47億5784万3780個 16
17. 相⼿の⽟を取れるのに, 放置されている局⾯の排除 盤⾯を⾒れば判定可能 • 通過: 5898万1117個 ◦ 50億標本の 1.18% • 排除: 1億2823万8946個 ➜ チェックを通過した5898万 1117個から合法局⾯を探索. ※将棋では, 王⼿の放置や⾃殺⼿は反則. 17
18. ⼿法 > ② 標本中の合法局⾯を⾒つける 擬合法局⾯の組から, 2段階に分けて⾮合法局⾯を取り除く A. 盤⾯を⾒ただけで分かる反則局⾯を除去 ◦ ⼆歩, ⾏き所のない駒, 王⼿放置 ◦ ここで左右の対称性のチェックも⾏う B. 反則ではないが, 初⼿から到達できない局⾯を除去 ◦ ここで合法性判定アルゴリズムが必要. 最も難しい ➜ 取り除かれずに残った局⾯が, 合法局⾯となる. 18
19. 反則ではないが, 初⼿から到達できない局⾯を除く • 局⾯が合法である ＝「初期局⾯から到達可能である」 • だが, 初期局⾯から特定の局⾯に到達可能かの判定は難しい ➡ 初期局⾯と相互に到達できる「遡りやすい合法局⾯」 を⽤意し, 「遡りやすい合法局⾯」に遡れるかを判定すれば良い. ➜ 擬合法局⾯から「遡りやすい合法局⾯」に辿れるならば,「遡りやすい合 法局⾯」を経由して初期局⾯にまで辿れる. 19
20. 反則ではないが, 初⼿から到達できない局⾯を除く 到達可能か不明 遡って探索 相互に遷移可能 遡りやすい合法局⾯ 初期配置 擬合法局⾯ ？ 20
21. 反則ではないが, 初⼿から到達できない局⾯を除く 「遡りやすい合法局⾯」として ”KK局⾯” を⽤いる KK局⾯ :=「⽟2枚のみの合法局⾯」 ただし⼿番, 駒の配置, 持ち駒は⾃由. 21
22. 反則ではないが, 初⼿から到達できない局⾯を除く 到達可能か不明 遡って探索 相互に遷移可能 KK局⾯の集合 初期配置 擬合法局⾯ 22
23. 擬合法局⾯からKK局⾯への探索 貪欲最良優先探索 (greedy best-first search) で, 末端からKK局⾯に向かって 遡っていく 23
24. 探索に⽤いるヒューリスティック関数の定義 王以外の 盤上の駒数 盤上の 成り駒数 盤上の成り駒が, 敵陣から 何段離れている かの総和 ならば pos は KK 局⾯ • 本研究では を採⽤ • ⼿番を考慮せず, 盤⾯を⾒て線形和を求めるだけ 24
25. • 本研究では を採⽤ • ⼿番を考慮せず, 盤⾯を⾒て線形和を求めるだけ 探索に⽤いるヒューリスティック関数の⽬的 盤上の駒を 減らす 盤上の成り駒を 減らす 盤上の成り駒を 成れる場所に 戻す ならば pos は KK 局⾯ 25
26. 探索に⽤いるヒューリスティック関数の計算例 26
27. 探索に⽤いるヒューリスティック関数の計算例 27
28. 探索で発⾒した, KK局⾯に遡る⼿順の例 (420⼿) ※局⾯は篠⽥ (2008) p.4 より引⽤ 28
29. ⼿法 > ③ ⺟⽐率の区間推定 • 中の合法局⾯の割合 • 標本数 , 標本中の合法局⾯の数 , 標本⽐率 この時, ⼆項分布の正規近似による の (約99.73%) 信頼区間は が分かれば, 全体の状態数 の期待値も求まる 29
30. 50億標本に対する3σの推定 推定時の条件 • (既出; 厳密な値は省略) • 標本数 (既出) • 実際に貪欲最良優先探索した局⾯数 5898万1117個 ＝ 合法性チェック (先述) を通った局⾯ • 探索した全局⾯に対して, 数万以内の探索ノード数で探索終了 ◦ KK局⾯への到達可能性を証明: 4049万1613個 ◦ KK局⾯への到達不能性を証明: 1848万9504個 30
31. 50億標本に対する3σの推定 結果 • 標本中に⾒つかった合法局⾯の数 ◦ ➜ 標本全体に占める合法局⾯率 • 合法局⾯数の期待値 • ⺟⽐率の 信頼区間 31
32. KK局⾯の貪欲最良優先探索がうまく⾏った理由 実験から判明した傾向: • 到達不可能な局⾯の場合, ⾏き詰まりがすぐに発⽣する • 到達可能な局⾯の場合, 少ないノード数で到達できる 32
33. 到達不可能な局⾯の⾏き詰まり 3⼿遡れた例: 到達不可能な局⾯は, すぐに途中で⾏き詰 まって遡れなくなる傾向 (表2参照) 33
34. 到達可能な局⾯の探索ノード数 貪欲最良優先探索は, 少ないノード数で解を発⾒していた. 34
35. 1. 擬合法局⾯ (:= 合法か分からない局⾯) を列挙する 2. 擬合法局⾯を何個かランダムに取り出し, その中の合法局⾯の数を調べる 3. 2.の結果から全体の状態数を推計する 関連研究 … ゲームの状態数の統計的推計 → チェスの状態数を 約 個と推計 (200万標本) Tromp (2021) による実験 ※合法局⾯の検出のため, 初期局⾯からの最良優先探索で到達可能性を判定 John Tromp. “Chesspositionranking.” https://github.com/tromp/ChessPositionRanking, 2021. 35
36. 関連研究 … 5五将棋の状態数 • 5×5マス盤で⾏う⼩型の将棋 • 本研究と同じ⼿法によって, 状態数を 約 個と推定 (⽯井・⽥中, 2024) Tromp (2021) との主な違い • 到達可能性の探索⽅向が逆 • 探索に “KK局⾯” を利⽤ ⽯井颯太郎, ⽥中哲朗. “5五将棋の実現可能局⾯数の推計.” 情報処理学会研究報告 ゲーム情報学 (GI), Vol. 2024-GI-53, No. 1, 2024. 36
37. まとめ 課題 将棋の状態数に関して, 既知の上下界はギャップが⼤きい. → 将棋の状態数を⾼い精度で正確に推定したい. 提案⼿法 • 将棋の合法局⾯ (=実現可能局⾯) の判定⼿法を開発した. • 同アルゴリズムを⽤いて, 将棋の状態数を推計した. 結果 約   個という有効数字3桁の推計値を得た. 37