囲碁

なんかよく分かんのだけど、
(というか、囲碁にそんなに詳しいわけでもないのだけど)
囲碁って先手必勝*1なのだろうか?
(先後関係なしに)先に打った方が勝ちだとすれば最善な場所に打てばいいし、
そうでなければ初手はパス、で後手もパスで持碁。

…でもなんだか定義がリカーシヴなのが気になる。
それに上の定義ならば、実のところ少しの情報しか得られていない。
先後のどちらが必勝なのかは結局のところ先に打った方が
勝ちなのか負けなのかに依存し、
(コミをx目半と制限すれば目数での持碁は無い。
三コウなどでは有りうるので一応それも考える)

• 先に打った方が勝ち(引き分けではない)だった場合。

自明に先手が必勝。
後手は必敗。

• 引き分けの場合。

どっちで打っても同じ。
先手も後手も必勝。
先手はパスしてもしなくても。

• 先に打った方が負けの場合。

先手パスで先後が実質変わるので、
一手目二手目ともにパスが最善で引き分け。
この場合も先手も後手も必勝となる。

でもって、
f(x)∈{勝ち|引き分け|負け} (x∈{先に打つ方|後に打つ方})
なんか記法がよくわからないが、f(x)を勝ち負け引き分けを決定する関数だとする。
この関数はコミに依存する。
fを与えるコミをk目半とすると、f(x)=g(k,x)と置ける。
勝ち=1、引き分け=0、負け=-1、とすると
g(k,先に打つ方)=h(k)なるh(k)はkに関する
単調減少関数となる(であろう…
目数のみで勝敗が決まればこのことは自明であるが、
特殊なルールを考慮するとこのことは自明じゃないと思うし
私には証明できない)。

囲碁のルールを定義すると定数c(双方最善を尽くした時に、
先に打った方がc目勝ちする…ような数。負の数も有りうる。
引き分けなら0とでもしておく)が定まり、
h(c)=勝ち
h(c-1)=負け
となる。
(引き分けのときはこの限りでもないんだよなぁ…どうするか
まぁ、どうでもいいか…うん)

最終的に、
先手必勝かどうかをa∈Bool、
後手必勝かどうかをb∈Bool
とおくと、
a,bはcの関数で、
aは定数関数、

a(c)=True

bは

b(c)={ True  (c<5.5)
     { False (otherwise)

こうなるのだろうか。コミ5目半なら。
cは実際にはルールから定まる関数なので
もうすでに決まっているはずだけど、
計算できなきゃ意味無いな〜。
結局のところ最初から分かっていた先手必勝が分かったぐらいだ。
で、cが万が一にも現在のコミ未満なら(ということが分かれば)
囲碁は最善を尽くすと、パス、パス、で終わってしまうゲームのようだ。
ただまぁ、最善というものはコンピューターがどんなに
高速化されても尽くすことは不可能だし(サイズの膨張を許すと…
19路盤限定でも10^300とも言われる盤面を探索するには
18ヶ月で二倍のスピードで高速化し続けても実用的な時間で
処理できるようになるには適当に計算して1500年はかかる)、
そもそもコミをいじって最善が引き分けになるようにすれば
どっちでもいいだろうなぁ。

まぁ、P=NPが証明されない限りどうでもいい考察なのだけど。
というか、この手のゲームってNPなのか?
NPの定義…。

解の検証を行う決定性多項式時間TMの存在。
問題に対する非決定性多項式時間TMの存在。
まぁ、本によって定義がまちまちなのだけど。

おそらく黒(白)必勝か?という問題は
盤面に対する最善手を求めよ、という問題に還元できるので、
それよりはやさしい。
最善手を求めるのは非決定性TMにて多項式時間で出来るだろう。
(O(最長手数=N*N?),N路盤)
でも、解の検証はどうやるんだ…
実際には最長手数がO(N^2)で収まらないのか?
まさか指数関数に。
そうだとするとPSPACEにすら入らないかもしれんのだなぁ。
囲碁の盤面数はO(3^(N*N))…なのか?
まぁ、EXPSPACEには入っている…って
結局ナンも分かってへん。
今日も混沌のまま終了。

*1:ここで必勝とは必ず負けない、の意味