オセロ求解へ向けた取 り組み 橋本剛 上田徹 橋本隼一 北陸先端科学技術大学院大学 情報科学研究科.

Presentation on theme: "オセロ求解へ向けた取 り組み 橋本剛 上田徹 橋本隼一 北陸先端科学技術大学院大学 情報科学研究科."— Presentation transcript:

1 オセロ求解へ向けた取 り組み 橋本剛 上田徹 橋本隼一 北陸先端科学技術大学院大学 情報科学研究科

2 まずは自己紹介 コンピュータ将棋 TACOS の開発をして ます。 趣味： 将棋（自分のプログラムにまっ たく勝てなくなった） 学会： 情報処理学会ゲーム情報学研究 会、ＩＣＧＡ（ International Computer Games Association ）

3 こちらの分野のホットな話題 コンピュータ将棋： 評価関数の自動学 習（Ｂｏｎａｎｚａ Ｍｅｔｈｏｄ, 保木 2006 ）  プロレベルまであと少し コンピュータ囲碁： モンテカルロ法（＋ ＵＣＴ）が猛威を振るう  9 路盤ではプロに勝った？ １９路盤でも有 段者に

4 昨年の大きな話題： Checkers is solved Checkers が解けた！結論は引き分け． [J. Schaeffer et al, Science, 2007] ． 世界中で大きく取り上げられ， Checker が有名でな い日本でも新聞などが取り上げた．  ゲームを解くという事は大きな話題を呼ぶ 大型計算機を数年間回し続けた（新聞では１８ 年計算しっぱなしで解いたなどと報道） checkers の次の候補は？ ⇒ オセロ

5 本日の流れ 研究の目的 関連研究紹介： Checkers is solved 証明数を使う探索 新しい探索法 WPNS の提案 オセロ・ソルバの開発・設計 まとめ

6 研究の目的 オセロは Checker よりも難しく解くのは困難 オセロが解けたらインパクトは大きい 8×8 オセロの読切り  ゲームの結論とそれに至る手順を求める

7 オセロを解く事の難しさ checkers の探索空間は 5×10 20 オセロの探索空間は 100000000×10 20  6×6 のオセロは解かれており、 16 対 20 で白勝ち． [Joel Feinstein 1993] ハードウェアの進歩や探索法の洗練によりコン ピュータの探索性能は格段に向上 容易に解く事は出来ないが， 決して夢物語ではない

8 チェッカーのルール ・駒は常に斜めに動く ・獲る事が可能な駒は必ず獲らなければならない。複数の獲り方がある場合は任意 に選択してよい。 ・相手の駒を穫った後もう一度穫ることが可能ならば、そのまま連続してもう一駒 穫る ・一番奥の列に駒を進めることによって、「成る」ことができる。成った駒は「キ ング」と呼ばれ、以後斜め後ろを合わせた 4 方向に進むことができるようになる ・以下のふたつの状況で勝敗が決定する。 ・相手の駒が全滅した場合、全滅させた側の勝利となる ・次に動かせる駒がなくなった場合、動かせなくなった側が敗北となる

9 Checkers is solved: アルゴリズム構成 Seeding  文献などから得る「 Best Play 」 の手順を入れる Proof tree manager  Proof number search Proof solver  αβ 探索 →dfpn 探索 Endgame database  駒残り 10 個以下の局面は すべて登録 証明数を使う探索 オセロにも使える？

10 証明数を使う探索

11 証明木 探索空間 O(b d )  b: 分岐因子  d: 深さ 証明木 : O(b d/2 )  節点が勝ちであること を証明する木 証明木になりそうな ノードを効率よく探 索する方法は？ ⇒ 証明数探索 例 OR 節点 AND 節点 A BC DEFG HIJKLM 不明勝ち 負け勝ち 不明負 負 勝 勝 勝 勝 証明木

12 証明数の定義 節点 n の証明数 pn(n)  n が勝ちであるために展開しなければならない先端節点数の下限値 (1) 節点 n が先端節点 (a) 未解決 pn = 1 (b) 勝ち pn = 0 (c) 負け pn = ∞ (2) 節点 n が内部節点 (a)n が OR 節点 pn = 子節点の pn の最小値 (b)n が AND 節点 pn = 子節点の pn の和 ∞ 2 2 110 ∞ 2 pn OR 節点 pn AND 節点

13 証明数を使って探索 証明数を使って効率よく探索するには？ ⇒ 証明数が最小のノードを常に展開すれ ばいい ⇒ 最良優先探索が簡単 ややこしいノードは後回し、証明数の少 ない簡単そうなノードを先に探索 手数が長くても応手数が少ない問題は特 に強い 最適解は保障しない

14 PN-search とその進化 証明数を閾値として探索を行う。証明数の少な い簡単そうなノードを優先して展開するので、 解に到達しやすい。 反証数も同時に閾値として扱う 最良優先探索 →PN-search [Allis,1994]  メモリの問題があり、難しい問題は解けない  詰め将棋の世界で深さ優先探索として発展、 PN* ： 証明数だけ、ミクロコスモスを初めて解く [Seo:1997]ミクロコスモス  参考 ミクロコスモス http://www.geocities.jp/k_7ro/o18.html df-pn ： 長手数詰め将棋問題をすべて解くことに成功 [Nagai:1999]

15 df-pn (depth first proof number search) 反証数も使い PN-search と等価 [Nagai:1999] 300 手以上の詰将棋問題を全て解く checkers が解かれた際の探索にも用いられる 詰碁でも優れた成果を挙げる 二人零和完全情報ゲームを解くための現時点で最 良の探索法

16 オセロを dfpn で解かせてみたら 残り手数 20 手以上の局面では性能がた落 ち オセロでは局面の合流が相当多く、 2 重カ ウント問題の影響が非常に大きいことが わかった！ 何か本質的な対策が必要

17 合流 証明数の 2 重カウント問題 A BC D E F GH AND 節点 OR 節点 原因：証明木に合流が存在すると起こる F+G+H 実際には？ pn(A) = F + 2G + H 証明数が高く見積もられてしまって いる 簡単な問題を難しいと勘違い！

18 2 重カウントへの対応 長井の 2 重カウント対策  合流検知に時間を要する  実装が難しい 経路分枝因数探索 (BNS)(2005, 岡部 )  経路分枝因数を用いた深さ優先の探索法  挙動は証明数探索に似ている  一部の詰将棋問題では df-pn よりも良い結果を収めて いる  合流の影響を受けない（ 2 重カウントが問題とならな い）  探索情報を活かしきれてない為， df-pn よりも探索性 能は劣る

19 証明数の定義 (1) 節点 n が先端節点 (a) 未解決 pn = 1 (b) 勝ち pn = 0 (c) 負け pn = ∞ (2) 節点 n が内部節点 (a)n が OR 節点 pn = 子節点の pn の最小値 (b)n が AND 節点 pn = 子節点の pn の和 pn ：証明数 bn ：経路分枝因 数 bn = 1 bn = 0 bn = ∞ bn = 子節点の bn の最小値 bn = 選択した子節点の bn + 非選択の未解決分枝因数 経路分枝因数の定義

20 解探索を行ってみた

21 コアとなる探索法 df-pn を用いた解探索 BNS を用いた解探索 オセロは合流を大量に持つ ため探索に影響を受ける 探索性能が低いため問題を 解くのに異常に時間がかか る 探索法をどうにかしないといけな い！

22 新しい探索法の提案

23 新しい探索手法の提案 Weak Proof Number Search 証明数探索 ＋ 経路分枝因数探索 探索効率 ＋ 合流の影響な し 両方を持つ df-pn のように探索効率が良く BNS のように合流の影響を受けない

24 既存の探索法と WPN の違い 各探索法 df-pn BNS WPNS AND ノードでの定義 子節点の pn の和 選択した子節点の bn + 非選択の未解決分枝因数 子節点の WPN の最大 + 未解決の指し手の数 実現は容易

25 × ○ 3 1 3 ∞ 4 432 212 OR node AND node A B C D E 局面 A ： 局面 B ： 6 5 df-pn BNS WPNS df-pn の場合 PN(A) = PN(C) + PN(D) + 3 ・・・・・ PN(A)=6 PN(B) = PN(E) + 1 + 2 ・・・・・・・・・ PN(B)=5 BNS ( 選択した局面が C,E の場合 ) BN(A) = BN(C) + 1 + 1 ・・・・・・・・・・ BN(A)=3 BN(B) = BN(E) + 1 + 1 ・・・・・・・・・・ BN(B)=4 WPNS の場合 WPN(A) WPN(B) = WPN(D) + 1 + 1 = WPN(E) + 1 + 1 ・・・・・・ WPN(A)=5 ・・・・・・ WPN(B)=4 挙動の違い（合流がない場 合） こっちの方が簡 単！

26 ○ 333 9 A B OR node AND node 0 0 7 CD E FG 挙動の違い（合流がある場 合） 局面 A ： 局面 B ： 10 15 df-pn の場合 PN(A)= PN(C) + PN(D) + 3 ・・・・・・ PN(A)=17 PN(B) = PN(E) + 3 + 3 ・・・・・・・・・・ PN(B)=15 df-pn BNS( 局面 D,E を選択した場合 ) BN(A)= BN(D) + 1 + 1 ・・・・・・・・・・ BN(A)=9 BN(B) = BN(E) + 1 + 1 ・・・・・・・・・・ BN(B)=11 BNS WPNS の場合 WPN(A) = WPN(C) + 1 + 1 ・・・・・・ WPN(A)=9 WPN(B) = WPN(E) + 1 + 1 ・・・・・・ WPN(B)=11 WPNS × WPNS はどちらでも正解 こっちの方が簡 単！

27 性能評価  オセロ終盤  詰将棋

28 性能評価（オセロ終盤） WPNS vs. df-pn WPNS vs. BNS プロットされた点が y=x より下： WPNS の方が性能が悪い プロットされた点が y=x より上： WPNS の方が性能が良い 探索性能が明らかに向上している

29 性能評価（詰将棋） WPNS vs. df-pn WPNS vs. BNS ‐テストセット‐ 将棋図巧・将棋無双 200 問  11 ～ 611 手の詰将棋問題集

30 性能評価（詰将棋） WPNS vs. df-pnWPNS vs. BNS df-pn よりはやや性能が劣るが BNS よりはやや性能が良い 10 ～ 60 手の問題が中心でオセロほど合流がないのでは？ 手数が多い問題ではどうなる？

31 性能評価（詰将棋） Tacos(WPNS) vs. 市販ソフト 将棋図巧 100 番 「寿」  2 つの作品中で最長手数の 611 手詰み ‐テスト問題‐

32 Tacos vs 市販ソフト 将棋ソフト名 銀星将棋 4 激指 7 Tacos （改良 前） 柿木将棋 8 AI 将棋 14 東大将棋 8 Tacos （ WPNS ） 探索ノード数解いた時間 unsolved 不明 1685848 797438 1 分 20 秒 17.3 秒 10.5 秒 7.2 秒 WPNS を用いただけで探索性能が格 段に向上した

33 オセロ・ソルバの開発・設計

34 メインアルゴリズム  WPNS その他の効率化  ゲーム終盤では αβ 探索を使用  トランスポジションテーブル中の GC の 改良  振動対策 WPNS を用いたオセロ・ソルバ このソルバを用いてオセロの解探索を 行う

35 オセロ読切り 元となる局面は fjt1  27 手の定石（残り 33 手）  オセロの本筋と考えられている定石 自動対戦で何手か進んだ局面を生 成  15 ～ 32 手の問題

36 オセロ読切り結果 WPNSdf-pnBNS 残り手 数 NodesTime(s)NodesTime(s)NodesTime(s) 195417849.881525713.490518614.1 2021428024416.627581028572.3642761541202.1 20154869329.8323015860.1378219467.9 251386541112868.1 解けない 2518740635759040549.1 263373868227533.1 32 2^64 以上 1 ヶ月半 他の探索法では不可能だった 32 手読みに成 功 問題 1 2 3 4 5 6 7 19 ～ 26 手：打切り条件として探索時間が 24 時間を越えたら解けないと する 32 手：打切り条件なし

37 結論 提案手法による好結果を得た  オセロでは◎  合流に対して有力 提案手法の可能性  詰将棋でも ○ 題材に依存しない オセロの解探索  WPNS オセロ・ソルバは唯一 32 手読みに成功

38 まとめ WPNS の提案 WPNS を用いたオセロ･ソルバの開発・設計  多くの問題で効率が良い  他の探索法では不可能だった 32 手読みに成功 結論  提案手法は合流に対して有力 df-pn BNS WPNS 基本性能 ○ △ ○ 合流に対して × ○

39 Future work 探索法の改良  オセロの特性（決まった手数で終了）に合う もっと良い探索法があるのでは？  強いオセロプログラムとの合体 並列化の研究  証明数系探索の並列化方法  grid computing 60 手読み切るまで道のりは長い