0

厳密な囲碁ルール

42
0
$$\newcommand{Atom}[0]{\mathcal{A}} \newcommand{bbC}[0]{\mathbb{C}} \newcommand{bbN}[0]{\mathbb{N}} \newcommand{bbQ}[0]{\mathbb{Q}} \newcommand{bbR}[0]{\mathbb{R}} \newcommand{bbZ}[0]{\mathbb{Z}} \newcommand{BMove}[1]{\overline{\mathfrak{#1}}} \newcommand{BMoves}[0]{\overline{\mathfrak{M}}^\ast} \newcommand{cEND}[0]{\mathcal{E}_c} \newcommand{cfg}[1]{#1} \newcommand{Cfg}[1]{#1} \newcommand{Cfgs}[0]{C^\ast} \newcommand{combi}[2]{{}_{#1}C_{#2}} \newcommand{Edge}[1]{#1} \newcommand{edge}[1]{\mathfrak{#1}} \newcommand{inv}[0]{^{-1}} \newcommand{liv}[0]{L} \newcommand{Move}[1]{\mathfrak{#1}} \newcommand{move}[1]{\mathfrak{#1}} \newcommand{Moves}[0]{\mathfrak{M}^\ast} \newcommand{Nei}[0]{\mathrm{Nei}} \newcommand{ocB}[0]{\mathscr{B}} \newcommand{ocM}[0]{\mathscr{M}} \newcommand{ocN}[0]{\mathscr{N}} \newcommand{ocP}[0]{\mathscr{P}} \newcommand{ocW}[0]{\mathscr{W}} \newcommand{pasfibo}[0]{![算術三角形とフィボナッチ数列](/uploads/image/20201113231516.jpg =360)} \newcommand{Path}[1]{#1} \newcommand{PATH}[1]{\mathcal{#1}} \newcommand{PE}[0]{PE} \newcommand{pl}[0]{\varepsilon} \newcommand{pldef}[0]{\varepsilon\in\{\pm1\}} \newcommand{Run}[1]{#1} \newcommand{RUN}[1]{\mathcal{#1}} \newcommand{RUNs}[0]{\mathcal{R}^\ast} \newcommand{sanzyutusankakukei}[0]{![算術三角形](/uploads/image/20201113231328.jpg =400)} \newcommand{score}[1]{s_{\mathrm{#1}}} \newcommand{sEND}[0]{\mathcal{E}_s} \newcommand{TE}[0]{TE} \newcommand{Vtx}[1]{#1} \newcommand{vtx}[1]{#1} \newcommand{wabun}[1]{\:\text{#1}\:} $$

グラフ理論についてはこちら↓
グラフ理論の基本
囲碁から始めるグラフ理論

道具・基礎ルール

碁盤グラフ

碁盤グラフとは最小次数$\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*}

  1. $v\in \Vtx{B}_c\sqcup \Vtx{W}_c$のとき、
    \begin{align*} \Vtx{B}_{\cfg{c}+\vtx{v}}&\coloneqq V\setminus \{\vtx{v}\},&\Vtx{B}_{\cfg{c}-\vtx{v}}&\coloneqq \varnothing,\\ \Vtx{W}_{\cfg{c}+\vtx{v}}&\coloneqq \varnothing,&\Vtx{W}_{\cfg{c}-\vtx{v}}&\coloneqq V\setminus \{\vtx{v}\},\\ \Vtx{N}_{\cfg{c}+\vtx{v}}&\coloneqq \{v\},&\Vtx{N}_{\cfg{c}-\vtx{v}}&\coloneqq \{\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}'$と書く。

打着列の延長
  1. $\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}$を打着列、$v\in\Vtx{V}$とする。
    \begin{align*} \Run{R}+\vtx{v}&\coloneqq\cfg{c}_0\move{m}_1\cfg{c}_1\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n(\cfg{c}_n,\cfg{c}_n+v)(\cfg{c}_n+v)\\ \Run{R}-\vtx{v}&\coloneqq\cfg{c}_0\move{m}_1\cfg{c}_1\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n(\cfg{c}_n,\cfg{c}_n-v)(\cfg{c}_n-v) \end{align*}
    と定める。
  2. $\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}$を打着列、$\move{m}=(\cfg{c}_n,\cfg{d})\in\Move{M}$を打着とする。
    $$\Run{R}+\move{m}=\cfg{c}_0\move{m}_1\cfg{c}_1\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n\move{m}\cfg{d}$$
    と定める。
  3. $\Run{R}=\cfg{c}_0\move{m}_1\cfg{c}_1\dots\cfg{c}_{i-1}\move{m}_i\cfg{c}_i,\Run{S}=\cfg{c}_i\move{m}_{i+1}\cfg{c}_{i+1}\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n\in\RUN{R}$を打着列とする。
    $$\Run{R}+\Run{S}=\cfg{c}_0\move{m}_1\cfg{c}_1\dots\cfg{c}_{i-1}\move{m}_i\cfg{c}_i\move{m}_{i+1}\cfg{c}_{i+1}\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n$$
    と定める。
勝敗

打着列の集合$\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. $\vtx{v}_{\move{m}_i}\in \Vtx{B}_{\cfg{c}_{i-1}}\sqcup \Vtx{W}_{\cfg{c}_{i-1}}$。
  2. $\cfg{c}_{i}\notin\Cfgs$。
  3. $\vtx{v}_{\move{m}_i}\in\Vtx{V}$かつ、ある$j< i$が存在し、$c_i=c_j$。
  4. $\vtx{v}_{\move{m}_i}$が$\cfg{c}_{i-1}$において二眼の眼である。

(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$は地石式式白勝ちという.

読者への演習問題

窮極性定理
  1. $\cfg{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in\Cfgs$を窮極盤面、$\pldef$、$\vtx{v}\in\Vtx{N}$を$\pl$の眼とする。
    このとき、ある$\vtx{u}\in\Vtx{N}$が存在して、$\vtx{c}+\pl\vtx{v},\vtx{c}+\pl\vtx{v}-\pl\vtx{u}\in\Cfgs$かつ$(\vtx{c}+\pl\vtx{v}-\pl\vtx{u})(v)=0$となる。
  2. $\vtx{c}=(\Vtx{B},\Vtx{W},\Vtx{N})\in\Cfgs$を窮極盤面、$\pldef$とする。$\cfg{c}_0=\cfg{c}$かつ$-\pl$が自身の眼に打たないような任意の有限の着手列$\Run{R}=\move{m}_1\cfg{c}_1\dots\cfg{c}_{n-1}\move{m}_n\cfg{c}_n$と任意の$\vtx{v}\in\cfg{c}\inv(-\pl)$に対し、$\cfg{c}_\Run{R}(v)=-\pl$が成り立つ。

おまけ(アイデア段階のもの)

正規着手列$\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$は簡潔式白勝ちという.

持が考慮されていない。(あと、名前が適当)

投稿日:10日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

三星聯
三星聯
37
14076
主にフィボナッチ数列とパスカルの三角形の関係について書いていくと思います。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中