囲碁プログラミングの探索における小目標間の依存関係解決に向けて

Presentation on theme: "囲碁プログラミングの探索における小目標間の依存関係解決に向けて"— Presentation transcript:

1 囲碁プログラミングの探索における小目標間の依存関係解決に向けて
美添 一樹 東京大学大学院情報理学系研究科 コンピュータ科学専攻 今井研究室

2 囲碁のルール 黒、白交互に交点に石を置いていく 最終的に「地」が大きいほうが勝ち 19x19の盤が普通
「地」とは一方の色の石だけで囲われた範囲のこと

3 囲碁のルール : 囲んだら取れる ▲のところに黒が打つと、白石を取れる 空点が無くなると取られる つながっている石は一蓮托生になっている
空点のことを、「呼吸点」「ダメ」などと言う つながっている石は一蓮托生になっている 取られるときはまとめて取られる つながっている石の集合を「連」という

4 囲碁のルール : 着手禁止点と例外 Aに打つと反則 そのまま取られる場所には打てない Bには打って良い 打った瞬間に黒石を取れるから

5 囲碁のルール : コウ 右図の形になったら、簡単に無限反復が生じる コウがあるせいで囲碁のプログラムは難しい・・・
取られてもすぐに取り返してはいけない 取り返すと反則 コウがあるせいで囲碁のプログラムは難しい・・・

6 生き、死に、という概念 着手禁止点が二つある石は、絶対に取られる事はない 二眼あると「生き」 絶対に取られない石を「生きている」と言う
着手禁止点のことを「眼」と言う 二眼あると「生き」

7 実戦例 「手談対局V」と私が9路盤で打った例 これは終局図 ちなみに引き分け 手加減したからです

8 研究の背景 : ゲームプレイング プログラム/コンピュータの強さ
チェッカー : CHINOOK (Jonathan Shaeffer) 1992, 1994にTinsleyと対戦 リバーシ : Logistello (Michael Buro) 1996に世界チャンピオン村上に勝利 チェス : Deep Blue 1997にKasparovに勝利 中国将棋 チェスと将棋の中間の強さらしい 将棋 :激指、 YSS 、IS将棋、… アマ五段クラス 角落ちでプロ(勝又五段)に勝利 アマ竜王戦ベスト16 (激指) しかし囲碁は・・・

9 囲碁プログラムの強さ 現在世界最強の囲碁プログラムはおそらく3級程度の強さ 現在最高の死活判定プログラムは非常に強い 大きなギャップ
速度と正確性は人間をはるかに上回る 「開いた」問題は解けない GoTools [Wolf] df-pn based life and death solver [岸本 and Muller] 大きなギャップ

10 囲碁プログラムの難しさ チェスなどでの成功 しかし囲碁では、・・・
評価関数 + 探索 しかし囲碁では、・・・ 早く正確な評価関数は存在しないし、今後も作れない(と思う) 多くのプログラムでは小目標(sub-goal, partial goal, local goal,…)ごとのサーチが用いられている 小目標 : 明確に定義された評価関数がある目標 石取り、連絡切断、死活、・・・

11 小目標ごとのサーチの問題点 各小目標の間の依存関係 既存の手法 端的に言えば、二つ以上の目標を同時に狙った手の発見が難しい
「両利き」の発見 既存の手法 石取り、死活に関する点をある程度記憶して置く GnuGo、Goemate(商品名「手談対局」) 複雑な候補手生成と評価関数で対応 Haruka(商品名「最高峰」)

12 「利き」を利用した依存関係の検出 「利き」の定義
利き : loserの手で、winnerが1回パスをするとloserとwinnerが入れ替わる手 上の図の×の点 利きのorderというものを定義することもできる 下の図の×の点はorder 2の利きと言える

13 Related Work “Search for Transitive Connections”
連Aと連Bは連結 (CN_AB) 連Bと連Cも連結 (CN_BC) では連Aと連Cは？ [Cazenave, Helmstetter 2004]

14 Related Work : “Trace” Introduced in [Cazenave and Helmstetter 2004]
小目標は、連絡切断に限られる “Trace”の定義は、探索アルゴリズムに依存する “the trace is a set of empty intersections such that if none is modified, the result of the search associated to the trace is not modified.” (from “Search for transitive connections”)

15 “Trace”の特徴 定義は探索アルゴリズムに依存する 比較的大きくなりにくい 現状、連絡切断以外には使われていない
GTS (Generalized Threats Search)が用いられている [Cazenave and Helmstetter 2004] 比較的大きくなりにくい 連絡切断の判定の性質 GTSは枝狩りと打ち切りの双方に有効 現状、連絡切断以外には使われていない

16 Related Work : Relevancy Zone (1/2)
Introduced in “Lambda-Search” [Thomsen 2000] 目指すところは “Trace” と同じ 真のR-Zone を発見するのは困難 R*-Zone というものが提案されている R*-Zoneの定義 “shadow stones” “surrounding stones” のダメ(呼吸点)の数

17 Related Work : Relevancy Zone (2/2)
[Ramon & Croonenborghs 2004] R*-Zoneを用いて、複数の小目標を組み合わせた目標を探索 NOT, AND, ORによる2つの小目標の組合せ 小目標は連絡切断、石取り、生き(眼持ち)

18 R*-Zoneの定義(概要) (1/2) [Thomsen 2000]から引用した盤面

19 R*-Zoneの定義(概要) (2/2) shadow stonesおよびそれに隣接する点 surrounding stonesのダメの一部

20 R*-Zoneの問題点 (1/2) 100%安全ではない この点は「利いて」いる(シチョウアタリになっている) どうやって発見するか?
Quasi-surrounding stones この白の連は、黒の連をshadow stones経由で囲んでいると言える

21 R*-Zoneの問題点 (2/2) “quasi-surrounding stones”のダメ(呼吸点)
shadow stone経由で間接的に相手の連を囲っている しかしshadow stoneは一意に定まるわけではない

22 「利き」を探索する動機 (1/2) “Trace”は連絡切断にしか使われていない R*-Zoneは100%ではない
1パターンのshadow stoneを使うだけでは基本的に安全でない 現状では、複数の目的を同時に考慮したサーチの正解率は低い 問題の種類によるが、正解率は50%~80% [Ramon and Croonenborghs 2004] より良いアイデアが必要

23 「利き」を探索する動機 (2/2) 特に「両利き」を発見するには、「利き」の範囲を厳密に知ることが重要
理想的には可能な全ての場合についてshadow stoneを発見すればよい 白が1に打つ(実は利いていない) 黒はどこか他のところに打てる 白が逃げようとしても ゲタでとられる

24 利きの求め方 : Alpha-Betaでとりあえずやってみた
まず普通にサーチしてwinnerとloserを求める winnerの他の勝ち方を求める(他の shadow stonesを求める) 囲碁ではパスは合法なのでnull movesは自動的にサーチされる サーチしたツリーから「利き」の情報を収集する

25 Step 1,2 まず普通に探索をする 枝狩りを限定したAlpha-Beta探索を実行 df-pnによる石取り探索を実装した
全てのshadow stoneを発見するため まず対象とした問題 白石の逃げ出しを可能にする「利き」の範囲を求める

26 Step 3 探索木から「利き」の情報を収集する 「利き」の候補手の情報はルートノードでは知られていないので、深いノードからも情報を収集する

27 Get Union of the inverting threat
lose Get Union of the inverting threat inverting threat lose lose lose OR nodeでのアルゴリズムの動作 winnerがパスすることによって結果が反転する場合、その直前の手が「利き」 子ノードから伝播してきた「利き」の和集合を取る pass lose win win OR node AND node

28 AND nodeでのアルゴリズムの動作 「最小の利き」を求める 子ノードから伝播してきた「利き」の共通部分を取る OR node
lose Take intersection of the inverting threat lose lose lose ? AND nodeでのアルゴリズムの動作 「最小の利き」を求める 子ノードから伝播してきた「利き」の共通部分を取る set of inverting threat lose lose pass lose win OR node AND node

29 結果 正しい「利き」を発見した 可能な全てのR*-Zone の共通部分と同じ 探索したノード数は2,000,000+ ほぼmini-max

30 Future Work Brute Force + Simulation (1/2)
期待していること 単一の目標に対しては、高速なアルゴリズムが知られている df-pn [Nagai 2002] Lambda Search [Thomsen 2000] Generalized Threats Search [Cazenave 2002] 典型的なシチョウやゲタでは探索ノード数は数十～数百ノード

31 Future Work Brute Force + Simulation (2/2)
1つ shadow stoneを見つける shadow stoneの要素の1つ1つについてそれが「利き」かどうか探索する それぞれについて石を打ってみて、普通に探索 それだけだと点の数に比例した時間がかかるので、simulation [Kawano 1996]により時間を短縮 再帰的に「利き」の範囲を限定していく

32 Open Problem :より間接的な 「利き」の発見(よりorderの高い利き)
1手で利く範囲を発見するだけでは不十分 この例では、×の付いた点は1手では利きではない 2手打たれて初めて利きとなる

33 結論 特に両利きの手を発見するためには、真の「利き」の範囲を発見することが重要 一応、「利き」を発見するアルゴリズムを作成した
そのためには、「最小の利き」を発見する能力が必要 一応、「利き」を発見するアルゴリズムを作成した このままではmini-maxに近い時間がかかる 性能向上のためのアルゴリズムを提案 2手以上打たれて初めて「利き」となる問題についてはアイデア募集中

34 おわり