グラフ理論を用いた囲碁 数式一覧

黒石または空点

黒石を表す2進(列)ベクトルです。単に黒石のところが 1 というだけでなく、空点も 1 になっていて、白石のところだけが 0 です。$(\boldsymbol{v})_i$ はベクトル $\boldsymbol{v}$ の $i$ 番目の要素を示します。 $$(\boldsymbol{b})_i = \begin{cases} 1 & i \; \text{is black or empty} \\ 0 & i \; \text{is white} \end{cases} \tag{1-1} $$ 例えば3路盤の場合、ベクトルの要素は$3 \times 3=9$個で、$i$ は 1 から 9 の値を取り、交点を表します。3路盤の初期局面ではすべての交点が空点なので $\boldsymbol{b}$ の要素はすべて 1 となり、 $$ \boldsymbol{b} = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} $$ となります。

白石または空点

黒石と同様に白石を表します。 $$(\boldsymbol{w})_i = \begin{cases} 1 & i \; \text{is white or empty} \\ 0 & i \; \text{is black} \end{cases} \tag{1-2} $$

空点

空点は $\boldsymbol{b}$ と $\boldsymbol{w}$ から求めることができます。 $$ \boldsymbol{l} = \boldsymbol{b} \wedge \boldsymbol{w} \tag{2} $$ 逆に黒石のみの点は $\boldsymbol{b} - \boldsymbol{l} = \boldsymbol{1} - \boldsymbol{w} = \overline{\boldsymbol{w}}$ で表せます。

隣接点

交点 $i$ に隣接する点と $i$ 自身を示す2進行列です。碁盤の形状を表しています。$_i N _j$ は $i$ が $j$ と等しいか、$i$ と $j$ が隣接している隣接関係を表します。$F_0$ において行 $i$ と列 $j$ を入れ替えても変わらないので、$F_0$ は対称行列です。 $$(F_0)_{ij} = \begin{cases} 1 & _i N _j \\ 0 & \text{otherwise} \end{cases} \tag{3} $$ 3路盤の場合、 $$ F_0 = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix} $$ となります。

連接点

交点 $i$ に連接する点と $i$ 自身を示す行列です。盤上の連を表しています。連とは隣接する同じ色の石の集合です。$_i M _j$ は $i$ が $j$ と等しいか、$i$ と $j$ が同じ連に含まれる連関係を表します。空点は各点が独立して連関係を満たします。下記の定義において $(F)_{ij}=1$ のとき $j$ は $i$ に連接するといいます。このとき、$i$ が着点ならば、$j$ は $i$ の連に含まれる石かその連に隣接する点で、$i$ が空点ならば、$j$ は $i$ に隣接する点です。この行列は連ができるごとに変化していきます。盤面に2子以上の連が1つもない場合、$F = F_0$ となります。$F_0$ が対称行列であるのに対し、$F$ は対称行列であるとは限りません。 $$(F)_{ij} = \begin{cases} 1 & ^\exists k; (_i M _k \; \text{and} \; _k N _j) \\ 0 & \text{otherwise} \end{cases} \tag{4} $$

アタリ

アタリになっている石を表すベクトルです。$^t F$ は行列 $F$ の転置(行と列を入れ替えたもの)、$\boldsymbol{e}_i$ は要素 $i$ のみが 1 の単位行列を表します。また、ベクトル $v$ の中の 1 になっている要素の数をベクトル $v$ の絶対値と呼び、$\left| v \right|$ で表します。なお、$^t M \boldsymbol{e}_i$ で行列 $M$ の $i$ 行目をベクトルとして取り出せます。したがって、$^t F \boldsymbol{e}_i \wedge \boldsymbol{l}$ は石 $i$ の活路を表し、$\left|^t F \boldsymbol{e}_i \wedge \boldsymbol{l} \right|$ はその数を表します。 $$(\boldsymbol{h})_i = \begin{cases} 1 & \left|^t F \boldsymbol{e}_i \wedge \boldsymbol{l} \right| =1\\ 0 & \text{otherwise} \end{cases} \tag{5} $$

$i$に着手してできる連

$i$ に着手したことによりできる連を示します。この結果は式(9)で新たな連接点行列 $F$ を求める際に利用されます。添字 $t$ は、$t$ 手目の着手後の局面での値であることを示しています。したがって $t=0$ の場合は初期局面です。$t$ is even ($t$ が偶数)および $t$ is odd ($t$ が奇数)はそれぞれ黒番、白番を表しています。なお黒が先手であることを前提としています。黒番の場合、 $F_t \boldsymbol{e}_i - \boldsymbol{w}_t$ は着点 $i$ を連接点とする黒石で、それに着点 $\boldsymbol{e}_i$ を加えて $i$ に着手した後の黒石の連を求めています。 $$ \boldsymbol{a}_t(i) = \begin{cases} F_t \boldsymbol{e}_i - \boldsymbol{w}_t \vee \boldsymbol{e}_i & t \; \text{is even} \\ F_t \boldsymbol{e}_i - \boldsymbol{b}_t \vee \boldsymbol{e}_i & t \; \text{is odd} \end{cases} \tag{6} $$

$i$に着手し取られる連

$i$ に着手したことにより取られてしまう石を示します。この結果は式(8-1)、(8-2)、(9)の新たな $\boldsymbol{b}, \boldsymbol{w}, F$ を求める際に利用されます。黒番の場合、 $F_t \boldsymbol{e}_i \wedge \boldsymbol{h}_t-\boldsymbol{b}_t$ は着点 $i$ を連接点とする敵(白石)のアタリの連を表します。この式は囲碁の取りのルールを表しています。 $$ \boldsymbol{d}_t(i) = \begin{cases} F_t \boldsymbol{e}_i \wedge \boldsymbol{h}_t - \boldsymbol{b}_t & t \; \text{is even} \\ F_t \boldsymbol{e}_i \wedge \boldsymbol{h}_t - \boldsymbol{w}_t & t \; \text{is odd} \end{cases} \tag{7} $$

新たな黒石または空点（黒石または空点の差分計算）

$t+1$ 手目で $i$ に着手した後の黒石または空点は次式で表すことができます。黒番では取られた白石を 1 にし、白番では打たれた白石を 0 にします。式(8-1)、(8-2)、(9)によって新たな局面が求められます。 $$\boldsymbol{b}_{t+1} = \begin{cases} \boldsymbol{b}_t \vee \boldsymbol{d}_t(i) & t \; \text{is even} \\ \boldsymbol{b}_t - \boldsymbol{e}_i & t \; \text{is odd} \end{cases} \tag{8-1} $$

新たな白石または空点（白石または空点の差分計算）

同様に $t+1$ 手目で $i$ に着手した後の白石または空点は次式で表すことができます。 $$\boldsymbol{w}_{t+1} = \begin{cases} \boldsymbol{w}_t - \boldsymbol{e}_i & t \; \text{is even} \\ \boldsymbol{w}_t \vee \boldsymbol{d}_t(i) & t \; \text{is odd} \end{cases} \tag{8-2} $$

新たな連接点（連接点の差分計算）

$t+1$ 手目で $i$ に着手した後の連接点行列 $F$ は次式で表すことができます。$A$ は、$i$ の連の要素に対応する行が着手後の $i$ の連接点で、それ以外の行がすべて0の行列です。$F_t$ と論理和をとることで新たな連接点が追加されます。$D$ は、$i$ への着手で取られた石の要素に対応する行が初期局面 $F_0$ と同じで、それ以外の行がすべて1の行列です。$F_t$ と論理積をとることで取られた石によって解消された連を初期状態に戻します。 $$\begin{align} F_{t+1} = & F_t \vee A \wedge D \\[3pt] \text{while} \\ A = & \boldsymbol{a}_t(i)(^t \boldsymbol{a}_t(i) F_t) \\ D = & F_0 \vee (\overline{\boldsymbol{d}_t(i)} \; ^t \boldsymbol{1}) \end{align} \tag{9} $$

着手可能点

着手可能点は以下の式で表せます。黒番の場合、$\boldsymbol{b}_t \oplus \boldsymbol{h}_t$ は空点または黒石でアタリでない石または白石でアタリの石を示し、着手可能点はそのいずれかに連接する空点です。 逆に言えば空点でも黒石のアタリの石(自殺手)か白石のアタリでない石(白石は取れない)のどちらかにしか連接していない点には着手できません。 この式は囲碁の着手禁止ルールを表しています。ただしコウなどの反復禁止については考慮されていません。 $$ \begin{align} F_t(\boldsymbol{b}_t \oplus \boldsymbol{h}_t) \wedge \boldsymbol{l}_t & \quad t \; \text{is even} \\ F_t(\boldsymbol{w}_t \oplus \boldsymbol{h}_t) \wedge \boldsymbol{l}_t & \quad t \; \text{is odd} \end{align} \tag{10-1} $$

数え上げ関数

これは式(5)のアタリを表すベクトルを一般化したものです。$k=2$のときはアタリ(および取られる石)を表します。 $$ (\boldsymbol{p}(k))_i = \begin{cases} 1 & \left|^t F \boldsymbol{e}_i \wedge \boldsymbol{l} \right| \lt k \\ 0 & \text{otherwise} \end{cases} \tag{11} $$

コウ（劫）

『コンピュータ囲碁の入門』^[2]のコウを求めるアルゴリズムを BWモデル に適用しました。この式は $t$ 手目で交点 $i$ に着手した結果、$t+1$ 手目にコウがあるかどうかを表しています。 黒番の場合、$\left| F_0 \boldsymbol{e}_i - \boldsymbol{e}_i \wedge \boldsymbol{b_t} \right| = 0$ は着手した点が白石に囲まれていることを表し、 $\left| \boldsymbol{d}_t(i) \right| = 1$ はそこに打って1子だけ取れたことを表します。 $$ \boldsymbol{k}_{t+1} = \begin{cases} \boldsymbol{d}_t(i) & \quad ( t \; \text{is even} \; \text{and} \; \left| F_0 \boldsymbol{e}_i - \boldsymbol{e}_i \wedge \boldsymbol{b_t} \right| = 0 \;　\text{or} \\ & \quad t \; \text{is odd} \; \text{and} \; \left| F_0 \boldsymbol{e}_i - \boldsymbol{e}_i \wedge \boldsymbol{w_t} \right| = 0 ) \;　\text{and} \\ &　\left| \boldsymbol{d}_t(i) \right| = 1 \\ \boldsymbol{0} & \quad \text{otherwise} \end{cases} \tag{12} $$

着手可能点（コウを考慮）

着手可能点の式に、コウを盛り込みました。ただし単純なコウ以外の反復禁止については考慮されていません。 $$ \begin{align} F_t(\boldsymbol{b}_t \oplus \boldsymbol{h}_t) \wedge \boldsymbol{l}_t - \boldsymbol{k}_t & \quad t \; \text{is even} \\ F_t(\boldsymbol{w}_t \oplus \boldsymbol{h}_t) \wedge \boldsymbol{l}_t - \boldsymbol{k}_t & \quad t \; \text{is odd} \end{align} \tag{10-2} $$

活路 (liberty)

Javaアプレット GraphGo の開発時には、『日本囲碁規約』^[3]の記述にしたがって、活き石、セキ石、死に石、目、地、ダメの6つのベクトルを定義しました。 しかしながら活き石は数式で定義できず、他のベクトルは活き石を使って定義されており、うまく機能しませんでした。これは、序盤で死活を判定できないことによります。 囲碁において死活を判定しない方法としては、死に石を打ち上げるまで対局を続ける方法があります。その局面になり、ダメも埋めれば、この6つのベクトルは活き石 = 盤上の石、セキ石 = なし、死に石 = なし、ダメ = なし、目 = 地 = 活路となります。そこで当面は6ベクトルの代わりに活路を計算し、最終的に地と等しくなるので、その近似値として扱っていこうと思います。 黒の活路を $\boldsymbol{i}_b$ 、白の活路を $\boldsymbol{i}_w$ と定義することにします。 $$ \boldsymbol{i}_b = \, ^t F \, \overline{\boldsymbol{w}} \wedge \boldsymbol{l} \tag{13-1} $$ $$ \boldsymbol{i}_w = \, ^t F \, \overline{\boldsymbol{b}} \wedge \boldsymbol{l} \tag{13-2} $$

プレイアウトのための着手禁止点 (restricted points for playout)

囲碁のシミュレーション時、単純にルール上打てるところにランダムに打っていくと、自分の眼を埋めて相手に取られるということをお互いに繰り返してしまいます。 これを避けるためには、少なくとも自分の一目の眼には打たないようにする必要があります。ただし、その眼を囲む石にアタリがある場合は打てるようにします。 $\boldsymbol{r}_b$ と $\boldsymbol{r}_w$ は黒と白の着手禁止点を表します。黒の場合、 $(F_0 \, \boldsymbol{e}_i - \boldsymbol{e}_i) \subseteq (\overline{\boldsymbol{w}} - \boldsymbol{h})$ はその点を囲む点がアタリでない黒石（自石）に囲まれていることを表しています。 なお、交点の集合 $\boldsymbol{a}, \boldsymbol{b}$ に $\boldsymbol{a} - \boldsymbol{b} = \boldsymbol{0}$ の関係が成り立つとき $\boldsymbol{a}$ は $\boldsymbol{b}$ の部分集合になり、 $\boldsymbol{a} \subseteq \boldsymbol{b}$ と書きます。 $$ (\boldsymbol{r}_b)_i = \begin{cases} 1 & (F_0 \, \boldsymbol{e}_i - \boldsymbol{e}_i) \subseteq (\overline{\boldsymbol{w}} - \boldsymbol{h}) \\ 0 & \text{otherwise} \end{cases} \tag{14-1} $$ $$ (\boldsymbol{r}_w)_i = \begin{cases} 1 & (F_0 \, \boldsymbol{e}_i - \boldsymbol{e}_i) \subseteq (\overline{\boldsymbol{b}} - \boldsymbol{h}) \\ 0 & \text{otherwise} \end{cases} \tag{14-2} $$

着手可能点（プレイアウト実行時）

着手可能点の式にコウの他にさらに自石の眼を埋めないよう変更したものです。プレイアウト実行時にはこの式を使って着手可能かどうかを決めます。 $$ \begin{align} F_t(\boldsymbol{b}_t \oplus \boldsymbol{h}_t) \wedge \boldsymbol{l}_t - \boldsymbol{k}_t - \boldsymbol{r}_b & \quad t \; \text{is even} \\ F_t(\boldsymbol{w}_t \oplus \boldsymbol{h}_t) \wedge \boldsymbol{l}_t - \boldsymbol{k}_t - \boldsymbol{r}_w & \quad t \; \text{is odd} \end{align} \tag{10-3} $$