コンピュータ囲碁プログラム 盤上を走査しよう

前回の記事 : 「コンピュータ囲碁プログラム ゲームデータを作ろう」 http://qiita.com/muzudho1/items/f7049ad58a6b19a41761

# 今回の記事
理屈を解説する。

お絵描きするのが大変なので、５路盤（ごろばん）とする。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a1.png?raw=true)

囲碁では石を　線の交点に置くので、
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a2.png?raw=true)

１辺の石の数を　数えて、５路盤と呼ぶ。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a2b2.png?raw=true)

n は自然数なんだが、 **数学** に出てくる　Ｎ　Ｚ　Ｑ　Ｒ　Ｃ　ってすごいな。なぜ早く教えてくれないのか……。こんな定規欲しいな、というときに数学は５本も用意している。数学は別記事で解説する。

で、コンピュータ情報科学では　碁盤の外側に　１つ余分に　線を引くことにしよう。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a3.png?raw=true)
これは　番兵（ばんへい。英語で言うとセンチネルでやけにかっこいい）と呼ばれるテクニックのうちの１つだ。

なんで　こんなことをするのかと言うと、「上側に出たか」「右上側へ出たか」「右側に出たか」「右下側へ出たか」「下側に出たか」「左下側へ出たか」「左側に出たか」「右上側へ出たか」の **８択をいちいち判定するのがめんどう** なので、「番兵か」「番兵じゃないか」の**２択にしよう**、というわけだ。

数学の道具を利用して理屈を作って　コンピューター情報科学で良い方法を思いついて楽をするという、いい話しだ。

**国語** も登場させれば「良い方法」は「ずるい」とも「工夫」とも両方取れる。わたしが思うに「自分の損になることは　ずるい、自分の得になることは　工夫」と言うだけの話しだと思うが、望むも望まぬも、テクノロジーは誰かが進化させてるし、利害関係者はルールを作る手間が毎度出てくるという工程を　無関係な私たちは　檻の外から　目の当たりにするのではないか。　もし世間に「ずるい」という空気が作られたときは、もっと全体的な得になる説明はないものかと「工夫」について思い出してほしい。

で、
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a4.png?raw=true)
左上の座標（Ｘ，Ｙ）　図では赤い数字、緑の数字（例えばUnityではRGBつまりRed、Green、Blueの順に並んでいるようだ）を　（０，０）　とすると、

![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a5.png?raw=true)
碁盤の　符号が　左上角から（１，１）から始まって、なんか　いい感じ。 **番兵やっほーっ！**

というのを コンピュータ囲碁ソフトの CgfGoBan とかで見れる。他の囲碁ソフトでも見かける。

休憩したあと、まだ　走査の話しが続く。

# 名前を付けよう
## 碁盤
で、とりあえず
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a6.png?raw=true)
この線の名前を　わたしは　Grid　にする。

他の囲碁ソフトを見てみると
Ray では **GoBoard**、
DarkForest では **Board**、
GNU Go 3.8 では **Board**、コメントで Go Board、
Fuego では **GoBoard**、

で、だいたい　ボード　なんだが、なんでお前は　グリッドなんだ、というと、**だってグリッドに見えるもん** ぐらいなんだが、多分　誰かがソースを Board で文字列検索して「ボード無いな……」「お前のソースは　読みにくい……」と言われることになるかと思うが　つらいところだ。

プログラムの記述とは、開発者の思考そのものの複写でもあるのだ。とは言え、言語の制約、複数人作業の制約から　お互い理由の妥協点に落ち着いていくのは否めないだろう。この見えない「枠」、あるいは「共通部分」のようなものに縛られていることは頭に入れておいてもいい。その枠を勝手に想像するのも　なかなか楽しい。

もし多数決で　決めるのなら Grid なんか言うやつはいなくて Board あたりが無難だろう。

**でも　わたしは　Grid　にする。**

次。

## 交点
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a7.png?raw=true)
この、いわゆる　碁ボード　の上にある　交点。　交点って英語で何て言うの？

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) の２軸以外でも、通し番号という１軸で振る方法もある。**番地** と呼ぶと分かりやすいだろうか。
####枠も含めて振る方法
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a12.png?raw=true)

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** と呼んでいる。

####盤上だけ振る方法
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a13.png?raw=true)

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** と呼んでいて、**この番地の振り方は全廃している。番地の数え方が２つもあったらややこしい。**

次。

## 連
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a8.png?raw=true)
（上図：そういえば忘れていたが、端っこは枠なんで石は置けない。黄緑色は間違いだ）

囲碁では　タテとヨコに石がくっついて、ナナメにはくっつかないという、ぷよぷよ　みたいなんだが、
この１つの石の集まり、または　石の集まりの全部のことを　英語で何て言うのか？

Ray では **String**、沢山あったら Stringの配列、
DarkForest では **Group**、沢山あったら Groups、
GNU Go 1.2 では 囲碁盤と同じサイズの **ml**配列を作って　つながっている石に印を付けていくのに使い、どの石がくっついていて、石の周りに空き地があるか数えている。
GNU Go 3.8 でも同じく **ml**配列を**MARK_LIBERTY**という別名にしていて、石と、その周りの空き地を数えている。連は  **String**、沢山あったら
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a9.png?raw=true)
**Dragon**、でもなんか色々やってて分からん、
Fuego では **GoRegion** だろうか。 **Block** とか **Chain** とかあって何やってんのか分かんない。

ren と書くと　複数形のとき困るし、string は文字列と紛らわしいし、DarkForest の Group は　なかなか楽しそうだ。

でも　わたしは **Area** と書くし、沢山あったら **Areas** だ。

で、なんで 連 が要るかというと、相手の石を囲んで取るとき　囲まれて１つのかたまりになってつながっている石、これが連だが、
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a10b.png?raw=true)
連をごっそり取ってくんで、**囲碁のルール上 連は必要** なわけだ。ただ、その石の呼び方や、アルゴリズムが異なるだけで。

少し休憩してから　また　のんびりと書き足していく。

## 呼吸点
そこに石を置かれたら　取られちゃうじゃないか、という交点を、
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a11.png?raw=true)
**呼吸点**（こきゅうてん）と呼ぶ。英語では **Liberty**（リバティー）。

この囲碁用語は　知る限り　みんな使っているようだ。

## 相対位置
他によく出てくるのが、ある点から方向を指定して１つ隣の番地だ。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a14.png?raw=true)
北(North)、南(South)、東(East)、西(West) と、ナナメだ。

番地に -1 すれば 西隣り を指すし、
番地から １行の幅 を引けば 北隣り を指す。

コンピュータ将棋ソフトでも東西南北＋桂馬跳びを使っているものを見かける。

囲碁でナナメなんか何に使うのかというと、打ち手を思考するときに使うようだ。

ちなみに、

###これ、４近傍
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a14b1.png?raw=true)
４近傍（よんきんぼう）というのは　東西南北の１つ隣を指す。英語にすると **Neighbor**(ネイバー)。

###これ、８近傍
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a14b2.png?raw=true)

将棋では　２４近傍　もよく出てくる。

###これ、隣接
ほかに、どっかがくっついて隣にいるときは 隣接(りんせつ)、英語にすると **adjacent**(アジェイセント) というのもよく出てくる。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a15.png?raw=true)

よく **adj** とか略す。

少し休憩して　まだ説明を書き足す。

#連の番号
**石**は、(x,y) を使ったり、point を使ったりすれば指定できるのは分かった。では**連**はどうだろうか？

たとえば　こんな盤面があったとして……。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a16.png?raw=true)
「あの連、呼吸点１個しか無いぜ！」「あの連ってどこだぜ？」「あれだぜ、あれ！」といった会話がしたいことがある。

連は　こんなにある。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a16b1.png?raw=true)
方法としては「座標(1,1)の石を含む連」とか、「枠を含んだ盤で左上を[0]として左から右、右端から次の行の左端と進んでいって[8]番目の石を含む連！」とか言ってもいいんだが、けっこう大変だ。

そこで、連に番号を振ってしまう　という考え方もある。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a16b2.png?raw=true)
こりゃ分かりやすい。でも　どうやって振るのか？

こうやって振るのさ！
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a16b3.png?raw=true)

Ray は **string_t**構造体を使って連を１個記憶している。覚えている番地は始点の石１個で、連に関するいろいろな情報を持っている。
DarkForest は **Group**構造体。
GNU Go 1.2 は 呼吸点の数を調べたいときに、その都度　連の中の石を１つ指定して　数えてグローバル変数に入れている。
GNU Go 3.8 のソースはよくわからん。
Fuego のソースもよくわからん。Blockが何か関係あるのか。

わたしは　連を探すついでに グリッドの交点に　連の番号　を振っていき、連１個　走査（スキャン）が終わるたびに　固定長配列に　連に関連するいろいろな情報を入れていっている。

次は　連を見つけ出す　走査（スキャン）　について記事を続けたい。

# 連を見つけ出すスキャン
とりあえず　どこか１点を指して、
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a17.png?raw=true)
数字は、走査する隣の交点の順番なんだが、じゃあまず　１　へ進んでみよう。

![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a17b2.png?raw=true)
このとき、さっきいた位置は　走査済みとしてマークを付けておく。これは少なくとも GNU Go 1.2 からある方法だ。

じゃあまた１へ進んでみよう。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a17b3.png?raw=true)
１は　枠　なので進めない。枠という呼び方は **CgfGoBan、CgfGoThink** で使われている。

こんな感じで進んでいき、何かにぶつかれば　次の順番の方向へ進む。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a17b4.png?raw=true)

どこにも進めなくなったら１つ戻り、残っている次の順番の方向へ進む。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a17b5.png?raw=true)

最初に指した石が　黒石なら　黒石の上ばっかり走査して、
最初に指した石が　白石なら　白石の上ばっかり走査して、
既に操作した point は走査しなくて、
最初に指した point が空き地でも走査しない、

という感じで、走査していないところを塗りつぶしていけばいい。
左上から順番に point を指していけばいいのではないだろうか。

これを **再帰関数** というアルゴリズムを用いると手短に実装できる。

# 再帰関数の理屈

また休憩してから書く。

ここにバケツがあるとしよう。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18.png?raw=true)

そして、
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18b2.png?raw=true)
バケツの中には　バケツがある。

![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18b3.png?raw=true)
この内側のバケツが、

![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18b4.png?raw=true)
外側のバケツなのだ。

すると永遠に　内側のバケツの内側に入っていきそうだが、安心してほしい。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18b5.png?raw=true)
実は　小さなフタが付いており、

![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18b6.png?raw=true)
この　小さなフタに引っかかると、

![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18b7.png?raw=true)
外側のバケツの　内側に戻されるのだ。

これで　どんどん元に帰っていける。これを俯瞰的な図に一望すると……。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18b8.png?raw=true)

一直線に深いところまで潜っていき、末端で暴れまわって　文句言いながら帰ってきたと思ったら　また潜るみたいな人になる。
戻ってきたと思ったら　また　隣に潜っていく。

まるで　木をさかさにして　その輪郭を　一筆書きするような動きに似ているだろう。
![Gazo](https://github.com/muzudho/HowToMakeGame/blob/master/img/2017-03/201703021642a18b9.png?raw=true)
途中で描くのが嫌になってきたが、潜っては　帰っていく様子が描けたかと思う。

# 今回の記事は終わり
これでまあ　そこそこ　盤面で起こっていることを説明できたのではないだろうか。
次回は　囲碁って　そもそも　どうやって勝敗を判定するのか、といったあたりも書いておきたい。