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

黒石∨空点

黒石を表す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$ 行目をベクトルとして取り出せます。 $$(\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_0 \boldsymbol{e}_i - \boldsymbol{w}_t$ は着点 $i$ に隣接する黒石、$^t F_t(F_0 \boldsymbol{e}_i - \boldsymbol{w}_t)$ はその連接点、$^t F_t(F_0 \boldsymbol{e}_i - \boldsymbol{w}_t)-\boldsymbol{w}_t \vee \boldsymbol{e}_i$ は着点 $i$ に隣接する黒石の連接点から白石と $i$ 以外の空点を除いたもの、すなわち $i$ に着手した後の黒石の連になります。 $$ \boldsymbol{a}_t(i) = \begin{cases} ^t F_t(F_0 \boldsymbol{e}_i - \boldsymbol{w}_t)-\boldsymbol{w}_t \vee \boldsymbol{e}_i & t \; \text{is even} \\ ^t F_t(F_0 \boldsymbol{e}_i - \boldsymbol{b}_t)-\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_0 \boldsymbol{e}_i \wedge \boldsymbol{h}_t-\boldsymbol{b}_t$ は着点 $i$ に隣接する敵石(白石)のアタリを表し、$^t F_t(F_0 \boldsymbol{e}_i \wedge \boldsymbol{h}_t-\boldsymbol{b}_t)-\boldsymbol{b}_t$ は着点 $i$ に隣接するアタリの敵石(白石)の連を表します。この式は囲碁の取りのルールを表しています。 $$ \boldsymbol{d}_t(i) = \begin{cases} ^t F_t(F_0 \boldsymbol{e}_i \wedge \boldsymbol{h}_t-\boldsymbol{b}_t)-\boldsymbol{b}_t & t \; \text{is even} \\ ^t F_t(F_0 \boldsymbol{e}_i \wedge \boldsymbol{h}_t-\boldsymbol{w}_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$ と論理和をとることで新たな連接点が追加されます。$D$ は、$i$ への着手で取られた石の要素に対応する行が初期局面 $F_0$ と同じで、それ以外の行がすべて1の行列です。$F$ と論理積をとることで取られた石によって解消された連を初期状態に戻します。 $$\begin{align} F_{t+1} = & F_t \vee A \wedge D \\[3pt] \text{while} \\ A = & \boldsymbol{a}_t(i)^t(^t F \boldsymbol{a}_t(i)) \\ 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} $$

数え上げ関数

これは式(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} $$

空接点

式(13-1)から(13-6)までの6つのベクトルを計算する準備として、空関係 $_i O _j$ と空接点を表す行列 $S$ を定義しました。隣接する空点をたどってできる空点の集合を空領域と呼び、$i=j$ または空点 $i$ と $j$ が同じ空領域に含まれるとき、空関係 $_i O _j$ が成り立つとします。$i$ を含む空領域とそれに隣接する点を空接点と呼び、$S$ は空接点を表します。$(S)_{ij}=1$ であるとき、$j$ は $i$ に空接すると言うことにします。 $$(S)_{ij} = \begin{cases} 1 & ^\exists k; (_i O _k \; \text{and} \; _k N _j) \\ 0 & \text{otherwise} \end{cases} \tag{12} $$ 連接点が連とそれを囲む空点または敵石を表していたのに対し、空接点は空領域とそれを囲む石を表します。初期局面での $S$ はすべて 1 の行列になります。

活き石 (alive)

『日本囲碁規約』^[2]の定義「相手方の着手により取られない石、又は取られても新たに相手方に取られない石を生じうる石」にしたがい、 $$ \boldsymbol{v} = \boldsymbol{v}_1\vee \boldsymbol{v}_2 \tag{13-1} $$ とします。ただし、$\boldsymbol{v}_1$ は相手方の着手により取られない石、 $\boldsymbol{v}_2$ は取られても新たに相手方に取られない石を生じうる石を表します。

死に石 (dead)

『日本囲碁規約』^[2]の定義「活き石以外の石」にしたがい、 $$ \boldsymbol{x} =\overline{ \boldsymbol{l}}- \boldsymbol{v} \tag{13-2} $$ とします。

目 (eye)

『日本囲碁規約』^[2]の定義「一方のみの活き石で囲んだ空点」にしたがい、 $$ ( \boldsymbol{y} )_i = \begin{cases} 1 & S \wedge (\boldsymbol{l} ^t \boldsymbol{1}) \ne \boldsymbol{l}\;^t(^t S \boldsymbol{l}) \quad \text{and} \\[3pt] & (\boldsymbol{l})_i=1 \quad \text{and} \\[3pt] & ( \; ^t S \boldsymbol{e}_i -\boldsymbol{l} \subseteq \boldsymbol{v} - \boldsymbol{w} \quad \text{or} \\[3pt] & ^t S \boldsymbol{e}_i - \boldsymbol{l} \subseteq \boldsymbol{v} - \boldsymbol{b} \; ) \\[3pt] 0 & \text{otherwise} \end{cases} \tag{13-3} $$ とします。$S \wedge (\boldsymbol{l} ^t \boldsymbol{1}) \ne \boldsymbol{l}\;^t(^t S \boldsymbol{l})$ は空領域が盤上で分断されていること、すなわち空領域が石に囲われていることを表します。$(\boldsymbol{l})_i=1$ は交点 $i$が空点であることを表します。$^t S \boldsymbol{e}_i - \boldsymbol{l}$ は 空点 $i$ を含む空領域を囲む石を表し、$\boldsymbol{v}-\boldsymbol{w}$ は黒の活き石を表し、よって $^t S \boldsymbol{e}_i - \boldsymbol{l} \subseteq \boldsymbol{v}-\boldsymbol{w}$ は空点 $i$ を含む空領域が黒の活き石に囲まれていることを表します。なお、交点の集合 $\boldsymbol{a}, \boldsymbol{b}$ に $\boldsymbol{a} - \boldsymbol{b} = \boldsymbol{0}$ の関係が成り立つとき $\boldsymbol{a}$ は $\boldsymbol{b}$ の部分集合になり、$\boldsymbol{a} \subseteq \boldsymbol{b}$ と書きます。

ダメ (dame)

『日本囲碁規約』^[2]の定義「目以外の空点」にしたがい、 $$ \boldsymbol{m} =\boldsymbol{l}- \boldsymbol{y} \tag{13-4} $$ とします。

セキ石 (seki)

『日本囲碁規約』^[2]の定義「ダメを有する活き石」にしたがい、 $$ \boldsymbol{s} = \boldsymbol{v} \wedge (^t F(^t S \boldsymbol{m} - \boldsymbol{l}) ) \tag{13-5} $$ とします。$^t S \boldsymbol{m} - \boldsymbol{l}$ はダメを囲む石を表し、$^t F$ との積をとることでダメを囲む石の連接点を表し、$\boldsymbol{v}$ と論理積をとることでダメを囲む活き石の連を表します。

地 (territory)

『日本囲碁規約』^[2]の定義「セキ石以外の活き石の目」にしたがい、 $$ ( \boldsymbol{t} )_i = \begin{cases} 1 & S \wedge (\boldsymbol{l} ^t \boldsymbol{1}) \ne \overline{\boldsymbol{l}}\;^t(^t S \boldsymbol{l}) \quad \text{and} \\[3pt] & (\boldsymbol{l})_i=1 \quad \text{and} \\[3pt] & \; ( ^t S \boldsymbol{e}_i -\boldsymbol{l} \subseteq \boldsymbol{v} - \boldsymbol{w} - \boldsymbol{s} \quad \text{or} \\[3pt] & ^t S \boldsymbol{e}_i - \boldsymbol{l} \subseteq \boldsymbol{v} - \boldsymbol{b} - \boldsymbol{s} \; ) \\[3pt] 0 & \text{otherwise} \end{cases} \tag{13-6} $$ とします。$\boldsymbol{v}-\boldsymbol{w}-\boldsymbol{s}$ は黒のセキ石以外の活き石を表し、$^t S \boldsymbol{e}_i - \boldsymbol{l} \subseteq \boldsymbol{v}-\boldsymbol{w}-\boldsymbol{s}$ は空点 $i$ を含む空領域が黒のセキ石以外の活き石に囲まれていることを表します。

黒石の眼の候補地

空点 $i$ が黒石の眼になる条件を式で表しました。$J_1$ と $D_2$ はそれぞれ隣接する(adjacent)点、ナナメの(diagonal)点を表していて、$\left| J_1 \boldsymbol{e}_i - (\overline{\boldsymbol{b}} - \boldsymbol{x}) \right|$ は $i$ に隣接するの敵(白)の活き石の数、$\left| D_2 \boldsymbol{e}_i \wedge (\overline{\boldsymbol{b}} - \boldsymbol{x}) \right|$ は $i$ のナナメにある敵(白)の活き石の数、$\left| D_2 \boldsymbol{e}_i \right|$ は $i$ のナナメにある交点の数を表します。 $$( \boldsymbol{c}_b )_i = \begin{cases} 1 & \left| J_1 \boldsymbol{e}_i \wedge (\overline{\boldsymbol{b}} - \boldsymbol{x}) \right| &=0 \quad \text{and} \\[3pt] & 2 \left| D_2 \boldsymbol{e}_i \wedge (\overline{\boldsymbol{b}} - \boldsymbol{x}) \right| &\lt \left| D_2 \boldsymbol{e}_i \right| \\[3pt] 0 & \text{otherwise} \end{cases} \tag{14-1} $$ $J_1$ と $D_2$ は3路盤の場合、 $$ J_1 = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \\ D_2 = \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} $$ となります。

白石の眼の候補地

同様に空点 $i$ が白石の眼になる条件を式で表しました。 $$( \boldsymbol{c}_w )_i = \begin{cases} 1 & \left| J_1{ \boldsymbol{e}_i } \wedge (\overline{\boldsymbol{w}} - \boldsymbol{x}) \right| &=0 \quad \text{and} \\[3pt] & 2 \left| D_2 \boldsymbol{e}_i \wedge (\overline{\boldsymbol{w}} - \boldsymbol{x}) \right| &\le \left| D_2 \boldsymbol{e}_i \right| \\[3pt] 0 & \text{otherwise} \end{cases} \tag{14-2} $$