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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18 研究成果 詰碁ソルバー 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] 比較的「少数」のゲーム「依存」の手法 + 「強力」なゲーム 「非依存」の手法を用いたアプローチ

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

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

21 証明数の定義 節点 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 が負け ) 3 2 2 11111 pn OR 節点 pn AND 節点

22 反証数の定義 節点 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 節点 2 2 11111 3

23 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

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

25 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 の値は一意に決まらな い

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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