AlphaGoが誇大広告ぎみな件

Googleが開発した囲碁ソフトのAlphaGoが、世界で初めてプロ棋士に勝ったコンピュータとして大きなニュースになっています。Nature誌に論文が掲載されたのですが、仔細に読むといくつか不可解な点がありましたので、調査・考察してみました。

SWoPPのFPGA囲碁論文 続報

論文執筆者にメール送って聞いてみました。と、すぐ回答送っていただけました。
私の理解が正しければ、先の例だと上辺の

*****+*
*ooo*o*

を見たとき、'o'の石はすべて自分の連ＩＤを持っているので、
右側の石の呼吸点が見つかると、それが同じサイクル中で
左側の同じＩＤの石すべてに伝播される（その行の中でつながって
いなくても）

ということらしいです。なるほど、これなら正しく動きますね。
私のは連ＩＤ持ってないので気づきませんでした（つながって
ないと伝えられない）。大変失礼しました。

連ＩＤを全部保持しないとならないので回路食いそうな気は
しますが。まあだからRAMにしまわざるをえなかったのでしょうかね。

SWoPPのFPGA囲碁論文を読んでみた…けど

いや、これじゃだめなんじゃ？

この論文ですが、全文読みましたが、上からスキャン、その後下からスキャン、ではたとえば

*****+*
*ooo*o*
*o*o*o*
*o*o*o*
*o*ooo*
*+*****

こんなとき、白の連の呼吸点は往復スキャン後、N字の左肩のみ２でその他はまだ２になってないですよね。これでは連の認識できてないと思いますが。

あれでも、学会の論文て査読とかあるんだっけ？それ通った？てことは私が何か勘違いしてるのか？…あれ会議は査読ないんだっけ？アカデミック界のことはまったくわかってません。

どなたかSWoPP2009出た人いませんか？質疑で何か言ってなかった？

しかしこれで実際間違いで、でもプレイアウトやったら実際勝率上がった、のだとしたらそれこそ「嘘のようだが本当なのだ！」ですね^^;

FPGA囲碁ソース公開

FPGAモンテカルロ囲碁のソースを公開します。このページの左上の「資料館」のところに置きます。

去年７月ころに作ってたものまったくそのままです。もう１年くらいいじってませんが、最近GPWやSWoPPで発表があったり、某ブログでも開発が始まったりしてるので、参考になるかと思い公開しときます。

＃一年前は「こんなの他に誰も興味ねぇんだろうな～」と思ってたんですが^^;

この回路がやるのは、単にモンテカルロのプレイアウトを終局まで行うだけです。１年くらい前に「UCTがネックだなー」と言ってたところで開発止まってて、そこから進んでません。FPGAに焼くための環境もできてませんが、SIMLはできます。合成も前にやったので通るはずです。SIMLの流し方は中のREADMEをご覧ください。多少の解説もREADMEに書いてます（あまり大したこと書いてませんが）

SWoPPの論文はまだ見てませんが、Webで見える要約だけは見ました。19路でのプレイアウト速度はなかなか出てないみたいですね。GPW2008の発表では、メモリをシリアルに読んでるとかいう話だったのでそこがボトルネックだと思ってましたが、SWoPPのは同じ構成なんでしょうか、別物なんでしょうかね。

打ち上げる石の認識は、やり方完璧に忘れてたので今コード見てみたら、ちょっとトリッキーなことやってますね。簡単に言うと、１サイクルで上下左右の四方に一路ずつ「連ID」と「呼吸点の数が0か1か2以上か」を伝播します。連IDとは、呼吸点の位置IDの最小値。連IDが意味を持つのは、呼吸点が１のときだけ。隣どうしが、呼吸点の数が違うか、呼吸点の数がともに１で連IDが違ったら、伝播して次のサイクルへ。伝播しきったら連の認識完了。つまり、１手打つごとに複数サイクルかかります。一局が400手強で2700サイクルだと、１手平均7サイクル弱かな？白の連の唯一の呼吸点に打つとき、その連を打ち上げます。

話は変わりますが、例のライブラリ論争中にずっと脳内を流れてた曲があるんですが、なんと動画ありました。だいぶ昔のなんですが。

これはぜひ選手権の公式ソングに認定してもええんではないかと。

変り身の術

暑い日が続いてますねぇ。いやー暑い。こう暑いと、コンピュータ将棋の開発なんてもうやってられなくなりますよね。いやーそれにしても暑い。

そんなわけなので、最近はもっぱらコンピューター囲碁の開発をやっております。前回書いたように、PC<->FPGA間の通信が遅いため、gtpはPC、UCTはNios、MCはFPGAエンジンで行う、という方針。MC部は一応できてます。gtp部はggmcのコードを見て、まあ半分以上パクれそうなので（というか、ggmcのgtp部自体半ばgnu goのパクリっぽいので）、これはまあできそう。PC<->FPGA、Nios<->エンジンのI/Fはまあ将棋の例を参考に適当に決めて、あと残るはUCT。

算数落ちこぼれの私には相変わらずあのlogやsqrtの意味はわからないものの、まあ呪文と思ってとにかくあの式の「UCB値」最大の枝を選ぶ、と思えば何とかできそう。ggmcやuct_aya.cppを眺めてるうちにアルゴリズムは何となくわかってきました。とここまで進めて、「何だけっこう簡単じゃん」などと一瞬思ったのですが…ここでハマってしまいました。

Niosは50～60MHz程度では動くはずですが、上限はまあ試したわけではないですが100MHzまではいかんでしょう(cyc3)。単純に考えてPC用CPUの数十分の一。MC部のエンジンは前回のとおり20MHz, 3000cycle/playoutとすると、Niosが60MHzとするなら9000サイクルごとに次にplayoutするノードを見つけないといかんわけです。ですが普通のUCTのアルゴリズムだと、１回ごとにルートノードからすべての手のUCB値をみて、最大の枝を見つけて降りて、そこでまた同じことを繰り返し、とやります。で各手ごとにlogやsqrt計算して。これ、ざっと考えると軽く9000サイクル越えるんですよね orz つまり、仮にMCエンジン単体が 10,000 po/sec の能力があっても、UCT部がネックになって、システムとしてはその半分の 5,000 po/sec も出ない。「ボトルネックはMC部。そこをFPGA化すれば速くなるはず」と思いこんでたんですが、ふと気づくとボトルネックはUCTになってました。

まあ速度に目をつぶれば「世界初のFPGA囲碁」を作るのはそう難しくはなさそうなんですが、囲碁的に弱いのはまあ最初は仕方ないとしても、速度(po/sec)的にPCソフトと大差ないのではFPGAにした意味がなく、インパクトがぜんぜんありません。これでは面白くない。

といってここで諦めるのもちょっとくやしいので、何とかUCTを高速化する手法がないものか考えてます。いやもともとこんなこと手を出すつもりはまったくなかったのですが、どうも成り行きで。一応アイデアっぽいものは考えてはいるんですが、まだ定量的に詰めきれてなくて、これでもまだ速度不十分かも。それにノード選択が若干不正確になるんでほんとにこんなんでいいのか。全く予想外の展開に頭を痛めてます。

つい出来心で…

作者急病につき、今週の「A級リーグ指し手１号」は休載します。お詫び申し上げます（編集部）

　　…えー、（コホン）…

コンピュータ囲碁ブログ始めるっす～
テーマは、FPGAでモンテカルロ囲碁、ということで。以後よろしゅうに～

というわけで、MC囲碁つくってみました。先日の講演会の後、３週間ほどこればっかやってたりして。現状、verilogコーディングはほぼ完。今のとこまだコウの扱いができてないので、SIMLでのplayoutではほぼ終局まで進み、最後に残ったコウで無限ループ、という状態ですが、まあ９割方できたといっていいでしょう。

CycloneIII EP3C120 で合成して、7万LUT弱。動作周波数は、STAでマルチサイクルパスの制約をちゃんと記述できてないのでまだはっきりわからないですが、たぶん20MHz前後でしょう。SIMLまだあまり数やってませんが、２回ほどやったとこでは、初期局面から終局まで3,000サイクル前後。約6,700 playout/secですか。山下さん講演では1,830 po/secとのことなので、ソフトの3.7倍くらい？まあ今は「とりあえず一発作ってみた」レベルなので、まだかなり速くはなりそうです。あとStratixIIIにすれば２倍になるだろうし。なんだかんだで、がんばればFPGA１コアがソフト１コアの10倍くらいでしょうか。

playoutでの手の選択は、今のところはかなり簡略化バージョンです。石を取る／アタリを逃げる、つまり（黒白とも）自由度１の連の呼吸点に打つ手は重み大、他は合法手すべて一律同じ、という感じ。pure randomよりは若干マシ、という程度です。3x3のパターンや、直前の手の近くを優先、くらいは割と簡単にできそう。シチョウは…あまり考えてませんが、一見難しそうかな。ローカルな情報だけでできることは簡単そうなんですが、遠くの情報が必要なことは大変そうです。アタリを「かける」のは、論理的にはそう難しくないですが、物量食うのがネック。自由度２まで認識せんといかんので。

TODOとしては、FPGAに焼くというのは当然ありますが、まずplayout以外のところを何とかしないと。ggmcがフリーでソース見れるので、まずはこれを19路に変えてそのまま使おう、ともくろんでます。でも私は、あのlogやらsqrtやらの意味さっぱりわかってませんので、FPGAのplayout部だけ私作るから、誰か組み込んでみません？とかいうことになるかもしれません。

今後は将棋にせよ碁にせよ、その時々で気の向いた方を書いてくつもりです。どっちかしか興味ねぇ、という方は、「カテゴリ」のところで「将棋プロセサ」か「囲碁プロセサ」を選んで下さいませ。