2017年4月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            

tweet

  • tweets

« つい出来心で… | トップページ | 開発道路地図(西日本編) »

変り身の術

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

そんなわけなので、最近はもっぱらコンピューター囲碁の開発をやっております。前回書いたように、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のアルゴリズムだと、1回ごとにルートノードからすべての手のUCB値をみて、最大の枝を見つけて降りて、そこでまた同じことを繰り返し、とやります。で各手ごとにlogやsqrt計算して。これ、ざっと考えると軽く9000サイクル越えるんですよね orz つまり、仮にMCエンジン単体が 10,000 po/sec の能力があっても、UCT部がネックになって、システムとしてはその半分の 5,000 po/sec も出ない。「ボトルネックはMC部。そこをFPGA化すれば速くなるはず」と思いこんでたんですが、ふと気づくとボトルネックはUCTになってました。

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

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

« つい出来心で… | トップページ | 開発道路地図(西日本編) »

囲碁プロセサ」カテゴリの記事

コメント

初めまして,ggmc の gg です.UCT 部の速度がネックになるとのことですが,9路なら兎も角19路でそれは考えられません.更新時にやれば木を降る時は ucb 値の計算をする必要はありませんし,回数も少なくなります.値を覚えておく場所が必要ですが.また木を下る回数(深さ)は余り増えませんよね.特に19路では.各レベルで(終盤を除いて)100手位分岐するとすれば木の深さは高々一桁でしょう.

ggさま
どうも、はじめまして。ggmcはかなり参考にさせていただいてます。

[彩のページより抜粋]
UCB = その手の勝率 + α * sqrt( log(すべての手を試した回数) / その手を試した回数 )

この値、1回playoutするごとに変わりませんか?「きちんと」やるなら1回ごとに再計算になる(値を覚えておく、が通用しない)と思うんですが。まあ「あんまり変わらない」ケースは多そうなので、そういうケースで再計算さぼる、とかいう手はあるとは思いますが。
ソース読んだときggmcも再計算してたような気がしましたが…勘違いしてたかな?

分岐100手、深さ5として500回。logもsqrtもdivも10cycle以上かかるので、こっちがボトルネックになると思ったんですが。

私は囲碁は新参者なので、何かとんちんかんなこと言ってましたらお許しください。

ggmcを利用して頂きありがとうございます(_ _).
本題ですが,playout毎で合ってます.しかしタイミングも含めて考えると,木を降る時に変化することはなく,シミュレーションが終わり,降りる時に通った経路中の手の値(具体的にはvisitした回数とwinの回数)を更新する時しか変わりません.ですから更新時に計算しておけば,降りる時に計算する必要はありません.但し,sum of visits(分母)が変わるのでノード中の全ての手について計算しなければなりませんが.
あら,今見直したら,MoGoのレポートの擬似コードでは降る時に計算してますね,なるほど.Sylvainがこんな簡単な最適化を見落とすとは思えないが...あ,結局計算する回数は同じになるのか.これは失礼しました (_ _).
これだけではあまりなので,情報を一つ.今のMoGoはUCTを使ってない,つまりαはゼロなんだそうです.これはRAVEや色々なheurisicsの効果と思われますが,こうなればハード化も楽になりましょう.

>sum of visits(分母)が変わるのでノード中の全ての手について計算しなければなりませんが.

これがガンなんですよねぇ…

>今のMoGoはUCTを使ってない,つまりαはゼロなんだそうです.

UCTを使ってない、はたしかComputer-Go MLで見ましたね。(MLには入ってませんが、アーカイブを時々見てます)ただ、じゃあどうやってるのか、がよくわかっていません。単純にα=0、というわけではないのでは?まあMogoはいろいろheuristicやら入れてますんで、簡単にはまねできないような予感がしますが、知りたいところではあります。

MoGoの手法の最新版はこれでしょう.
http://www.lri.fr/~teytaud/eg.pdf
でも私のも今は Cp=0 が一番勝率が高い.RAVEしか入ってないのに.Network 並列なので一局面複数シミュレートになってますけど.
後,これは一手当たりの時間を固定して測っているので,計算が省けて速くなってる分も含まれてます.

情報ありがとうございますm(__)m
ざっと見ました。タイトルがggさんが以前和訳されたものと似てますが、中身違うのですね。
α=0、はこれですか。

「playoutでいい手打つようにしても強くならない」と断言してるのが印象強かったです。
"dark art"かぁ…助けてスネイプ先生

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/507007/22413409

この記事へのトラックバック一覧です: 変り身の術:

« つい出来心で… | トップページ | 開発道路地図(西日本編) »