変り身の術

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

そんなわけなので、最近はもっぱらコンピューター囲碁の開発をやっております。前回書いたように、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部だけ私作るから、誰か組み込んでみません？とかいうことになるかもしれません。

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