Document

囲碁プログラミングの探索
における小目標間の依存
関係解決に向けて
美添一樹
東京大学大学院情報理学系研究科
コンピュータ科学専攻
今井研究室
囲碁のルール
黒、白交互に交点に石を置いていく

19x19の盤が普通
最終的に「地」が大きいほうが勝ち

「地」とは一方の色の石だけで囲われた範囲のこ
と
囲碁のルール : 囲んだら取れる
▲のところに黒が打つ
と、白石を取れる

空点が無くなると取ら
れる
空点のことを、「呼吸
点」「ダメ」などと言う

つながっている石は一
蓮托生になっている
取られるときはまとめて
取られる
つながっている石の集
合を「連」という
囲碁のルール : 着手禁止点と例
外
Aに打つと反則

そのまま取られる場
所には打てない
Bには打って良い

打った瞬間に黒石
を取れるから
囲碁のルール : コウ
右図の形になったら、簡単
に無限反復が生じる


取られてもすぐに取り返して
はいけない
取り返すと反則
コウがあるせいで囲碁のプ
ログラムは難しい・・・
生き、死に、という概念
着手禁止点が二つある石は、
絶対に取られる事はない


絶対に取られない石を「生きてい
る」と言う
着手禁止点のことを「眼」と言う
二眼あると「生き」
実戦例
「手談対局V」と私が9
路盤で打った例



これは終局図
ちなみに引き分け
手加減したからです
研究の背景 : ゲームプレイング
プログラム/コンピュータの強さ
チェッカー : CHINOOK (Jonathan Shaeffer)

1992, 1994にTinsleyと対戦
リバーシ : Logistello (Michael Buro)

1996に世界チャンピオン村上に勝利
チェス : Deep Blue

1997にKasparovに勝利
中国将棋

チェスと将棋の中間の強さらしい
将棋 :激指、 YSS 、IS将棋、…


アマ五段クラス角落ちでプロ(勝又五段)に勝利
アマ竜王戦ベスト16 (激指)
しかし囲碁は・・・
囲碁プログラムの強さ
現在世界最強の囲碁プログラムはおそらく3級程度
の強さ
大きなギャップ
現在最高の死活判定プログラムは非常に強い


速度と正確性は人間をはるかに上回る
「開いた」問題は解けない
GoTools [Wolf]
df-pn based life and death solver [岸本 and Muller]
囲碁プログラムの難しさ
チェスなどでの成功

評価関数 + 探索
しかし囲碁では、・・・

早く正確な評価関数は存在しないし、今後も作れない(と
思う)
多くのプログラムでは小目標(sub-goal, partial goal,
local goal,…)ごとのサーチが用いられている

小目標 : 明確に定義された評価関数がある目標
石取り、連絡切断、死活、・・・
小目標ごとのサーチの問題点
各小目標の間の依存関係

端的に言えば、二つ以上の目標を
同時に狙った手の発見が難しい
「両利き」の発見
既存の手法


石取り、死活に関する点をある程
度記憶して置く
GnuGo、Goemate(商品名「手
談対局」)
複雑な候補手生成と評価関数で
対応
Haruka(商品名「最高峰」)
「利き」を利用した依存関係の検出
「利き」の定義

利き : loserの手で、winnerが1回
パスをするとloserとwinnerが入れ
替わる手
上の図の×の点

利きのorderというものを定義する
こともできる
下の図の×の点はorder 2の利きと
言える
Related Work
“Search for Transitive Connections”
連Aと連Bは連結 (CN_AB)
連Bと連Cも連結 (CN_BC)
では連Aと連Cは？
[Cazenave, Helmstetter 2004]
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”)
“Trace”の特徴
定義は探索アルゴリズムに依存する

GTS (Generalized Threats Search)が用いられ
ている [Cazenave and Helmstetter 2004]
比較的大きくなりにくい


連絡切断の判定の性質
GTSは枝狩りと打ち切りの双方に有効
現状、連絡切断以外には使われていない
Related Work :
Relevancy Zone (1/2)
Introduced in “Lambda-Search” [Thomsen
2000]
目指すところは “Trace” と同じ
真のR-Zone を発見するのは困難

R*-Zone というものが提案されている
R*-Zoneの定義


“shadow stones”
“surrounding stones” のダメ(呼吸点)の数
Related Work :
Relevancy Zone (2/2)
[Ramon & Croonenborghs 2004]
R*-Zoneを用いて、複数の小目標を組み合わ
せた目標を探索


NOT, AND, ORによる2つの小目標の組合せ
小目標は連絡切断、石取り、生き(眼持ち)
R*-Zoneの定義(概要) (1/2)
[Thomsen 2000]から引用した盤面
R*-Zoneの定義(概要) (2/2)
shadow stonesおよび
それに隣接する点
surrounding stonesのダメ
の一部
R*-Zoneの問題点 (1/2)
100%安全ではない
この点は「利いて」いる(シ
チョウアタリになっている)
どうやって発見するか?
Quasi-surrounding stones
 この白の連は、黒の連を
shadow stones経由で囲んで
いると言える
R*-Zoneの問題点 (2/2)
“quasi-surrounding stones”のダメ(呼吸点)


shadow stone経由で間接的に相手の連を囲っている
しかしshadow stoneは一意に定まるわけではない
「利き」を探索する動機 (1/2)
“Trace”は連絡切断にしか使われていない
R*-Zoneは100%ではない

1パターンのshadow stoneを使うだけでは基本
的に安全でない
現状では、複数の目的を同時に考慮した
サーチの正解率は低い

問題の種類によるが、正解率は50%~80%
[Ramon and Croonenborghs 2004]
より良いアイデアが必要
「利き」を探索する動機 (2/2)
特に「両利き」を発見するには、「利き」の範囲
を厳密に知ることが重要

理想的には可能な全ての場合についてshadow
stoneを発見すればよい
1. 白が1に打つ(実は利いていない)
2. 黒はどこか他のところに打てる
3. 白が逃げようとしても
4. ゲタでとられる
利きの求め方 :
Alpha-Betaでとりあえずやってみた
1. まず普通にサーチしてwinnerとloserを求め
る
2. winnerの他の勝ち方を求める(他の
shadow stonesを求める)

囲碁ではパスは合法なのでnull movesは自動
的にサーチされる
3. サーチしたツリーから「利き」の情報を収集
する
Step 1,2
まず普通に探索をする

df-pnによる石取り探索を実装した
枝狩りを限定したAlpha-Beta探索を実行

全てのshadow stoneを発見するため
まず対象とした問題
白石の逃げ出しを可能にする
「利き」の範囲を求める
Step 3
探索木から「利き」の情報を収集する

「利き」の候補手の情報はルートノードでは知られ
ていないので、深いノードからも情報を収集する
lose
Get Union of the inverting threat
inverting
threat
lose
lose
pass
lose
win
lose
OR nodeでのアルゴリズム
の動作


win
OR node
AND node
winnerがパスすることによっ
て結果が反転する場合、その
直前の手が「利き」
子ノードから伝播してきた「利
き」の和集合を取る
lose
Take intersection of the inverting threat
lose
lose
set of lose
inverting
threat
pass
lose
lose
AND nodeでのアルゴリズ
ムの動作


lose win
OR node
?
AND node
「最小の利き」を求める
子ノードから伝播してきた「利
き」の共通部分を取る
結果
正しい「利き」を発見し
た
可能な全てのR*-Zone
の共通部分と同じ
探索したノード数は
2,000,000+

ほぼmini-max
Future Work
Brute Force + Simulation (1/2)
期待していること

単一の目標に対しては、高速なアルゴリズムが
知られている
df-pn [Nagai 2002]
Lambda Search [Thomsen 2000]
Generalized Threats Search [Cazenave 2002]

典型的なシチョウやゲタでは探索ノード数は数十
～数百ノード
Future Work
Brute Force + Simulation (2/2)
1. 1つ shadow stoneを見つける
2. shadow stoneの要素の1つ1つ
についてそれが「利き」かどうか
探索する


それぞれについて石を打ってみて、
普通に探索
それだけだと点の数に比例した時
間がかかるので、simulation
[Kawano 1996]により時間を短縮
3. 再帰的に「利き」の範囲を限定し
ていく
Open Problem :より間接的な
「利き」の発見(よりorderの高い利き)
1手で利く範囲を発見するだけでは不十分


この例では、×の付いた点は1手では利きではな
い
2手打たれて初めて利きとなる
結論
特に両利きの手を発見するためには、真の「利き」
の範囲を発見することが重要

そのためには、「最小の利き」を発見する能力が必要
一応、「利き」を発見するアルゴリズムを作成した


このままではmini-maxに近い時間がかかる
性能向上のためのアルゴリズムを提案
2手以上打たれて初めて「利き」となる問題について
はアイデア募集中
おわり

Download Report