本稿は、D. B. Benson による "Life in the Game of Go" を自分なりに咀嚼して再構成したものである。 定理の証明は載せていないが、原論文を読むときの手がかり、あるいは、 コンピュータ碁プログラムの作成の一助となれば幸いである。

【点、状態、配置】

盤上、線と線が交わるところを 点 (point) と呼ぶ。 盤面全体の点の集合を P で表す。

原論文では、「交点 (intersection)」 と呼ばれている。

点は、黒石 (black )、 白石 (white )、または 目 (empty ) という 状態 (state) を持つ。 状態の集合を S で表す。

S  ＝  { black , white , empty }

盤面上の各点に対して状態を割り当てる関数を 配置関数 あるいは単に 配置 (arrangement) と呼び、 a で表す。

a : P → S

1手ごとの盤面の状態推移は、この配置関数の列によって表現される。

【隣接点】

点 p に対して縦または横に隣接している点を 隣接点 (adjacent point) と呼ぶ。 隣接点の集合を AP (p ) で、また、 隣接点に点 p 自身を加えた集合を AP+ (p ) で表わす。

┠┼┼┼┼┼┼┼┼
┠┼┼┼┼┼┼┼┼
┠┼┼┼ａ┼┼┼┼
┠┼┼ｂ●ｃ┼┼┼
┠┼┼┼ｄ┼┼┼┼
┠┼┼┼┼┼┼┼┼
┗┷┷┷┷┷┷┷┷

上図の ● の隣接点は、a, b, c, d の4点であり、

AP (●)  ＝  { a, b, c, d }
AP+ (●)  ＝  { a, b, c, d, ● }

となる。当然のことながら、辺や隅における隣接点の数は、それぞれ、3個と2個になる。

【領域】

領域 (region) とは点の連結集合である。すなわち、領域 R 内の任意の2点に対して、 R の部分集合で、縦横に隣接した2点間移動による経路となっているものが存在する。 領域の集合を Reg (P ) で表す。

Reg (P )  ＝  { R ⊆P | ∀p, q ∈R 、 ∃{p1, p2, ..., pn } ⊆R   [ p ＝p1 、 q ＝pn 、 pi + 1 ∈AP+ (pi ) ] }

とくに 1点からなる集合も領域である。 また、領域 R に属さない点の集合を ~R で表す。

~R  ＝  P −R

【内部、境界、外包】

領域 R 内の点 p に対して、p に隣接する点がすべて R に含まれるならば、p を R の 内点 と呼ぶ。 すべての内点の集合を 内部 (interior) と呼び、 Int (R ) で表す。

Int (R )  ＝  { p ∈R | AP (p ) ⊆R }

R −Int (R ) を R の 境界 (border) と呼び、 Brd (R ) で表す。

Brd (R )  ＝  R −Int (R )

R に含まれない点で、R 内のどれかの点に隣接するものを R の 外接点 と呼ぶ。 R の外接点の集合を R の 外包 (exterior) と呼び、 Ext (R ) で表す。

Ext (R )  ＝  { p ∈ ~R | AP (p )∩R  ≠ φ }

┼┼┼┼┼┼┼┼┼
┼┼┼┼○○┼┼┼
┼┼○○●●○┼┼
┼○●●・・●○┼
┼○●・・・●○┼
┼┼○●●・●○┼
┼┼┼○○●○┼┼
┼┼┼┼┼○┼┼┼
┼┼┼┼┼┼┼┼┼

上図において、● と ・ からなる領域を考えると、● が境界、・ が内部、○ が外包となる。

【連】

黒石のみ、もしくは白石のみからなる極大領域のことを 石連 または単に 連 (string) と呼ぶ。

原論文では、縦横に連接した石の集合のことを 「ブロック (block)」 と呼んでいるが、ここではコンピュータ囲碁の世界で一般的な用語と思われる 「連 (string)」 を使用した。

x を black または white とするとき、 x 石のすべての連の集合を Str (x ) と記述する。

Str (x )  ＝  { S ∈Reg (P ) | a (S ) ＝ { x }、 a (Ext (S )) ∩ { x }  ＝ φ }

┼┼┼┼┼┼┼┼┼
┼●┼○○○┼┼┼
┼●┼┼○┼○○┼
┼●●┼○┼○○┼
┼●┼●┼○┼┼┼
┼●●┼○○○┼┼
┷┷┷┷┷┷┷┷┷

上図において、Str (black ) には2個、 Str (white ) には3個の連が含まれている。

【呼吸点】

連 S の外包に属する点で、石が置かれていない、つまり目になっているものを S の呼吸点 (liberty) と呼ぶ。S の呼吸点の集合を Lib (S ) と記述する。

Lib (S )  ＝  { p ∈Ext (S ) | a (p ) ＝ empty }

┼┼┼┼┼┼┼┼┼
┼┼○○○○○┼┼
┼○●●●●●ｃ┼
┼○●ａ○ｂ●○┼
┼┼○●●●●○┼
┼┼┼○○○○┼┼
┷┷┷┷┷┷┷┷┷

上図において黒石の連の呼吸点は、a, b, c の3点である。

【 x の小閉域】

x を black または white とするとき、 x の小閉域 (small x -enclosed region) R とは次の3条件をみたすような領域のことである:

1. R には x 色の石が存在しない ;

   a (R ) ∩ { x } ＝ φ

2. R は x 色の石によって囲まれている ;

   a ( Ext (R ) ) ＝ { x }

3. R の任意の点は、R の境界であるか、x の敵石であるか、 またはその両方である。 すなわち、R の内部はすべて x の敵石でなければならない ;

   a ( Int (R ) ) ＝ { ~x }

x の小閉域の集合を SEReg (x ) で表す。

以前は、「小閉域」のことを「内領域」と呼んでいたが、名前を改めた。

┼┼┼┼┼┼┼┼┼┼    ┼┼┼┼┼┼┼┼┼┼
┼┼○○○○○○┼┼    ┼○○○○○○○┼┼
┼○●●●●●┼○┼    ┼○●●●●●┼○┼
┼○●○○○┼●○┼    ┼○●○┼○┼●○┼
┷○●○┷○○●○┷    ┷○●○○○○●○┷

上図左の黒で囲まれた領域は、内部に目が存在するので黒の小閉域ではない。 右は、黒の小閉域になっている。要するに小閉域とは、一方の石で囲まれた (閉じた) 領域であって、その内部に敵石によって囲まれた目を作ることができない領域のことである。

【 内呼吸点、外呼吸点】

x 石連 S の呼吸点 p がある x の小閉域に属しているとき、 p は S の 内呼吸点 (inside liberty) であるという。 S の内呼吸点の集合を InLib (S ) で表す。

内呼吸点以外の呼吸点を 外呼吸点 (outside liberty) という。 外呼吸点の集合を OutLib (S ) で表す。

┼┼┼┼┼┼┼┼┼┼    ┼┼┼┼┼┼┼┼┼┼
┼┼○○○○○○┼┼    ┼○○○○○○○┼┼
┼○●●●●●ｏ○┼    ┼○●●●●●ｏ○┼
┼○●○○○ｏ●○┼    ┼○●○ｉ○ｉ●○┼
┷○●○┷○○●○┷    ┷○●○○○○●○┷

上図において、i は内呼吸点、o は外呼吸点である。

【 健全領域】

x の小閉域 R について、 R 内の任意の目が連 S ∈Str (x ) の呼吸点になっている場合、 R は連 S に対して 健全 (healthy) である (または S に対する 健全領域 である) といい、 H (R, S ) と記述する。

H (R, S )  ⇔  R ∈SEReg (x )、 Emp (R ) ⊆ Lib (S )
(ただし、Emp (R ) は R に含まれる目の集合)

┼┼┼┼┼┼┼┼┼
┼┼┼○○○┼┼┼
┼○○●●○○┼┼
┼○●┼●●●○┼
┷○●ａ┷ｂ●○┷

上の図における黒の小閉域は、どちらの黒の連に対しても健全ではない。 (たとえば a は大きいほうの連の呼吸点になっていないし、 b は小さいほうの連の呼吸点になっていない)

┼┼┼┼┼┼┼┼┼
┼┼┼○○○┼┼┼
┼○○●●○○┼┼
┼○●┼●●●○┼
┷○●●┷ｂ●○┷

a に手を入れた上の図でも、b のほうは依然として左側の連に対して健全ではない。 ある連に対して健全な小閉域が高々1つしかない場合、 (味方がパスをすることによって) 敵に連続して石を置かれるとその連は取られてしまう。

┼┼┼┼┼┼┼┼┼
┼┼┼○○○┼┼┼
┼○○●●○○┼┼
┼○●２●●●○┼
┷○●●１┷●○┷

白に 1、2 の順で石を置かれると左側の黒石連は取られてしまう。

【近傍連】

領域 R に対して、 x 石連 S の外包の一部(または全部)が R に含まれるとき、 S を R の x 近傍連 (neighboring string) という。 R のすべての x 近傍連の集合を NS (R, x ) で表す。

NS (R, x )  ＝  { S ∈Str (x ) | Ext (S )∩R ≠φ }

とくに石色 x を明示する必要のない場合は、 たんに NS (R ) と記述することもある。

【活性領域】

X を x 石連の集合とする。 X に属する連 S に対して健全な x の小閉域 R が存在し、 R の近傍連がすべて X に属しているとき、 領域 R は X の元 S に対して活性的 (vital) である (または S に対する 活性領域 である) といい、 V (R, S, X ) と記述する。

V (R, S, X )  ⇔  X ⊆ Str (x )、S ∈ X、 R ∈Reg (P ) に対して、 H (R, S ) かつ NS (R ) ⊆ X

┼┼┼┼┼┼┼┼┼
┼┼┼○○○┼┼┼
┼○○●●○○┼┼
┼○●┼●●●○┼
┷○●●┷┷●○┷

上図の2つの黒石連の集合において、左側1目の小閉域は左側3子の黒石連に対して活性的である (同小閉域は同石連に対して健全であり、同小閉域の近傍連はともに黒石連集合の要素であるから) が、右側2目の小閉域は同石連に対して活性的ではない。

【無条件活き】

x 石連 の集合 X について、 X に属する任意の連に対して相異なる 2つの活性領域が存在するとき、 X は無条件活き (unconditionally alive) であるという。

上の図は無条件活きではないが、

┼┼┼┼┼┼┼┼┼      ┼┼┼┼┼┼┼┼┼┼
┼┼┼○○○┼┼┼      ┼┼┼┼○○○┼┼┼
┼○○●●○○┼┼      ┼○○○●●○○┼┼
┼○●┼●●●○┼      ┼○●●┼●●●○┼
┷○●●┷○●○┷      ┷○●┷●┷┷●○┷

は無条件活きである。

【安全な連】

S を x 石連とする。 敵石の (着手禁止点を除く) 任意の手の列に対し、x が自分の手番をすべてパスしても S が補獲されずに残っているとき、S は安全 (safe) であるという。

【定理】

x 石連の集合 X が無条件活きならば、 X に属する任意の連は安全である。

【定理】

X がすべての安全な x 石連の集合であるならば、 X は無条件活きである。

【領域連結性】

x 石連 S₁ と S₂ について、ある x の小閉域 R が存在して両連が R の近傍になっている、 つまり、

{ S₁, S₂ } ⊆ NS (R )

のとき、S₁ と S₂ は結合 (joined) しているという。

┼┼┼┼┼┼┼┼┼
┼┼┼┼┼┼┼┼┼
┼┼●●●┼┼┼┼
┼┼●○┼●●┼┼
┼┼●┼○┼●┼┼
┼┼●┼○○●┼┼
┼┼┼●●●┼┼┼
┼┼┼┼┼┼┼┼┼

上図で3つの黒石連に囲まれた領域は黒の小閉域であり、3連ともその小閉域の近傍となっている。 したがって、3連のうちどの2連をとってもそれらは結合していることになる。

連 S を含む結合関係による閉包、すなわち、 結合関係の連鎖によって到達できるすべての連の集合を [S ] と記述する。

[S ] ⊆ Str (x )

また、Y ⊆ Str (x ) に対して、 Y の閉包を [Y ] と記述する。

[Y ] ＝ ∪ { [S ] | S ∈ Y }

【台】

Y ⊆ Str (x ) に対して、X ⊆ [Y ] となる最大の無条件活き連集合 X を考える。 このとき、X ∩Y を Y の 台 (support) と呼び、Supp (Y ) で表す。 Y に属する任意の安全な連は、Supp (Y ) にも含まれる。

【アルゴリズム】

Z₀ ＝ [Y ]、 R₀ ＝ { R ∈SEReg (x ) | NS (R ) ⊆ [Y ] } とする。
i ≧ 0 に対し、Z_i に属する連のうち、 R_i に属する健全な領域を2つ持つような連をすべて集めたものを Z_{i + 1} とする。

Zi + 1 ＝ { S ∈ Zi | 相異なる2つの領域 Q, R ∈ Ri が存在して、 H (Q, S ) かつ H (R, S ) }

R_{i + 1} は、 その近傍連が Z_{i + 1} に含まれているような x の小閉域の集合とする。

Ri + 1 ＝ { R ∈SEReg (x ) | NS (R ) ⊆ Zi + 1 }

【定理】

Z を 上の列 Z_i の不動点、 すなわち、Z ＝ Z_n かつ Z_n = Z_{n + 1} とする。このとき、 Z は [Y ] に含まれる最大の無条件活き連集合となる。

【系】

Supp (Y ) ＝ Y ∩ Z かつ Z ＝ Supp ( [Y ] )