FPGAによるコンピューター将棋 2012年の結論
ここ1ヶ月ぐらい更新をお休みしていたのは私のなかで一つの結論が出たからです。
その結論を書いても仕方ないかと思い、書かずにこのブログのことは放置しておりました。
ところが昨日、GA将!!!!!!さんにこのブログが見つかった(http://d.hatena.ne.jp/Gasyou/20121215/1355545292)のでここにその結論を書いていきます。
かなり長い話になるので順を追って説明していきますね。
Terasicから最新のFPGAを搭載したFPGAボードが発売された
まず、現段階で入手可能な内蔵メモリのそこそこ多い、最新のFPGAボードのお値段が発表されました。
DE5-Net FPGA Development Kit
http://www.terasic.com.tw/cgi-bin/page/archive.pl?Language=English&CategoryNo=158&No=526
$8,000です。digikeyで70万円ぐらいでしょうか。そこそこお高いです。
内蔵メモリは3MB程度しかありません。当然いまどきのコンピューター将棋の評価関数テーブルは載りません。
評価関数のためにメモリを食いつぶすアプローチは失敗する
Bonanzaの評価関数のうち、ビットを圧縮したり、無駄な部分を取り除いたり、3駒関係のうち、駒が近接していなければ大きな値はつかないのでそういうのを端折ったり…まあいろいろ考えたのですが、そういうアプローチでは無理です。どうやっても載りません。
FPGAは製品サイクルがかなり長く、なかなか次の世代のFPGAが出ません。
Stratix V(が搭載されている評価ボード)は出たばかりなので、次の製品は2,3年後ぐらいになるでしょう。
2,3年後にいまの内蔵RAMが倍のサイズになったとしてもそれでもBonanzaの評価関数を載せるのはかなり厳しいものがあります。
(評価関数のためだけに内蔵RAMを使いきってしまうわけにもいきませんし…)
ゆえに、こういうアプローチではどうしようもならないことがわかります。
わかりますというか、わかりました。
A級リーグ指し手1号の製作後、その作者の伊藤さんがBonanzaの保木さんに「Bonanzaの評価関数そのままというわけにはいかないのですか？」と尋ねられたことがあったと思うのですが、いまですら内蔵RAM的には極めて厳しいので、当時なら当然全く話にもならないレベルだったでしょう。
よく知りませんので間違ったことを書いているかも知れませんが、FPGAの内蔵RAMとはSRAMです。SRAMはとても高価です。
IntelのCore i7のL1 cacheとか長らくコア当たり16KBから増えないところをみますと、SRAMを大きくするのは高くつくというのがわかるかと思います。
FPGAはそのSRAMが3MBも(!)載っているわけです。この時点で、FPGAが高価になるのは自明の理です。
2,3年後にいまの倍の内蔵RAMが載っているFPGAが発売になったとしても、お値段も倍ぐらいになっていることは想像に難くありません。
そこで評価関数のためにメモリが数MB規模で必要になるようなアプローチは3年ぐらい先まで見越したとしてもFPGAでは現実的ではないということがわかります。
省メモリな評価関数の設計
結局、3駒関係は無理、KKPも厳しいかも知れません。
しかしBonanzaの発表資料を振り返ってみるに、初代Bonanzaは10K程度の評価因子しかなかったそうです。
つまりその程度であっても1Mnps程度(?)の探索速度でR2400ぐらいにはなるということです。
そう考えますと全く希望がないわけではありませんね。
次に、GPS将棋の評価関数を1サイクルで求めるようなものを考えていたのですが回路規模が極めて大きくなります。
回路効率は全くよろしくありません。たぶん上記のDE5-Netでも到底載り切らないでしょう。デバッグもすこぶるしにくいです。
そこでアプローチを変えまして、将棋専用のCPUを64個ぐらい実装すればどうかと思ったのです。
FPGA型コンピューター将棋において汎用CPUを複数載せるアプローチは失敗する
まず最初に考えたのは汎用CPUを載せて、それらを並列的に使って評価関数を求めるという手法です。
AlteraはNios IIとopen sourceなCPUを公開しているのですがStratix V(最新のFPGA)において300MHz程度にしかなりません。
300MHzとはひどい話です。DMIPS値でCore i7と比較しますと1/100程度の値でしかありません。
Core i7でさえ、4GHz近く出ますし、うまく命令を選べば1クロックで2命令実行できたり(よく知りません)、アドレッシングが豊富なのでこの部分をうまく利用しますと1命令でも普通のRISCマシンの2,3命令分ぐらいの仕事が出来たりします。
そう考えますと、300MHzのCPUが20個ぐらいあって初めてCore i7の1コア相当ぐらいにしかなりません。
しかも並列的に評価関数の計算をしなくてはならないため、そのタスクを分散させるオーバーヘッドもあります。
こう考えますとどう頑張っても汎用CPUではCore i7にすら及ばないというのが見えてきます。
この結論に至った時点で私はかなり萎えまして、このブログを更新する気力すら失せていました。
将棋専用CPUを作ろう
そこで汎用CPUとは決別して将棋専用CPUを作るという発想に至ります。
汎用CPUに、81bit(将棋盤9×9)のBitboard演算を1命令でこなすような命令などを追加したものだと考えてください。
またそれぞれのCPUの出力を足し合わせる回路をそのCPUの外側につけてあるので評価値を足しあわせる部分の時間は無視して考えられるものとします。
評価関数をこのようなCPUに分散して担当させるということです。
幸い、GPS将棋のような評価関数というのは評価項目は比較的独立していますので、それぞれのCPUにタスクを割り振って、並列的に計算させること自体はそれほど難しいことではありません。
またデバッグがしにくくなるので、その将棋専用CPUのエミュレーターをPC側で実装して、そこでデバッグまで終わらせ、FPGAには最終的にそのエミュレーター用に書いていたコードを持っていくというアプローチが考えられます。この手法にはかなりの実現可能性があり、ある程度の成功も収めそうです。
ここまでで一応評価関数の問題は解決しそうです。
PC側で、将棋CPU向けの評価関数の開発をする作業にかなりの時間をとられるでしょうけど。
やはり難しい指し手生成
そうなってきますと指し手生成のほうがむしろ問題として浮上してきます。
評価関数の計算を将棋CPUに分散させることにしたので、将棋CPU自体は300MHz程度で動作させるとします。
しかし指し手生成回路はそんな速度で動作しません。
指し手のオーダリングのためにコンパレーター(比較器)を何段にも重ねているからです。
また、将棋盤の各升×(10方向+駒打7種)もの指し手を一気にコンパレーターで比較しようとするのは回路的にもすこぶる無駄です。
回路的に無駄なのはまあ仕方ないとしても、それをもう少し安価なFPGAボードで開発～動作テストできませんと、開発がままなりません。
いきなり$8,000の評価ボードを購入するわけにはいかないからです。
そこで、指し手生成にもさきほど評価関数の計算のために作成した将棋CPUを使い回すことを思いつきます。
つまり将棋CPUには指し手生成のための機能もつけます。
ところが、この部分がすごく難しいのです。
うまく将棋CPUに分散させて、そして現実的な時間で指し手生成が出来るかという問題です。
例えば、1段ごとに1CPUを割り当てて、9段で9個のCPUを割り当てるとします。各升で最大17種類の指し手があります。
まあ、17種類すべてがあるケースはまずないでしょうけど、7種の駒打ちと、大駒の移動などで1段に100種類ぐらいの指し手が生成されることはあるでしょう。
そうしますと、1クロックで1つの指し手を生成できたとしても100クロック要することになります。
将棋CPUが300MHzで動作しているとしまして、指し手生成以外の処理は一切要らないとしましても、このとき3Mnpsでしか動作しません。
ボトルネックになっていることは自明で極めて遅いということがわかります。
すべての指し手を都度生成するのは、回路規模を小さく保とうと考えたときに、この部分がボトルネックになりそうです。
ついでに指し手にスコアをつけてオーダリングもしたいわけですが、さきほども書きましたようにCore i7の何十分の1ぐらいの性能しかない汎用CPUでソートするわけにはいかず、ソートもハード的に特化した何らかのアプローチが必要になります。
A級リーグ指し手1号が100K LE程度で収まっていることを考えますと、たぶんすべての指し手を1クロックで生成し、スコアが最大の指し手を選ぶような回路を合成したとしてもおそらく200K LE程度で収まるのではないかとは思います。ちなみに上に書いた$8,000のFPGAボードに載っているFPGAは622K LE相当のようです。収まると言えば収まります。
つまり、
1) 毎回全指し手を生成し、指し手のスコアが最大のものを選ぶ
2) 指し手を生成し、ソートして、それをメモリに保存しておく
とどちらが良いアプローチかということです。
前者は回路規模が大きくなりますが、メモリに保存しておく必要はないのでシンプルな作りになるでしょう。
後者は回路規模は小さくなりそうですが、高速にソートするための回路を作るのはかなり難しく、そしてそれほど速くはないでしょう。
Bonanzaのソースコードなどに倣うとしますと、オーダリングは次のようにするのが普通かと思います。
a) 置換表の指し手
b) 捕獲する手、SEEの値順
c) Killer×1,2
d) スコア最大の手 上位2手
e) あとは総当り
指し手の全生成(駒を取らない指し手など)が必要になるのはd)のところなのですが、上位2手だけならソートする必要はなく、あとは都度生成するとしても、並び替える必要がないのであれば続きの手を1つ生成するだけで済みます。
しかし、こういうオーダリングですと探索深さで先細っていくような前向き枝刈りを考えたときに、ここがソートされていて欲しいというのはあります。
次の記事はStockfishのmarginに関しての記事ですが、前向き枝刈りの先細りに関しても同様の議論が成り立ちます。
[Stockfish] futility margins array
http://d.hatena.ne.jp/sakurapyon/20121214#1355453198
ただ、d)まで行ってβcutされていない状況ですと、もうあとはe)をすべて見てもβcutされない可能性は極めて高いはずで、前向き枝刈りのためにソートする価値があるのかどうか疑問ではあります。
あと余談ですが、FPGAでコンピューター将棋を実装する場合、b)のSEEは損でしょう。
ここはMVV-LVAにすべきだと思います。FPGAで作る場合、局面を進めたり戻したりするコストが馬鹿にならないからです。
並列的に指し手を生成するのであれば、将棋CPUそれぞれが勝手に局面を進めたり戻したり出来ると良いのですが、そういう作りにしようと思いますと、将棋CPUそれぞれが将棋盤を正確に(大駒の利きなども含めて)持っていないといけませんし、それぞれの将棋CPUが盤面情報を更新できないといけません。これは極めて大掛かりになます。
ともかく、どうやれば指し手生成をうまい形で並列化させられるか、そしてソートさせられるかという部分について私はまだ考え中でこの部分に関しましては結論らしきものは得ていません。
長々と書いてきたわりには中途半端ではありますが以上が2012年のFPGAによるコンピューター将棋の結論らしきものです。
FPGAによるコンピューター将棋をご検討の方の参考になりましたら幸いです。
Altera DE0 nanoで実装できるか？
DE0 nanoのSDRAMについて
DE0 nanoには32MBのSDRAMが搭載されています。Terasicの評価ボードのうち、これだけ大容量のSDRAMが搭載されているモデルは珍しく、その点はなかなか良いと思うのです。
出来れば、DE0 nanoで動作速度は遅くとも一通り思考ルーチンが動作すれば今後の開発意欲も湧いてくるというものです。
Nois IIに専用命令を拡張していき実装することを考えていたのですが、Nois IIは論理合成にそこそこ時間がかかるのでターンアラウンドタイムが非常に時間が悪くなってしまいます。まだverilog初心者の私が採るべき方法ではないと判断しました。
そこでまずはDE0 nanoのSDRAMについて少し調べてみます。
DE0 nanoに搭載されているSDRAMのデータシートはこちら。
ftp://ftp.altera.com/up/pub/Altera_Material/11.0/Tutorials/Verilog/DE0-Nano/Using_the_SDRAM.pdf
データバスは16bitのようで、16bitずつしか読み書きできないようですが…置換表は128bitの読み書きがしたいのでどうせならばこのSDRAM8個ついてくれているとすごく良かったのですが…ついてないものはどうにもなりませんね。
ピンヘッダー自体は出ていますからSDRAMのドーターボードがあれば良いのですが…何故か売られていないようです。
指し手生成がボトルネックになる？
局面を進めたあと、置換表を参照しに行く必要があり、通常、そのメモリアクセスがボトルネックになるでしょうから、その間に指し手生成をしておけば指し手生成に要する時間は相対的には無視できるのかも知れません。(よくわかりません)
ただ、局面を1つ戻して(探索深さを1つ戻して)次の指し手について調べるようなときに、その再度すべての指し手生成が必要になり、このときは置換表を調べに行く必要がないのでこの間の時間もすこぶるもったいないです。
未生成の指し手のうちオーダリングで2番目に来るべき指し手についてもピックアップできていれば良いのですが、コンパレーターツリーの出力付近に2番目がいるとは限らず(早い段階で1番目の値と比較され、出力付近まで残れていない可能性があります)、2番目を求めるためのコンパレーターツリーを別途用意するかという話になるのかも知れません。それとも、次の局面に進め、置換表を見に行っている時間に指し手生成部では局面を進めずに2番目の指し手を生成だけやっておくのはアリなのではないでしょうか。
もしそういうことが可能なのであれば、結局、置換表への読み書き部分がボトルネックであるということになるのかも知れません。置換表に評価値が書かれていないときは評価値を評価関数で計算しますが、しかしそれは置換表を調べに行く程度の時間でおそらく出来るはずです。
探索部も考えてみますと…
・ある局面を展開したとき、最初に置換表を調べる
case 1) 置換表に載っている → 既知の局面なのでまず置換表の指し手を試す。置換表の指し手を生成済みにしたあと指し手生成をしておく。そのあと局面を進める。置換表は先行して調べておく。
case 2) 置換表に載っていない → 未知の局面なので評価関数を呼んで評価値を取得。その間に指し手生成。評価値によってはβcutがなされる。
・ある局面に戻ってきたとき
case 3) 枝刈りの条件を満たしている → 局面をさらに戻る。置換表に書き出すならば書き出す。またbest moveとして生成した指し手のhistoryを加点する(指し手生成器がこの点数を保持している)
case 4) 枝刈りの条件を満たしていない → 次の指し手を生成する必要がある。(ここに時間がかかる。他に何もできない！馬鹿らしい！)
つまりはcase 4でストールするわけです。ここでストールする割合がどれくらいあるのかよくわかりませんが結構あるような気がします。複数コアで探索していれば、置換表の読み書き自体がボトルネックになるでしょうからそうでもないと思うのですが、LEが余っているのであれば複数コアにするよりは少しでも評価関数の充実を図りたいのでcase 4が許せないのです。
case 4の割合がどれくらいあるのか考えてみますと、置換表の指し手がある場合は普通その手で枝刈りがされますから、たいてい遅延表に指し手が書かれていなかったケース、すなわち新規局面なのだと思うのですが、新規局面は全体の半分以上が新規局面だと思うので、この部分が時間がかかりますと非常に苦しいものがあります。
こうして見ますと2番目の指し手も同時に生成してしまうのはアリではないかと思えてきます。2番目の値を抽出するコンパレーターをうまく書く方法がよくわからないのですが、N個ずつ組みにして値を比較して、上位2個ずつ残していけば、最後に残るのは上位2個ですかね…。コンパレーターツリー、何段必要なのでしょうか。わけがわかりません。簡単にできそうにないですね。これをやるぐらいなら、指し手生成をもっと並列化するほうが現実味がありそうです。
そんなわけでして、指し手生成は極めて難しいということは前回の考察から理解できたのですが、まずはDE0 nanoに収まるように書きたいので、まずは81セルの指し手生成器を用意して17クロック固定で使用して6段のコンパレーターツリーで実装してみるところからやってみたいと思います。
Noisが150MHz程度で動作するところを見ますと(5段パイプラインですが…)、6段のコンパレーターツリーと言えども100MHz程度では動作するのでしょうから(なんなら分割すれば…)、指し手生成が17+3クロック程度で終わるとしまして…他の処理に要する時間は相対的に無視できるとしまして…。5Mnps程度。DE0 nanoで(このLE数で合成できるかどうかは知りませんが)5Mnps程度！
いまどきたいした数字ではないのでしょうけども、1Mnpsでもなんでも動けばこっちのものです。あとは指し手生成をさらに並列化するなり、評価関数を充実させるなり、もっと速いFPGAボードに移行するなり、探索コアを複数載せるなり、なんでもできます。
そのためには動くことを第一段階目の目標にせねばなりません。
DE0 nanoに搭載されているSDRAMについて
SDRAMの型番 → ISSI IS42S16160B-7
データシート
http://pdf1.alldatasheet.com/datasheet-pdf/view/153633/ISSI/IS42S16160B-7B.html
100MHz動作でCAS latency = 2のようです。つまりはREADコマンドが発行されたクロック信号の立ち上がりから数えて、2つ目のクロック信号の立ち上がりでデータがもらえるようです。
つまりは、最悪でも1/50M秒でデータが取り出せていると考えていいわけですかね。8回の読み出しには10回要することになりますね。置換表を1ノードに1回、読み書きするならばこのメモリの読み書きに要する時間だけでおおよそ1/5M秒。ああ、置換表への書き出しはそのノードの評価値が確定したときのみですので、それよりはマシだとしまして…それでも1/10M秒。指し手生成などが時間0としましても10Mnpsしか出ません。なかなかメモリアクセスだけでも大変ですね。
SDRAMが8つ載っているならおおよそ1/8で済むのでしょうけども。16bitずつの読み書きはさすがに遅すぎますね。内蔵RAMにcacheすることも考えられますが、そんなに訪問済みのノードばかりに当たるわけでもなくその部分ではそんなに効率化は図れないでしょうね。なんとももどかしいものがあります。
コンピューター将棋に適したFPGAボード
Altera DE4 Development and Education Board
http://www.terasic.com.tw/cgi-bin/page/archive.pl?Language=English&CategoryNo=138&No=501
Terasicの評価ボードには、Stratix IVが載っていてSO-DIMM(64bit幅で転送できるみたい？)が2本載っているものがあります。お値段$2,995。228KLE,FPGA内蔵メモリ17,133Kbit(おおよそ2MB)。Stratix IVとVはさほど速度に違いはないようですし、内蔵メモリ的にも現時点で最大級です。LE的にもちょうどいい感じだと思いますし、この評価ボードならばうまくすれば50Mnpsぐらい出せるのではないでしょうか。
DE5-NET
こちらはまだTerasicからは買えないみたいですが(国内代理店では立野電脳が「短納期です」とアナウンスしています)、DDR3 SO-DIMMが2本載るのでよさげですが、5SGXEA7N2F45C2が載っていて、これが5SGXA7だと思うのですが、
を見ますと622,000LEの製品でして、おそらく80万円ぐらいするのだと思います。
高額なFPGAボードが欲しいかも
現時点では私には指し手生成器と評価関数にどれくらいのLE数が必要なのかがよくわからないため、FPGAボード選びに苦労します。DE0 nanoである程度実験してみたいと思います。(そもそもDE0 nanoのLE数で足りるのかどうか…)
それはそうと、指し手生成を完全に並列化した場合、仮に150K LEでそれが出来るとしまして、探索自体にはさほどLEは必要ありませんから、あとのLEはすべて評価関数のために使うことが出来るという意味はあります。内蔵メモリが少ないので大きなテーブルを用いる評価関数は載らないとは思いますが、しかし、評価項目が増えてもLE数が余分にいるだけで、動作速度はそれほど遅くはならないでしょうから、LE数の限界まで評価関数を大きくしてみるのも面白いのではないでしょうか。
置換表がSDRAMを食いつぶす
仮に100Mnps出るとしまして、1秒間に100M回×16バイト(128bit)書き続けますと4GBのメモリですとものの数秒で溢れてしまいます。4GBはもしかすると少ないのかも知れません。まあ、探索ノードすべてで置換表に書き出すわけではありませんがそれにしても…。
そういう意味では内蔵メモリや搭載できるSDRAMのメモリ量の上限が決まっている評価ボードですと置換表に書き出すメモリが足りなくて困るということはありえるのでしょうね。なかなか難しいですね。
FPGA用コンピューター将棋で一番難しいのは指し手生成
Hydraの解説を読んでいて、だいたい作りが理解できました。
1) 探索は状態マシンで、たいした状態数ではないので普通に実装すれば問題なさげ。
2) 評価関数はFPGAらしく並列で計算して問題なさげ。
3) 指し手に従って局面を進める / 戻す
4) 指し手生成～オーダリング～1手選択
1),2)をパイプライン化することで性能は変わりそうですが、それはあとでもやろうと思えば出来るでしょうし、そこは難しい部分ではないのであまり問題にはならないです。3) は簡単なので説明を要しません。
問題は4)ですね。いかにして超並列的に指し手を生成し、オーダリングして1手選択するか。どうもコンピューター将棋やチェスではこの部分の設計が非常に難しく、そしてボトルネックになりうるようです。
半面、評価関数のほうは、評価因子をいくら増やそうと内蔵メモリに評価関数テーブルが載る限りはルックアップは並列化できますし、どんどん増やすことが出来ます。
ゆえに、指し手生成を並列的に高速に出来た時点でFPGAのコンピューター将棋のうちの半分は完成したようなものではないかと思います。(PC版のコンピューターをFPGA化することを前提に話をしていますので、評価関数および探索アルゴリズム自体はすでに確定しているものとします)
Hydraプロジェクトに学ぶ
http://fpgashogi.hateblo.jp/entry/2012/11/17/200418
Hydraの指し手生成を将棋にこれをこのまま応用できるかですが、意外と将棋でもうまくいくような気がします。なぜなら、空いているマスには駒が打てるはずで、生成される指し手は駒種(二歩と打ち歩詰めを除く)だけあるはずですし、空いていないマスに自駒があればその自駒を移動させる指し手があるはずだからです。残念ながら敵駒のあるマスに対して生成される指し手はないわけですが。
あと、1マスから生成される指し手は、空のマスの場合、駒打ちですから最大7通り。移動の場合、敵陣にいる飛車が左右と上下で16箇所に対して成りと不成がありますね。飛車の不成って生成する必要があるのかどうかはわかりませんが。ともかく32が最大ですね。後段に7段のコンパレーターが必要ですが、この7段のコンパレーターは1クロックで実行するとしまして、飛車に関して32回クロックも使って指し手生成をしていいのかということにはなりそうですね。飛車が敵陣に出てくるノードに遭遇するごとにこのような生成をするのはさすがに効率が悪そうです。
Bonanzaのように飛車の不成は生成しないとしましても16回。16って多いですね。駒打ちの最大が7ですから、ここも7ぐらいになって欲しい気はします。それに龍だと16+4 = 20ですか。大きいですね。この部分、100MHzぐらいで合成できたとしても毎ノード、20クロックも指し手生成に必要だと探索も評価関数もなしで指し手生成しかなくとも5Mnpsしか出ません。そもそも7段もコンパレーターがあって100MHzで合成できるのかよくわかりません。
裏を返せば指し手生成器を20倍に増やして、コンパレーターツリーをあと数段増やせば1クロックで指し手生成～選択まで可能だということですか。81×20 = 1620個の指し手生成器..。どうも何か間違っている気がしなくはないですね。どう考えてもLEを消費しすぎます。
1クロックでそれぞれのマスの担当がそのマスで生成する指し手のうちベストなものを出力するというのはアリのような気はします。飛び利きを持つ駒ですとLMRなどでオーダリングしようと思いますと20個指し手があるので大変ですが、この部分、オーダリングがないならばアリなんでしょうね。もう少し考えてみます。
「アマ4段を超える―コンピュータ将棋の進歩〈4〉」に書かれている指し手生成
「アマ4段を超える―コンピュータ将棋の進歩〈4〉」にFPGAによる将棋の指し手生成の論文が掲載されていたと思うので引っ張りだしてきたのですが、複数クロックで生成するようになっています。当たり前と言えば当たり前かも知れませんが。
指し手生成にこんなにクロック数が必要なのならばコンパレーターツリーの最後の段のほうで、1位～8位まで確定させて、それをメモリにbufferしておくのはアリなのではないかと思います。
FPGAで書かれたコンピューターチェスの指し手生成
あとFPGA型のchessの指し手生成のソースコードがあったのでそちらも見てみたのですが、そちらはVHDLで書かれていて読めませんでした。VHDLで書かれている大切な記事も結構あるので、こういうときのためにverilogだけではなくVHDLも勉強したほうがいいのかも知れませんね。
「A級リーグ指し手1号」の指し手生成
「A級リーグ指し手1号」はどうしてあるのだろうと思い、ソースコードを見たのですが規模が大きすぎてよく理解できませんでした。
→ 理解できた範囲で説明を書いておきます。
mecellというのが盤面のマス目に対応する指し手生成器のようです。geninst.plがこれから不要な部分を除去したりしながら(よく読んでいません)81個複製するPerlのソースコードのようです。これによりinst_mecells.vというソースコードが生成されます。これはmeall.vのなかでincludeしています。
生成された指し手を選択するのはselectmv.vのようです。cmp3x3が3×3個のデータ2組を比較するコンパレーターのようです。
私の考える指し手生成その1
1サイクルですべての指し手を生成し、それぞれの指し手のhistoryの値でオーダリングするとしますと、そのオーダリングする値を8ビットの数値としまして、各マス64×龍の移動20 = 1280個程度の指し手生成器が必要になります。まあ盤の端では龍の移動は20ではありませんので実際は1000ぐらいかと思います。そのあとコンパレーターによるバイナリーツリーがありますのでコンパレーターもそれくらいの数だけ必要だということになるかと思います。
1つの指し手生成器が100LEぐらいで実現されるとしまして、これだけで100k LEを消費することになります。指し手生成でオーダリングを欲張ってしようとするのが悪いのだと思うのですが、それにしてもさすがに大きすぎます。
一方、評価関数のほうはメモリに収まらないのは気がかりですが、足し合わせる評価項目としては500程度に収まると思いますので、評価値を足し合わせる16ビット加算器(上流ではそこまで大きな値にはなりませんので最初は8ビット加算器ぐらいで事足りるはずです)が並ぶだけですから、たぶん1項目当たり2,30LE程度ではないかと思います。
仮にBonanzaと同等の評価関数を考えたとしましても足し合わせる数は1200程度。テーブルが内蔵RAMに収まらないという問題はありますが、それはいまおいておくとしますと、1項目50LEずつだとしても60k LEです。
そう考えますと指し手生成の高速化がいかに大きな規模の回路が必要になるかがわかります。
私の考える指し手生成その2
そこで、別の案としまして、飛・龍・角・馬に関してはそれ専用の指し手生成器を用意し、各マス用の指し手生成器では生成しないというのが考えられます。飛車と龍はセットで考えるとしまして、また、角と馬もセットで考えるとします。
つまり、(角 or 馬) + (飛 or 龍) は、盤上に4枚しかありません。この4枚に対しては最大20通りの指し手(注:成りと不成は生成するフェーズが異なるので別々にして考えることができます。また香のことはいま無視して考えます)が生成されますので80個の指し手生成器を用意します。
これを除きますと各マスでは最大でも8近傍の指し手のみで済みますから、8つで済みます。角・馬・飛・龍に関しても8近傍への移動に関してはここで生成してしまいましょう。そうすれば最大でも12通りで済みます。
81マスのうち、辺は8近傍ではなく5近傍ですし、かどは3近傍です。ゆえに8×81 - 4辺×7箇所×3 - 4隅×4 = 548個。大駒4駒×12 = 48個。合計596個の指し手生成器で済みます。1個の指し手生成器が100LEで構成されるとしまして、596個×100LE = 59.6k LE。DE0 nanoには到底載りませんが、現在20万円ぐらいのFPGAボードであれば200k LE程度内蔵されていますのでそこそこ現実的な範疇ではないかと思います。(香のことは考えていませんが、香は9段目では成りしかないので、通常移動としては8段目まで。しかし8段目での不成は打ち歩詰め回避のときしか意味がないので実際は7段目まで。つまり生成される指し手は最大で6通り。ゆえに、これは専用の指し手生成回路は用意しないものとします。)
しかし大駒は移動があり、移動させたときに飛び利きを指し手生成器は、その移動後の周辺のマスの情報を保持して更新しないといけませんから、これが結構大変かも知れません。
私の考える指し手生成その3
さらにもう少し考えかたを変えまして、もし各駒用の指し手生成器があればどうかという考えに至ります。つまり、40駒用のそれぞれの専用の指し手生成器があるとしたら…。歩などは前しか行きません。ただし成っていることもあるので6方向の指し手が最大で生成されます。そう考えますと、角・飛が20通り、それ以外の駒は6方向、王は8方向。ゆえに、34枚×6 + 4枚×20 + 8 = 292。292個の指し手生成器で済みます。あーっと、駒打ちを忘れておりました。駒打ちが残りの空いてるマスに対してありますので…全然駄目ですね。
よく考えますとチェスの指し手には駒打ちがありませんので空いているマスは何も出力しません。そこで、たとえば大駒を移動させる手であれば隣接するマスに移動するよという情報を伝播していき、そして、自分のマスが空のマスであれば移動できるものとして、この指し手を生成するという方法があります。(何かの論文で見た気がします) この方法は結構理にかなっていると思うのですが、将棋では駒を打つ手があり、空いているマスは打つ手の生成に忙しいのでそれどころではありません。
私の考える指し手生成まとめ1
結局のところ、81マスの指し手生成器をたとえば上記に書いた596個の指し手生成器を用意した場合、回路規模は8倍近くになります。8倍の回路規模で8倍速になれば良いですが、実際は3倍速にすらならないのではないかと思います。であれば、ここで指し手生成を頑張ってもあまり意味はなく(その豊富なLEを生かして評価関数の改善を行なうか、探索コアを複数載せて並列探索をしたほうがマシ)、ここが最終的にどうしてもボトルネックになったときに考えたほうが良いのではないでしょうか。いきなり、大きな規模の回路を作ってしまいますと論理合成に時間がかかりすぎて開発がままなりませんので得策とは思えません。
指し手生成を1クロックで行わなくて良いならばそこそこパイプライン化も出来るはずですので効率面ではかなり良くなるはずです。
私の考える指し手生成その4
FPGAのチェスの論文を見ていて、何故セル間を捕食情報を伝播するのか(たとえば飛車が他の駒をとるために移動できる先にある駒を探す処理において、飛車が移動できる経路を隣のマスに次々と伝播していくこと)意味がずっとわからなかったのですが、意味がやっとわかりました。同じ方向からの飛び利きが重複することはありえないので捕食のされかたというのは、8通しかないのです。
逆に言えば、通常の駒もこの移動経路に従って情報を伝播した場合、1つのセルにおいて生成される指し手は8通り。桂を含めても10通り。最大で1つのマスに10通りの駒しか利かないのでこのことは当然でしょう。また桂の移動は伝播していく必要がないので伝播しなくてはならないのは8方向だけ。
ゆえに、たとえば銀の移動を考えるときに、銀の移動先情報として斜め上、上、右上、左下、右下に「銀が移動できるよ」という情報を伝播します。情報を伝播されたセルは、これは銀なので(飛び利きではないので)これ以上他のセルには情報を伝播させません。また、このセルは指し手を生成しますが、このセルから最大で10通りの指し手が生成されるだけです。コマ打ちを生成するセルとは分離しておくことが出来るとしますと、このセルから生成される指し手は10×91。(盤面の端のほうではもう少し少なくなりますが)
つまり、最大でもこのセルからの出力は10回しかありません。(成りと不成は別のフェーズで生成することとし、同時にカウントしないものとします) また、飛車の移動であれば行き先のマスを担当するmoduleが指し手をそれぞれ生成するので飛車があるから16サイクル必要ということもなく、最大でも1つのマスから生成される組み合わせのサイクルで終了します。駒打ちとは分離するのであればこの数は最大で10通りです。ひとつの局面で1箇所に利いている自駒は多くとも4か5程度でしょうから、どちらかと言えば駒打ちの指し手生成のほうがボトルネックになることが多いでしょう。また、駒打ちのほうがボトルネックになるのであれば、歩・香・桂・銀と金・角・飛とを別々の指し手生成器を使うだとかそういう感じの並列化は可能かと思います。
完全に指し手並列を並列化するとしまして、その場合は81マス×10通り + 81マス駒打ち×7通り = 1377ですね。組み合わせは意外と多いですが、しかし他のセルの情報は保持しなくて済むようになりますのでロジックは単純化できそうです。
私の考える指し手生成その5
「私の考える指し手生成その4」で1377個の指し手生成器を用意するところまで話を進めました。仮に2クロック要していいならばおおよそこの半分の数の指し手生成器とコンパレーターで済むのではないでしょうか。
つまり、各マスについて
・上下方向
・左右方向
・斜め+45度方向
・斜め-45度方向
・桂馬跳び
・駒打ち 歩・香
・駒打ち 桂・銀
・駒打ち 金・角
・駒打ち 飛
のようになります。81×9=729の指し手生成器ですね。3クロックの場合どうでしょうか。
・左右上
・斜め+45度方向と桂馬右跳び
・斜め-45度方向と桂馬左跳び
・駒打ち 歩・香・桂
・駒打ち 銀・金・角
・駒打ち 飛と下移動
81×6の指し手生成器ですね。駒打ちと下移動が混じっているのが少し気持ちわるいですね。しかし512以下に抑えられるのでコンパレーターツリーが8段で済みますね。
4クロックではどうでしょうか。
・上下左右(4)
・斜め方向(4)
・桂馬跳び(2)
・駒打ち 歩香桂(3)
・駒打ち 銀金角飛(4)
81×5で、指し手生成器の数は言うほど減りません。桂馬跳びが端数を生み出していて嫌な感じですね。指し手生成器が大きくなってきますと、アービターも大きくなりますね。
いや、必ず4クロック使用して良いのであればアービターは不要ですが…。かならず4方向のいずれかの指し手はあるでしょうから、この場合アービターは入れるだけ無駄ですかね。
あと打ち歩詰めと王手が回避できているかにつきましては局面を進めてみないと判定できませんね。まあ、それはそれでいいのではないかと思います。少し無駄ですが、打ち歩詰めとか王手がかかっている局面はそれほど多くないと思うのでそれはそれで良いのではないかと思います。
そんなわけでLEが余ればこのへん消費クロック数を減らしてもう少しなんとか出来るのかも知れませんが。そもそも8bit値であろうとコンパレーターツリーがそんなに大きくなっていいのかどうか私にはよくわかりません。
指し手はfrom,to,成り/不成・打ちの情報は少なくとも必要ですから10bit必要です。コンパレーターツリーで8bitの数値を比較して行き、最後に残った指し手に関するこの10bitの情報が必要です。これにどれくらいのLE数が必要なのか想像もつきませんが…。
結局、1マスから生成される指し手の最大数は17(10方向 + 駒打ち7種)なので3で割って6サイクルで処理するのが一番キリがいいのかも知れませんね。81×3なら256に収まるので7段のコンパレーターで済みますし。
// ここに何かいいアイデアが浮かべば追記するかも知れません
実験項目
このあと、小さな指し手生成器2つ程度とコンパレーター1つを実際に作ってみて、どれくらいのLEを消費するのか見てみたいと思います。
// 指し手生成について何か思いついたらここに追記します。
Hydraプロジェクトに学ぶ
FPGAによるコンピューターチェスとしてHydraプロジェクトがあります。
Hydraプロジェクト
http://direct.xilinx.co.jp/xcell/xl53/jp53xcell_23.pdf
現在、67のブロックRAM、9,879のスライス、5,308のTBUF、534のフリップフロップ、18,403のLUTが使用されています。探索ノードあたりのサイクル数の上限は9サイクルです。純粋なソフトウェア ソリューションでは、少なくとも6,000 Pentiumサイクルが必要だと推定されています。VirtexTM-I 1000上では、最長パスは51のロジック レベルで構成され、このデザインは30 MHzで動作します。プログラムが50 MHzで動作できるようにするため、デザインをVirtex XC2VP70-5に移植したところです。
→ 回路規模18,403LUTだそうで、これがAlteraのLEでどれくらいになるのかよくわかりませんが、同等程度だとしたらDE0 nanoでも収まりそうです。
ソフトウェアでは、指し手ジェネレータは通常重ループとしてインプリメントされます。重ループには、すべての駒タイプに対する1ループ、そのタイプの駒に対する内部ループ、その駒が移動可能なあらゆる方向に対するもう1つの内部ループ、そして現在の方向を考慮して駒が移動できるマスに対する最も内側のループがあります。特に、駒獲得のための指し手を指し手リストの先頭に進める必要があることを考えると、これはまさにシーケンシャル プロシージャです。
→ ですよね…。
しかし、微粒パラレル デザインには、働きの非常に異なる、高速で小型の指し手ジェネレータが装備されています。指し手ジェネレータは図3に示すように、原則として2つの8×8チェスボードから構成されています。GenAggressorおよびGenVictimのモジュールは、それぞれ64マスのインスタンスを示します。両モジュールは、入力信号を隣接するどちらのマスに送るべきかを判定します。
→ 8×8で64マス。64マスそれぞれ用の指し手生成器があるようですね。その64マスがNUMA的につながってて、そこに大きなコンパレーターがあって指し手を選択すると。その機能ブロックがGenAggressorおよびGenVictimのようです。
マスのインスタンスは、それぞれの駒情報の信号を送り（そのマスに駒がある場合）、広範囲に及ぶ駒の信号を隣接するマスのインスタンスに転送します。そのほか、各マスは“victim found（取れる駒が見つかった）”信号を出力します。その結果、そのマスが“victim（取れる駒）”（自分が正当な指し手で移動できる敵の駒があるマス）であることがわかります。すべての“victim found”信号の集合は、最も興味ある未検討の“victim”を選択するアービタ（コンパレータ ツリー）に入力されます。
→ この部分の仕組みがいまひとつわかりません。あとで詳しく調べてみます。
GenAggressorモジュールは、アービタの出力を入力として取り込み、スーパー ピース(あらゆる駒の組み合わせ)の信号を送信します。たとえば、敵のrook-move（ルークは将棋の飛車に相当）信号が自分自身のルークをヒットすると、それは“aggressor（侵略してくる駒）”（敵が正当な指し手で移動できる敵側の駒があるマス）であることがわかります。このように、多くの正当な指し手がパラレルに生成されます。
これらの指し手はソートする必要があるため、すでに検討済みの指し手をマスクしなければなりません。指し手のソートは別のコンパレータ ツリーを使用して行われ、選択されるべき手はツリーの6レベル以内で判定されます。ソート基準は、攻撃される駒の値とその指し手がキラー指し手かどうかをベースにしています。
→ このへんの仕組みがどうなっているのか、あとで詳しく調べてみたいと思います。
図4に、再帰的Alphabetaアルゴリズムの有限ステート マシンを示します。図の左側に、ヒューリスティックなヌルムーブ（nullmove：新しい指し手を必要としない）を含む通常探索のステートが表示されています。右側は、静止探索のステートを示します。サブロジックの一部（評価と指し手ジェネレータ）が1サイクルではなく2または3サイクルを必要とする場合があるため、タイミングの管理が重要になります。探索はFS_INITから開始します。実行すべきことがある場合、またヌルムーブが適用不能な場合は、フル探索の開始（FS_START）に移ります。
→ 探索も有限ステートマシンで作成してあるようですね。
場合によっては、探索の深さを増やしてから（図4には表示なし）状態FS_VICTIMに入り、その後、上述したように次の正当な指し手を実行するFS_AGGRに入ります。状態FS_DOWNに到達することは、1ポイントのウインドウ（α,α + 1）のAlphabetaアルゴリズムを再帰的に呼び出すことを意味します。探索の残りの深さがゼロより大きい場合、状態FS_STARTで指し手を探します。ゼロ以下の場合は、評価検討から始まる静止探索に入ります。静止探索では、駒獲得とチェック（詰め）の回避の指し手だけが考慮されます。
探索スタック（図中表示なし）はデュアルポートRAMの6ブロックによって実現され、16ビット幅のRAMとして構成されます。したがって、2つの16ビット ワードか1つの32ビット ワードを一度にRAMに書き込むことができます。探索FSMによって制御される深度変数は、データ フローを制御します。さまざまなテーブルが再帰的探索の多様なローカル変数を収集します。
→ あとで詳しく見てみます。
疑問点
・置換表を参照するような箇所がないのですが、置換表はPC本体側に持っていて、残り深さが少なくなったら(5～7ぐらい？)になったらFPGAに投げているということなのでしょうか…。
・指し手生成がいまひとつ理解できませんでした。あとで詳しく調べてみます。
解決編
Marc Boul ́eさんの論文「An FPGA Move Generator for the Game of Chess」(2002)を読んでいろいろ意味が理解できましたので以下に書いておきます。
6レベルというのは6段のバイナリーコンパレータのツリーという意味のようです。マスが64マスありますから、32個のコンパレータ1段目で32に減って、2段目16個のコンパレーターで16,3段目で8,4段目で4,5段目で2,6段目で1。つまり64マスそれぞれのマスに対応する指し手生成器があって、そこで生成された指し手を6段のコンパレーターを通して一つ選ぶ仕組みがあり、それぞれのマスがそのマスに関連するすべての指し手を生成するまでは終了しないという作りになっているのではないかと思います。つまりは指し手生成は64並列ですね。
また、それぞれの64マスに対応するmoduleが現在の探索中の指し手のうち、生成したものをbitとして持っているのではないかと思います。つまり、一度生成した指し手は次にこのノードに戻ってきたときには生成しないような仕組みですね。PCでの指し手生成ですと生成した指し手をすべてメモリに残しておくわけですが、FPGAの場合、指し手自体をメモリに残しておいても次回にそれらのうちベストスコアのものを選択するのにアービター(何段ものコンパレーターツリー)が必要になりますから、そういうのは効率が悪いということのようですね。なんとなくわかってきました。
FPGA実習課題 16種
verilog HDLについてはある程度勉強が終わって、簡単なCPUなら設計できそうというところまで来ました。このあとNios IIをやってもいいのですが、どうせならNios IIのソースコードも読みたいですし、Nios IIのカスタム命令も作りたいです。しかしいきなり複雑なことをやると論理合成～デバッグに時間がかかり、効率が悪そうです。
そこで、FPGAで何か簡単なプログラムを16個書いてみて、それから考えることにしよう！と思いました。16個というのはキリが良いのでこの数字にしました。
1) LEDに結果(数値など)を表示するmodule(デバッグのために使いたい)
2) ブロックRAM・分散メモリ読み書き
3) コンパレーター
4) エンコーダー
5) Stack / Queueの実装
6) SRAM読み書きのテスト
7) SDRAM読み書きのテスト
// 他、思いついたら追加します
16) パイプライン型の32bit RISC型CPUの実装
// やってみたあとに追記していきます。
FPGA入門 その2
FPGA関連でつまずいたことをトピック別に書いていきます。
・ブロックRAMと分散メモリとの違い
いまさら聞けない FPGA入門
http://monoist.atmarkit.co.jp/mn/articles/0609/20/news118.html
[引用ここから]
ブロックRAM・乗算器」は、論理を実現するためのリソースです。図3のように回路内全体に均一的にブロックRAM・乗算器が提供されることで、ユーザーはFPGA内での回路の位置に制限を受けることなく、演算処理とデータの保持ができます。
なお、ロジックセル内のルックアップテーブルは、ロジックの実現だけでなく小型のメモリ（4入力のLUTは16bitメモリ）として使うこともできます。従って、ブロックRAM以外に局所的にメモリを増やすことができます。この場合は、LUTを「分散型メモリ」と呼びます。
[引用ここまで]
・波形ビュアー
GTKWave
http://linuxcom.info/gtkwave.html
[引用ここから]
GTKWaveは、Verilog 標準のVCD / EVCDファイルと同様にFST、LXT、LXT2、VZT、そしてGHWのファイルを読み取り、その表示をするGTK+ ベースの波形ビューアです。 GTKWaveは、オープンソースgEDAプロジェクトと提携したアプリケーションの一つです。
[引用ここまで]
verilog入門 完全版
Verilogに関しては入門書を買わずにネット上の情報だけでなんとかしようと思います。 勉強に使ったURLを書いていきます。簡単な順番に並べてあります。
Verilog-HDL入門
http://cas.eedept.kobe-u.ac.jp/~arai/Verilog/
→ 文法のところだけ流し読み しました。
初めてでも使えるVerilog HDL文法ガイド ―― 記述スタイル編
http://www.kumikomi.net/archives/2009/07/verilog_hdl.php
初めてでも使えるVerilog HDL文法ガイド ―― 文法ガイド編
→ 記述スタイルのほうは参考になりました。文法ガイドのほうは、こういうのが使えるということはわかるのですが、使い方の説明が雑なのであまり参考になりませんでした。
HirokiNakaharaOboe-Tips
DE0のことや、順序回路・組み合わせ回路の説明がわかりやすく書かれていたので参考になりました。
「完全マスター！ 電子回路ドリル II」最新記事一覧
→ デジタル回路(フリップフロップ回路関連) 必要になりそうなら読むことにします。
「完全マスター！ 電子回路ドリル III」最新記事一覧
→ verilog入門記事。全14回。一番わかりやすかったです。
Verilog 自習帳
→ verilogによるサンプルプログラムがたくさん書いてあって参考になりました。
verilog-HDL 入門
→ 筑波大学の講義資料のようです。丁寧かつ網羅的に書かれていて、これを読めば本を買う必要はなさそうです。
パイプラインの記述とその RTL シミュレーション
→ 同じく筑波大学の講義資料です。verilogでパイプライン実行するCPUを製作するときに役立ちました。また、あるmoduleがどこまではクロックサイクル内で実行できているのかを理解するのに役立ちました。
Verilog 「脱」入門
→ wire 、ブロッキング代入/ノンブロッキング代入について理解が深まりました。verilogを使い始めて9年という大ベテランの人で、非常に深い考察だと思いました。
ブロッキング代入は何時おきるか
→ 上記のVerilog「脱」入門のブロッキング代入に対する反論的なもの。
TINYCPU / MINICPU
→ 広島大学の講義資料のようです。100行足らずのverilogのコードで実装されているTINYCPU。そしてそれをパイプライン化して高速化したものや、高機能化したMINICPU。あとそれら用のコンパイラ、アセンブラのソースコード(それぞれわずか30行程度！)が公開されており、非常にためになります。ただ解説はそこまで詳しくはないのでverilogのソースコードを読むための力は必要となります。
→ より高度なサンプルがいろいろ掲載されています。まだ読んでいません。
インターネットの情報だけで勉強しようと思っていたのですが、assignとregに対する理解が不十分であることに気づき、左の2冊の本を購入しました。
1つ目の本は、verilogの文法について詳細かつ網羅的に書かれており、例も豊富で、ミーリ型、ムーア型回路についてもわかりやすかったです。
2つ目の本には、いつラッチが生成されるか詳しく豊富な例とともに言及してあり、これが非常にためになりました。moduleの出力手前のところにラッチが生成される場合、その後段に別のmoduleをつくっけた場合、そのmoduleへの入力は、ひとつ前のクロックでの出力になるわけですが、ここの部分が正しく理解できていなかったことがよくわかりました。
これらの点を踏まえて上記のTINYCPUのソースコードを見なおしたところすんなり理解できました。
インターネットの情報だけではサンプルコードの例示が不十分であったり、説明が間違っていたりとなかなか独習には厳しかったです。verilogの学習のための必要知識の4割ぐらいはインターネットの情報だけでなんとかなるのですが、あとの3割は本を見て、そして残り3割は自分で試してみる、みたいな方法が一番習得が早いかなぁと思いました。参考になれば幸いです。
