The 19th Annual Conference of the Japanese Society for Artiﬁcial Intelligence, 2005

1A1-03

空間分節化による注意決定の囲碁への適用
Attention by Space Segmentation in Computer-Go∗1

高濱 昌孝∗1大沢 英一∗2

Masataka Takahama

Ei-ichi Osawa

公立はこだて未来大学システム情報科学研究科

Graduate School of System Information Science, Future University–Hakodate∗2

公立はこだて未来大学システム情報科学部情報アーキテクチャ学科
Department of Media Architecture, Future University–Hakodate

The major problems in computer-Go include the size of its search space and the complexity of evaluation ofgames. These two problem lead to hardness of estimating accurate and eﬀective move in various game situation.
On the other hand, recent studies in the limited and small games found various kind of eﬀective game strategies. If
a computer-Go program can successfully divide an entire game into several groups of smaller game, it will be able
to utilize already developed strategies for smaller games. In this paper, we propose a method for dividing a gameinto several smaller segments, and an attention method with which the program can identify the most importantsegment.

1.

はじめに１

コンピュータに囲碁をプレイさせることは，人工知能研究の良い題材であるとされ，盛んに研究されている．しかし，現在もっとも強いプログラムでもアマチュア初段程度である [1]．
コンピュータ囲碁における最大の問題は，探索空間の大きさと，局面の評価の難しさであり，これらに対する有効な解決法は，いまだ発見されていない．
囲碁における探索空間の大きさは，チェスなどの他のゲームなどと比較しても相当大きく（チェスは 10120 オーダで囲碁は10360 オーダと言われている），よく知られている効率の良いアルゴリズムを適用しても，正しい着手を生成することができない局面が非常に多い．そして，そのような局面は，特に中盤に多く見受けられる．
局面の評価については，いくつかの限定された問題においては，ある程度うまく解決できているものが存在する．例えば，布石に関しては，定石のデータベースを利用した，人間に近い着手が可能となっている [2]．ヨセに関して言えば，Berlekamp
らによって組合せゲーム理論を適用した数理的な解析がなされている [3]．さらに，局所的な盤面に関しては，詰め碁を解くプログラムなどの探索を主とした方法 [4] や，パターン認識による方法 [5] によって有効な手が生成できる．
そこで，盤面をそのような部分問題に分割することで，うまく問題を解決できると考えられる．しかしながら，囲碁では盤面を完全に分割することが困難であり，それによって適切な評価が難しくなっている．それでも，もし，ある局面において最も注目すべき盤面の部分が固定可能なら，探索空間を限定でき，より適切な盤面の評価を得ることができると考えられる．
本稿では，問題空間を限定する手法として注意を取り上げ，囲碁を題材に局面の分節化と注意決定のメカニズムについて考察する．

2.

２３ ３

４５ ５

図 1: 注意決定の例
ニズムについて述べる．

2.1

概念

本稿で提案する注意決定の流れを説明する．この注意決定とは，座標系を持つ空間から，ある 1 点を選び出すような問題に対して，その空間を何らかの方法で分節化し，選び出す 1点が存在する空間を決定することである。
囲碁における注意決定について説明する．まず，盤面を複数に分節化する．このとき，囲碁ではゲームの特性上，盤面を完全には分割できないので [6]，複数の部分盤面で重複する点が存在することになる．次に，各部分盤面ごとに注意決定に必要な要素を計算する（注意に必要な要素については，次節で例をあげる）．そして，計算された要素に基づいて注意決定を行い，その後は注意された部分盤面に着手するか，または，注意を一つの着手決定への目安として扱うことになる．図 1 は注意の例で，この図では右下の楕円で囲まれた部分に注意を向けている∗1 ．

分節化と注意決定2.2

盤面の分節化

本節では囲碁における盤面の分節化の手法と，分節化された各々の部分盤面を評価し，着手する部分盤面を決定するメカ

ここでは分節化の方法の一つとして「群」と，その「影響力」を基準とした分節化を提案する．ここで言う群とは，コン連絡先: 高濱 昌孝, 公立はこだて未来大学 システム情報科学研究科知能情報科学領域専攻, g2104027@fun.ac.jp∗1 この図の注意は筆者が作成したもので，プログラムから提示された注意決定ではない．

1

The 19th Annual Conference of the Japanese Society for Artiﬁcial Intelligence, 2005

2.3

BA A

AAA

部分盤面の注意に必要な要素の計算

分節化された各部分盤面について，注意決定に必要だと考えられる要素について考察する．
まず，注意すべき場所を決定するということは，着手すべき場所を発見するということであるので，少なくとも着手に必要なクリティカルな要素は計算する必要がある．そのような要素には，生き死にの探索と攻め合いの解析が必要となる．しかし，計算コストをなるべく抑えるために，これらを求めるアルゴリズムは単純な探索ではなく，状態を分類して計算するような，工夫されたものであるべきで，具体的には Benson のアルゴリズム [8] や Muller の手法 [9] が参考になる．その他，計算コストの小さい要素についても，必要なものとして積極的に取り入れていくことが望ましい．
これらの要素は，例えば次のような手順で計算することになる．まず [10] のように眼形を認識する．次に石や群の生き死にを，眼形による分類や Benson のアルゴリズム [8]，攻め合いの解析 [9]，探索によるシチョウの判断などから計算する．
また，石や群の安定の度合いや働きを表す，群の強さもこのように計算する．そして，群の強さを反映した影響力を計算し，地合いの見積もりとする．
各部分盤面ごとに計算した要素から，その部分に着手することが，どのような意味を持つのかを解析することは，注意決定時に役に立つと考えられる．なぜなら，ある盤面の状況が分かり，その状況に適した戦略や目標が明確にあるならば，その戦略や目標に適した部分盤面に着手するのが自然であり，それには各部分の着手の意味が重要だからである．もしもその状況に適切な部分に注意したのならば，それは目標や戦略に沿っている注意だということになる．
「その部分盤面が持つ意味」と，「全体の状況から発生した目標や戦略」が一致するかどうかの確認を容易にするために，これらは同じ表現であることが望ましい．

C

図 2: 分節化に用いる認識の例
ピュータ囲碁で使われる一般的な概念であり，直接つながってはいないが，非常に近くにまとまっている同じ色の石の集合のことである．さらに本稿では，群を，直接つながってはいないが，事実上連絡している「連」の集合とする．連とは，直接つながっている同じ色の石の集合のことである．例えば，図 1 の右上では，同じ数字が振ってある黒石がそれぞれ一つの連で，数字の振ってあるすべての黒石が一つの群である．また，本稿で言う影響力とは，一般的に言うポテンシャルや勢力のことで，石が周りの座標に及ぼす影響のことである．
群を認識するためには，連の他に，石の連絡を表す「結線」を認識しなければならない．結線を認識するためには．探索やパターン認識，ポテンシャルなどを用いる方法が知られている [7]．図 2 では，A と書かれた白石の結線が太い線で表され，それらが一つの群をなしている（つまり，楕円で囲まれた部分の白石すべてで一つの群となっている）．
群を認識したら，つぎに各群の影響力を計算する．影響力の計算については，単純に各石から一定距離の範囲内へと発するものや，囲碁における石の働きの度合いにより，発する距離が異なるものなどが考えられる．本稿で提案する囲碁における注意決定では，群の影響力がぶつかり合っている点を用いて「関係」を考慮する．群の関係は，違う色の群の間でしか存在しないものではなく，同じ色の石の間にも存在することが望ましい．また，隣り合う，違う色の群の間にも関係が存在することに気をつけなければならない．
そして，関係する群同士をひとつの部分盤面として認識する．関係から部分盤面を認識する方法には，(1) 一つの群に対して，それ自身と，関係するすべての群を用いて，一つの部分盤面として認識する方法，(2) 一つの群に対して，それ自身と，関係する（すべてではない）複数の群を用いて，一つの部分盤面として認識する方法，(3) 一つの群に対して，それ自身と，関係する一つの群を用いて，一つの部分盤面として認識する方法，などが考えられる．いずれにせよ，この方法を用いると，結果的に複数の部分盤面に属する点が存在する可能性が出てくる．図 2 では，黒と白のそれぞれの色の小さな四角形で示された点がそれぞれの色の群の影響力で，白の三角形で示された点が白の異なる群の影響力がぶつかり合っている点，バツ印で示された点が異なる黒と白の群の影響力がぶつかり合っている点となっている．
すべての群の関係について考慮したならば，最後に，群にも影響力の及ぶ点にも分類されない空点が残ることになる．これらについては，後述する注意決定のための要素の計算を考慮して，連続している空点を，その周りにある群の一部を含めた形で，ひとつの部分盤面として認識するのが良いと考えられる．

2.4

注意決定

注意は，分節化された部分盤面に対して，何らかの方法で評価値を生成し，それを基準として特定の部分盤面を選び出すという方法で実装される．
注意決定では，全体の状況を判断した結果と，前述した各部分盤面のその部分に着手することの意味との比較が重要になる．ここで言う状況とは，例えば形勢はどちらに有利か，何目の差があるか，戦いの最中であるか，などである．
この状況を認識するには，各部分盤面について計算した結果（要素）を用いることもできるが，新たに計算する要素が存在するかもしれない．もしも状況が正しく認識でき，盤面全体の目標や戦略が決まるのならば，それ以前の盤面で生成された目標や戦略を考慮することによって，コンピュータ囲碁が抱える問題のひとつである，目標の持続性の問題を解決できる可能性がある．盤面全体の目標は，例えば生き死にや群の強さ，地合いなどから決める．もし生き死にに関わるような場所があれば，その場所を殺す，または助けるように目標を決定する．
評価値は，部分盤面ごとの評価要素に，ある重み（パラメータ）を掛け合わせ，それらの和で計算する（重み付け線形関数[11]）．そのとき，大きな地の増減に関わる部分などの重要な要素や，群の生き死にに関わるような要素，またはそれらと同じように囲碁において重要な部分に関わるものには，大きい値のパラメータが設定されるべきである．これらのパラメータの調整については今後の課題であるが，それは製作者の経験や勘で設定されるか，各種学習アルゴリズムによって設定されることになる．また，パラメータが目標や局面の状況によって動的に変化することで，より柔軟な注意決定が実現できることが期

2

The 19th Annual Conference of the Japanese Society for Artiﬁcial Intelligence, 2005
待される．パラメータが決まったならば，評価関数が出した評価値に従って注意する部分盤面を決定する．

2.5

3.3

注意決定の課題

正しい注意決定には，分節化された部分盤面の注意に必要な要素の正しい計算結果のほかに，重み付け線形関数，およびそれに代わる関数のなかの適切な要素の係数（パラメータ）の設定が必要になる．適切なパラメータを設定するには，プロの棋譜を教師信号とした学習を適用することも視野に入れるべきである．

注意を用いた囲碁プログラムの構成

一般的な囲碁プログラムでは，着手を次のように決定する[12]．

1. 盤面の認識
2. 戦略の評価

4.

3. 候補手の生成

本稿では，注意決定と盤面の分節化について提案し，注意決定の利点や問題点について考察した．本稿で述べた内容については，現在，我々が作成している囲碁プログラムに実装中である．今後は，これらの実装を終え，評価・改善を繰り返していく．

4. 最善手の決定（候補手の評価）本稿で提案する注意決定を用いた着手決定は次のような手順を想定している．

1. 盤面の認識
2. 盤面の分節化

参考文献

3. 戦略の評価[1] 佐々木宣介, 清愼一, 中村貞吾. 囲碁. 情報処理, Vol. 44,
No. 9, pp. 910–915, September 2003.

4. 注意決定
5. 候補手の生成[2] 斉藤康己. 囲碁 これからは囲碁プログラミングが面白い. 松原仁, 竹内郁雄（編）, ゲームプログラミング, pp.
59–72. 共立出版, 1998.

6. 最善手の決定（候補手の評価）
注意決定を候補手の生成の限定に用いるならば，生成される候補手が減少し，最善手の生成のための計算コストが抑えられると考えられる．その際，盤面の分節化や注意決定のコストが大きくならないように気をつける必要がある．

3.

[3] E. Berlekamp and J. H. Conway. Winning Ways – foryour Mathematical Plays –. Academic Press, 1982.
[4] T. Wolf. The Program GoTools and its computergenerated tsumego database. ゲーム・プログラミング
ワークショップ’94, pp. 84–96, 1994.

課題と考察

囲碁において，盤面を分節化してから注意決定を行い，探索空間を削減するには，克服しなければならない様々な問題の発生が予想される．ここでは，それらの課題の詳細をあげ，考察する．

3.1[5] 清愼一, 川嶋俊明. 記憶に基づく推論を使った囲碁プロ
グラム「勝也」の試作. ゲーム・プログラミング ワー
クショップ’96, pp. 115–122, September 1996. the 3rdGame Programming Workshop.

適切な空間分節化[6] J.S. Reitman. Skilled Perception in Go. Cognitive Psychology, Vol. 8, pp. 336–356, 1976.

分節化の適切さを数量的に評価することは難しい．理由として，人間の強いプレイヤーは部分盤面を長期記憶にあるパターンや経験などから捕らえていると考えられており [13]，それは記述することが困難であることがあげられる．また，人間の思考に合った分節化が，必ずしもコンピュータにとって有効なものとは言えないこともあげられる．しかしながら，もし分節化の段階で適切さを評価しなければならないのならば，現状での基準は人間の感覚に頼らざるを得ない．

3.2

まとめ[7] 清愼一, 佐々木宣介. 囲碁プログラミング講習会 〜
マニュアル（その 2）〜, 2004. 岐阜チャレンジ 2004
囲碁プログラミング講習会資料 http://www.computergo.jp/gifu2004/event/pdf/cgf200406.pdf.
[8] D.B Benson. Life in the Game of Go. Information
Sciences, Vol. 10, pp. 17–29, 1976.

部分盤面の要素の計算

適切な注意決定には，評価関数のパラメータよりも計算された要素の種類や質のほうが大切かもしれない．しかし，我々が欲する要素をすべて計算させることは，コストを考えた上では現実的でない．たとえ部分盤面の要素を時系列に沿って保持したとしても，すべての要素を計算により得ることは現実的ではない．囲碁における質の高い着手の要素は，計算コストが高いものが多い．そのようなときには，パターン認識などを用いて効率的に要素の値の近似値を計算するなど，多少の工夫が必要になる．
囲碁の盤面を分節化しても，それぞれの部分盤面にとって，近くのほかの部分盤面の状態は無視できず，完全に独立なものとして考えることはできない．このようなときは，単一の部分盤面にとらわれず，盤面全体を考慮することが望ましい．しかし，そのときの計算コストには気をつける必要がある．

[9] Martin Muller. Race to Capture: Analyzing Semeaiin Go. Game Programming Workshop in Japan’99,Vol. 99, No. 14, 1999.
[10] David Fotland. Static Eye in ”The Many Faces of Go”.
ICGA Journal, Vol. 25, No. 4, December 2002.
[11] Stuart Russell and Peter Norvig. エージェントアプロー
チ 人工知能. 共立出版, 1997. 古川康一 監訳.
[12] DavidFotland.
コ ン ピュー タ 囲
碁 設 計 の 問 題,
1996.
訳：山 下 宏,URL:http://www32.ocn.ne.jp/˜yss/mfgshort.txt.

3

The 19th Annual Conference of the Japanese Society for Artiﬁcial Intelligence, 2005[13] 吉川厚. ゲームプログラミングと認知科学. 松原仁, 竹内郁雄（編）, ゲームプログラミング, pp. 207–219. 共立出版, 1998.

4