オセロ求解へ向けた取 り組み 橋本剛 上田徹 橋本隼一 北陸先端科学技術大学院大学 情報科学研究科 まずは自己紹介 コンピュータ将棋 TACOS の開発をしてます。 趣味： 将棋（自分のプログラムにまったく勝 てなくなった） 学会： 情報処理学会ゲーム情報学研究会、 ＩＣＧＡ（International Computer Games Association） こちらの分野のホットな話題 コンピュータ将棋： 評価関数の自動学習（Ｂ ｏｎａｎｚａ Ｍｅｔｈｏｄ, 保木2006） プロレベルまであと少し コンピュータ囲碁： モンテカルロ法（＋ＵＣＴ） が猛威を振るう 9路盤ではプロに勝った？ に １９路盤でも有段者 昨年の大きな話題： Checkers is solved Checkersが解けた！結論は引き分け．[J. Schaeffer et al, Science, 2007]． 世界中で大きく取り上げられ，Checkerが有名でない日 本でも新聞などが取り上げた． ゲームを解くという事は大きな話題を呼ぶ 大型計算機を数年間回し続けた（新聞では１８年計 算しっぱなしで解いたなどと報道） checkersの次の候補は？ ⇒ オセロ 本日の流れ 研究の目的 関連研究紹介： Checkers is solved 証明数を使う探索 新しい探索法WPNSの提案 オセロ・ソルバの開発・設計 まとめ 研究の目的 オセロはCheckerよりも難しく解くのは困難 オセロが解けたらインパクトは大きい 8×8オセロの読切り ゲームの結論とそれに至る手順を求める オセロを解く事の難しさ checkersの探索空間は5×1020 オセロの探索空間は100000000×1020 6×6のオセロは解かれており、16対20で白勝ち．[Joel Feinstein 1993] ハードウェアの進歩や探索法の洗練によりコン ピュータの探索性能は格段に向上 容易に解く事は出来ないが， 決して夢物語ではない チェッカーのルール ・駒は常に斜めに動く ・獲る事が可能な駒は必ず獲らなければならない。複数の獲り方がある場合は任意に選 択してよい。 ・相手の駒を穫った後もう一度穫ることが可能ならば、そのまま連続してもう一駒穫る ・一番奥の列に駒を進めることによって、「成る」ことができる。成った駒は「キング」と呼ば れ、以後斜め後ろを合わせた4方向に進むことができるようになる ・以下のふたつの状況で勝敗が決定する。 ・相手の駒が全滅した場合、全滅させた側の勝利となる ・次に動かせる駒がなくなった場合、動かせなくなった側が敗北となる Checkers is solved: アルゴリズム構成 Seeding Proof tree manager Proof number search Proof solver 文献などから得る「Best Play」 の手順を入れる αβ探索→dfpn探索 Endgame database 駒残り10個以下の局面は すべて登録 オセロにも使える？ 証明数を使う探索 証明数を使う探索 証明木 探索空間 O(bd) 例 A 勝 分岐因子 d: 深さ b: 負 証明木: O(bd/2) 節点が勝ちであることを 証明する木 証明木になりそうなノード を効率よく探索する方 法は？ H ⇒ 証明数探索 OR節点 証明木 不明 AND節点 勝 B 不明 D I 負け C 負 E J 勝 勝 G F K L M 勝ち 勝ち 勝ち 勝ち 証明数の定義 節点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の和 pn 2 2 1 1 ∞ 0 ∞ OR節点 pn AND節点 2 証明数を使って探索 証明数を使って効率よく探索するには？ ⇒ 証明数が最小のノードを常に展開すればい い ⇒ 最良優先探索が簡単 ややこしいノードは後回し、証明数の少ない 簡単そうなノードを先に探索 手数が長くても応手数が少ない問題は特に 強い 最適解は保障しない PN-searchとその進化 証明数を閾値として探索を行う。証明数の少ない簡 単そうなノードを優先して展開するので、解に到達し やすい。 反証数も同時に閾値として扱う 最良優先探索→PN-search [Allis,1994] メモリの問題があり、難しい問題は解けない 詰め将棋の世界で深さ優先探索として発展、 PN*： 証明数だけ、ミクロコスモスを初めて解く[Seo:1997] 参考 ミクロコスモス http://www.geocities.jp/k_7ro/o18.html df-pn： 長手数詰め将棋問題をすべて解くことに成功 [Nagai:1999] df-pn (depth first proof number search) 反証数も使いPN-searchと等価 [Nagai:1999] 300手以上の詰将棋問題を全て解く checkersが解かれた際の探索にも用いられる 詰碁でも優れた成果を挙げる 二人零和完全情報ゲームを解くための現時点で最良 の探索法 オセロをdfpnで解かせてみたら 残り手数20手以上の局面では性能がた落ち オセロでは局面の合流が相当多く、2重カウ ント問題の影響が非常に大きいことがわかっ た！ 何か本質的な対策が必要 証明数の2重カウント問題 原因：証明木に合流が存在すると起こる AND節点 A OR節点 B F+G+H C 実際には？ D F 合流 E G H pn(A) = F + 2G + H 証明数が高く見積もられてしまっている 簡単な問題を難しいと勘違い！ 2重カウントへの対応 長井の2重カウント対策 合流検知に時間を要する 実装が難しい 経路分枝因数探索(BNS)(2005, 岡部) 経路分枝因数を用いた深さ優先の探索法 挙動は証明数探索に似ている 一部の詰将棋問題ではdf-pnよりも良い結果を収めてい る 合流の影響を受けない（2重カウントが問題とならない） 探索情報を活かしきれてない為，df-pnよりも探索性能は 劣る 証明数の定義 経路分枝因数の定義 bn：経路分枝因数 pn：証明数 (1)節点nが先端節点 (a)未解決 pn bn = 1 (b)勝ち bn = 0 pn (c)負け bn = ∞ pn (2)節点nが内部節点 (a)nがOR節点 bn = 子節点のpnの最小値 子節点のbnの最小値 pn (b)nがAND節点 bn =選択した子節点のbn + 非選択の未解決分枝因数 pn = 子節点のpnの和 解探索を行ってみた コアとなる探索法 df-pnを用いた解探索 オセロは合流を大量に持つた め探索に影響を受ける BNSを用いた解探索 探索性能が低いため問題を 解くのに異常に時間がかかる 探索法をどうにかしないといけない！ 新しい探索法の提案 新しい探索手法の提案 Weak Proof Number Search 証明数探索 ＋ 経路分枝因数探索 探索効率 ＋ 合流の影響なし 両方を持つ df-pnのように探索効率が良く BNSのように合流の影響を受けない 既存の探索法とWPNの違い 各探索法 ANDノードでの定義 df-pn 子節点のpnの和 BNS 選択した子節点のbn +非選択の未解決分枝因数 WPNS 子節点のWPNの最大 + 未解決の指し手の数 実現は容易 挙動の違い（合流がない場合） df-pnの場合 BNS = PN(C) + PN(D) + 3 ・・・・・PN(A)=6 PN(A)(選択した局面がC,Eの場合) BN(A) BN(C) + + 11 + + 21・・・・・・・・・・BN(A)=3 PN(B) = PN(E) ・・・・・・・・・PN(B)=5 WPNSの場合 BN(B) = BN(E) + 1 + 1・・・・・・・・・・BN(B)=4 WPN(A) = WPN(D) + 1 + 1・・・・・・WPN(A)=5 WPN(B) = WPN(E) + 1 + 1・・・・・・WPN(B)=4 ○ df-pn × BNS 局面A：6 B 2 C 1 A 3 3 OR node D ∞ 1 4 局面B：5 WPNS 2 4 AND node E こっちの方が簡単！ 3 2 挙動の違い（合流がある場合） df-pnの場合 BNS(局面D,Eを選択した場合) WPNSの場合 BN(A) BN(D) ++ PN(D) 1 + 1 ・・・・・・・・・・BN(A)=9 PN(A) = PN(C) + 3 ・・・・・・PN(A)=17 WPN(A) = WPN(C) + 1 + 1・・・・・・WPN(A)=9 BN(B) PN(E) ++ 31 ++ 31 ・・・・・・・・・・BN(B)=11 BN(E) PN(B) = = WPN(B) WPN(E) + 1 +・・・・・・・・・・PN(B)=15 1・・・・・・WPN(B)=11 WPNSはどちらでも正解 df-pn ○ BNS 局面A：10 WPNS C D F G こっちの方が簡単！ 0 A 7 B 3 E 9 0 3 × 局面B： 15 3 OR node AND node 性能評価 オセロ終盤 詰将棋 性能評価（オセロ終盤） プロットされた点がy=xより下：WPNSの方が性能が悪い プロットされた点がy=xより上：WPNSの方が性能が良い Search nodes(WPNS vs BNS) 5.0E+06 2.5E+06 4.0E+06 2.0E+06 BNS(search node) df-pn(search node) Search nodes(WPNS vs df-pn) 3.0E+06 2.0E+06 1.5E+06 1.0E+06 1.0E+06 5.0E+05 0.0E+00 0.0E+00 0.0E+00 0.0E+00 1.0E+06 2.0E+06 3.0E+06 WPNS(search node) WPNS vs. df-pn 4.0E+06 5.0E+06 5.0E+05 1.0E+06 1.5E+06 WPNS(search node) WPNS vs. BNS 探索性能が明らかに向上している 2.0E+06 2.5E+06 性能評価（詰将棋） WPNS vs. df-pn WPNS vs. BNS ‐テストセット‐ 将棋図巧・将棋無双 200問 11～611手の詰将棋問題集 性能評価（詰将棋） Search nodes(WPNS vs BNS) Search nodes(WPNS vs df-pn) 4.0E+06 3.0E+06 3.0E+06 BNS(search node) df-pn(search node) 4.0E+06 2.0E+06 1.0E+06 0.0E+00 0.0E+00 2.0E+06 1.0E+06 1.0E+06 2.0E+06 3.0E+06 WPNS(search node) WPNS vs. df-pn 4.0E+06 0.0E+00 0.0E+00 1.0E+06 2.0E+06 3.0E+06 4.0E+06 WPNS(search node) WPNS vs. BNS •df-pnよりはやや性能が劣るがBNSよりはやや性能が良い 10～60手の問題が中心でオセロほど合流がないのでは？ 手数が多い問題ではどうなる？ 性能評価（詰将棋） Tacos(WPNS) vs. 市販ソフト ‐テスト問題‐ 将棋図巧 100番 「寿」 2つの作品中で最長手数の611手詰み Tacos vs 市販ソフト 将棋ソフト名 探索ノード数 解いた時間 銀星将棋4 unsolved 激指7 unsolved Tacos（改良前） unsolved 柿木将棋8 不明 1分20秒 AI将棋14 不明 17.3秒 東大将棋8 1685848 10.5秒 Tacos（WPNS） 797438 7.2秒 WPNSを用いただけで探索性能が格 段に向上した オセロ・ソルバの開発・設計 WPNSを用いたオセロ・ソルバ メインアルゴリズム WPNS その他の効率化 ゲーム終盤ではαβ探索を使用 トランスポジションテーブル中のGCの改良 振動対策 このソルバを用いてオセロの解探索を行う オセロ読切り 元となる局面はfjt1 27手の定石（残り33手） オセロの本筋と考えられている定石 自動対戦で何手か進んだ局面を生成 15～32手の問題 オセロ読切り結果 WPNS 問題 残り手数 Nodes df-pn Time(s) 1 19 541784 2 20 21428024 3 20 1548693 29.8 4 25 138654111 2868.1 5 25 187406357590 40549.1 6 26 7 32 337386822 2^64以上 9.8 Nodes 815257 416.6 27581028 7533.1 3230158 BNS Time(s) 13.4 Nodes Time(s) 905186 14.1 572.3 64276154 1202.1 60.1 3782194 67.9 解けない 1ヶ月半 19～26手：打切り条件として探索時間が24時間を越えたら解けないとする 32手：打切り条件なし 他の探索法では不可能だった32手読みに成功 結論 提案手法による好結果を得た オセロでは◎ 合流に対して有力 提案手法の可能性 詰将棋でも○ 題材に依存しない オセロの解探索 WPNSオセロ・ソルバは唯一32手読みに成功 まとめ WPNSの提案 df-pn BNS WPNS 基本性能 ○ △ ○ 合流に対して × ○ ○ WPNSを用いたオセロ･ソルバの開発・設計 多くの問題で効率が良い 他の探索法では不可能だった32手読みに成功 結論 提案手法は合流に対して有力 Future work 探索法の改良 オセロの特性（決まった手数で終了）に合うもっと 良い探索法があるのでは？ 強いオセロプログラムとの合体 並列化の研究 証明数系探索の並列化方法 grid computing 60手読み切るまで道のりは長い
© Copyright 2024 ExpyDoc
