この翻訳は NIFTY-Serve FIGOM の有志によってなされています。 ５章についてはグーターさんのコメントに一部変更しています。 また、各章間の文体の統一を私が若干行ってます。 翻訳担当： 西野さん 要約、1章 彩 2,3,4章 まんもすさん 5章 グーターさん 6,7,8,9,10,11章 1997/12/17 彩（CXJ00674 山下　宏) __________________________________________________________________________ Many Faces of Go の知識表現 David Fotland 4863 Capistrano Ave San Jose Ca 95129 fotland@hpihoc.cup.hp.com 1993年2月27日 __________________________________________________________________________ 要約 　この論文は、強いコンピュータ碁プログラムの一つである Many Faces of Go の中 の囲碁知識の表現について記述している。 知識は、低いレベルの（局面の）特徴を認識するアルゴリズム、現在の局面を記述 するデータ構造、妥当な着手を選ぶのに使用されるパターンとして表現されている。 1. はじめに Many Faces of Go は、販売されているもっとも強い囲碁ソフトのひとつである。 1988年、1991年そして1992年のUSAコンピュータ囲碁大会で優勝し、USAで13級にラン ク付けされている。プログラムはα-βサーチ、ルールベースエキスパートシステム、 パターンマッチングの古典的なＡＩ手法に基づいている。 碁を打つアルゴリズムは、Ｃ言語で30000行のコードに、パターンデータベース、 定石データベースを付け加えたものである。プログラムは、一人の人物によって、 趣味で10年以上の期間にわたって書かれたものである。 販売されているプログラムには、IBM-PC、X-window、PenPoint のための ユーザーインタフェース用のコード約20000行が追加されている。 　碁はチェスよりもさらに難しい人工知能(AI)の問題であり、力任せの探索よりも むしろ知識にもとづくアプローチで挑戦すべきである。 2. 碁はチェスよりも難しい。 　なぜ碁がチェスより難しい問題であるか、ということにはいくつかの理由がある。 強いチェスプログラムは深さ７か、もしくはそれ以上の深さの全幅探索に依存してい る。碁の局面を評価するのはチェスよりもはるかに難しいので、この方法は碁では可能 ではない。 　碁の局面の正確な評価は、死活の分析をし、厚みと地の相対的な関係を数値に変換し なければならない。安全な地の場所を決定することはとても難しい問題である。チェス の評価は、盤上に残っている駒の価値で大部分が決まり、その駒の価値は容易に計算で きる。 　もし、碁プログラムで死活の判断を誤まれば評価値に大きな誤りを生じるだろう。 これが、碁の評価関数が、チェスよりも非常に時間がかかる理由である。パソコンのチ ェスプログラムが手を指す場合に、毎回10万局面を調べているのに対し、MFGは100個未 満の局面を調べるにすぎない。 　2番目に，碁には，チェスよりも可能な手の数がとても多い。仮に評価関数が同じ速 度だとしても碁のプログラムは多くの局面を先読みできない。 　3番目に，人間にとってはチェスよりも碁のほうがより深く先を読みやすい。 強いチェスプレーヤは10手先を読むかもしれないが、強い碁の打ち手は通常もっと深く 読む。これは碁ではチェスに対し、手が進んだ後に局面が大きく変化しないためである。 そのため、人間にとっては、長い先読みの後の局面を盤上に視覚化することが簡単と なる。初心者でさえ、盤の端から端までの60手のシチョウを読むことができる。 3. Many Faces of Go の知識 　MFGには５つの主要な碁の知識が組み込まれている。 　まず最初に、評価に組み込まれた低レベルな碁の知識があり、それはＣ言語の "if" 文でぎっしりと書かれている。これは、石の連絡、眼型、潜在的眼型、及び地を決定す るための知識である。同様に、手の生成ルーチンや戦術的な手の選択にも使われる。 この部分の一般的な作り方は、最初に分類をして、次に分析を行う事である。 これにより、コードのデバッグがより簡単になる。 　2番目に、現在の局面の状態について保存される動的な知識がある。このデータはグ ローバルなデータベースに格納され、連続する手の流れにしたがい、抽象化の低レベル から高レベルまで、蓄積される。 　3番目に，約200の規則を持つエキスパートシステムがある。それらの規則は局面全体 の評価のために、もっともらしい手を候補に選ぶ。私は評価関数の間違いがひどい手を 打つ原因となる可能性を少なくするために、意味がある手だけを選択するようにしてい る。 　4番目に、基本的な隅における定石データーベースがある。現在、3万6000個以上の手 を含み、Ishi Pressから発行された定石の本の大部分のすべての手を含んでいる。 　5番目に，8x8のパターンのパターンデータベースがある。１つのパターンに１つの打 ち手の木が付き、現在は、700以上のパターンと4000を超える手が入っている。 4. プログラムの構成 　局面について格納された動的なデータは、3つのレベルに分かれる。 　1番目は、部分更新されるデータであり、「隣り合う空点」、または「連の呼吸点の 数」などの低レベルなローカルデータのために使われる。これらのデータ構造は石の追 加、削除と同時に部分的に更新される。 　2番目に、必要な時に再計算されるデータがある。１手、又は数手の手順の後、この 手によって影響を受けた盤上の領域が再計算され、影響を受けない領域はそのまま古い 値を保持される。これには連絡の強さ、眼型、連の戦術要素がある。 　3番目に、１手、又は数手の後に盤面全体にわたって再計算されるデータである。こ れらは群の強さと放射状の影響である。 ・動的なデータの構成 　格子点の環境 　　どの連が、格子点をどの位置を占めているか（又はいないか） 　　黒、白の連に隣接するリスト 　　空点に隣接するリスト 　　黒、白、空点に隣接する数。 　　連絡のリスト 　　この位置は眼型のどの位置を占めているか。 　連のデータ 　　色 　　連の石の位置のリスト 　　連の呼吸点のリスト 　　隣接する敵の連のリスト 　　戦術的な状態（捕獲された、危ない、大丈夫） 　　連結のリスト 　　この連が群のどの位置を占めるか。 　 ・・・ 　連結のデータ 　　２つの連 　　連結している位置を示すリスト 　　連結の数 　　連結の種類 　　連結の強さ 　眼型のデータ 　　眼の位置のリスト 　　重要な位置のリスト 　　眼型の種類 　　眼の数 　群のデータ 　　群に含まれる連のリスト 　　群に含まれる眼のリスト 　　群に含まれる眼の数 　　群の強さ 　　潜在的な眼のリスト 　　自由度のリスト 　　隣接する敵の群のリスト 　地 　評価値 部分変更のデータ構造は、手が打たれた時と戻された時に変更される。その他のデータ は評価関数によって保持される。 ・評価関数 　私は他のところで評価関数を記述している。その主な要素は戦術的な分析である。 評価関数は、単一の連に対して、盤上から取り去られるか（死ぬ）、もしくは5つの呼 吸点を持つ、又は2眼を作る（生きる）、という2つの目標を与える。 また、連結の評価、眼型の評価、群の強さの評価、地の評価を行う。そして、中国式の 計算の仕方で点数が局面に付けられる。 盤上の各格子点は、+1 から -1 までの値を持ち、その点が、白、黒、どちらにより、 どの程度支配されているかを表す。評価は複数の経路の過程である。 ・戦略 　手を打つ前に、戦略関数は動的なデータを参照し、盤上の重要なエリアに焦点を当て ようとする。 　関数は局面が、どの状態（序中終盤）にあるかを決める。定石が打たれていない隅が 存在している間は布石と判定される。もし、120手以上打たれており、全ての群が安定 している場合には終盤となる。それ以外は中盤である。 　終盤から中盤に局面の状態が行ったり来たりする事は可能である。局面の状態は、 ある手の生成がふさわしいかどうかの判定にも使われる。例えば、「ダメをつめる」と いうルールは終盤でなければ適用されない。 　戦略関数は相対的な優劣を判断する。優劣は、"かなり有利"（40目以上）、"有利" （40〜20目）、"互角"、"不利"（10目以上）、"かなり不利"（20目以上）、と分類され る。優劣判定は手の生成判定にも使われる。例えば、プログラムは自分が有利だと思っ ている時には大きな群を殺した状態を確実なものにするために、余分な手を打つ。不利 なときには根拠のない無茶な侵入する手を打つ。 　戦略関数は、先手の価値を決定する。この値は序盤における7目から、220手以上の （終盤の）1目まで小さくなる。盤面全体の先読みと、静けさ探索の末端において、こ の値は手番を握っている方に付加される。それは、おそらく、どこか他の場所に大きい 手があり、それだけの点を次に得ることが出来るだろうという、推測による。 ７目は序盤において使われている。なぜなら、プログラム内部では中国式で計算して おり、中国式では、１手の価値が日本ルールに対して１目増加しており、そして日本ル ールでは最初の手は約５目半の価値があることが知られているからである。 　戦略関数はまた、素早く防がなければならない関係の深い群を調べる。これらは切断 している群や大きな群である。また、素早く捕獲せねばならない敵の群も調べる。これ らは大きな群や、切断している群、素早く防ぐ必要がある群に隣接している群である。 　緊急であるとマークされた群の攻撃や防御の手、及び緊急であるとパターンマッチン グによってマークされた手は最初に調べられ、妥当な緊急の手が見つかれば、他のいか なる手も考慮されない。 ・盤面全体の先読み 　盤面全体の先読みの手順は、定石や、パターンデータベースから与えられる。定石の 変化は盤面に展開され、定石の終わりで評価される。これは、プログラムが、隣接する 隅に対してうまく働く定石や、プログラムが理解している定石を取り出すことを許す。 また、パターンは、パターンの終わりで評価される手順を提案する。 候補手生成は、群の種類や、眼型の可能性、脱出点（群を殺したり助けたり、攻め合い で戦ったり、中央に逃げ出すための手順を生成するための）を調べる。 ルールベースのシステムが、その他の意味ある手、地を増やす、模様の拡大、などなど を生成する。 ・静けさ探索 　評価関数は、最終的に局面の状態を単一の数値（50の要素から出される）に変換しな ければならないため、静かな局面においてだけ計算される。静けさ探索は、関係が深い 未解決の群を助けるためや、関係がもろい敵の群を殺す手を生成し、局面が静かだ、と 判定されるまで、再帰的に自分を呼び出す。接近戦のために、特別な「明らかに部分的 に処理できる」パターンが、局面を静かにする手を生成する。 5. 動的なデータ ・接続 　対となる連と連との間の接続性は全て、各々の接続構造体により保持される。接続ポ イントは、連の呼吸点で、それは、そこから直線を伸ばして距離が１〜３のところに別 の同色の連があるような呼吸点である。これは、跳ね、一間飛び、桂馬、ニ間飛び、大 桂馬、三間飛びの関係を見つけるのには十分である。但し、ハザマ（double kosumi） と２線ににある２つの石からの１線の渡りをみつけることはできない。これらは、特殊 ケースパターンとして扱われている。各ポイントにおいて各方向の最も近い石への距離 を記録した低レベルの加算的なデータ構造体が、基本的な接続の部分更新的なメンテナ ンスを容易にする。その構造体は下記のようなもの string s1, s2; // ２つの連の番号 int num_d1; // 距離が１の接続の数 int num_d2; // 距離が２の接続の数 int num_d3; // 距離が３の接続の数 list_t d1points; // 距離が１の接続ポイントのリスト list_t d2points; // 距離が２の接続ポイントのリスト list_t d3points; // 距離が３の接続ポイントのリスト int type; // 接続の型: // hane 跳ね // one point jump 一間飛び // half knight's move 半桂馬 // knight's move 桂馬 // two point jump 二間飛び // half large knight's move 半大桂馬 // large knight's move 大桂馬 // 3 point jump 三間飛び // multiple 複数の組み合わせ int strength; // 接続強度 // Already cut　既に切れている // Cuttable 切ることができる // Shared connection 先着した方が連結できる // Connected with aji　味によって接続 // Connected solidly　しっかりした接続 "type"と"strength"は必要に応じて再計算する。 その他は、変化が有ったときに部分更新する。 各点は、その点が関係する連結構造データへのポインター・リストを持つ。 各連は、その連が関係する連結構造データへのポインター・リストを持つ。 以上述べた様な連結に関する分析をする機能は、碁の低レベルの知識として直接 Ｃ言語で書かれている。 約1500コード行ある。 ・眼形 個々の眼形構造体は、同じ色の石に完全またはある程度囲まれた<アキ連>や、 事実上捕られた<石連>を記録する。 list_t points; // 眼形内の空点 list_t vital; // 眼形の急所, 眼をつぶしたり、完成させたりするための int type; // 眼形の型 // single point　１空点 // two point　２空点 // line eye (closed, open one end, open both ends) 　 線状の目（閉じている、片開き状態、両開き状態） // big eye 大きな眼形 // dead group eye　捕獲した群で出来る眼形 int color; // color of the eye　眼の色 int min_eyes; // 相手が２手打った場合の眼の数 int typ_eyes; // 相手が先に打った場合の眼の数 int max_eyes; // 自分が先に打った場合の眼の数 　眼形の数は、眼ひとつにつき８として保有している。よって半眼は４である。各ポイ ントは、ただ１つだけの眼の一部となり得る、そしてその眼は、ポイントについての他 のデータと伴に記録される。眼形構造体のすべての部分は必要に応じて再計算を行う。 眼形分析は、約2400行のＣ言語で記述されている。眼形の認識のためには、接続の認識 と比較すると、より多くのパターンが存在し、部分的にデータを更新していって死活を 判定することはできない。もし私が再度最初から作り直すならば、Ｃ言語ではなくパタ ーンベースの仕組みで作るだろう。 ・眼形候補 各群は眼形候補構造体のリストと脱出点のリストを持つ。 これらは、群の強度を評価したり、攻撃・防御の手を生成する時に使う。 眼形候補は、評価値、位置、タイプをもっている。 タイプとは： 境界を拡張するタイプ 評価値：着手後の眼点の数 位 置：拡張の基点となる呼吸点 急所に打って眼を作るタイプ 評価値：着手後の眼形の数 位 置：急所点 他の群に連結するタイプ 評価値：全眼形の数 位 置：連結番号 弱い連を捕獲するタイプ 評価値：全眼形の数 位 置：捕獲対象の連の番号 領域境界を侵食からまもるタイプ 評価値：着手後の眼点の数 位 置：侵食の標的となる呼吸点 　脱出点は、脱出方向が味方もしくは敵の石に向かっているかによって決まるタイプ別 に、いくつかのリストに記録されている。 　評価を行う度に、盤面全体に渡って、眼形可能性と脱出点の再評価を行っている。 その作業は、プログラム全体の実行時間の7%を占める。 ・影響力関数 影響力関数は、各石からその群の強さによって決まる初期値（影響力）が放射される。 そして距離にしたがって減衰する。放射された影響力は、各ポイントで黒白別に合計さ れる。影響力は、石や接続を通過しては放射されない。影響力は、領地や厚みの計算、 脱出のための着手のよい見当を得ることや模様の構築や削減／侵入の着手の生成を助け ることに使われる。勢力は、群の接続の判断には使われない。 1/距離 で減衰する関数は、完全に囲まれた領域の中にコンスタントなフィールド を作る。それがどんなに大きくとも、それは、領地を見積もるのに望ましい性質であ る。死んだ石は逆の勢力を放射する。 6. 候補手生成のためのルール・ベース・システム (訳者注：ルール・ベースのエキスパート・システム ＝知識ベースの中の専門知識が<生成規則>の形で収まっているもの） 候補手生成知識ベースには、以下のものがある： 布石 アキ隅の打ち方 シマリとカカリ 定石 辺での大きい動き 相手の石の方向に打つ場合 進入する場合 自分の石の間に打つ場合 中央での戦い（ケシの手、切りチガイ） 優勢局面での安全な打ち方 死んだ群に敵が手を入れて来たときの対応 ほぼ死んだ敵の大石にさらに念を入れて打つ 劣勢局面での＜もがき＞ みせかけの進入を仕掛ける 絶望的な群にも手入れしてみる パターン・マッチング キリ・ツナギのパターン 包囲・包囲突破のパターン 進入・進入防止のパターン 終局のパターン 死活のパターン 形を決める手 弱い群を助ける 眼をつくる 脱出する 攻め合いの戦い方 危ない連を助ける 取れそうな連を捕獲する 弱い群を殺す 包囲 眼を奪う キリとツナギ 接近戦 ブロックする アキ(呼吸点)を増やす ハネ コウ争い 大きなアタリをかける ダメを詰める 候補手生成のコードは、パターンや別の基準に沿った<生成規則>を加えること によって、容易に拡張可能である。プログラムは各ルールに対応する文章を持っ ているので、各着手の理由を説明できる様にしてある。これを利用するとデバッ グが容易にできる。 7. 定石データ・ベース 定石データ・ベースは、アキ隅から始まる手順の有向非周期グラフの形式で保存 される。方位変換したデータは、データ入力を終える都度、手作業でデータ・ベース に組み込む。非圧縮表現はASCIIファイルとして保管される。 非圧縮形式でのノードは、以下の内容を含んでいる： 隅からの相対座標ＸとＹ（1-16の値） 兄弟ノードへのポインター 第１子ノードへのポインター タイプ：緊急、通常、難解、トリック、悪手、無視、.... フラグ：色、対称形、色反転 緊急手は、他の手より優先する。 難解とトリックは、劣勢局面で無ければ選択しない。 悪手は、絶対選択されないが、相手が打って来た場合に正しく応手で きる様に入れてある。 無視は、間違ったデータを消すためのもの。 色は、この手番が、この隅に先着した色と同じか否かの判別に使用する。 対称形は、この手を打つと隅の形が再び対称形になることを示す。 色反転は、いくつかの置き換えで必要となる。例えば、特定の３〜４の定石は色を 　　反転すると５〜３の定石に置き換えられる。 圧縮形式はプログラムで直接使用できる。 座標(Ｘ,Ｙ)は"LOOKUP TABLE"で６ビットに圧縮される。 ６ビットの値の内、 0−62の値は、62個の最もよく使われる(X,Y)のペアをいれた "LOOKUP TABLE"のインデックスになっている。 63は、実際の(X,Y)ペアの値が入っている後続バイトへの エスケープ値とする。 兄弟ノードと子ノードへのポインターは、２ビットで置き換えられる。 この２ビットで、兄弟ノードの有無、子ノードの有無を表わす。 データは深さ優先の順に配列される。ただし方位変換の結果ノードが重なって しまう場合は、例外として２バイトのポインターのままで記録される。 大抵のエントリーは１バイト長で済む。可能な最大長は５バイト。 データ・ベース全体を平均すると、１手を1.2バイトで表現出来ている。 8. パターン・データ・ベース パターン・マッチャーは500パターン以上を持っている。 各パターンは８ｘ８で、その各点は、黒、白、アキ、不問、白かアキ、黒かアキ、 白か黒、などが指定されている。 各パターンは、幾つかの特性を持っていて、この特性もマッチングの対称になる。 例えば、”(４,２)の石は活きであること”とか、 ”(２,５)の石は２つ以上の呼吸点を持つこと”などである。 各パターンは、手順ツリーをも持っており、盤全体の先読みに使用される。 パターンはまた、形からして不可欠な部分手順を表わすのに使用される。 内部的には、パターンは３つの８バイト配列に成っている。 １つは黒の位置、１つは白の位置、もう１つはアキの位置である。 例えば黒の配列では、黒石の有る位置に対応するビットをオンにする。 ”黒かアキ”の条件は、黒の配列とアキの配列の対応するビットを共にオンに すれば良い。 ”不問(なんでも良い)”の条件は、３つの配列の対応するビットを全部オンに して表わせる。 各パターンは、盤上の各点と８方位変換、２色変換をしながら全て比較する。 わたしの場合は、パターンを変換するのではなく、盤面を変換して比較している。 色変換は、黒配列と白配列を交換する方法をとっている。 盤面から或位置の３種の配列を作ったら、パターン・マッチは簡単である。 黒、白、アキの各配列毎の"AND"をとり、３つの結果の"OR"をとって、結果すべて のビットがオンならパターンは一致したと判定できる。 一致するパターンが見つかったら、つぎに特性を比較する。 　わたしは、少なくとも1000パターンを持とうとしているので、パフォーマンス は重要な問題である。1000パターンを361の盤面位置と16方位変換の比較をすると、 500万回になる。全比較は、24バイトの"AND"、16バイトの"OR"、８比較、言い換えれば 48回の基本オペレーションが必要となる。結果、一つの盤面のパターン・マッチングで およそ３億オペレーションが必要になる。 比較するパターンの数を減らすために、８ビット・ハッシュを使用する。 もちろん、パターンの中に"不問"もあるので、ハッシュ・チェーンが延びる もの（現在平均３チェーン）がある。 ハッシュを使うことで、試されるパターンの数を1/20見当減らす。 どのパターンが着手が進むに連れてマッチするか記憶しておき、最終着手の近辺だけ 比較する。 これで、パターン比較を必要とする盤面位置を361から50に減らせる。 ビット毎のオペレーションを32ビット同時に処理して、大抵のパターンは最初の ワード比較で不一致になり、オペレーションの数を平均６まで落とした。 これで、全パターン比較に必要なオペレーションを350,000にした。 それでもまだ遅くて、１手決め、読み順を決める時に全パターンを一度だけ比較 するのがやっと。 パターンのちいさなサブ・セットを作り、局地的な必然手順を見出す静止探索の先 読みの時に使用している。 現在プログラム実行時間全体の1.5％をパターンの比較に費やしている。 9. 知識獲得 グラフィカル定石エディタを使用して、１時間当たり約400手の入力が出来るし、 定石データ・ベースをプログラムで使用可能な圧縮形式に変換することも出来る。 グラフィカル・パターン・エディタでは、各種パターンや着手ツリーの編集が出来る。 36のパターンを同時に表示することも出来る。 このプログラムは、プロの対局をなぞりながらプレーし、プログラムの手と プロ棋士の手とを比較することが出来る。そして、プログラムがプロ棋士 の手を 候補手にも挙げていなかった場合には、そのパターンを対局から切り 出して保管することが出来る。 この方法は、期待した程の効果は無いことが判明した。 なぜなら、このような場面の多くは、難解な戦いの最中であり、８ｘ８パターン では 小さすぎて納まらなかったり、局所パターン以外の深いヨミによる着手 だったりするからである。 10. デバッグ補助 多くのデータ構造は、部分変更が可能な形式である。 わたしは、定期的に全体を計算し直し、部分変更で管理してきたデータを 検査する機能を選択できるようにした。 この機能では、全てのリストをたどって、メモリー・リークの検査もする。 わたしのプログラムには、部分変更とメモリー管理に関するバグは無いと 確信している。 幾つかのデータは必要に応じて再計算される。 しばしば、眼や戦略上の先読み では再計算が必要になりますが、どこでどうしたかは分からない。 この周辺でのバグを見つけるために、各位置を先読みの前と後の２回評価する コードをいれた。違いが有れば、何かが再評価されていないことになる。 再評価もれが起きる状況は様々。テスト・ゲームでは、1000手に１回位発生する。 人間にも有る見落としみたいなもので、重症のバグでは無いが、見つける毎に 修正している。 デバッグ版のプログラムは、すべての内部データ構造を読みやすい形式で表示する。 プログラムがおかしな手を打ったら、即座にその原因を見つけられる。 ２種類の特殊テストを行う。 第１に、すべてのチェック機構を働かせて、種々の強さレベルとハンデを設定した 100ゲームを自動プレーさせる。 第２に、"Graded Go Problems For Beginners" からつくった400の問題集 を自動的に流して、どの問題で間違った解答を出したかを見る。 "Many Faces of GO" と "Internet Go Server" のインターフェースを作って、 人間不在でも対局可能にした。 悪手を打つ問題を直す為に微妙なところまで試せるサンプルとして、幾つかの テスト・ゲームを集めた。 11. まとめ 碁を巧くプレーすることは、難解なＡＩ問題の一つである。 盤面が広いことと評価が難しいことからして、巨大な探索は実際的で無く、 知識集約なアプローチが必要となる。 Many Faces は、部分的で、低レベルの知識を、スピードの早い'Ｃ'で書き、 高レベルのパターン知識を、小さく最適化したデータ・ベースに入れた。