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数でいかにうまく設計するかという話になってくるかと思います。それが現実的に可能な範疇なのかどうかというのはいまの私には判断がつきません。このあと数々の実験を通じて調べてみたいと思っています。

FPGA 入門 その1

まず、FPGAの研究用にTerasic製のDE0 nanoを共立エレショップにて購入しました。

 

http://eleshop.jp/shop/g/gBAD121/

 

 

 

9800円と大変お安いです。(digikeyですと7470円+送料だそうです。digikeyで買ったほうが良かった？)

 

 

ALTERA CycloneIVが載っていて、22,320 LEだそうです。1000LE程度で32bit RISCコアが作れますから22個もCPUコアが載りますね。

USB Blasterを基板上に搭載しているようで、USBケーブルでつなぐだけでプログラムを転送することが出来るようです。

 

 

FPGA ボードで学ぶ組込みシステム開発入門　?Altera編?

 

「FPGAボードで学ぶ組み込みシステム開発入門 Altera編」(asin:4774148393)は、あちこちでお勧めされているようなので買いました。

DE0についても書かれているのでDE0 nanoを買って勉強しようという人は、まずはこの本を買うべきだと思います。

 

 

第１回 関西FPGA・DE0勉強会(2012/5/19)やってみた

 

http://d.hatena.ne.jp/ksksue/20120520/1337533844

 

 

 

発表スライドへのリンクなどがあり、勉強になります。DE0 nanoを入門機として買うのは良い選択だったようです。

以下、DE0 nanoで本書に従って学習したときに気づいたことをメモしておきます。

 

 

・本書のQuartus IIはv11.0ですが、現在はv12.0sp2らしく、インストールするときにNios IIをインストールするかしないかなどの選択ダイアログは出ませんでした。

 

 

・DE0用の説明になっているのでDE0 nanoの場合、FPGAとしてCyclone  IV EP4CE22F17C6を選択する必要があります。

 

・DE0 nano付属のUSBケーブルはぜんまいによる巻き取り式になっているのですが、速攻ネジが破損して巻き取る本体がばらけてぜんまいが飛び出したので本体部分捨てました。

 

・DE0 nanoには7セグメントがないので本書の手順で進めても動作テストができません。

 

 

・LEDが8個ついているのでこれを代わりに使って試します。

 

 

・DE0 nanoの付属のCD-ROMのうち、Quartusが入っているほうのCD-ROMはAlteraのサイトから最新版がダウンロードできるのでこのCD-ROM自体が不要。

 

 

・USB Blasterのドライバーは、Quartusのインストールフォルダのdriver/ フォルダ配下にある。ゆえにCD-ROMは不要。

 

 

・DE0 nano本体を付属のUSBケーブルでPCに接続すると(USB Blasterのドライバーをインストールする前の段階で)LEDライトがゆっくりと点滅する。

デモ用に出荷時にそういうプログラムが書かれているようです。

 

 

・DE0 nano付属のQuartusの入っていないほうのCD-ROMはいろいろ入っていて面白い。

Usermanual\DE0_Nano_User_Manual_v1.7.pdf

→ ユーザーマニュアル(英語)

Schematic\de0-nano-c4-rev-c(release_cd_rom)

→ 回路図

Tools\DE0_Nano_ControlPanel

→ LEDの個別のON/OFFテスト、ボタン型スイッチのON/OFFの検出、ディップスイッチのON/OFF状態の検出、メモリ(SDRAM等)の読み書き

などのテストができる。

Tools\DE0_Nano_SystemBuilder

→ 他のTerasic製のadd-onボードなどを載せたときにこれで設定するようです。よくわかりません。

 

 

あと、このボードのpin assignファイルは、

Demonstration\DE0_NANO_default\DE0_NANO.qsf

を使うと良いようです。DE0用のものは本書の著者がいじったものが技術評論社のサイトのほうからダウンロードできるようなのだが( http://gihyo.jp/book/2011/978-4-7741-4839-7/support )、DE0 nanoのものはないのでそのまま使います。

 

・Verilogについては本書では解説が10ページほどしかないです。簡単に文法が載っているだけです。インターネットで検索すればいくらでも情報は出てくるので別の本を買うつもりはいまのところありません。

 

・DE0 nanoには7segが搭載されていませんので、本書の3章までのサンプルはそのままでは動きません。適当に読み替えて動作確認をします。

 

・自分でmoduleを書いてQuartusでコンパイルしたときに

Error: Top-level design entity "xxxxx" is undefined.

と表示されました。変数xxxxxはreg宣言していたのですが、この変数が使えないのかと思ったのですが、そうではなかったです。プロジェクト名とmodule名が一致していない場合、このmodule名をtop-level desingとして指定する必要があるようです。Assignments→Settingのところから設定しました。

 

・自分でmoduleを書いてコンパイルしたとき

Verilog HDL Procedural Assignment error at counter.v(17): object "LED" on left-hand side of assignment must have a variable data type

と表示されました。LEDをreg宣言していなかったためのようです。output reg [7:0] LED と変更しました。

 

・20LEぐらいの簡単なプログラムでもコンパイルに20秒ぐらいかかります。HDDからガリガリ聞こえてくるのでSSDならば半分ぐらいの時間で済むのかも知れません。それにしても遅いですね。

 
 
・moduleのなかでinput CLKと書いていたのですが、CLKがどこから与えられているのかわからず、動作もしませんし、エラーにもならないのですが、おそらくどこかに設定するところがあると思うのですが…。pin assignファイル(.qsf)を見ますとCLOCK_50というピンから50MHzのクロックを供給してもらっているようなのでCLOCK_50に変更したところ意図通りに動作しました。
 
 
・ボタン型スイッチに対応するpinである、KEY[0],KEY[1]は負論理になっているようです。(押されたときに0になります)  LED[7:0]は正論理のようです。

 

 

・サンプル書いてみました。KEY1を押すと1秒ごとにLEDが2進数的に1ずつ加算され、KEY2を押すとLEDに表示されている2進数的な値が0にリセットされます。

 

module UPCOUNTER(

input CLOCK_50,

input [1:0] KEY,

// KEY[0] == RESET ,

// KEY[1] == increment

output reg [7:0] LED

);

 

reg [7:0] counter;

reg [25:0] time_counter;

 

always @( posedge CLOCK_50 ) begin

if ( ~ KEY[0] ) // reset

counter <= 8'h0;

else if ( EN1HZ ) // increment

time_counter <= 26'b0;

else

time_counter <= time_counter + 1'b1;

 

if (EN1HZ && ~ KEY[1])

counter <= counter + 8'h1;

 

LED <= counter;

end

 

assign EN1HZ = (time_counter == 26'd49999999); // 50MHzを分周して1Hzに

 

endmodule

 
 
・4章のSignalTapIIだがp.132で「Add Nodes..」を選ぶように書いてあるのだが、これが選択できません。回路図を描いてないから？
 
参考資料)
SignalTap II エンベデッド・ロジック・アナライザを使用したデザインのデバッグ (PDF)
 
たぶんそういう波形レベルでのデバッグはしばらくやらないと思うのでこれはスルー。
 
・5章 → Nios IIの導入。verilogの勉強をもう少ししてからにしたいのでこれは後回し。
・6章 → Nios II のバスに付いて。Nios IIの導入がまだなのでスルー。
・7章 → Nios II の周辺回路の設計。→ コンピューター将棋で周辺回路を作ることはないと思うのでスルー。
・8章 → メモリコントローラーの設計。SDRAMコントローラーを製作しているみたい。verilogの勉強をもう少ししてから自分でもやってみる。
・9章 → μClinuxの搭載 → 使うことはないだろうからスルー。
 

以上で本書は終わり。

 

残りの課題としては…

 

課題1) verilogのプログラム、もう少し自分で書いてみて勉強する。

課題2) 小さなCPUを自分で設計してみる

課題3) SDRAMコントローラーを設計してみる

課題4) Nios IIの導入

 

という感じ。

スーパー田舎将棋の名前の由来

FPGAの内部RAMはとても小さいので初代Bonanza相当の評価関数テーブルすら乗りません。最新のFPGA(100万円ぐらしますが…)でも3MB程度しか内部RAMがなく、その3MBをまるごと評価関数のテーブルを置くわけにもいきませんから、結局、評価関数の精度自体は下げざるを得ないと私は思っています。

 

しかし探索速度自体は10Mnps程度は可能だと思うので(DDRメモリのアクセスで律速しそう？)、序盤はあまりよろしくなく、終盤はめっぽう強いという田舎のおっちゃんのような将棋になるのだと思います。探索速度自体を速くして行った場合、田舎将棋の極端な形になることは想像に難くありません。序盤はアマチュアレベルなのに中終盤がトッププロレベル。

 

そんな将棋になることを夢見て「スーパー田舎将棋」と名付けました。