「くろねこにゃ」がちょっと変な気がする

まだ「気がする」レベルで、テストが出来ていないんですが…

くろねこにゃは、いわゆるモンテカルロ木探索アルゴリズムで動いているわけですが、１０秒回した結果と１秒回した結果で、強さに大差がないような……。

つまり、探索量に対して強さがスケールしていないことになります。

モンテカルロ木探索の一番良いところは、探索量に強さがスケールするところのはずなので、これは明らかに何かがおかしい、です。

原因はいくつも思いつくのですが、バグの可能性が一番高いような…。かといって、どこにバグがあるのか、まだ見当も付きませんが。

バグじゃないとすると、Progressive Wideningのあたりが怪しくて、少ない試行回数に対しては応手を正しく返す（手を絞り込んでいる）ので正しそうな結果が返ってくるけれども、試行回数が増えて、幅を広げる際には、無駄な手を読んでシミュレーションを行うだけでただ単に局面評価のノイズが増えるだけ、とかいう可能性はありそうです。

この辺、少々手抜きな実装で、一気に幅を広げるので…。

…しかし、あの辺りはいじるのもテストも大変なんだよなぁ(--;

恥ずかしい写真

左の写真は、去る2009年6月20日に行われた、CGFオープンの９路盤での黒番「caren」、白番「くろねこにゃ」の戦い…になってない様子です。

（なお、写真提供は、YSSと彩の作者の山下さんです。）

棋譜を残し忘れたので、お見せするのに時間がかかってしまいました。

ちょっと設定を間違えて、MCの中で使うパターンデータベースファイルとして、変なデータを読み込んでしまい…結果として、毎回のMCによる終局までのシミュレーションの結果がメチャクチャになり、こんな惨状が起きてしまいました。

この局面を写真に撮って貰った直後、プログラマーの判断で投了したのですが…もしも、最後までやったら、どうなってたのかな…とか、今更考えてみたり。

学習失敗、というか何と言うか。

９路盤の学習、先の通り、してみました。

結論から言うと、一部成功しているものの、明らかに弱くなっています（爆）。

成功例ですが、例えば、いきなり盤の端に打つような変な手が明らかに減っています。

が。

プレイアウトの中で盤の端に打つ手の確率も減っているようで…そうなってしまうと、盤の端まで追って行って石を殺すことがMCの中で出来ません（爆）

石を取る手があったら優先的に読むとか入れていこうとすると、処理がえらい重くなるのも分かっているので…さて、どうしたものか(--;

九路盤で学習してみました

…データとしてよいものが取れているかどうかはまだ謎ですが。

方法は、基本的に棋譜からの学習なのですが、自己対戦から３ｘ３のパターンを切り出し、パターンの登場頻度と実際にそこが最善手として打たれた回数を求めて、回数／頻度をMC部の中で確率として使うようにしてみました。

さて、『完全ランダム』なMC部と、頻度を考慮したMC部とで、どちらが強くなっているか、実験ですね。

今回は、単純にパターンを抜き出したのですが、厳密には、

・その着手で石が取れる場合／取れない場合

・その着手でダメが増える／増えない

などを考慮しないと、何となくまずいことになりそうです(--;

　＜ちょっと実験してみた感じだと、どうも何かおかしいような…。

囲碁の方は、棋譜からの『学習』に挑戦中

囲碁の方は、棋譜から、実現確率のパターンを学習することに挑戦中。

・候補手の周囲の石８近傍だけを見る簡単なパターン

・32bitに収まるように出来るだけ大きなパターン

とを考えているので、多少変則的なものになるのかな…。これらをモンテカルロシミュレーションの中で、打つ手の確率にあて、さらにUCTのノードを作成する時には、もっと大きなパターンも用意して、progressive wideningを行うつもりです。

これに成功したら、19路でもそこそこ打てるものになりそうだと思ってます。（予備実験はまだですが。）

こっちの方が実は将棋よりも優先順位が高かったりします…。

さて、きっちりと片付けて将棋に戻ろう。

まぁ、勝也の中をある程度知っている私の感覚としては、ある程度大きなパターンを準備して、ある程度大きな棋譜データから学習しても、手でパターン追加しないといけないっていうことも十分にありそうに思うんですけれどね…。でも、まずは実証実験から。

GTPが検索キーワードになってるみたいなので。

GTPのクライアント側実装例を示そうかな、とか思ったら勝也のGTP対応ソースをどこかに置いて来てます。

何か今週はこんなことばかりやってるような気がする…。

何やってるんだかなぁ。

というわけで、予告：くろねこにゃのソースはGTP対応してから公開します。

アルゴリズムの解説は、工学社から発刊する予定の『コンピュータ囲碁のアルゴリズム（仮題）』にて。

さて、もっと原稿書かないといけない状態に自分を追い込んだぞ、と…。

『くろねこにゃ』でＣＧＦ特別例会に参加してきました

実質10日間で書いたプログラムで参戦。厳密には、このブログでくろねこにゃと読んでいたものともちょっと違うので、何と名前を付けたらいいものか？

途中の試合運びで、明らかになんか盤面認識が変なことは分かってたんですが、原因が追求できず。で…やっと原因が分かって、最終戦前にバグ修正したら、最終戦だけ勝てましたＯＴＬ。1勝6敗。棋譜は…掲載に耐えません（苦笑）。

いや、思考ログとか残してればまだ色々とこういうバグがこうなるとか、面白ネタを提供できそうなんですが、ログも残してない＆バグ修正前のプログラムが残ってないので、再現が…。

後は、囲碁の棋譜再現、どうやってやろうかなぁという問題もありますね。多分、フリーでいいものがいっぱいあると思うんですけれど。

で、バグのことを考えると、Ｉ／Ｏの連載用に書いてたプログラムの方が強かったみたいです（苦笑）。あれはあれでまた別のバグがあるんですが…。（Ｉ／Ｏ連載版は、最終的に日本ルールで動かすことを念頭においていたので、中国ルールだと色々とまずいことが…。例えば、スーパーコウには対応していないですし。勝敗の判定が最終地＋ハマだったり。）

今回、普段持ち歩いているノートと、普段使っているデスクトップの速さの差に参りました。幾らなんでも単位時間あたりのプレイアウト数が５倍も違うとは思いませんでした(--;クロックで２倍くらいしか違わないし、コア数も同じなのになぁ。

最大の違いは、デスクトップのＯＳが２０００、ノートのＯＳがＶｉｓｔａなこと。

ウイルススキャンの速度とかも全然違うかも知れませんね。どーにかして、ＸＰでポータブルで、高速なノートが欲しいなぁと切実に感じました(--;

さて、今後の方針。

・プレイアウトをもっと精密にする。
　とりあえず、３ｘ３のパターンを作成する予定です。

・まだ多分残っているであろうバグを消し去る。

・プレイアウトの高速化
　一番簡単なのは、プレイアウト部分のマルチスレッド化かなぁ。

・１９路への再挑戦

・日本ルールへの再挑戦

…とりあえず、これ位、片付けて、ＵＥＣ杯に参加できるといいなぁ。

とりあえず、これでいいかな？

まず、盤の端では、相手から打てないところでも石を繋げる手なら打つように変更。

次に、ある程度盤面が込み合ってきた場合には、パスを可能手に追加するように変更。これで、セキの自爆の問題は回避。

最後に、アタリだったら取る手を優先するように…と言うところで、下らない間違いをしているのを発見。ちゃんと書き直したら、どうやらまともに動くみたいです。

UCB1→UCB1-TUNEDにする作業は、一旦やってみたものの、式を正しく書いている『つもり』なのに、何か却って弱くなっている感じなので、何か計算式を勘違いしていないかどうか、その内再チェックすることにして…コンピュータ将棋選手権やら、今抱えている仕事やらがちゃんと終わるまで、ねこにゃは封印しておこうかと思います。

あ。

ねこにゃなんですが、今は９路しか打てないので。

「くろねこにゃ」と呼んでます（ｗ

ねこにゃ、弱くなったか？

『相手から打てないところには打たない』というルールで手を絞り込んでいたのですが、例えば、図のような局面。

　ＡＢＣＤＥ
１┌○○┬
２●○┼┼
３●○┼┼
４├●○┼
５●●○┼

ここで、黒番だと、Ａ４に打ってくれないのですよね。で、黒Ａ１に打って、白Ａ４に打たれて石を取られて、また黒Ａ３・黒Ａ２・黒Ａ１として、白Ａ４、以下無限ループ（苦笑）。

相手から打てないだけで判定してはダメだな、というのは明らかなんですが、さーて、どう調理しようかな。

それから、課題がもう一つ。

勝率が十分に高い時に、相手がパスしたらパスするというロジックを入れたら、パスした局面ではまだ全然途中で勝負が付いてない（苦笑）。というより、勝也の勝敗判定を借りて勝敗を判定すると、思い切り負けてる。

…で、手で勝也を相手に続きを打ってみたら、盤面全部がセキになるというすばらしい棋譜が出来上がり。…セキのことを考えると、合法手にパスを入れないとまずいみたい。（現在は、合法手にパスを入れていないので、こんな風に盤面全体がセキになったら、ちょうどそこで手番を持っているプレイヤーが、『自爆』してしまいます。）

ＵＣＴ＋ＭＣ囲碁、細かい所を詰めていくと、結構色々課題が出てくるものです。

あ、そうだ。

現在、手の選択に、ＵＣＢ１を使っているのですが、これをＵＣＢ１－ＴＵＮＥＤにしようと言うのも思ってたんだっけ。

それから、まだシミュレートしていない手の中では、アタリになっている石を取る手を優先的に選択するようにしたら、なんとなくかえって弱くなった感じがします。

コンピュータ将棋も同じですが、工夫のしどころは、実験と経験を積みながら身に付けていくか、先人の知恵を拝借してみて、うまく行く・行かない、行くなら何故、行かないなら何故かをちゃんと分析していくという作業が欠かせないですね。

…いい加減、世界コンピュータ将棋選手権に向けて、『うさぴょん』の開発に戻らなくては。

ＵＣＴなど

ねこにゃの開発は、少しだけ進展。

長らくバグっていた連の差分更新やらその他を諦めて、超シンプルなコードから書き直し。

この状態で、ほぼ完全にランダムに手を選択すると、

9路の初手からは、平均110手でシミュレート完了・1500Playout/sec位でした。

で、そのままＵＣＢ１・ＵＣＴを入れてみて、10秒思考で勝也と対局。

勝也は、ほとんどの局面で1手1秒もかけずにバシバシ打ってくるので、大分思考時間に差がありますが、どうやら『中国ルールなら』互角に戦えるっぽい感じです。

…そして、また『日本ルール』の壁にぶちあたってます。

単純に勝也がパスした局面でパスすると、ほぼ確実に負けてるんですよね（苦笑）。その後、ごちゃごちゃ打ってると、いつの間にか戦いが全盤面を巻き込んでいて、怪しげな手で『中国ルールなら』勝っているという感じ。

そう、日本ルールでは２～３目負けてるんです…ＯＴＬ

『日本ルール用終局判定』とか作成して、『日本ルールで』勝っていたら相手がパスしたらパスするとか、そういう工夫をするか、あらかじめ少しコミを大きめに設定しておくという手があるかと思うんですが…前者は結構実装が大変。そして後者については、試してみたら、『負けてる』と思い込んで、暴れまくって状況を悪くするケースが目立つ目立つ（苦笑）。

そして、この程度のシミュレーションの精度や速度では、１９路では使い物にならないこともほぼ明らか。

シミュレーションの精度をあげて行く工夫と、速度を上げるための何かを並行して考えていかないとダメですね。速度を上げるには、一つ比較的簡単な方法があって、モンテカルロシミュレーション部分を並列化するというのがあるのですが、手持ちのマシンでは所詮2倍とか4倍程度しか早くならないですし。精度を上げていく方は、読まなくてもいいような変な手も読んでいるので、これをどうにかしていく（パターンを使うことになるでしょうね）方向が一つと、ＵＣＴの各ノードで、とりあえず全候補手を（ランダムな順で）読んでみる代わりに、一部の候補手（たとえばアタリの石を逃げる手や石を取る手）の優先度をあげていくとか、最初は一部の候補手しか読まない（適当な回数シミュレートしてみて、どうも思わしい手がないと思ったら別の候補手も読む）とか、そういう工夫が必要そうです。

また、ＵＣＴに関しても、単純に上のノードに1回のシミュレーションの結果を繰り上げるのではなくて、もっとＭｉｎＭａｘ的なことをやってもいいような気がしています。

たとえば、あるノードで、次にある手を打たれたら「勝ちはない」のなら、そのノードの勝率は完全に０にしてしまうとか。…全然理論的な裏づけはないんですが（苦笑）。

うーん…先の、最初は一部の候補手しか読まないとか、キラー手的な手を先に読むだけで、同じような効果が得られるか…。

いまいち、どういう風にチューニングしていけばいいのか、という感覚が掴めない感じですね。未だにアルゴリズム的に何となく納得できていないっていうのが一番大きな理由かも知れません。うまく行くことは分かるんだけれど、っていう意味では、αβでも同じような感覚が未だにありますね、そういえば。

…長い長い呟きでした。しかも、誰の役にも立ちそうにないし（苦笑）。