変り身の術

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

そんなわけなので、最近はもっぱらコンピューター囲碁の開発をやっております。前回書いたように、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を高速化する手法がないものか考えてます。いやもともとこんなこと手を出すつもりはまったくなかったのですが、どうも成り行きで。一応アイデアっぽいものは考えてはいるんですが、まだ定量的に詰めきれてなくて、これでもまだ速度不十分かも。それにノード選択が若干不正確になるんでほんとにこんなんでいいのか。全く予想外の展開に頭を痛めてます。