前回の記事 : 「コンピュータ囲碁プログラム ゲームデータを作ろう」 http://qiita.com/muzudho1/items/f7049ad58a6b19a41761
今回の記事
理屈を解説する。
お絵描きするのが大変なので、５路盤（ごろばん）とする。
囲碁では石を 線の交点に置くので、
１辺の石の数を 数えて、５路盤と呼ぶ。
n は自然数なんだが、 数学 に出てくる Ｎ Ｚ Ｑ Ｒ Ｃ ってすごいな。なぜ早く教えてくれないのか……。こんな定規欲しいな、というときに数学は５本も用意している。数学は別記事で解説する。
で、コンピュータ情報科学では 碁盤の外側に １つ余分に 線を引くことにしよう。
これは 番兵（ばんへい。英語で言うとセンチネルでやけにかっこいい）と呼ばれるテクニックのうちの１つだ。
なんで こんなことをするのかと言うと、「上側に出たか」「右上側へ出たか」「右側に出たか」「右下側へ出たか」「下側に出たか」「左下側へ出たか」「左側に出たか」「右上側へ出たか」の ８択をいちいち判定するのがめんどう なので、「番兵か」「番兵じゃないか」の２択にしよう、というわけだ。
数学の道具を利用して理屈を作って コンピューター情報科学で良い方法を思いついて楽をするという、いい話しだ。
国語 も登場させれば「良い方法」は「ずるい」とも「工夫」とも両方取れる。わたしが思うに「自分の損になることは ずるい、自分の得になることは 工夫」と言うだけの話しだと思うが、望むも望まぬも、テクノロジーは誰かが進化させてるし、利害関係者はルールを作る手間が毎度出てくるという工程を 無関係な私たちは 檻の外から 目の当たりにするのではないか。 もし世間に「ずるい」という空気が作られたときは、もっと全体的な得になる説明はないものかと「工夫」について思い出してほしい。
で、
左上の座標（Ｘ，Ｙ） 図では赤い数字、緑の数字（例えばUnityではRGBつまりRed、Green、Blueの順に並んでいるようだ）を （０，０） とすると、
碁盤の 符号が 左上角から（１，１）から始まって、なんか いい感じ。 番兵やっほーっ！
というのを コンピュータ囲碁ソフトの CgfGoBan とかで見れる。他の囲碁ソフトでも見かける。
休憩したあと、まだ 走査の話しが続く。
名前を付けよう
碁盤
で、とりあえず
この線の名前を わたしは Grid にする。
他の囲碁ソフトを見てみると
Ray では GoBoard、
DarkForest では Board、
GNU Go 3.8 では Board、コメントで Go Board、
Fuego では GoBoard、
で、だいたい ボード なんだが、なんでお前は グリッドなんだ、というと、だってグリッドに見えるもん ぐらいなんだが、多分 誰かがソースを Board で文字列検索して「ボード無いな……」「お前のソースは 読みにくい……」と言われることになるかと思うが つらいところだ。
プログラムの記述とは、開発者の思考そのものの複写でもあるのだ。とは言え、言語の制約、複数人作業の制約から お互い理由の妥協点に落ち着いていくのは否めないだろう。この見えない「枠」、あるいは「共通部分」のようなものに縛られていることは頭に入れておいてもいい。その枠を勝手に想像するのも なかなか楽しい。
もし多数決で 決めるのなら Grid なんか言うやつはいなくて Board あたりが無難だろう。
でも わたしは Grid にする。
次。
交点
この、いわゆる 碁ボード の上にある 交点。 交点って英語で何て言うの？
Ray では pos、多分ポジションぐらいの意味だろう、
DarkForest では c、Coord のこと、
GNU Go 1.2 では node、水平は i軸、垂直は j軸。こいつは行列演算で盤を回転させる。
GNU Go 3.8 では pos、交点のことは Intersection と呼んでいて unsigned char型の別名にしている、
Fuego では p とか point、
物持ちが悪くて 他のソースにすぐアクセスできないんだが、わたしは Point にしている。
そういえば GNU Go 1.2 は よく読んだなあ。モンテカルロ木探索が出てくるよりもっと前の コンピュータ囲碁プログラムだ。
Ray とか DarkForest は 第9回UEC杯 のあとに公開されたソースで、１年前というのは わりと最近という感じがするものだ。
DarkForest は当時 準優勝で、これ多分 ディープ・ラーニングを使ってるんじゃないだろうか。いいんじゃないか。わたしには何がなんだか読めないんだが……。
数字の振り方なんだが
(X,Y) の２軸以外でも、通し番号という１軸で振る方法もある。番地 と呼ぶと分かりやすいだろうか。
枠も含めて振る方法
Ray では 枠も含めて BOARD と呼んでいて、番地は前述の通り pos と呼んでいる。
DarkForest では x,y を EXTENDOFFSETXY マクロ関数を使ってこの通し番号に変換する。オフセットというのは配列の添え字ぐらいの意味だろうか。
GNU Go 1.2 は番兵を使っていない。
GNU Go 3.8 では yがI軸、xがJ軸、に名前を変えて、番地は前述の通り pos と呼んでいる。POS関数マクロを使って、(i,j) を pos に変換できる。ただ、１行下駄を履かせて番号の開始地点をずらしているかもしれない。よく分からない。
Fuego は枠を持っていないんじゃないか。盤上だけでループを回せるという強みがある。枠かどうかは IsBorder( )関数で調べる。
わたしは 枠も含めて Grid と呼んでいて、番地は point と呼んでいる。
盤上だけ振る方法
Ray では盤上だけの部分を PURE_BOARD と呼んでいて、この盤上だけのサイズに対応する onboard_pos配列 には pos が入っていて 枠も含めた番地に変換する。
DarkForest では x,y を OFFSETXY マクロ関数を使ってこの通し番号に変換する。
GNU Go 1.2 では yがI軸、xがJ軸、に名前を変えて、番地は前述の通り node と呼んでいる。
GNU Go 3.8 は難しくて読めないんだが、ON_BOARD2 マクロ関数を使うと、盤上かそうでないか判定できるようだ。
Fuego は盤上だけ番号を振っている。番地は前述の通り point と呼んでいて、0～(SG_MAXPOINTの手前)まで。
わたしは 盤上だけの部分を GridWithoutFrame と呼んでいて、この番地の振り方は全廃している。番地の数え方が２つもあったらややこしい。
次。
連
（上図：そういえば忘れていたが、端っこは枠なんで石は置けない。黄緑色は間違いだ）
囲碁では タテとヨコに石がくっついて、ナナメにはくっつかないという、ぷよぷよ みたいなんだが、
この１つの石の集まり、または 石の集まりの全部のことを 英語で何て言うのか？
Ray では String、沢山あったら Stringの配列、
DarkForest では Group、沢山あったら Groups、
GNU Go 1.2 では 囲碁盤と同じサイズの ml配列を作って つながっている石に印を付けていくのに使い、どの石がくっついていて、石の周りに空き地があるか数えている。
GNU Go 3.8 でも同じく ml配列をMARK_LIBERTYという別名にしていて、石と、その周りの空き地を数えている。連は String、沢山あったら
Dragon、でもなんか色々やってて分からん、
Fuego では GoRegion だろうか。 Block とか Chain とかあって何やってんのか分かんない。
ren と書くと 複数形のとき困るし、string は文字列と紛らわしいし、DarkForest の Group は なかなか楽しそうだ。
でも わたしは Area と書くし、沢山あったら Areas だ。
で、なんで 連 が要るかというと、相手の石を囲んで取るとき 囲まれて１つのかたまりになってつながっている石、これが連だが、
連をごっそり取ってくんで、囲碁のルール上 連は必要 なわけだ。ただ、その石の呼び方や、アルゴリズムが異なるだけで。
少し休憩してから また のんびりと書き足していく。
呼吸点
そこに石を置かれたら 取られちゃうじゃないか、という交点を、
呼吸点（こきゅうてん）と呼ぶ。英語では Liberty（リバティー）。
この囲碁用語は 知る限り みんな使っているようだ。
相対位置
他によく出てくるのが、ある点から方向を指定して１つ隣の番地だ。
北(North)、南(South)、東(East)、西(West) と、ナナメだ。
番地に -1 すれば 西隣り を指すし、
番地から １行の幅 を引けば 北隣り を指す。
コンピュータ将棋ソフトでも東西南北＋桂馬跳びを使っているものを見かける。
囲碁でナナメなんか何に使うのかというと、打ち手を思考するときに使うようだ。
ちなみに、
これ、４近傍
４近傍（よんきんぼう）というのは 東西南北の１つ隣を指す。英語にすると Neighbor(ネイバー)。
これ、８近傍
将棋では ２４近傍 もよく出てくる。
これ、隣接
ほかに、どっかがくっついて隣にいるときは 隣接(りんせつ)、英語にすると adjacent(アジェイセント) というのもよく出てくる。
よく adj とか略す。
少し休憩して まだ説明を書き足す。
連の番号
石は、(x,y) を使ったり、point を使ったりすれば指定できるのは分かった。では連はどうだろうか？
たとえば こんな盤面があったとして……。
「あの連、呼吸点１個しか無いぜ！」「あの連ってどこだぜ？」「あれだぜ、あれ！」といった会話がしたいことがある。
連は こんなにある。
方法としては「座標(1,1)の石を含む連」とか、「枠を含んだ盤で左上を[0]として左から右、右端から次の行の左端と進んでいって[8]番目の石を含む連！」とか言ってもいいんだが、けっこう大変だ。
そこで、連に番号を振ってしまう という考え方もある。
こりゃ分かりやすい。でも どうやって振るのか？
こうやって振るのさ！
Ray は string_t構造体を使って連を１個記憶している。覚えている番地は始点の石１個で、連に関するいろいろな情報を持っている。
DarkForest は Group構造体。
GNU Go 1.2 は 呼吸点の数を調べたいときに、その都度 連の中の石を１つ指定して 数えてグローバル変数に入れている。
GNU Go 3.8 のソースはよくわからん。
Fuego のソースもよくわからん。Blockが何か関係あるのか。
わたしは 連を探すついでに グリッドの交点に 連の番号 を振っていき、連１個 走査（スキャン）が終わるたびに 固定長配列に 連に関連するいろいろな情報を入れていっている。
次は 連を見つけ出す 走査（スキャン） について記事を続けたい。
連を見つけ出すスキャン
とりあえず どこか１点を指して、
数字は、走査する隣の交点の順番なんだが、じゃあまず １ へ進んでみよう。
このとき、さっきいた位置は 走査済みとしてマークを付けておく。これは少なくとも GNU Go 1.2 からある方法だ。
じゃあまた１へ進んでみよう。
１は 枠 なので進めない。枠という呼び方は CgfGoBan、CgfGoThink で使われている。
こんな感じで進んでいき、何かにぶつかれば 次の順番の方向へ進む。
どこにも進めなくなったら１つ戻り、残っている次の順番の方向へ進む。
最初に指した石が 黒石なら 黒石の上ばっかり走査して、
最初に指した石が 白石なら 白石の上ばっかり走査して、
既に操作した point は走査しなくて、
最初に指した point が空き地でも走査しない、
という感じで、走査していないところを塗りつぶしていけばいい。
左上から順番に point を指していけばいいのではないだろうか。
これを 再帰関数 というアルゴリズムを用いると手短に実装できる。
再帰関数の理屈
また休憩してから書く。
ここにバケツがあるとしよう。
そして、
バケツの中には バケツがある。
この内側のバケツが、
外側のバケツなのだ。
すると永遠に 内側のバケツの内側に入っていきそうだが、安心してほしい。
実は 小さなフタが付いており、
この 小さなフタに引っかかると、
外側のバケツの 内側に戻されるのだ。
これで どんどん元に帰っていける。これを俯瞰的な図に一望すると……。
一直線に深いところまで潜っていき、末端で暴れまわって 文句言いながら帰ってきたと思ったら また潜るみたいな人になる。
戻ってきたと思ったら また 隣に潜っていく。
まるで 木をさかさにして その輪郭を 一筆書きするような動きに似ているだろう。
途中で描くのが嫌になってきたが、潜っては 帰っていく様子が描けたかと思う。
今回の記事は終わり
これでまあ そこそこ 盤面で起こっていることを説明できたのではないだろうか。
次回は 囲碁って そもそも どうやって勝敗を判定するのか、といったあたりも書いておきたい。