囲碁研究

4月になって、あわただしく、なかなか作成に手がつかず。。。
1週間、更新が止まってしまった。
GWまでには復活したいが
忘れ去られそうだ。。。
煮詰まっているという事もないのですが、
乱数の部分をモンテカルロへと。。。


明日、富士通杯があるようだ。
期待できる要素はあるのだろうか。
張栩もあまり調子が良さそうではないし。
日本勢の1回戦の相手を見ると
欧米か？南米か？となっているようで、
正直、いきなり壊滅状態ということはないと思うけど。

モンテカルロ法への準備として
乱数で打つ関数と眼には打たないチェック関数をなんとか実装。
まだバグがありそうで、処理速度にも疑問がありますが
黒白どちらも乱数で、19路盤で対戦させてみた。
乱数で打つ分には大きい盤でも対応が容易ですね。



終局図の一例ですが、とりあえず形になって、、ない？でしょうか。
途中の手順は無茶苦茶ですが。

乱数でも、空いている所へ置いて、終局と思えるところまで
行くと、ちょっと楽しく思えます。

今日から4月1日。暖かいですね。
部屋に篭ってプログラミング、という陽気じゃないですね。
とか言ってみたり。。。

評価関数がやはり難しい。
いわゆる連や群を計算し、
それを元に、石の強弱や死活を判断する、
という方法で停滞している感がある中で、
話題のモンテカルロ法にトライしようかと。。

何もすすんでいない。。。
最近、あわただしくて落ち着いて進められない、と一人で言い訳。

三路盤は小さくて、なんとかできるかもと思ったのだが、
同じやり方で一路増やして
四路盤にすると、一手に何秒かかるかわからんし。
単純な比較だけど

(3×3)! = 9! = 362880
(4×4)! = 16! = 20922789888000

と、桁違い。
一路でこの差は改めて驚いてしまった。
もう少し三路盤で修行しようかと。

先日、将棋プログラムがトッププロと対局した試合が大きく報じられていましたが、記事にはその試合のために400万局面/秒を先読みするように改良してきたとあり、改良前でも80万局面/秒を読んでいたとのこと。

それで、自作のプログラムではどうだろうか？と考えてみたのですが、
前回のブログの三路盤MinMaxでは、3万局面/秒ほどだったので、かなり遅いです。
マイPCはceleron 2.66GHzなので、最新CPUより数倍遅いかもしれませんが、評価関数の計算時間が極わずか、なのにです。

いきなりC++の話ですが、
動的配列のvectorクラスが便利で先読みの中で使っていたのですが、これが遅い原因でした。やはり、というかVisual C++に対して、その事を指摘していたホームページを見たことががあったものの、あまり変わらないだろう、と思っていましたが、違いました。先読みルーチンの中でvector配列を使用しないようにすると、1手35秒が、5秒までになりました。

さらに基本的な事っぽいですが、releaseでビルドしたら2秒までなり、結果、約50万局面/秒まで軽くなった。ただ、評価関数をまともに実装しようとすると、すぐ重くなりそうですが。

をなんとか実装してみました。

候補手はパスを含めて、着手可能な全ての場所
評価関数は単純に(黒石 - 白石 + アゲ白石 - アゲ黒石)
その他、αΒやハッシュ表などもなく、
全末端ノードの評価値によるMinMax（のつもり）で
初手をどこに打つか、やってみたりしました。

深さ　評価局面　計算時間　着手位置
　7　　996192　　　約35s　　(1 二) 　
　8　 4265041　　約2m40s　(1 二)
　9　16787146　約10m30s　(2 二)←真ん中
(列がずれてしまう。。。）

と、一応、動いているかも？という感じでした。
探索が深さ7で、真ん中に打ってこなかったが、
上の評価関数では、机上で考えた限りでも
初手が(1 二)と(2 二)で評価値に差がでないかもしれず。
動作に、半信半疑なところもありますが、気になっていた
move/undoで暴走することは、今のところなかった。

深さ7で、COM(1 二),MAN(2 二)の後の下の局面で

どちらかハネる思っていて、赤い所へ打ってきたので
少し驚いた。ハネると、隅に打たれてコウがらみでややこしい。
三路盤も考え出すと、はまりこみそうな気がした。

先読みは基本中の基本であるminmaxを実装中。
それでも、
・候補手作成の関数
・評価関数
の二つは少なくとも必要と思われるが、簡単に
1.は三路盤(笑）として、全ての空点。
2.は残っている石の数
にしようかと。

など、先読みで必要となる情報を考え、データ構造を変更したり
一方で、勢いで書いた部分も多かったソースを見直していて
いくらかスリムになった。
囲碁に関係している部分は実質、数百行ぐらいだろうか。

ただ、この辺りから、一筋縄ではいかないというか、
進捗が停滞気味。。。

を、どう実装するかが悩みの種の一つだったりしました。
先読みの中で幾度となく呼ばれるので、
いかにして軽くできるかと。
struct {
int bs[BSIZE];
int ws[BSIZE];
}
の構造体を一手ごとに全コピーを
最初に考えていたのですが、やはりでかすぎ。

チェスではxorで簡単にできるような書き込みを見て、
囲碁ではどうか、と考えていたら、
単に打石とアゲ石を配列にpushしていけばいいことに気づく。
戻すときはpopして現盤面とxorすればいいだけでした。

前回、話題にしたブログが2chのスレに貼り付けられたりして
ここを見た方がした、ということもないと思うのですが
少なくとも、私はしておりませんので(笑)。

数日前、ビット演算を調べ回っていたら
コンピュータ将棋で有名なY氏の本家ページとは別の
「FPGAで将棋プログラムを作ってみるブログ」
なるブログを見つけた。
そこで、モンテカルロ法の囲碁プログラムが手強いことを知る。
今までも、名前は目にしていたけど、？？？という感じだった。

2chの囲碁ソフトスレでも話題になってるけど、
MoGoってのが現在進行形で強くなってるようで
時代はモンテカルロ法、という感じがしてきた。

話は戻りますが、上記のブログで参考にされていて、
アマゾンでも高評価だったので
「ハッカーのたのしみ」(Hacker's Delight)
をアマゾンで注文してしまいました。
それで、今日、届きました。名前はアレですが、
ビット演算や数式による説明が多々ある真面目な本。

と、まとまりがないですが、
先読みのルーチンにどう手をつけたらいいものか思案中。。。

ハッシュによる同一局面チェックをしばらく考えてましたが
αΒ検索などの先読みで生じる場合に、
探索を効率化するのが主な使い方と思われる。

そのことをもあって、ハッシュについて調べてましたが、
コウを禁止着手としてはじくチェックとしては、
単に２手前の局面との比較でよかったみたいだ。
他の同一局面は３手以上進むし。
パスも考慮してアゲ石数の比較もするとして。

そうは思ったのですが、一応、ハッシュ関数は超単純に
int bs[BSIZE];　int ws[BSIZE];
を全部足して、% HASHSIZE したキー値の配列に手数を代入。
衝突は+1の場所に代入、としてハッシュ表を使うようにした。
これでもチェックになっていると思うが
最終的には局面データ同士の比較が必要なので、
コウチェックのみなら２手前の単純比較で十分っぽい。

とりあえず、石をとる、コウチェックで
一人二役だけど碁が打てるという状況になった。