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によるコンピューター将棋をご検討の方の参考になりましたら幸いです。
