01025/01027 CXJ00674  彩               Computer Go Design Issues
( 8)   97/04/28 00:49                     コメント数：1

　囲碁プログラマーの皆さん、こんにちは。

インターネットを探検中に、コンピュータ囲碁メーリングリストの説明を見つけ
ました。その中で MFG の作者 David Fotland が書いている囲碁ソフトについて
の概要が面白そうだったので、日本語訳を流します。

原文は

http://cs.anu.edu.au/~Lex.Weaver/COMPUTER-GO/Fotland_summary_Oct_96.html

にあります。

良く分からない所は意訳してます（でも意味不明な所はたくさんあります(;_;)）

翻訳のアップについては David の許可をもらいました（英語で質問するのは少し
緊張しましたけど^^;）。
他に訳して転載したい人がいれば自由にやってくれ、とのことでした。

訳していて、まだまだコンピュータに教えるべき事はたくさんあるな、と思いました。

01026/01027 CXJ00674  彩               コンピュータ囲碁設計の問題（日本語訳）
( 8)   97/04/28 00:53  01025へのコメント

　これは、コンピュータ囲碁テクニックの概要です。
コメントして下されば、より多くの事をつけ加えるつもりです。特に、他の囲碁プ
ログラマー達からの、どの様な方法を使っているか、というコメントを歓迎します。


　　　　　　　　　　　　コンピュータ囲碁設計の問題
        　　　　　             David Fotland

　これは、コンピュータ囲碁プログラマが直面している主要な設計問題と、幾つか
の可能な解決方法についての簡単な解説である。

　囲碁プログラムで最重要視すべき要素は、戦略の評価、手の選択、盤面全体の評
価、及び探索戦略である。

局面全体の正しい評価関数を作ることは非常に難しく、作ったとしても非常に計算
時間がかかるだろう。評価に時間がかかるため、全幅探索は非現実的であり、良い
手の選択が不可欠である。

プログラムは、戦いの局面では5〜10手の深さの先読みをする必要がある。静かな
局面では、手の選択は戦略の問題に依存するので、１手の先読みでいいだろう。

あらゆる探索や評価の結果には不確実性がつきまとう。強いプログラムはその不確
実性を扱うことができ、信頼できる結果とできない結果の差を表現できる。

多くの局面において、戦略のたて方が手の選択に影響する。その結果として生じる
盤面全体の評価は非常に似てくるだろう。
そのため、戦略の目標を決めて、それに基づいて手の選択をすることが重要である。


一般的なやり方は次の通りである。

・まず最初に、局面の戦略的評価をして、目標を選ぶ。
・次に手を選択して、何度かの盤面全体の探索を行う。
　目標に従って手を評価するか、または目標に従って生じた局面を評価する。
・最後に、最善手を決定する。

ほとんどの碁の局面では、同じぐらいの価値を持った手が存在する。


手を選択する上で重要な問題は次の２つである。

・大きい群を捨てないこと！。
　これは即、負けにつながる。全ての対局において、正確な死活の読みが何度か重
　要となる。石の連絡や、眼を作る空間の安全性の評価を誤ると、多くの対局で負
　けるだろう。

・指し手を無駄にしないこと！。
　完全に無駄な手、１手につき、棋力がおよそ１級下がる。必要もないのに、自分
　の群に石を追加したり、又は、敵の小さな群の捕獲に過度に手を入れすぎたり、
　敵の強い群に対して攻撃を加えて手を無駄にする事も同様である。


1) 最初に決定すべき事は、どのように最も良い手を選ぶかである。
　A) あるプログラムはコンピュータチェスで使われているように、盤面全体の評価
　　関数を用意して、評価が最大になるような手を探して探索する。（ Go4++ ）
　B) あるプログラムは戦略の問題やいくつかの探索木の決定に従って手を評価し、
　　最高の優先度を持つ目標を達成する手を選択する。( Nemesis, Go Intellect )
　C) ほとんどのプログラムがこれらの組合せを利用している。( Many Faces of Go )


2)　戦略の評価。
　A) 今、形勢は有利か、不利か、もしくは互角か？。不利ならば攻撃的で危険な
　　手を打ち、有利なときは安全な手を打つ。
　B) 今、序盤か中盤か終盤か？。
　 ・序盤なら１手は20目の価値がある。
　 ・中盤なら弱い群の攻防に焦点を当てる。
　 ・終盤ならば手の大きさに焦点を当てる。
　C) 先手を握っている価値はどのくらいか？。
　 ・手を進めるごとに変わる。
　 ・石が置かれていない盤では12〜15目程度。
　D) どこに、弱い群があるか？。
　　石を殺すべきか、追い回すか、取り囲むか、又は後手で生かすべきか？。
　　自分の弱い群から手を引くか、又はそれを犠牲にするべきか。
　E) 死活の探索を戦略評価の一部とするか？、又は盤面全体の評価の一部とするか。
　F) より首尾一貫した手を打つために、手から手への戦略の判断を覚えさせるか？
　G) 相手の最後の打ち手の目的を理解し、それに反撃するようにする。
　H) 自分がパスをしたらどうなるか。相手から受ける最悪のダメージはどのくらい
　　で、その場所はどこか。


3) 手の選択。
　A) 定石ライブラリ
　　1) ２、３の基本的な系列で十分。
　　2) 定石か、定石の知識から定石に近いものをプレーするようにした方がよい。
　B) 布石ライブラリ
　　1) 最初の５手程を超えるとそれほど役に立たない．
　  2) 作るのは簡単である。数千のプロの対局、又は100,000以上のIGSでの対局が
　　　利用可能である。
　C) 弱い石への攻撃、防御。
　D) 自分の地を増やしたり、相手の地に侵入したり、減らす手。
　E) 模様を作る手、中央に飛ぶ手。
　F) 寄せの手。
　　1) 数学的な寄せの分析により、正確な値か、優先する順番を決める事が可能
　　　である。( Explorer )
　G) パターンデータベース。
　  1) 約3000程の典型的なパターンから手が生成され、調整される。
　  2) 対局から自動的に生成する。・・・あまり役には立たない。
　  3) パターンのサイズ(5x5、8x8、11x11、任意）
    4) ビットマップ 対 パターン記述言語 対 探索木
 　 5) パターン内の位置の属性。
  　　a) 呼吸点の数。
  　　b) 群の強さ。
  　　c) 群の戦術的な安定性。
 　 6) グラフィカルなパターンエディタ。どの様に組織化するか。
　H) コウの脅威。
　  1) 当たりの脅し。
　  2) 殺すための脅し。
    3) 生きるための脅し。
　I) 安全な手。（有利なとき）
　  1) 相手の手に応じる。（たとえそれが、死に石に石を付け足すような悪手に
　　　思えても）
　  2) 相手の石の安全な捕獲。
　  3) 大きな地を安全に。侵入から守るため。
　J) 無茶な手（不利な時）
　  1) 大きな１眼を持ち、取り囲まれた群を殺す手。
    2) いくらかの生きる可能性を持つ死んだ群を助ける手。
 　 3) 無茶な侵入をする手。
  K) ニューラルネット
　L) その他の学習技法。
　M) どのくらいの手を調べるか。(5手 [Intellect]、10手 [MFGO] 50手まで [Go4++])
　N) 手を、その大きさ、優先度、連絡によってソートする。
　O) 悪い手を無視すること。
　P) 時間節約のために、明確で大きな価値の手を素早く作る。


4) 局面全体の評価。
　A) 評価関数の要素。
　  1) 連。
　  2) 呼吸点の数。
　  3) 連の戦術的な安定性。
  　　A) 非常に速い戦術の探索エンジンが必要である。
 　 4) 連同士の接続。
  　　A) １間トビは実際に評価するのは困難である。
  　　B) 多くの場合、「切り」は可能だが良くはない。効果的な接続を。
  　　C) A が B と接続しており、 B が C と接続している事は、A が C と接続
  　　　している事を意味しない。
  　　D) 連結パターンのデータベース。
 　 5) 接続している（もしくは、すぐ近くの）群。
 　 6) 眼の数、安全な眼の空間
　　　A) 大きさの静的評価。部分的に囲まれた眼の評価は困難である。
  　　B) 眼の形状パターンのデータベース。
  　　C) 境界線のヒューリスティック。
 　 7) 自由度、または囲まれている度合い。
 　　 A) 大きな空いた領域へのアクセス。
  　　B) 隣りの相手の群との相対的な厚み。
 　 8) 群の強さ。
 　　 A) 中盤において、典型的な安定した群は２つの小さな眼は持たない。
　　  B) 近くの相手の群の相対的な強さに依存する。
　　  C) 囲まれている場合、２眼作れる能力。
　　  D) ２眼作れない場合、どこか有利な場所に逃げ出せる能力。
　　  E) ２眼持てるか、又は逃げ出せる場合、近くの敵を捕獲出来る能力。
　  9) アジ。厚い所と薄い所。
　 10) 模様。潜在的な地。
 　11) 安全な地。
　　  A) 生きている石から４方に広がる影響(influence)。
　　　　各点における自分と相手の勢力の比較。多くの影響関数がある。
　　    1) 影響は距離に反比例（1/距離）して低下する。
　　　　　（全ての石からの総和）( MFGO )
  　　  2) 影響は距離の２乗に反比例(1/距離^2)する。
          (全ての石からの総和）( Intellect )
  　　  3) 石がある点に高い値を割り当て、すぐ近くの点に対する影響の大部分
          を持つ各点に繰り返し突き当たる。( Goliath )
　　　  4) 石から石の繋がりまで、または敵の石まで境界線を延ばして行き、
          そして縮小する。
  　　B) 石の間の安全な結線を見つけ、結線で囲まれた内外の領域を見つける。
       （ Nemesis ）
　　　C) 各点において、敵が生きた石をここに置くことが可能かどうか。( Go4++ )
　 12) 中国ルール（MFGO）または日本ルールで数えるか。
　B) 高速化のために、どのくらい評価に差分（インクリメンタル）を用いるか。
　　1) ほとんどのプログラムは大部分が差分である。
　　2) 再評価や、再探索のために、どのくらい情報を保持するか。
　C) 評価は、次にどちらが打つか、に依存する。
　D) 評価の一部分としての部分的な死活探索の評価。
　E) 戦略の問題や手の選択の目標がどのように評価関数を変更するか。
　F) どのように地や、潜在的な地、そして群の強さを単一の数値に変換するか。
    又は、これらの単一な数値への変換を選ばないならば、どのように他の手段
    を探すか。
　H) 実際の善し悪しを評価する、又は、局所的な黒と白の手の間の差を評価する。


5) 探索戦略。
　A) 盤面全体から、指し手を選ぶために。
　  1) データベースからの手順（定石、布石、パターン）
　  2) 元の手の目標を継続する。
　  3) 静かな局面を目指して探索する。
　  4) 深さ優先のαβ法。
　  5) 深さと幅。
　B) 死活探索のために。
　  1) 探索の種類。
  　　a) 深さ優先のαβ法（ MFGO ）
  　　b) PN（Proof Number）探索。( New Goliath )
  　　c) その他。(未来のMFGO)
 　 2) キラーヒューリスティック。
      （ある局面での相手の好手が別の局面でも好手になりやすい）
　  3) 敵の急所が我が急所。
　  4) 深く、狭く読むか。又は、多くの手を力任せに読むか。
　  5) ルート(探索木の浅い部分）付近では多くの手を読む。
　  6) 最初だけではなく、第１層目では全ての手を探す。
　  7) ハッシュテーブル（ XORを利用した確率的盤面圧縮）
　  8) 有段クラスの実力が可能（ Gotools )
　  9) 手の生成・順序づけは不可欠。
　C) 連の戦術のために。
　  1) いくつの呼吸点があるか。（ 3,4,5 MFGO )
　  2) 呼吸点が増えるときと減るときに注目する。
　  3) すぐ近くの相手の連への攻撃、防御。
　  4) 非常に深い探索。50手か、それ以上。シチョウのために。
　  5) ２眼と簡単なセキの理解は必要。
 　 6) セキのために１手パスをする。
　  7) ルート付近では多くの手を読む。
　  8) 手の生成・順序づけは不可欠。
　D) 連絡のために
　  1) 決まり切った手順をチェック（こう打たれると場合、こう打つ）
　  2) 石を切断する状態のチェックのために戦術を使う。
　E) 時間の制御のために、どのように探索を制限するか。
　  1) コンピュータの手の選択のために一定の探索をする。
　  2) 戦いのために一定の探索をする。複雑な局面ではより時間をかける。( MFGO )
　F) 不確実性を扱う。

日本語訳：彩（ CXJ00674@niftyserve.or.jp ）
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
言葉の説明：
群( group )　 　　　　　　ゆるやかに連結した石の集団（死活の単位）
連( string ) 　　　　　　 縦横に繋がった石の集団
結線( linkage )　　　　　 石と石の連結具合
自由度( running ability ) 石の逃げ出せる可能性。
点( point )               格子点。石を置くところ。
呼吸点( liberty ) 　　 　 ダメやアキと同じ。
戦術( tactics )           局所的な戦いの技術。ゲタ、とか。
戦略( strategy )          長期的な方針