５路盤の完全解析の結果論文名：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例会電通大 1 ページへジャンプ目次         1.Introduction 2.碁のルール 3.評価関数 4.探索方法 5.スーパーコウ（同型反復を全て禁止）による問題 6.実験結果 7.結論と将来の予想 8.参照 1 ページへジャンプ 1. Introduction    探索ベースのアプローチによって解かれた（最善手をプレイし続けると、どちらが勝ちなのか解明された）ゲームがたくさんあるが、囲碁はまだ。小さい碁盤ならば、４×４までは解けている（２０００年、清）。証明はされていないが、７×７までは人手で解いたという報告はある。 1 ページへジャンプ 2. 碁のルール  コンピュータで解かせる場合に、考慮しなければいけないことがある。 (1) 劫と同型反復、自殺手、地の計算様々なルールが存在する (2) 生死の判定生死をコンピュータが判定できるか 1 ページへジャンプ最後まで打たずに「生きている石」を判定する    人間どうしの対局では、両者が終局を合意したときに終局となる。 → コンピュータには無意味な概念。合法手がある限り打ち続けると、なかなか終わらないので、合法手が残っていても終局の判定をしたい。「生きている石」の判定には、Benson のアルゴリズム(1976)が有効。 ※対局プログラムにとっては、Bensonのアルゴリズムは遅くて使い物にならない！ 1 ページへジャンプ Bensonのアルゴリズム  領域（同一色で囲われている）について、呼吸点や連結の度合いから、生死を判定する。 1 ページへジャンプ最後まで打たずに「地」を判定する    眼は、Bensonのアルゴリズムによってわかる。ダメは、両者の生き石に接続。または生き石に接続してない（序盤）。一方の石に囲まれた大きな領域が、地か否かの判定は、計算が必要。 1 ページへジャンプ「地」の判定     囲っている側が全てパスしたと仮定して、侵入側が打ちつづけた場合に、眼が２つ以上できれば「地」ではない。「欠け眼」の判定は簡単（眼の斜めを調べればよい）。「欠け眼」だけでも生きている場合があるが、これはEuler数で判定できる。「中手」「セキ」の判定も必要（詳細不明）。 1 ページへジャンプ終局時の生死について     通常はパス２回で終局劫があると、パスは３回以上続かないと終局にならない。終局時に、死に石は、相手の地にカウントされる。スーパーコウでは、盤上に存在する石が、そのまま生き石となる。 1 ページへジャンプ採用したルール     自殺手は無し２眼作れない石（セキを除く）は死に曲がり４目は生死の判定をせずに打ちつづける巨大墓場は死に 1 ページへジャンプ 3.評価関数        1.盤上置ける最大の石数 2.ダメの数を最大にする 3.盤の端に打つ手を避ける 4.石を連絡する。 5.眼を作る石の連結とか眼の数の計算は時間がかかる。オイラー数（Euler Number)を持ちいることで連絡と眼の数を高速に計算できる。 1 ページへジャンプ連絡と眼の評価連絡する方が好型 W=2 W=1 連絡して眼を作ればさらに好型 W=2 W=0 1 ページへジャンプ Euler Number（オイラー数)  Topology(位相)の用語らしい。  オイラー数＝物体の数－孔の数      ００００００００１１１０１００１０１０１０ → ０１１１００００００００００物体の数は２孔の数は１なのでオイラー数は２－１＝１となる 1 ページへジャンプ Euler数が囲碁に適用できる！    囲碁では眼を作ることと石を連絡することが一般的に好ましい。オイラー数＝物体の数－孔の数、なので物体の数を減らすこと＝連絡、孔の数＝眼を作ることになり、オイラー数を減らすことがいい評価関数になりうる。 1 ページへジャンプ Euler数の計算の仕方 diagonal(対角線） 1 ページへジャンプ Euler数の計算の仕方２  オイラー数を減らすのは石を連絡して眼を作ることになる 4W=n(Q1) - n(Q3) -2n(Qd) 4W=12 - 0 -2*2 = 8, W=2 4W=8 -0 -2*4 = 0, W=0 ここでは斜めでも連絡、というEuler数で計算している 1 ページへジャンプ Euler数の計算の仕方３   ０１１０１１０ Q1=２、Q3=０、Qd=２０００１０００盤の枠に０があるとして  縦に2行ずつ取り出してこの部分だけ Q1,Q3,Qdの数をカウントすれば高速に計算できる。  あらかじめ2^14=16384通りのテーブルを作っておく  黒を計算するときには白は無視する。 1 ページへジャンプ４．探索方法の概略  PVSによる反復深化法。  αβ法の改良版の一つ。一番最初に探索する手以外は枝刈りされると期待して幅1のNull Windowで探索する。失敗すれば真面目に再探索する。  途中局面の末端では軽い評価関数を使い、終局局面では特別の関数で正しい値を出す。 1 ページへジャンプ４．探索方法の詳細     4.1 ハッシュ表 4.2 対称形の照合 4.3 内部の無条件限界 4.4 手の並び替えの向上 1 ページへジャンプ 4.1 ハッシュ表(探索した局面を保存）   two-deep replacement ハッシュが衝突した場合にどれを捨ててどれを残すか、という手法。  ハッシュ表をA、Bの2つ持ち、ハッシュを読む場合は、A,Bと2つ調べる。  登録するときは、まずAを見て、より深い探索結果の場合はをBにコピーしてAに情報を書き込む。それ以外の場合は無条件にBに上書きする。   A...より深い結果だけを登録。 B...常に最新の情報で上書きされる。 1 ページへジャンプ 2つからなるハッシュ表（続き）    1つだけのハッシュ表で深い探索結果と入れ替える方法よりも一番効率がいい。他には探索された局面数の多い方を残す方法も有力ハッシュ表が十分大きいなら関係ない 1 ページへジャンプ 4.2 対称形の照合   回転で4通り、対称型で2通り、さらに白と黒と入れ替えたパターンで2通り、全部で4*2*2=16通りの対称形を考慮している。対称形のハッシュ値はいちいち計算しなおしている。--->時間がかかる！  が問題なし。これは浅い深さ（深さ５ぐらいまで）でのみ。対称形が効果を最大限に発揮するのは最初の方なので。  SSK（同型反復禁止）ルールでは手順が問題になるので手の並び替えにしかハッシュの情報を使えない。 1 ページへジャンプ 4.3 無条件地での枝刈り     無条件の地、を使って枝刈りが可能例えば、黒の確定地が5x5で8目を超えていれば、(alpha,beta)=(-25,+6)の場合に即座に枝刈りされる。黒は8目以上負けようがないので。同時に無条件地の中に打つ手は普通は試す必要がないので手の制限にもなる。 SSK（同型反復禁止）の場合は全部試す。 1 ページへジャンプ 4.4 読む手の順番       1. ハッシュの手 2. ヒストリー手 3. キラー手 4. ヒストリーの2番目 5. キラー手の2番目 6. ヒストリーの残りの手全部 1 ページへジャンプヒストリー手     ある局面で枝刈りが起こった手の場所を覚えておき、その場所を＋していく。枝刈りが起きやすい場所が点数が高くなり、その手を優先的に試す。キラー手、は兄弟局面で枝刈りが起きた手。ヒストリーと似てる。敵の急所は我が急所、で黒白のテーブルは一緒。 1 ページへジャンプキラー手とsibling promotion   キラー手 Sibling promotion(敵の好手を先に試す） 1 ページへジャンプ 5.スーパーコウ（SSK）による問題   全ての同一局面の反復を禁止するこのルールではハッシュを使っているとGHIという問題が発生する。 GHI(Graph History Interaction)  異なる手順で同一局面が出現する問題の事。  ハッシュにはその局面に至った手順が含まれていないためハッシュの情報を鵜呑みにすると間違える。 1 ページへジャンプこの論文でのGHIの対応策  ハッシュにパスの回数と取った石の数を加えた。  簡易版（appr.SSK）  その局面に至った手順のハッシュ情報を通常のハッシュと別に持ち、両方が一致した時のみを同一局面とする。  完全版(full SSK)  探索効率がかなり悪化する。 1 ページへジャンプ 6.実験結果 P4-2.0GHz ハッシュで1600万局面を記憶 1 ページへジャンプルールの違い     Basic Ko … 2手のコウのみ禁止。同型反復は全て許可。 Japanese Ko … 同型反復は持碁（引き分け） Appr.SSK … 全ての同型反復は禁止。ハッシュに取った石の数、パスの回数を含む。 Full SSK … その局面にいたった手順情報のハッシュを別に持つ。 1 ページへジャンプ 5路盤での初手の位置による結果     天元は黒25目勝ち辺は黒3勝ち隅は白1目勝ちそれ以外は白が25目勝ち 1 ページへジャンプ天元、辺、隅における最善手順   辺の手順は趙治勲の解析手順と一緒辺で白６を黒７の位置に打つ変化は趙治勲の解析は間違いらしい天元辺隅 1 ページへジャンプ辺に打った場合の趙治勲の解析手順最善手順と同一。黒３目勝ち（日本ルールでは黒２目勝ち） 1 ページへジャンプ辺で白６を打った場合の趙治勲の解析手順最終図は両コウゼキになって持碁中国ルールでは白1目勝ちになる。ルールの差の問題？ 1 ページへジャンプ探索手法による探索局面数の減少    ハッシュ表は効果絶大対称性を考慮したハッシュも効果的 HistoryがKillerよりも効果的 1 ページへジャンプ 6路盤の解析（8個石を置いた後で）  6路盤では8個以上石を置いた局面を幾つか解いた。 1 ページへジャンプ結論と将来の予想       5x5は全ての初手に対して完全に解いた。 6x6は盤上に石が8以上ある場合を幾つか解いた。探索手法やヒューリスティックな評価関数、無条件地の判定が探索効率を高めた。清と川嶋が解いた4x4で1400万ノードに対して MIGOSは70万ノードで解いている。探索速度は20 万から30万局面/秒次なるステップ6路、7路盤の解析へ… 人間による解析結果黒4目勝  7x7 黒9目勝  6x6 1 ページへジャンプ