なんでまた『オープンソースで学ぶバイオインフォマティクスほしい』のか？

うさねこブログで宣伝（？）を見まして。けっこう興味あったりします。

http://itoshi.tv/d/?date=20080219

私はバイオという分野自体についてははっきり言って門外漢です。が、そこで行われている計算に興味があります。オープンソースならまあ計算の中身については多少はわかるでしょうから（なぜそういう計算をするのか、がわからなくても）。

バイオに限らんのですが、今現在は１００％ソフトで行われている計算を、FPGAで専用ハード作れないか？そしたらなにがしかメリット出せないか？という観点から見てみたい。

ここ半年あまり、私は（それまでは１００％ソフトでやっていた）コンピュータ将棋をFPGAで実現する、という目標に向けていろいろ試行錯誤してきました。その結果、思ってたよりも簡単にFPGA化が実現でき、しかも性能が（まあ単純比較すれば）ソフトの１０倍以上出せそうなことがわかってきた。もちろん将棋の場合は「強く」ないと製品としてはNGなわけで、将棋として強くする工夫はまだまだ必要でしょう。ですが、研究と製品開発、とフェーズを分けて考えると（私は企業のエンジニアなのでこういう見方をついしてしますのですが）、実現のfeasibilityを示す、という研究面では一応成功した、と言えるかと思います。これから強くする工夫を含む「製品開発」フェーズがあり、それはそれでもちろん大変なわけですが。

で、コンピュータ将棋の「製品化」作業は進める一方で、「他にFPGA化できそうなものってないのだろうか？」という、別の「研究」対象探しに興味が多少向かっている、というわけです。

今の実社会でのFPGAの使われ方を見ると、今までASIC（カスタムLSI）で作ってたものを、開発費の安いFPGAで置き換える、あるいは今まで汎用マイコン＋外付けグルーロジックで作ってたものをFPGAでまとめて小さく作る、といった、いわば「ハードを別のハード（FPGA）で置き換える」という例が大半なんじゃないかと思います。ソフトをハードで置き換える例というのはあまりない気がします。まあ私の知らないところでいろいろあるのかもしれませんが。

コンピュータ将棋のFPGA化を通じて、私は「これはものすごいポテンシャルあるかも」と感じました。もちろん、FPGAにはソフトと比べていろいろ制約がありますので、何でもFPGA化するわけにはいかない。FPGA化に向いたものと向かないものがあるだろうと思います。なので、計算インテンシブな分野をひとつひとつ見ていき、対象になりそうなものがないか探していこう、と画策してるわけです。

バイオはその手はじめ。他にもいろいろあるんでしょう。計算化学なんてのも面白いのかも。素因数分解なんかも実はやってみようかとちらっと思ったんですが、最近WEB見直してみたら、RSA Challenge（素因数分解に賞金出してた）が去年終わってたようで、なーんだ残念、賞金出ないとやる気出んなー、などと思っていたところ。

こういうことをやるにあたって最大のネックは言うまでもなく、ハード設計のできる人間がバイオなり化学なり代数なりをある程度は理解しないとならん（あるいはその逆）、というところ。私はコンピュータに関してはハード・ソフトとも一応わかってるつもりですが、バイオも化学もまるで素人ですから。ただ、１００％理解する必要はなくて、要はそこでどういう計算が行われるのか、だけ理解すればいいわけで。何とかその辺を「少ない工数で、計算部分だけ理解」といかないかな、などと考えてるわけです。まあそうはいってもなかなか難しいんですが。

AlteraさんAlteraさん、どうなってるんでつか？

最近floodgateが盛り上がってるようで。とてもすばらしい試みだと思います。開発者の方々に大感謝です。

で、私としてもやってみたいのですが、何しろまだ自動対戦ができていない状況で^^; あらかじめ配列で与えた局面たちへのregressionと、コンソールから指し手を手入力して盤面を進める、& 手を考える、というのしかまだ実装してません。そこまでできたところで将棋のデバッグに戻り、FPGAの環境立ち上げの方は後まわしにしてたんですが。floodgateが来たのでこれは是非やりたいと思い、通信の方も少し優先度を上げてやりはじめました。

以前からFPGAとホストの通信形態として 1) hostfs でパイプに読み書き 2) USB 3) Ethernet の３つを検討していたのですが、1)は実験したところ動かないことが判明。2)もいろいろボードの構成を調べたところ、config用途以外には使えないことがわかりました。もともとEtherが本線だろうなとは思っていたので、これを検討しだしたのですが。

Etherの細部の仕様など当然知らなかったので、例によってまた本等読んで調べて。MACコアはAlteraサポートに問い合わせ、Triple Speed Ethernet (TSE)を選択。あと、ボードのスケマを目を皿にして眺め、TSEとFPGAピンの結線を決めて。

それでまあいちおうFPGAを設計してみました。あ、まだ将棋エンジンは入れず、Nios + MACだけ入れて、Etherを動かすためだけの実験用。で、コンパイルしてみたのですが、次のようなエラーが。（原文は英語）

　rx_controlはピン位置AB4にアサインできません。同じバンクの他のピンのVREFとして
　使用しています。

ボードにMarvell 88E1111というEther PHYチップが載っていて、それとFPGAがRGMII でつながっています。RGMIIの仕様ではピンは1.5V HSTLで、これにはVREFがいるのですが、Cyc3ではI/Oのピン位置ごとにVREFのピンが決まっています。で、このrx_controlピンは、他のEtherのピンがVREFとして使うピンにアサインされている。

…いや、これ、ボードの設計ミスのような気がするんですが--; いちおうAlteraに問い合わせ中ですが。あれ、何か勘違いしてるのかなぁ。でもやっぱり…

MIIでも別にできるならいいんですけど、このボード(DK-DEV-3C120N)、MIIの信号つながってないんですよね。RGMII決め打ち、みたいで。逃げようがない。

実はこれだけでなく、別件でソフトにもバグがあって。Alteraから提供される環境をそのまま使ったのではコンパイルエラーになってしまう、というのもありました。やはりTSE周り。まあこれは、#define追加で簡単に直る程度のものだったのでいちおう使えてるのですが。

そんなこんなで、或る寺さんにはいまいち不安を覚えている今日この頃です。NiosII + 将棋エンジン、の構成で今までやってたぶんにはバグはなかったんですが。TSEとかNiosとか、コンポーネントによって出来不出来があるんでしょうかね。Niosは力入れてるけど、TSEはおざなり、みたいな。

Cyc3が発表されたのが、昨年夏くらい？このキットができたのは去年１１月のようです。（中のファイルをls -lすると。）ちょっと早く買いすぎたのか…まだバグの取れてない「α版」をつかまされた？という気もしてます。でも、開発キットってupdateとかあるんでしょうか。

私の不安が的中してると、このボードではどう逆立ちしても通信できない、ということになってしまうので、またまた前途多難な状況です。

アッラーの御名において、Stand-Patは気持ち悪い

先週の記事を書いたところ西村さんからご指摘をいただきまして。もう少しコメントします。

まず「静止探索」という用語ですが、私は単に一般的に「末端を安定した局面にする手法の総称」という意味で使ってます。ですが、西村さん記事を見て、Stand-Patを使う手法がもしかして一般的で、静止探索といえば普通こちらを指すのかな、と気になったので、以下ではこちらは「Stand-Pat方式」と呼んでおきます。

私のやってる（広義の）静止探索は、最初の記事に書いたとおり、通常探索と手生成の幅以外まったく変わりません。パスは２連続してはじめて末端になります。ですが西村さん記事を見ると、Stand-Pat方式ではパス１回で末端にしてることと等価、と思えます。（私はStand-Patのことを読んだのはだいぶ前で、ろくに覚えてませんが。勘違いしてたらご容赦。）で、先週の記事は、私の流儀を前提に書いてる、ということでご理解ください。

最初にDeep Purpleを作りはじめたとき、静止探索の手法も検討したはずですが、たしかそのときは検討したけど「何か変」とか思ってStandPatはやめた、と記憶してます。私は世の中のやり方に従うより「原理原則に照らして、本来どうあるべきか」と考えてしまう「原理主義者」なもので。

StandPat方式で、たとえば読み技２３図△２五桂のあとでパスして末端、とする理由は、推察するに「▲３八馬みたいな応手がたぶんあるだろう。あると仮定しよう。また、細かい位置関係（馬が３七か３八か）は無視して駒の損得だけ考えることにすれば、３七馬の状態で評価したっていいはずだよね」なんだろうと思います。でもこれやっぱ変ですよね。駒が詰まされてたり両取りだったりして、うまい応手がないこともあるし。また、たとえば先手が２八玉、３七金とあるようなときに△２五桂が来たとして、金が３八へ引くか２六に出るしかないか、によって評価値はだいぶ変わる。３七で評価していいの？とか。

と言いつつも、ハードで作ると「応手」を生成するのがけっこう難しいので、StandPatも少し検討してみました。パス１回で末端にするのは簡単だったので実装してみて。あと先週書いた「打ち以外のみ生成」も実装したので、全幅１手＋打ち以外１手＋静止４手、の設定にして、「パス１回で末端(≒StandPat?)」と「２連パスで末端」とを両方読み技２５題regressionして比較。手が変わるものもありますが、同じ手を返した問題どうしを比べると、２連パス末端の方が1.3～2倍くらいノード数が増えました。うーんこれはたしかに大きいのですが。

手が変わった中では、先週も出した２３図でStandPatの方は▲６四馬、となりました。相手玉近くに利きが増えるのと、次△２七歩成を比べて、歩成の効果の方が小さいというのはまあチューニング不十分ですが、２八飛が詰んでることに気づかないのは致命的。StandPatだとここでパスして終わり、ですから。対して２連パスの方は▲３八馬になりました。△２五桂をあらかじめ避けたんでしょう。今回は２手めに打ちがないので、△６五歩の心配がなく、歩損がなくなったようです。

ノード数と悪手回避とどちらをとるか、ですが、この例見るかぎり私としては、んーやはりStandPatをやる気はしないな、と思ってしまうんですが。

静止探索の具体的手法って、強さに直結する割にはあまり議論されてないような気がするんですが、気のせい？探索がαβかPVSか、とかよりもよっぽどクリティカルだと思うのですが。理論化とかがしづらく議論しにくい話題なのか、それとも皆さんノウハウで外に出さないのでしょうか。

Bugじゃない、Featureだ！

regressionを流して、見つかるバグを対処中です。まあ毎度のことではありますが、後から後からという感じで出てくるのを、嫌気さしながらも順次直してるところ。

探索は、当初は反復深化やら延長やらといろいろ入れてたのですが、デバッグのときややこしいので、まずは超単純に、ということで、「超基本αβ」バージョンを作って、これでデバッグしてます。探索はαβ。反復深化無し。深さ固定、延長一切なし。手生成はもちろん、全幅＋静止のみ。

…いやー、何かいい感じ？余分なもの全部そぎ落とした、男のコンピュータ将棋、みたいな？

これでバグったらアホやろ、と思いつつ、しっかりバグってましたが。まあ見つけ次第直してるんですが、そのうち、悪手なんだけどよくよく調べるとバグじゃない、というのがあって困っているところ。

例をあげます。「読みの技法」第６図。

A1 F3

ye----gey
--igo-i--
f-ffff--f
------H--
---------
-------h-
F-uFFFF-F
-GI---IF-
YE-O--GEY

F2
senteban

みづらい書き方ですみませんが、私はいつもこれ使ってるもんで。
　歩香桂銀金角飛王　＝　FYEGIAHO
　成ると　　　　　　＝　TSMZ UR
です。'K'ではじまる駒は多いので、それらはアルファベットの２文字め(KYO なら 'Y')。SMZはわかりづらいですが、SMはkyoSha, keiMaから。Zは全。先手大文字、後手小文字です。

全幅２手＋静止６手、でやってみそ。▲３二飛成、と指してくれやがります。最初「やれやれ、またバグかよ。しょーがねぇなぁ…」とかいってデバッグ始めたのですが、実はバグでない＝全幅の本質的問題、と気づき愕然。他の全幅ソフトでもおそらくこう指すと思います。

▲３二飛成、△同銀、▲７七銀(金)、▲パス、△パスと読んでいる。（２連パスで末端。）初手▲７七銀なら、△４九角！と読みます。ここで深さ２消費したので、次からは取りしか読みません。以下▲パス、△３八角成、▲同銀、△２八飛成、▲パス、△３八竜。で、「▲７七銀より▲３二飛成がマシ」と結論するわけです。つまり、△４九角の後で急に読みが狭まるため、△４九角が(実は悪手なのだが）いい手に見えている。で、それを追い出す水平線効果で無茶をする。

これって要は、「末端までには局面を収束させなきゃだめ。そのためには、全幅＋静止だけじゃ不十分」と言ってる気が。全幅と静止で「段差」がありすぎるのが×。前に指した手の「応手」はひととおり指せる程度に「段階的に」手を狭めていく必要がある。（手生成の「バリアフリー化」？）言い換えると、「しょせん全幅じゃだめ」ってこと、と思えるんですが。末端に行くにしたがって前向き枝刈りはしょせん必須…というのは、考えてみれば静止が必須という時点でわかってるべきことですが。

もう１例。深さ設定は同じで、読み技第２３図。

F1

ye-i----y
-og-i----
-ff--ge-f
f---fafh-
-----f---
F-FFF-Ff-
-F--G-U-F
--OIIG-H-
YE-----EY

F2
senteban

ここで▲３五歩です。歩損はしかたないと思っている。△６五歩が来ると歩損必至なので、それには▲７七桂（か▲６七金＊）だとよさそうですが、すると△２五桂！とはねます。対して▲３八馬とかできればなんてことはないのですが、静止なのでそれはない。以下▲２六馬、△同角、▲同飛、で末端。馬×角交換は歩損より大きい設定になってるので、「歩損やむなし」と結論してます。

…うーん、またまた困った…全幅じゃだめ、前向き枝刈り必須、と言われても、ハードだとあまり複雑な手生成はできません。まあそこを何とか、ハードでできる範囲でどこまで手生成を絞るか、が次の課題となりそうです。

チェスでは全幅＋静止で十分だったようですが、やはり将棋とは違うんでしょうか。打ちがあるのがやっぱ大きいのかな。まあ、「打ち以外のみ生成」くらいだったらハードでも何とかできそうなので、このくらいでうまく行ってくれるとありがたいのですが。でも上の２３図ではこれじゃだめですけどね。

しかし、いっそバグであってくれればよかったのになぁ…直せば済むんだから。これ、根本的に考えなおさないと…

Bonaとかどうしてるんでしょうね？