５路盤の完全解析の結果 論文名：Solving Go on Small Boards 著者： Eric C.D. van der Werf

Presentation on theme: "５路盤の完全解析の結果 論文名：Solving Go on Small Boards 著者： Eric C.D. van der Werf"— Presentation transcript:

1 ５路盤の完全解析の結果 論文名：Solving Go on Small Boards 著者： Eric C.D. van der Werf
H.Jaap van den Herik Jos W.H.M. Uiterwijk オランダのマーストリヒト大学 出典： ICGAジャーナル 2003年6月号 紹介：清 愼一、山下 宏 2003年10月11日 CGF例会 電通大

2 目次 1.Introduction 2.碁のルール 3.評価関数 4.探索方法 5.スーパーコウ（同型反復を全て禁止）による問題
6.実験結果 7.結論と将来の予想 8.参照

3 1. Introduction 探索ベースのアプローチによって解かれた（最善手をプレイし続けると、どちらが勝ちなのか解明された）ゲームがたくさんあるが、囲碁はまだ。 小さい碁盤ならば、４×４までは解けている（２０００年、清）。 証明はされていないが、７×７までは人手で解いたという報告はある。

4 2. 碁のルール コンピュータで解かせる場合に、考慮しなければいけないことがある。 (1) 劫と同型反復、自殺手、地の計算
様々なルールが存在する (2) 生死の判定 生死をコンピュータが判定できるか

5 最後まで打たずに「生きている石」を判定する
人間どうしの対局では、両者が終局を合意したときに終局となる。　　　　→　コンピュータには無意味な概念。 合法手がある限り打ち続けると、なかなか終わらないので、合法手が残っていても終局の判定をしたい。 「生きている石」の判定には、Bensonのアルゴリズム(1976)が有効。 　※対局プログラムにとっては、Bensonのアルゴリズムは遅くて使い物にならない！

6 Bensonのアルゴリズム 領域（同一色で囲われている）について、呼吸点や連結の度合いから、生死を判定する。

7 最後まで打たずに「地」を判定する 眼は、Bensonのアルゴリズムによってわかる。
ダメは、両者の生き石に接続。または生き石に接続してない（序盤）。 一方の石に囲まれた大きな領域が、地か否かの判定は、計算が必要。

8 「地」の判定 囲っている側が全てパスしたと仮定して、侵入側が打ちつづけた場合に、眼が２つ以上できれば「地」ではない。
「欠け眼」の判定は簡単（眼の斜めを調べればよい）。 「欠け眼」だけでも生きている場合があるが、これはEuler数で判定できる。 「中手」「セキ」の判定も必要（詳細不明）。

9 終局時の生死について 通常はパス２回で終局 劫があると、パスは３回以上続かないと終局にならない。
終局時に、死に石は、相手の地にカウントされる。 スーパーコウでは、盤上に存在する石が、そのまま生き石となる。

10 採用したルール 自殺手は無し ２眼作れない石（セキを除く）は死に 曲がり４目は生死の判定をせずに打ちつづける 巨大墓場は死に

11 3.評価関数 1.盤上置ける最大の石数 2.ダメの数を最大にする 3.盤の端に打つ手を避ける 4.石を連絡する。 5.眼を作る
石の連結とか眼の数の計算は時間がかかる。 オイラー数（Euler Number)を持ちいることで連絡と眼の数を高速に計算できる。

12 連絡と眼の評価 連絡する方が好型 W=2 W=1 連絡して眼を作ればさらに好型 W=2 W=0

13 Euler Number（オイラー数) Topology(位相)の用語らしい。 ０００００００ 物体の数は２
オイラー数＝物体の数－孔の数 ０００００００　　　　物体の数は２ ０１１１０１０　　　　孔の数は１なので ０１０１０１０ →　　オイラー数は ０１１１０００　　　　２－１＝１となる ０００００００

14 Euler数が囲碁に適用できる！ 囲碁では眼を作ることと石を連絡することが一般的に好ましい。 オイラー数＝物体の数－孔の数、
なので物体の数を減らすこと＝連絡、孔の数＝眼を作ることになり、オイラー数を減らすことがいい評価関数になりうる。

15 Euler数の計算の仕方 diagonal(対角線）

16 Euler数の計算の仕方 ２ オイラー数を減らすのは石を連絡して眼を作ることになる 4W=n(Q1) - n(Q3) -2n(Qd)
2017/3/1 Euler数の計算の仕方 ２ オイラー数を減らすのは石を連絡して眼を作ることになる 4W=n(Q1) - n(Q3) -2n(Qd) 4W= *2 = 8, W=2 4W= *4 = 0, W=0 ここでは斜めでも連絡、というEuler数で計算している

17 Euler数の計算の仕方 ３ ０１１０１１０ Q1=２、Q3=０、Qd=２ ０００１０００
０００１０００　 縦に2行ずつ取り出してこの部分だけQ1,Q3,Qdの数をカウントすれば高速に計算できる。 あらかじめ2^14=16384通りのテーブルを作っておく 黒を計算するときには白は無視する。 盤の枠に０があるとして

18 ４．探索方法の概略 PVSによる反復深化法。 途中局面の末端では軽い評価関数を使い、終局局面では特別の関数で正しい値を出す。
αβ法の改良版の一つ。一番最初に探索する手以外は枝刈りされると期待して幅1のNull Windowで探索する。失敗すれば真面目に再探索する。 途中局面の末端では軽い評価関数を使い、終局局面では特別の関数で正しい値を出す。

19 ４．探索方法の詳細 4.1 ハッシュ表 4.2 対称形の照合 4.3 内部の無条件限界 4.4 手の並び替えの向上

20 4.1 ハッシュ表(探索した局面を保存） two-deep replacement
ハッシュが衝突した場合にどれを捨ててどれを残すか、という手法。 ハッシュ表をA、Bの2つ持ち、ハッシュを読む場合は、A,Bと2つ調べる。 登録するときは、まずAを見て、より深い探索結果の場合はをBにコピーしてAに情報を書き込む。それ以外の場合は無条件にBに上書きする。 A...より深い結果だけを登録。 B...常に最新の情報で上書きされる。

21 2つからなるハッシュ表（続き） 1つだけのハッシュ表で深い探索結果と入れ替える方法よりも一番効率がいい。
他には探索された局面数の多い方を残す方法も有力 ハッシュ表が十分大きいなら関係ない

22 4.2 対称形の照合 回転で4通り、対称型で2通り、さらに白と黒と入れ替えたパターンで2通り、全部で4*2*2=16通りの対称形を考慮している。 対称形のハッシュ値はいちいち計算しなおしている。--->時間がかかる！ が問題なし。これは浅い深さ（深さ５ぐらいまで）でのみ。対称形が効果を最大限に発揮するのは最初の方なので。 SSK（同型反復禁止）ルールでは手順が問題になるので手の並び替えにしかハッシュの情報を使えない。

23 4.3 無条件地での枝刈り 無条件の地、を使って枝刈りが可能
例えば、黒の確定地が5x5で8目を超えていれば、(alpha,beta)=(-25,+6)の場合に即座に枝刈りされる。黒は8目以上負けようがないので。 同時に無条件地の中に打つ手は普通は試す必要がないので手の制限にもなる。 SSK（同型反復禁止）の場合は全部試す。

24 4.4 読む手の順番 1. ハッシュの手 2. ヒストリー手 3. キラー手 4. ヒストリーの2番目 5. キラー手の2番目
6. ヒストリーの残りの手全部

25 ヒストリー手 ある局面で枝刈りが起こった手の場所を覚えておき、その場所を＋していく。
枝刈りが起きやすい場所が点数が高くなり、その手を優先的に試す。 キラー手、は兄弟局面で枝刈りが起きた手。ヒストリーと似てる。 敵の急所は我が急所、で黒白のテーブルは一緒。

26 キラー手とsibling promotion

27 5.スーパーコウ（SSK）による問題 全ての同一局面の反復を禁止するこのルールではハッシュを使っているとGHIという問題が発生する。
GHI(Graph History Interaction) 異なる手順で同一局面が出現する問題の事。 ハッシュにはその局面に至った手順が含まれていないためハッシュの情報を鵜呑みにすると間違える。

28 この論文でのGHIの対応策 ハッシュにパスの回数と取った石の数を加えた。
簡易版（appr.SSK） その局面に至った手順のハッシュ情報を通常のハッシュと別に持ち、両方が一致した時のみを同一局面とする。 完全版(full SSK) 探索効率がかなり悪化する。

29 6.実験結果 P4-2.0GHz ハッシュで1600万局面を記憶

30 ルールの違い Basic Ko … 2手のコウのみ禁止。同型反復は全て許可。 Japanese Ko … 同型反復は持碁（引き分け）
Appr.SSK … 全ての同型反復は禁止。ハッシュに取った石の数、パスの回数を含む。 Full SSK … その局面にいたった手順情報のハッシュを別に持つ。

31 5路盤での初手の位置による結果 天元は黒25目勝ち 辺は黒3勝ち 隅は白1目勝ち それ以外は白が25目勝ち

32 天元、辺、隅における最善手順 辺の手順は趙治勲の解析手順と一緒 辺で白６を黒７の位置に打つ変化は趙治勲の解析は間違いらしい 天元 辺 隅

33 辺に打った場合の趙治勲の解析手順 最善手順と同一。黒３目勝ち（日本ルールでは黒２目勝ち）

34 辺で白６を打った場合の趙治勲の解析手順 最終図は両コウゼキになって持碁 中国ルールでは白1目勝ちになる。ルールの差の問題？

35 探索手法による探索局面数の減少 ハッシュ表は効果絶大 対称性を考慮したハッシュも効果的 HistoryがKillerよりも効果的

36 6路盤の解析（8個石を置いた後で） 6路盤では8個以上石を置いた局面を幾つか解いた。

37 結論と将来の予想 5x5は全ての初手に対して完全に解いた。 6x6は盤上に石が8以上ある場合を幾つか解いた。
探索手法やヒューリスティックな評価関数、無条件地の判定が探索効率を高めた。 清と川嶋が解いた4x4で1400万ノードに対してMIGOSは70万ノードで解いている。探索速度は20万から30万局面/秒 次なるステップ6路、7路盤の解析へ… 人間による解析結果 6x6 黒4目勝 7x7 黒9目勝