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

Slides:



Advertisements
Similar presentations
1 プリミティブ Web サービスの 入出力データに関する一考察 2005 年 3 月 21 日 松江工業高等専門学校 情報工学科 奈良先端科学技術大学院大学 情報科学研究科 越田高志 電子情報通信学会 2005年総合 大会.
Advertisements

コンピュータ囲碁における Root 並列化について 発表者 副島 佑介. 目次 研究背景 – 囲碁の難しさ – モンテカルロ木探索について – 並列化手法の先行研究 提案手法 – Root 並列化における合議制 実験結果 まとめ.
2004 年新潟県中越地震と スマトラ沖巨大地震の 震源で何が起こったのか? 八木勇治 (建築研究所・国際地震工学セン ター)
高性能な詰碁ソルバーの 探索技術について 岸本 章宏 公立はこだて未来大学システム情報科学部 情報アーキテクチャ学科 共同研究者: Martin Mueller Department of Computing Science, University of Alberta,
©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
三木 光範 (同志社大学工学部) 廣安 知之 (同志社大学工学部) 花田 良子 (同志社大学工学部学部 生) 水田 伯典 (同志社大学大学院) ジョブショップスケジューリング問 題への 分散遺伝的アルゴリズムの適用 Distributed Genetic Algorithm for Job-shop.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
コンピュータ囲碁の仕組み ~ 将棋との違い ~
    有限幾何学        第8回.
四路の碁アプリ開発 情報論理工学研究所 高倉秀斗.
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
5.チューリングマシンと計算.
5.チューリングマシンと計算.
リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ  前田昂寛.
第8回  問題解決.
人 工 知 能 第3回 探索法 (教科書21ページ~30ページ)
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ  大石 貴弘.
多数の遊休PC上での 分散ゲーム木探索 導入 ゲーム木探索 ⇒遊休PCを利用して高速化 例)コンピュータ将棋における次手の計算
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習
モンテカルロ法と囲碁・将棋ソフトの人知超え
数独パズルの難易度判定 ~解法ロジックを用いた数値化の提案~
単位 おねだり ☆オセロ おねだり隊☆D班.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
京都大学 ○太田圭亮 川原純 伊藤大雄 堀山貴史
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
二分探索木によるサーチ.
型付きアセンブリ言語を用いた安全なカーネル拡張
決定木とランダムフォレスト 和田 俊和.
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
情報論理工学 研究室 第10回 完全解析されたゲーム.
二人零和不完全情報ゲームであるジャンケンにおけるゲームの洗練法
WWW上の効率的な ハブ探索法の提案と実装
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
逆算法に基づく 詰将棋の列挙 堀山貴史 中塚裕之 岩間一雄 (京都大学) 持駒なし 9手詰め.
適応的近傍を持つ シミュレーテッドアニーリングの性能
モンテカルロ法を用いた 立体四目並べの対戦プログラム
Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
第2回  発見的探索(1).
Data Clustering: A Review
B03 量子論理回路の 最適化に関する研究 西野哲朗,垂井淳,太田和夫,國廣昇 電気通信大学 情報通信工学科.
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
第16章 動的計画法 アルゴリズムイントロダクション.
5.チューリングマシンと計算.
飛び駒を考慮した逆算法に基づく詰将棋問題の列挙
飛び駒を考慮した逆算法に基づく詰将棋問題の列挙
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
半正定値計画問題(SDP)の 工学的応用について
数値解析Ⅱ ~五目並べのプログラミング~ C班.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
分枝カット法に基づいた線形符号の復号法に関する一考察
第28回世界コンピュータ将棋選手権アピール文章 作成:井本 康宏 作成日:2018/3/吉日
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
情報論理工学 研究室 第1回:並列とは.
参考:大きい要素の処理.
C.岩崎雅哉 大須賀佑介 杉原雄太 中野武重 日名啓吾
ベイジアンネットワークと クラスタリング手法を用いたWeb障害検知システムの開発
1 ひとりにしてくれ数 東北大学 大学院情報科学研究科 ◎鈴木 顕 内澤 啓 国立情報学研究所 情報学プリンシプル研究系 宇野 毅明.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

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

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

こちらの分野のホットな話題 コンピュータ将棋: 評価関数の自動学 習(Bonanza Method, 保木 2006 )  プロレベルまであと少し コンピュータ囲碁: モンテカルロ法(+ UCT)が猛威を振るう  9 路盤ではプロに勝った? 19路盤でも有 段者に

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

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

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

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

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

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

証明数を使う探索

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

証明数の定義 節点 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 pn OR 節点 pn AND 節点

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

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

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

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

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

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

証明数の定義 (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 + 非選択の未解決分枝因数 経路分枝因数の定義

解探索を行ってみた

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

新しい探索法の提案

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

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

× ○ ∞ 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) ・・・・・・・・・ PN(B)=5 BNS ( 選択した局面が C,E の場合 ) BN(A) = BN(C) ・・・・・・・・・・ BN(A)=3 BN(B) = BN(E) ・・・・・・・・・・ BN(B)=4 WPNS の場合 WPN(A) WPN(B) = WPN(D) = WPN(E) ・・・・・・ WPN(A)=5 ・・・・・・ WPN(B)=4 挙動の違い(合流がない場 合) こっちの方が簡 単!

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

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

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

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

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

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

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

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

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

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

オセロ読切り結果 WPNSdf-pnBNS 残り手 数 NodesTime(s)NodesTime(s)NodesTime(s) 解けない ^64 以上 1 ヶ月半 他の探索法では不可能だった 32 手読みに成 功 問題 ~ 26 手:打切り条件として探索時間が 24 時間を越えたら解けないと する 32 手:打切り条件なし

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

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

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