開発道路地図

モンテカルロ将棋キターー！！！
http://d.hatena.ne.jp/yos92/20080625
いやぁやってくれましたねえ。yowai_gpsに勝てれば１次突破レベルですよね。今でこれだと、来年の大会ごろはどうなってることか。楽しみというかこわいというか。
しかしだんだん、皆さん好き勝手というかハチャメチャやるようになってきましたねー。いやハチャメチャとか言っちゃ失礼なんですが。でも私の中では誉め言葉なんですよ。「バカヤロウは愛の言葉」とかいう歌もありましたが。いやそれはともかく、コン将まじで面白くなってきてるかも。私も謹んで前衛の道に邁進したいと思います。（ちょっと待てお前どっちゃ行くんだコラ）

さてタイトルですが、和訳してみました。何かこう、全然違うような。オフロードバイクで週末どこ行こうか、みたいな。こういうこと書いてると、「オフロード　地図」とかで検索してくる人必ずいるんですよね。中身見て脱力するんじゃないかと思うと申し訳ない気も。まこれは検索エンジンの問題ということで。単純なgrepみたいなアルゴリズムじゃだめだぞGoogle。アキバ＠Deepみたいなの作れんのか。

というわけで前号の続きですが、

２）ハッシュ

…まだできてませんorz　いちおう動くものはいったん作ったんですが。6/22-23 floodgateでやってたのがそれ。ただ、次の一手問題でノード数計ると、１割減くらい。レーティングも５月末と大差ありません。このバージョンまだ性能バグはあるんですが、それ直しても大幅改善はなさそう。ハッシュだけで３週間くらいかなり力入れてやったんですが、うーんたった一割か…当初は、もしかしたら２倍くらい行ってくれんかのう、と期待してたのですが、外れ。あもしかして実装どっか間違ってる？まあ３週間で10%向上ならよい方なのかもしれませんが。他に「３割５割は当り前ー！」（古いか？）のネタもいくつかありますし、最近何かと他で忙しいこともあり、ハッシュ関連はモチベーションが下がってあまり進んでない状況です。まあいずれ「失敗の記録」ということで顛末を書きたい気もしますが。

３）デバイスグレードアップ

08年5月の大会で使った（＆今も使ってる）FPGAは、Altera社のCycloneIIIというやつです。このCycloneというのは「普及品」のシリーズで、もう一つ高級品のStratixというシリーズがあります。これの今の最新版はStratixIII。つい最近StratixIVの発表がありましたが、実物の出荷は恐らく来年以降なので、09年の大会には調整等含めると間に合わないでしょう。で、近々StIIIのボードの購入を検討中。

Altera製ボードで、30万円強のStIIIボードがあり、今のところこれが本命。
http://www.altera.co.jp/products/devkits/altera/kit-siii-host.html

搭載FPGAはStIIIのEP3SL150で、今のCycIII EP3C120より回路規模はちょっと大きいくらい。ツールは、無料のWeb EditionはStIIIには使えないのですが、このボードには通常のSubscription版の１年限定ライセンスがついてきます。１年過ぎると使えなくなるんですが、まあ１年後にはまたStIVのボード買ったりするかもしれんので、まずはこれでいいか、と思ってます。

あと候補としては、台湾Terasic社のDE-150というボードもあり。価格は大差ないですが、こちらはツールがついてこないのがネック。こっちの魅力は、DE-340という大型チップの載ったボードが同じシリーズであり、こちらへの移行準備にもなるという点なんですが、この辺は後のマルチコアのところでまた書きます。
立野電脳(Terasic代理店） http://www.dsp-tdi.com/
　　　　　※ここ、時々うちのブログのSponsered Linkのとこに広告として載りますね

StIII化による性能向上ですが、実物がなくてもコンパイルはできるので試してみたところ、まったく同じソースでCycIII->StIIIに変えるだけで15MHz->30MHzと２倍になりました。これはもうほんとに私は何にもせずに、お金出すだけで倍になるので、非常にありがたい。ボード立ち上げはたぶんほとんど手かからんと予想してます。

♪首ったけの彼女を　押え込みできるぜ
　金がありゃ　（金　ねーか）
　金がありゃ　（金　ねーか）

Heinzの論文に「深さ１深く読むとレーティングで200上がる」というのがありました。ほんとか？というのもありますが仮に信じるとしましょう。だいたい深さ＋１でノード数５倍くらいになると思ってます。とすると速さ倍になれば
200 x log2 / log5 ≒ 80
くらいレーティング上がるのかな？かな？と、絵に描いた狸の餅算用をしてます。今、目先の目標はマイムーブですが、レーティング差が250くらい。うーん、まだ届かん…

開発ロードマップ

昨日6/14は電通大の講演会に行ってきました。調布といえば（私の中では）天神通商店街の路上アートですが、かなり久しぶりに行ってみると何と！鬼太郎＆目玉おやじ復活してましたね。いやーめでたい。もちろん猫娘ねずみ男も健在でした。

演題の方は、５五将棋もなかなかでしたが、FPGA派の私としてはUCTに興味をそそられました。これってFPGA向きじゃね？とか。コンピュータ囲碁は実はもう何年も前から興味は持ってて、GNU GOのドキュメント目通したりはしてたのですが、コン将で手いっぱいでとても手がまわらなくて。今回も結局思っただけで終わりとなるような気もしますが。うーんでもいつかやってみたいなー。

帰りはコン将関係者と夕飯。他の開発者の皆さんと話してると開発意欲が湧いてきますねー。実はこれがいちばんの収穫だったりして。

さて本題ですが、大会が終わって「とにかく早く間に合わせないと」のパニック状態から脱け出して落ち着いたところで、今後の開発方針をじっくり考えてました。もちろん大会中に仕入れた情報も反映の上。現在のロードマップとしては、大項目は以下を考えてます。優先順位順に

１）時間制御
２）ハッシュ
３）デバイスグレードアップ
４）P&R
５）パイプライン
６）マルチコア

この他にも細かい項目はいろいろあるんですが、数十％以上の効果が期待できるものとしてはこのくらい。このうち１）は既に実装完。２）－４）は来年の大会までには十分できると予想してます。５）は微妙。６）は来年は間に合わないかもしれないが、再来年はできる見込み。

以下、各項目について（次号以下も含めて）詳しく書いていきます。

１）時間制御

自戦記でも書きましたが、マイムーブの時間制御は大変参考になりました。大会版のAリーグは、とにかく１手を決められた深さ読みきるまで読むようになってました。これだと１手１秒のこともあれば５分のこともある。すると時間制御としてはワーストケースに合わせざるを得ないため、時間のあるうちは深さ８、残り少なくなると深さ７、と固定で探索してました。西村さんから聞いたのは、ルートで深さ１ずつ反復深化していき、あるループが終わった時点で消費時間等を考慮して、次のループに行くかどうかを決める、というもの。これだと、深さ８が１秒で終われば、次深さ９を安心して読めるわけです。これはよいと思ったのでさっそく採用。ルートの反復だけ特別にハードで作るのも大変なので、ここだけNiosのソフトで扱うようにしました。また、そうしたついでに、aspirationも実装。これは大した手間じゃないですからね。あ、あと相手時間中の先読みも入れて。これで、序盤で9-11手、終盤でもワーストケースを除いて8-9手読むようになりました。１局の消費時間も、今までは3,4分で終わったかと思えば次はタイムアウトで負けたり、というのがありましたが、安定して10分前後使うように(floodgate, 15分で)。この効果は如実で、KShogi初級には勝ち越せるわ、floodgateのレーティングは上がるわ、マイムーブには念願の初勝利をあげるわ。西村大先生ありがとうございます。

ちなみに５月末ころfloodgateでやってたバージョンは、大会版から
　・例のバグ対策
　・定跡のランダム選択(floodgate対策）
　・上記時間制御＋aspiration
を変更したものです。他の点（評価パラメタ等）は変えてません。というか、上記の変更の効果を知りたかったので、意図的に同じにしてあります。

２）ハッシュ

これも自戦記に書いたとおり、大会中にいろいろ皆さんから話を聞いてやる気になってみたものです。ここ２週間ほどずっとハッシュを検討してまして、実はいったんコーディングもしてみたんですが、いろいろと課題がありまして、見直し中。今書くととりとめなくなりそうなので、続きはまた一段落したら書きます。次号はハッシュ特集、になるかも。