高性能な詰碁ソルバーの 探索技術について 岸本 章宏 公立はこだて未来大学システム情報科学部 情報アーキテクチャ学科 共同研究者: Martin Mueller Department of Computing Science, University of Alberta,

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

コンピュータ囲碁における Root 並列化について 発表者 副島 佑介. 目次 研究背景 – 囲碁の難しさ – モンテカルロ木探索について – 並列化手法の先行研究 提案手法 – Root 並列化における合議制 実験結果 まとめ.
©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
オセロ求解へ向けた取 り組み 橋本剛 上田徹 橋本隼一 北陸先端科学技術大学院大学 情報科学研究科.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
5路盤の完全解析の結果 論文名:Solving Go on Small Boards 著者: Eric C.D. van der Werf
囲碁プログラミングの探索における小目標間の依存関係解決に向けて
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
コンピュータ囲碁の仕組み ~ 将棋との違い ~
    有限幾何学        第8回.
四路の碁アプリ開発 情報論理工学研究所 高倉秀斗.
On the Enumeration of Colored Trees
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
人 工 知 能 第3回 探索法 (教科書21ページ~30ページ)
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ  大石 貴弘.
多数の遊休PC上での 分散ゲーム木探索 導入 ゲーム木探索 ⇒遊休PCを利用して高速化 例)コンピュータ将棋における次手の計算
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
モンテカルロ法と囲碁・将棋ソフトの人知超え
9.NP完全問題とNP困難問題.
データ構造と アルゴリズム 知能情報学部 新田直也.
単位 おねだり ☆オセロ おねだり隊☆D班.
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
京都大学 ○太田圭亮 川原純 伊藤大雄 堀山貴史
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
プログラム実行履歴を用いたトランザクションファンクション抽出手法
シミュレーション論 Ⅱ 第15回 まとめ.
協調機械システム論 ( ,本郷) 協調機械システム論 東京大学 人工物工学研究センター 淺間 一.
計算機実験の計画 References 研究目的 囲碁・将棋での強化学習 高信頼性人工知能システムへの展望 大規模な強化学習技術の実証と応用
シャノンのスイッチングゲームにおけるペアリング戦略について
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
佐藤のゲーム とその仲間たち (完全可解ゲームの話) 関西学院大学  川中 宣明 数理科学研究センター談話会    2011年6月29日.
人工知能特論 9.パーセプトロン 北陸先端科学技術大学院大学 鶴岡 慶雅.
7.4 Two General Settings D3 杉原堅也.
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
第3回 アルゴリズムと計算量 2019/2/24.
早わかりアントコロニー最適化 (Ant Colony Optimization)
東京工業大学 情報理工学研究科 数理・計算科学専攻 千葉研究室 栗田 亮
数独の解生成と 解に対する番号付け 理学部 情報科学科 渡辺研究室 戸神星也.
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
電機情報工学専門実験 6. 強化学習シミュレーション
モンテカルロ法を用いた 立体四目並べの対戦プログラム
研究背景と目的 局面対による学習の高速化 学習器の説明 今後 大規模な強化学習技術の実証と応用 一方で、 強化学習手法の台頭
Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化
マイグレーションを支援する分散集合オブジェクト
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
第16章 動的計画法 アルゴリズムイントロダクション.
ISO23950による分散検索の課題と その解決案に関する検討
5.チューリングマシンと計算.
飛び駒を考慮した逆算法に基づく詰将棋問題の列挙
飛び駒を考慮した逆算法に基づく詰将棋問題の列挙
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
数値解析Ⅱ ~五目並べのプログラミング~ C班.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
第28回世界コンピュータ将棋選手権アピール文章 作成:井本 康宏 作成日:2018/3/吉日
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).
情報論理工学 研究室 第1回:並列とは.
参考:大きい要素の処理.
MPIを用いた 並列処理 情報論理工学研究室 06‐1‐037‐0246 杉所 拓也.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

高性能な詰碁ソルバーの 探索技術について 岸本 章宏 公立はこだて未来大学システム情報科学部 情報アーキテクチャ学科 共同研究者: Martin Mueller Department of Computing Science, University of Alberta, Canada

発表概要 研究背景 関連研究 詰碁ソルバー: TsumeGo Explorer 実験結果 – GoTools との性能比較 まとめと今後の課題

ゲームと人工知能研究 なぜゲームなのか ? – 探索アルゴリズムにとって理想的な題材 簡単なルールと結果 膨大な探索空間 リアルタイムに応答する必要性 – 多くのアプリケーションが存在 シークエンスアラインメント問題 定理証明など – 研究者への明確な動機付け 世界チャンピオンに勝てるようなプログラムの作成

コンピュータ囲碁研究の意義 チェスでの Deep Blue の Kasparov への勝 利 – 探索ベースのアプローチ より難しいゲームへ 次のターゲットは囲碁 – 大きな探索空間 チェス 囲碁 – 局面の評価の難しさ チェス 駒の損得 囲碁 ???

囲碁のルール 白黒が交互にプレイ 空点に石を打つ手か パスが合法 石を取ることが可能 自殺手は禁止 地の大きな方が勝ち 例

コンピュータ囲碁の現状 強さ – 中級者が最強のプログラムに簡単に勝てる レベル 足りないものは ? – よい評価関数 – 効率のよい探索アルゴリズム 囲碁は難しいので「賢い」探索アルゴリ ズムが必要

コンピュータ囲碁における 詰碁(死活)問題 囲碁はやはり探索するのが困難 囲碁の部分問題に着目 – 詰碁は探索アルゴリズムにとって理想的な部分問 題 強い囲碁プログラムの重要な要素の一つである 現状では常に正しい結果を保証するには探索し かない

詰碁問題とは? 攻め方は△のついた石 をすべて取る 受け方は活きようと する – 例: 二眼、セキ 着手は領域内に制限 例

AND/OR 木と詰碁の関係 AND/OR 木探索アルゴリズムを用いて 詰碁を解くことが可能 – 先手は勝ちに至る少なくとも一つの 着手を見つければよい ( OR 節 点) – 後手は全ての着手が負けに至ること を示せばよい ( AND 節点)

AND/OR 木の定義 (1 / 2) OR 節点と AND 節点 – OR(AND) 節点の子節点は AND(OR) 節点 各節点は3つの値の可能性 – 勝ち : OR の勝ち – 負け : AND の勝ち – 不明 : 今のところ分からない 終端節点:子節点のない節点 – 勝ちか負けの値 先端節点:未展開の節点 内部節点:子節点を持つ節点 ルート節点:開始節点 (OR 節点 ) A B C D EF ルート節 点 不明 先端節点 終端節点 勝ち負け 内部 節点 OR 節点 AND 節点

AND/OR 木の定義 (2 / 2) OR(AND) 節点の値の決定 – 1つ以上の子節点が勝ち (負け)ならば勝ち ( 負け ) – 全ての子節点が負け ( 勝ち ) ならば負け(勝ち) – それ以外は不明 ルート節点が勝ちか負け になるまで木を展開 例 A BC DEFG HIJKLM 不明 勝ち 負け 不明 負 勝 勝 負勝 勝 OR 節点 AND 節点

探索効率向上技術の重要性 探索空間 O(b d ) – b: 分岐因子 – d: 深さ 証明木 : O(b d/2 ) – 節点が勝ちであることを 証明する木 トレードオフ:探索速度 を落とさずに探索節点 数を減らしたい 例 OR 節点 AND 節点 A BC DEFG HIJKLM 不明勝ち 負け勝ち 不明負 負 勝 勝 勝 勝 証明木

探索効率向上へのアプローチ ゲーム非依存の性質を用いる – AND/OR 木探索一般に応用可能 ゲーム依存の知識を用いる – そのゲームにのみ利用可能 高性能なソルバーは両方を用いるのが通常

性能向上手法の例 (1 / 2) トランスポジションテーブル DAG の性質を利用 前の探索結果をハッ シュに保存 ゲーム非依存の方法 例 A ハッシュ表 B C D OR 節点 AND 節点 A 勝ち D B C 1 回の探索で OK 勝ち

性能向上手法の例 (2 / 2) 評価関数による節点の並べ替え 評価関数 – 局面を「評価」し、点数化 – ゲーム依存の知識 ある石を捕れるのでプラス 10 点 2つの石がつながっているのでプラス 5 点 … 評価関数による子節点の並べ替え – 探索時にすべての子節点を評価 – 評価値のよい子節点から探索 – この枠組み自体はゲーム非依存

以前の詰碁ソルバーの研究 GoTools [Wolf:2000] – 石の生死を判定する強力なルール – 何年にもわたって書かれた囲碁の知識 着手の並べ替え等に利用 – 単純な αβ 法+トランスポジションテーブル – 過去 15 年にわたって最強の詰碁ソルバーとして君 臨 – 14 空点程度の問題しか解けない 「多数」のゲーム「依存」の手法 + 「単純」なゲーム「非依 存」の手法

コンピュータ将棋における研 究 詰将棋ソルバー – 強力な探索アルゴリズム Df-pn アルゴリズム+トランスポジションテーブル [Nagai & Imai:1999] – 様々な将棋の知識 囲碁における知識よりもずっと単純 – プロ棋士を凌駕する解答能力 現存する 100 手詰以上の問題はすべて解答可能 [Nagai:2002] 比較的「少数」のゲーム「依存」の手法 + 「強力」なゲーム 「非依存」の手法

研究成果 詰碁ソルバー TsumeGo Explorer の実装 – 新しい探索アルゴリズム df-pn(r) を利用 Df-pn アルゴリズム [Nagai & Imai:1999] をベースに利用 Graph-History Interaction (GHI) 問題の解決策 [Kishimoto & Mueller:AAAI2004] サイクルに関する証明数・反証数計算の問題の解決 [ Kishimoto and Mueller:ACG2003] df-pn の閾値の調整法 [Kishimoto & Mueller:AAAI2005] – 現状での最強の詰碁ソルバー [ Kishimoto & Mueller:AAAI2005] 比較的「少数」のゲーム「依存」の手法 + 「強力」なゲーム 「非依存」の手法を用いたアプローチ

TsumeGo Explorer の概要 探索エンジン : df-pn(r) ゲーム依存プラグイン – 終端局面の判定 – 着手生成 – 性能向上手法 接続 [Mueller:GPW1997] 強制手順 シミュレーション [Kawano:1996] 評価関数

Df-pn アルゴリズム [Nagai & Imai:1999] 証明数と反証数 [Allis:94] を利用 深さ優先探索 – 証明数と反証数の閾値を持つ トランスポジションテーブルによる効 率化

証明数の定義 節点 n の証明数 pn(n) – n が勝ちであるために展開しなければなら ない先端節点数の下限値 pn(n) = min(pn(c1), …, pn(ck)) (n: 内部 OR 節点, ci: 子節点 ) pn(n) = pn(c1) + … + pn(ck) (n: 内部 AND 節点 ) pn(n)= 1 (n: 先端節点 ) pn(n)= 0 (n が勝ち ) pn(n)=∞ (n が負け ) pn OR 節点 pn AND 節点

反証数の定義 節点 n の証明数 dn(n) – n が負けであるために展開しなければなら ない先端節点数の下限値 dn(n) = dn(c1)+…+ dn(ck) (n: 内部 OR 節点, ci: 子節点 ) dn(n) = min(dn(c1),…,dn(ck)) (n: 内部 AND 節点 ) dn(n)= 1 (n: 先端節点 ) dn(n)= 0 (n が負け ) dn(n)=∞ (n が勝ち ) dn OR 節点 dn AND 節点

Df-pn アルゴリズム (1 / 2) 閾値を用いた深さ優先探索 例 A BC EFD pn(D)=1 dn(D)=1 pn(E)=1 dn(E)=1 pn(F)=1 dn(F)=1 thpn(A)=INF thdn(A)=INF OR 節点 AND 節点 pn(B)=1 dn(B)=1 pn(C)=1 dn(C)=1 pn(A)=1 dn(A)=2 thpn(B)=2 thdn(B)=INF-1 pn(B)=3 dn(B)=1 pn(B)=3>=thpn(B)=2 thpn(C)=4 thdn(C)=INF-1 GH pn(H)=1 dn(H)=1 pn(G)=1 dn(G)=1 pn(C)=2 dn(C)=1 thpn(G)=3 thdn(G)=2 IJ pn(G)=1 dn(G)=2 dn(G)=2>=thdn(G)=2 thpn(H)=3 thdn(H)=3

Df-pn アルゴリズム (2 / 2) 何度も内部節点を展開 トランスポジションテーブルの利用 – 以前に展開した節点を保存 証明数・反証数など – 探索や証明数の計算時に参照 – 内部節点の再展開を減少

Graph-History Interaction (GHI) 問題 [Palay:83] 詰碁の探索空間はサイ クルを含む – 以前の局面に戻る着 手は禁じ手 C.f. SSK ルール トランスポジション テーブルは経路を無視 – 間違えた答えを返す 可能性 例 A D BC A  B  D(  B) 勝ち 勝ち or 負け ? A  C  D  B(  D) 負け OR 節点 AND 節点 D の値は一意に決まらな い

Df-pn(r) における GHI 問題対策 [Kishimoto & Mueller:AAAI2004] トランスポジションテー ブルの各エントリーに局 面 + 経路情報を保持 不明の節点は証明数・反 証数の情報を利用 サイクルがらみの勝ち負 けは勝ち / 負け via path と 保存 サイクルが無関係のとき は「無条件」勝ち / 負けと 保存 例 A D BC D via A  B  D 勝ち D via A  C  D 負け

TsumeGo Explorer の中身 ( 残りの部分 ) 探索エンジン : df-pn(r) ゲーム依存プラグイン – 終端局面の判定 – 着手生成 – 性能向上手法 接続 [Mueller:GPW1997] 強制手 シミュレーション [Kawano:1996] 評価関数

TsumeGo Explorer の ゲーム依存プラグイン 着手生成 – パス+領域内の着手全て – 強制手 終端節点の判定 – 活き形である 例:二眼、セキ 受け方の勝ち – 眼を作るスペースがない 攻め方の勝ち 黒:受け方 白:攻め 方

見合い戦略 [Mueller:GPW97] を 用いた接続 攻め方の接続のみを 考慮 不安定な石を活きた 石と判定可能 受け方の石の死を早 い段階で判定 黒死の例 黒:受け方 白:攻め 方

強制手:安全枝刈り方法 強制手の例

シミュレーション [Kawano:96] 「似た」局面の証明木を高速に構築する方法 勝ちの局面 P1 P2 P3P4 P5P6 似た局面 Q1 Q2 Q3Q4 Q5Q6 OR 節点 AND 節点

シミュレーションの詰碁への 適用 P1 P2 A4 P5 Df-pn(r) P3P4 Simulation A4 Df-pn(r) 勝ち

評価関数を利用した 証明数・反証数の初期化 (1 / 2) Df-pn ベースの方法の 問題 – 石を捕ることを嫌う – 一時的な証明数・反証 数が大きくなる 証明数・反証数の初 期化のために評価関 数を利用 [Nagai:GPW2001] P1 P2 先端節点 pn(P2) = 1 dn(P2) = 1 pn(P2) = evalPN(P2) dn(P2) = evalDN(P2)

評価関数を利用した 証明数・反証数の初期化 (2 / 2) 二眼を作れる距離の概 算 目を奪う着手の評価値

その他の話題 ( 囲碁プレイヤー向け ) コウの取り扱い – 詰碁問題の結果に影響 TsumeGo Explorer のでコウの取り扱い – 2 回の探索によって対応 1 回目:コウ立てなしとして探索 2 回目:負けたプレイヤーに無限にコウダテが あると仮定して再探索 通常は再探索のオーバーヘッドは少ない

TsumeGo Explorer と GoTools の性能比較 マシン環境 : Athlon XP 制限時間 : 各問 5 分 利用した問題 – Mueller のテスト問題 Mueller によって作成された 148 題 簡単なものから非常に難しいものまで様々な難易度 – Wolf のテスト問題 GoTools にとっての難問 418 題

利用した問題の例 Mueller のテスト問題 ( 白先白活 ) Wolf のテスト問題 ( 白先白活 )

Wolf の問題における性能比較 解けた問題数 実行時間の 合計 ( 秒 ) GoTools 418 1,235 TsumeGo Explorer 合計数 418

Wolf の問題における パフォーマンスグラフ 両方のプログラムで解けた問題のプロッ ト

Mueller の問題における 性能比較 実行時間の 解けた問題の数 合計 ( 秒 ) (119 問 ) GoTools TsumeGo Explorer 合計 148

Mueller のテスト問題における パフォーマンスグラフ 両方のプログラムで解けた問題のプロット

Lessons Learned (1 / 3) GoTools の知識は小サ イズの問題には有効 – GoTools は静的に解答 – TsumeGo Explorer は 3,159 節点で解答 (0.1 秒 ) 白先黒死

Lessons Learned (2 / 3) 黒先黒活 難しい問題ではより 良い探索アルゴリズ ムが必要 – GoTools は 5 分以内に 解答不可能 – TsumeGo Explorer は 0.73 秒 (22,616 節点 ) で 解答

Lessons Learned (3 / 3) 性能向上には強力な探索アルゴリズムと様々 な性能向上のためのアイデアの両方が必要 566 題のテスト問題を用いた場合の性能比較 解けた問題 合計実行時間 展 開節点総数 (566 題中 ) (564 題中 ) (564 題中 ) (1): df-pn(r) 564 6, ,195,987 (2): (1) + 連結 564 3, ,639,307 (3): (2) + 強制手 566 1,480 63,049,713 (4): (3) + シミュレーション 566 1,146 54,265,265 (5): (4) + 評価関数 ,592,360

まとめと今後の課題 まとめ – df-pn ベースのアルゴリズムを詰碁へ応用 – 比較的少ないゲーム依存の知識 – 現在最高性能の詰碁ソルバーの実装に成功 今後の課題 – より大きなサイズの問題への挑戦 22 ~ 27 空点サイズの問題を解くのが限界 C.f. GoTools は 14 空点程度 知識をもっと足す必要あり? – 開いた問題を解けるソルバーの開発 – 実際の囲碁を打つシステムへの利用

最終的に解きたい問題の例 囲碁発陽論 第 1 番 ( 白先白活 )

宣伝:現在進行中のプロジェ クト Akebono プロジェクト – 「日本発」の強いコンピュータ囲碁プログラムの 開発 – 現在のメンバー 岸本章宏 (はこだて未来大学情報アーキテクチャ学科助 手) 金子知適 (東京大学大学院広域科学専攻助手) 美添一樹 ( 東京大学大学院情報理工学系研究科今井研 ) 吉本晴洋 ( 東京大学大学院情報理工学系研究科田浦研 ) – 現在は 9 路盤のみ実装、将来は 19 路盤も – 興味のある方は ま