FPGAによるコンピューター将棋「スーパー田舎将棋」作ってます!!

FPGAでコンピューター将棋を作っちゃうブログ

FPGAによるコンピューター将棋の作り方 考察

FPGAによるコンピューター将棋の作り方についての考察を書きます。

 

概説

 

 近年、FPGAの内蔵メモリは大容量化してきました。そうは言っても2012年現在、最大級のものでも3MB程度が限界であり、評価関数テーブルにすべての内蔵メモリを割り当てるわけにもいかないので、実際に使えるのは1MBかそれ以下だと思います。

 

ゆえに、現在のBonanzaの評価関数は評価関数テーブルが載り切らないのは明白であり、評価関数をどこかで妥協しなければなりません。

 

また、最大級のFPGAが搭載されている評価ボードは100万円前後しますのでそれを買ってまで開発すべきなのかという予算的な問題もあります。

 

それゆえ、まずはDE0 nanoという1万円程度の評価ボードを購入し、どこまでが現実的なラインなのかを調査してみることにしました。

 

 

評価関数設計の方針について

 

評価関数の計算自体はそこそこ並列的に計算できるとみなせると思います。

 

つまり、評価関数の計算に関してはその計算量の増加はあまり問題ではなく、評価関数テーブルが内蔵メモリに収まることのほうが大切です。

 

そこが従来と発想の転換を迫られるところで、評価関数の評価因子はそこそこ増やしてもよく、しかし、テーブル自体は極力小さくして、Bonanzaと同等ぐらいの評価関数が設計できるかという部分が一つ目のハードルになります。

 

置換表について

 

置換表を持たない、あるいは並列探索において共有していない場合、探索のパフォーマンスは著しく低下します。

 

反復深化においては1つ浅い深さの探索での最善手を最初に調べることによって(それが今回の探索での最善手である可能性が一番高いので)効率的に枝刈りを行なう手法ですので、置換表が使えないとまずいのです。

 

また、FPGAですと探索速度は速いはずですので、置換表の消費速度もそこそこ速いと考えられます。ゆえに、16GB程度のメモリにアクセスしたいです。ただ、置換表は小さくとも、そこまでパフォーマンスは損ねない気はしますが、これに関しては実験データがないのでよくわかりません。最悪2GB程度のメモリでも構わないとは思います。

 

2GBのメモリにアクセスするためには、FPGAボード上に高速なメモリを載せてある必要があると思います。PC本体と通信してPC本体側のメモリが使えれば良いのですが、PCIeで接続するとしてPCIeの往復の時間は0.5μ秒程度になると言われており、ゆえに、2Mnps程度が探索速度の理論的な限界となってなってしまいます。

 

並列探索し、FPGAボード側からの結果を待たずにどんどん評価したい局面をPC本体側からFPGAボードに投げるような設計にすればスループットは上がりますが、設計が複雑になるのでこれについては最後の手段にしたいと思います。

 

探索について

 

置換表をFPGAボード側に配置する以上、探索もFPGAボード側で行ないます。こうしてFPGAボードだけで通常思考ルーチン(定跡部を除く)が完結するようにしようと考えています。 

 

CPUコアについて

 

探索自体をNios II のようなCPUコアを用いて実装し、評価関数・指し手生成など時間がかかる部分だけをカスタム命令を用意して拡張することは考えられるのですが、Nios II自体がそれほど速く動作しないらしいので(最新のFPGAでも300MHz程度？)、探索自体にNios IIを使うのが正しいソリューションなのかどうか決めかねています。

 

ARM系のCPUにFPGAがくっついたようなSoCも発売されており、そういうものであれば、ARM系のCPU部分に探索を任せて、時間のかかる部分をFPGAで実装するようなことも出来るかと思うのですが、このへんは評価ボードを入手してテストしてみないとよくわかりません。

 

設計方針

 

そこで第一段階目の設計方針としては遅くとも良いのでNios II + カスタム命令 + FPGAボード上のSDRAM(32MB程度)を用いて、思考ルーチンを実装することです。これにより、世界で<b>二番目に開発された</b>FPGAによるコンピューター将棋プログラムとなります。

 

カスタム命令を用意しなくて良いのならばC++で書いたコードがそのままNios II上で動くでしょうから(メモリが足りるのかどうかはわかりませんが)、評価関数の設計以外は比較的簡単に実現できると思います。

 

評価関数自体は、どの規模の評価関数なら実装できるのかをカスタム命令を用意しながら検討し、その方針が決まったらPC側で棋譜からの学習を用いて評価関数のテーブルを作成しようと思っています。

 

Nios II自体はDE0 nano(Cyclone IV)上で150MHz程度で動作します。探索部はStockfishに倣おうと思っています。あとは初代Bonanza程度の評価関数が設計できていたなら、初代Bonanzaを昔のノートパソコン(CoreDuo2 , 2.8GHz程度。初代Bonanzaはこの条件でR2400相当だと言われています)で動かしたときの1/10～1/20ぐらいの探索速度になると思われます。探索速度が倍になるごとにR150程度変わるとしまして、R1800程度になる計算になります。

 

ということで、この時点で世界初のFPGAによるコンピューター将棋「A級リーグ指し手1号」と同等以上ぐらいにはなるのではないでしょうか。DE0 nano(1万円しないFPGAボード)で<b>世界最強のFPGAによるコンピューター将棋</b>(≠世界最強のコンピューター将棋)が作れるだなんてわくわくしますね！

 

ともかく、ここまでを一つの目標にしたいと考えています。そして、そのあと

・カスタム命令の追加による高速化

・CPUコアの差し替え(or 専用の探索コアの搭載等による高速化)

を第二段階目の目標と考えています。

 

最終的にはもっと大容量LE(ロジックエレメント)を持ったFPGAコアを使用しての高速化、大容量の内蔵RAMを持ったFPGAで、もっと精度の高い評価関数への差し替え等を考えていますが、そのへんは第二段階目まで完了して、そのとき私の予算が許せばということでご容赦ください。

 

まとめ

 

FPGAによるコンピューター将棋をどう実現するのか、私の考える設計方針についてざっと書いてきました。

 

世界初のFPGAによるコンピューター将棋は「A級リーグ指し手一号」ですが、1クロックで全指し手を生成して1手選んで局面を進めて、次の1クロックで局面を戻すというようにかなり力技かつ掟破りなものであったと私は思います。

 

じっくりと腰を落ち着けて設計すれば、もう少し強いコンピューター将棋が少ないLE(ロジックエレメント)のFPGAでも実現できるでしょうし、他の研究者の足がかりになるかと思っています。

 

FPGAによって最強のコンピューター将棋が出来るかどうかはいまの私にはわかりません。その原因の大半はFPGAの内蔵メモリの少なさに起因するのですが、この部分が解決するようなFPGAが出現するころには、PC側も本格的なmany coreの時代に突入していて、状況が一変している可能性があります。

 

ですので、PC側が進歩しないうちに大容量内蔵メモリを搭載したFPGAが出てくれればFPGAによるコンピューター将棋が最強になる可能性もあるのですが、FPGAはそんなに短いサイクルでは新製品は出ませんのでこれは極めて厳しいものがあると思います。

 

ゆえにPCと同等以上の強さを持つコンピューター将棋をFPGAで作ろうと思えば、少ない内蔵メモリ、少ないLE数でいかにうまく設計するかという話になってくるかと思います。それが現実的に可能な範疇なのかどうかというのはいまの私には判断がつきません。このあと数々の実験を通じて調べてみたいと思っています。