グラフ理論についてはこちら↓
グラフ理論の基本
囲碁から始めるグラフ理論
碁盤グラフとは最小次数$\delta(G)\geq1$であるような無向グラフ$G=(\Vtx{V},\Edge{E})$のことである。
以下、碁盤グラフ$G=(\Vtx{V},\Edge{E})$上で考える。
また$\overline{v}\notin\Vtx{V}$とし、$\overline{\Vtx{V}}=\Vtx{V}\sqcup\{\overline{v}\}$と定める。
配置とは写像$\cfg{c}:\Vtx{V}\to\{0,\pm1\}$のことである。配置全体の集合を$\Cfg{C}$と書く。
$\pl\in\{0,\pm1\}$、配置$\cfg{c}\in\Cfg{C}$、頂点$\vtx{v}\in\Vtx{V}$に対して、
$\cfg{c}\inv(\pl)\coloneqq\cfg{c}\inv(\{\pl\})$、$\cfg{c}\inv(\vtx{v})\coloneqq\cfg{c}\inv(\{\cfg{c}(\vtx{v})\})$と略記する。
配置$\cfg{c}\in\Cfg{C}$に対して、$\Vtx{B}_{\cfg{c}}\coloneqq\cfg{c}\inv(1)$、$\Vtx{W}_{\cfg{c}}\coloneqq\cfg{c}\inv(-1)$、$\Vtx{N}_{\cfg{c}}\coloneqq\cfg{c}\inv(0)$と定める。
$\Vtx{B}$の元を黒石、$\Vtx{W}$の元を白石、また、$\Vtx{B}\sqcup\Vtx{W}$の元を石、$\Vtx{N}$の元を空点と呼ぶ。
配置$\cfg{c}$が明らかな場合、添え字の$\cfg{c}$は略することがある。
$\cfg{c},\cfg{d}\in \Cfg{C}$を配置とする。
任意の頂点$\vtx{v}\in\Vtx{V}$に対して、$\cfg{c}(\vtx{v})=\cfg{d}(\vtx{v})$を満たすとき、$\cfg{c}=\cfg{d}$と書く。
配置を頂点集合の分割とみて、$\cfg{c}=(\Vtx{B}_{\cfg{c}},\Vtx{W}_{\cfg{c}},\Vtx{N}_{\cfg{c}})$と書くこともある。
さらに、$\Vtx{N}_\cfg{c}$も省略して$\cfg{c}=(\Vtx{B}_{\cfg{c}},\Vtx{W}_{\cfg{c}})$と書くこともある。
$\cfg{c}\in\Cfg{C}$を配置、$\vtx{u},\vtx{v}\in\Vtx{V}$を頂点とする。
$\vtx{u}\sim_{\cfg{c}}\vtx{v}$であるとは、ある$\vtx{u}\text{-}\vtx{v}$道$\Path{P}\in\PATH{P}(\vtx{u},\vtx{v})$が存在して、$\Vtx{V}(\Path{P})\subseteq\cfg{c}\inv(\vtx{u})$を満たすことをいう。
さらに、$[\vtx{u}]_{\cfg{c}}\coloneqq\{\vtx{w}\in\Vtx{V}\mid\vtx{u}\sim_{\cfg{c}}\vtx{w}\}$と定める。
$[\vtx{u}]_{\cfg{c}}$を$\cfg{c}$における$\vtx{u}$の連という。
$\cfg{c}\in\Cfg{C}$を配置, $\vtx{v}\in\Vtx{B}\sqcup\Vtx{W}$を石, $\vtx{u}\in\Vtx{N}$を空点とする。
$\vtx{u}$が$\cfg{c}$における$\vtx{v}$の呼吸点であるとは、ある$\vtx{w}\in[\vtx{v}]_{\cfg{c}}$が存在して、$\vtx{u}\vtx{w}\in\Edge{E}$を満たすことである。
$\cfg{c}$における$\vtx{v}$の呼吸点全体の集合を$\liv_{\cfg{c}}(\vtx{v})$と書く。
さらに, $\liv_{\cfg{c}}\inv(\vtx{u})\coloneqq\{\vtx{w}\in \Vtx{B}\sqcup\Vtx{W}\mid\liv_{\cfg{c}}(\vtx{w})=\{\vtx{u}\}\}$と定める。
$+:\Cfg{C}\times\Vtx{V}\to\Cfg{C};(\cfg{c},\vtx{v})\mapsto\cfg{c}+\vtx{v}$、$-:\Cfg{C}\times\Vtx{V}\to\Cfg{C};(\cfg{c},\vtx{v})\mapsto\cfg{c}-\vtx{x}$を以下を満たすように定める。
(1) $\vtx{v}\in \Vtx{N}_\cfg{c}$のとき、
\begin{align*}
\Vtx{B}_{\cfg{c}+\vtx{v}}&\coloneqq\Vtx{B}_{\cfg{c}}\sqcup\{\vtx{v}\},&\Vtx{B}_{\cfg{c}-\vtx{v}}&\coloneqq\Vtx{B}_{\cfg{c}}\setminus \liv\inv_{\Vtx{B}_{\cfg{c}}}(\vtx{v}),\\
\Vtx{W}_{\cfg{c}+\vtx{v}}&\coloneqq\Vtx{W}_{\cfg{c}}\setminus\liv\inv_{\Vtx{W}_{\cfg{c}}}(\vtx{v}),&\Vtx{w}_{\cfg{c}-\vtx{v}}&\coloneqq\Vtx{W}_{\cfg{c}}\sqcup\{\vtx{v}\},\\
\Vtx{N}_{\cfg{c}+\vtx{v}}&\coloneqq(\Vtx{N}_{\cfg{c}}\setminus\{\vtx{v}\})\sqcup\liv\inv_{\Vtx{W}_{\cfg{c}}}(\vtx{v}),&\Vtx{N}_{\cfg{c}-\vtx{v}}&\coloneqq (\Vtx{N}_{\cfg{c}}\setminus\{\vtx{v}\})\sqcup \liv\inv_{\Vtx{B}_{\cfg{c}}}(\vtx{v}).
\end{align*}
$\Move{M}$を以下で定め、$\Move{M}$の元$\move{m}=(\cfg{c},\cfg{d})$を打着と呼ぶ。
また、$\pldef$に対して、$\Move{M}_{\pl}$の元を$\pl$の打着と呼ぶ。
\begin{align*}
\Move{M}_1&\coloneqq\{(\cfg{c},\cfg{d})\in\Cfg{C}^2\mid\wabun{ある}\vtx{v}\in \Vtx{V}\wabun{が存在して}\cfg{d}=\cfg{c}+\vtx{v}\},\\
\Move{M}_{-1}&\coloneqq\{(\cfg{c},\cfg{d})\in\Cfg{C}^2\mid\wabun{ある}\vtx{v}\in \Vtx{V}\wabun{が存在して}\cfg{d}=\cfg{c}-\vtx{v}\},\\
\Move{M}&\coloneqq \Move{M}_1\sqcup \Move{M}_{-1}.
\end{align*}
上の式の$\vtx{v}$を$v_{(\cfg{c},\cfg{d})}$と書き、打着$(\cfg{c},\cfg{d})$の着点と呼ぶ。
$\BMove{M}_1\coloneqq \Move{M}_1\sqcup\{(\cfg{c},\cfg{c})\mid\cfg{c}\in\Cfg{C}\}$と定める。
$\BMove{M}_{-1},\BMove{M}$についても同様に定める。
$\{(\cfg{c},\cfg{c})\mid\cfg{c}\in\Cfg{C}\}$の元をパスと呼び、$v_{(\cfg{c},\cfg{c})}\coloneqq\overline{\vtx{v}}$と定める。
$\move{m}=(\cfg{c},\cfg{d}),\move{m}'=(\cfg{c}',\cfg{d}')\in \BMove{M}$を打着またはパスとする。
$\cfg{c}=\cfg{c}'$かつ$\cfg{d}=\cfg{d}'$を満たすとき、$\move{m}=\move{m}'$と書く。
有向グラフ$(\Cfg{C},\Move{M})$上の有向歩道$\Run{R}=\cfg{c}_0\move{m}_1\cfg{c}_1\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n$を($n$手の)打着列と呼ぶ。
このとき、$n$を打着列$\Run{R}$の手数と言い、$|\Run{R}|$で表す。
$\cfg{c}_0$を$\Run{R}$の初期配置と呼ぶ。
また、$\cfg{c}_n$を$\Run{R}$の最終配置と呼び、$\cfg{c}_{\Run{R}}$と書く。
打着列全体の集合を$\RUN{R}$と書く。
打着列$\Run{R}=\cfg{c}_0\move{m}_1\cfg{c}_1\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n$と$\Run{R}'=\cfg{c}'_0\move{m}'_1\cfg{c}'_1\dots\cfg{c}'_{n'-1}\move{m}'_{n'}\cfg{c}'_{n'}$に対して、$n=n'$であり、任意の$i=0,1,\dots,n$に対して$\cfg{c}_i=\cfg{c}'_i$を満たすとき、$\Run{R}=\Run{R}'$と書く。
打着列の集合$\RUN{S}\subseteq\RUN{R}$に対して、写像$\score{}:\RUN{S}\to\bbR$を得点という。
得点$\score{}:\RUN{S}\to\bbR$と$h\in\bbR$を固定したとき、$\Run{R}\in\RUN{S}$に対して、$\score{}(\Run{R})>h$ならば黒勝ち、そうでないならば白勝ち言う。
配置$\cfg{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in C$が盤面であるとは、任意の$\vtx{v}\in \Vtx{B}\sqcup \Vtx{W}$に対し、$\liv(v)\neq\varnothing$となることである。
盤面全体の集合を$\Cfgs$と書く。
$\cfg{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in \Cfgs$を盤面、$\vtx{v}\in \Vtx{N}$を空点、$\pldef$とする。
$\Nei(v)\subseteq \cfg{c}\inv(\pl)$となるとき、$v$を$\pl$の擬眼と呼ぶ。
$\pl$の擬眼全体の集合を$\PE_{\cfg{c}\inv(\pl)}$、擬眼全体の集合を$\PE=\PE_{\cfg{c}}=\PE_{\Vtx{B}}\sqcup \PE_{\Vtx{W}}$と表す。
さらに、盤面$\cfg{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in \Cfgs$に対して、$\tilde{\cfg{c}}\coloneqq(\Vtx{B}\sqcup \PE_{\Vtx{B}},\Vtx{W}\sqcup \PE_{\Vtx{W}},\Vtx{N}\setminus \PE)\in \Cfg{C}$と定める。
擬眼$\vtx{v}\in \PE$に対して$[\vtx{v}]_{\tilde{\cfg{c}}}\setminus \{\vtx{v}\}$が連結であるとき、$\vtx{v}$を眼という。
つまり、$\{\vtx{v}\}$が$[\vtx{v}]_{\tilde{\cfg{c}}}$を分離しないとき、$\vtx{v}$を眼という。
石$\vtx{u}\in \Vtx{B}\sqcup \Vtx{W}$に対して$[\vtx{u}]_{\tilde{\cfg{c}}}$に含まれる眼を$u$の眼という。
$\pldef$とし、$\pl$の眼(すなわち、$\pl$の擬眼であるような眼)全体の集合を$\TE_{\cfg{c}\inv(\pl)}$、眼全体の集合を$\TE=\TE_{\cfg{c}}=\TE_{\Vtx{B}}\sqcup \TE_{\Vtx{W}}$と表す。
$\cfg{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in \Cfgs$を盤面、$\vtx{v}\in \Vtx{B}\sqcup \Vtx{W}$を石とする。
$[\vtx{v}]_{\tilde{\cfg{c}}}$内に擬眼がちょうど2つあり、ともに眼であるとき、$\vtx{v}$は二眼活きであるという。
$\cfg{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in \Cfgs$を盤面、$\vtx{v}\in \TE_{\cfg{c}}$を眼とする。
$\Nei(\vtx{v})$内の石が二眼活きであるとき、$\vtx{v}$を二眼の眼であるという。
$\Run{R}=\cfg{c}_0\move{m}_1\cfg{c}_1\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n\in\RUN{R}$を打着列、$1\le i\le n$とする。
$\move{m}_i$が$\Run{R}$中の禁じ手であるとは、以下のいづれかを満たすことである。
(1)の場合を配置的禁じ手、
(2)の場合を盤面的禁じ手、
(3)の場合を反覆的禁じ手、
(4)の場合を眼形的禁じ手と呼ぶ。
$\Moves$を以下で定め、$\Moves$の元$\move{m}=(\cfg{c},\cfg{d})$を着手と呼ぶ。
また、$\pldef$に対して、$\Moves_{\pl}$の元を$\pl$の着手と呼ぶ。
\begin{align*}
\Moves_1&\coloneqq\{(\cfg{c},\cfg{d})\in \Cfgs\times \Cfgs\mid \wabun{ある} \vtx{v}\in \Vtx{N}_{\cfg{c}}\wabun{が存在して}\cfg{d}=\cfg{c}+\vtx{v}\},\\
\Moves_{-1}&\coloneqq\{(\cfg{c},\cfg{d})\in \Cfgs\times \Cfgs\mid \wabun{ある} \vtx{v}\in\Vtx{N}_{\cfg{c}}\wabun{が存在して}\cfg{d}=\cfg{c}-\vtx{v}\},\\
\Moves&\coloneqq \Moves_1\sqcup \Moves_{-1}.
\end{align*}
$\BMoves_1\coloneqq \Moves_1\sqcup\{(\cfg{c},\cfg{c})\mid \cfg{c}\in \Cfgs\}$と定める。
$\BMoves_{-1},\BMoves$についても同様に定める。
$\Run{R}\in\RUN{R}$を打着列とする。
$\Run{R}$が有向グラフ$(\Cfgs,\Moves)$上の有向歩道であるとき、$\Run{R}$を着手列と呼び、さらに$\Run{R}$中に禁じ手が存在しないとき、$\Run{R}$を正規着手列と呼ぶ。
正規着手列全体の集合を$\RUNs$と書く。
原始式得点$\score{p}:\RUNs\to\bbZ$を、正規着手列$\Run{R}\in\RUNs$に対して、$\score{p}(\Run{R})\coloneqq\sum_{\vtx{v}\in\Vtx{V}}\cfg{c}_R(v)=|\Vtx{B}_{\cfg{c}_\Run{R}}|-|W_{\cfg{c}_\Run{R}}|$で定める。
$h\in\bbR$を固定したとき、$\Run{R}\in\RUNs$に対して、$\score{p}(\Run{R})>h$ならば原始式黒勝ち、そうでないならば原始式白勝ち言う。
$\cfg{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in\Cfgs$を盤面、$\vtx{v}\in\Vtx{B}\sqcup\Vtx{W}$を石、$\pl\coloneqq\cfg{c}(\vtx{v})$とする。
$(\Cfgs,\Move{M}_{-\pl})$上の有向道であるような$\cfg{c}$を初期盤面とする任意の正規着手列$\Run{R}$に対して、$\cfg{c}_\Run{R}(\vtx{v})=\cfg{c}(\vtx{v})=\pl$であるとき、石$\vtx{v}$は盤面$\cfg{c}$において絶対活きであるという。
盤面$\cfg{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in\Cfgs$が窮極盤面であるとは、任意の石$\vtx{v}\in\Vtx{B}\sqcup\Vtx{W}$が二眼活きであり、任意の空点$\vtx{u}\in\Vtx{N}$が眼であるような盤面である。最終盤面が窮極盤面であるような正規着手列$\Run{R}$を窮極着手列という。
正規着手列$\Run{R}\in\RUNs$と、頂点$\vtx{v}\in\Vtx{V}$、$\pldef$に対して、打着列$\Run{S}=\Run{R}+\pl\vtx{v}$が禁じ手を含むとき、$\vtx{v}$を$\Run{R}$における$\pl$の着手禁止点という。
$\Run{R}\in\RUNs$を正規着手列とする。
$ \cfg{c}_\Run{R}$の任意の空点が黒の着手禁止点であるとき、$\Run{R}$を黒原子的という。
$ \cfg{c}_\Run{R}$の任意の空点が白の着手禁止点であるとき、$\Run{R}$を白原子的という。
$\Run{R}$が黒原子的かつ白原子的であるとき$\Run{R}$を原子的と呼ぶ。
原子的な正規着手列全体の集合を$\Atom$と書く。
$\Run{R}\in\RUNs$を正規着手列とする。$\Run{R}^1$、$\Run{R}\inv$を以下で定義する。
\begin{align*}
\Run{R}^1 &\coloneqq\{\Run{R}+\move{m}\in\RUNs\mid\move{m}=(\cfg{c}_\Run{R},\cfg{d})\in\Move{M}_1,d\in\Cfgs\}\\
\Run{R}\inv &\coloneqq\{\Run{R}+\move{m}\in\RUNs\mid\move{m}=(\cfg{c}_\Run{R},\cfg{d})\in\Move{M}_{-1},d\in\Cfgs\}
\end{align*}
$\RUNs\times\Vtx{V}$の非交和な部分集合$\ocB$、$\ocW$、$\ocN$、$\ocM$、$\ocP$を以下の(1)、(2)、(3)、(4)によって再帰的に定める。
(1) $\Run{R}$が原子的であるとき、
$$
(\Run{R},\vtx{v})\in\begin{cases}
\ocB&(\vtx{v}\in \Vtx{B}\sqcup \Vtx{TE}_\Vtx{B}\:\text{のとき})\\
\ocW&(\vtx{v}\in \Vtx{W}\sqcup \Vtx{TE}_\Vtx{W}\:\text{のとき})\\
\ocN&(\vtx{v}\in \Vtx{N}\setminus \Vtx{TE}\:\text{のとき}).
\end{cases}
$$
(2) $\Run{R}$が黒原子的かつ白原子的でないとき
$$
(R,v)\in\begin{cases}
\ocW&(\exists R'\in R^{-1},(R',v)\in\ocW\:\text{のとき})\\
\ocP&(\forall R'\in R^{-1},(R',v)\notin\ocW\:\text{かつ}\:\exists R'\in R^{-1},(R',v)\in\ocP\:\text{のとき})\\
\ocN&(\forall R'\in R^{-1},(R',v)\notin\ocW,\ocP,\ocM\:\text{かつ}\:\exists R'\in R^{-1},(R',v)\in\ocN\:\text{のとき})\\
\ocB&(\forall R'\in R^{-1},(R',v)\in\ocB\:\text{のとき}) \end{cases}
$$
(3)
$$
(R,v)\in\begin{cases}
\ocB&(\exists R'\in R^{1},(R',v)\in\ocB\:\text{のとき})\\
\ocP&(\forall R'\in R^{1},(R',v)\notin\ocB\:\text{かつ}\:\exists R'\in R^{-1},(R',v)\in\ocP\:\text{のとき})\\
\ocN&(\forall R'\in R^{1},(R',v)\notin\ocB,\ocP,\ocM\:\text{かつ}\:\exists R'\in R^{-1},(R',v)\in\ocN\:\text{のとき})\\
\ocW&(\forall R'\in R^{1},(R',v)\in\ocW\:\text{のとき})
\end{cases}
$$
(4) 上記(1)、(2)、(3)以外のとき
正規着手列$\Run{R}\in\RUNs$に対して、
\begin{align*}
\ocB_R&\coloneqq\{v\in V\mid (R,v)\in\ocB\}、&
\ocW_R&\coloneqq\{v\in V\mid (R,v)\in\ocW\}、&
\ocN_R&\coloneqq\{v\in V\mid (R,v)\in\ocN\}、\\
\ocM_R&\coloneqq\{v\in V\mid (R,v)\in\ocM\}、& \ocP_R&\coloneqq\{v\in V\mid (R,v)\in\ocP\}
\end{align*}
と定める。
$R\in\RUNs$を正規着手列とする。
任意の頂点$v\in V$に対して、$(R,v)\notin\ocM$となるとき、$R$は地石的終局可能であるという。
地石的終局可能な着手列全体の集合を$\sEND$と書く。
地石式得点$s_\mathrm{s}:\sEND\to\bbZ$を、地石的終局可能着手列$R\in\sEND$に対して、$s_\mathrm{s}(R)\coloneqq|\ocB_R\sqcup(\ocP_R\cap B_{c_R})|-|\ocW_R\sqcup(\ocP_R\cap W_{c_R})|$と定める。
$h\in\bbR$を固定したとき, $R\in \RUNs$に対し$s_\mathrm{s}(R)> h$のとき$R$は地石式黒勝ち, $s_\mathrm{s}(R)\le h$のとき$R$は地石式式白勝ちという.
正規着手列$\Run{R}\in\RUNs$に対して、$b:\Run{R}\to\bbZ$と$w:\Run{R}\to\bbZ$を以下で再帰的に定める。
(1) $\Run{R}$が原子的であるとき、
\begin{align*}
b(\Run{R})=w(\Run{R})=\score{s}(\Run{R})
\end{align*}
(2) $\Run{R}$が黒原子的であるとき、
\begin{align*}
b(\Run{R})&=\score{s}(\Run{R})\\
w(\Run{R})&=\min_{\Run{S}\in\Run{R}^-}\{b(\Run{S})\}
\end{align*}
(3) $\Run{R}$が白原子的であるとき、
\begin{align*}
b(\Run{R})&=\max_{\Run{S}\in\Run{R}^+}\{b(\Run{S})\}\\
w(\Run{R})&=\score{s}(\Run{R})
\end{align*}
(4) それ以外のとき
\begin{align*}
b(\Run{R})&=\max_{\Run{S}\in\Run{R}^+}\{w(\Run{S})\}\\
w(\Run{R})&=\min_{\Run{S}\in\Run{R}^-}\{b(\Run{S})\}
\end{align*}
$\Run{R}\in\RUNs$を正規着手列とする。
$b(\Run{R})=w(\Run{R})$となるとき、$\Run{R}$を簡潔的終局可能であるという。
簡潔的終局可能な着手列全体の集合を$\cEND$と書く。
簡潔式得点$\score{c}:\cEND\to\bbZ$を、簡潔的終局可能着手列$R\in\cEND$に対して、$\score{c}\coloneqq b(\Run{R})=w(\Run{R})$と定める。
$h\in\bbR$を固定したとき, $R\in \RUNs$に対し$\score{c}(R)> h$のとき$R$は簡潔式黒勝ち, $\score{c}(R)\le h$のとき$R$は簡潔式白勝ちという.
持が考慮されていない。(あと、名前が適当)