Hydraプロジェクトに学ぶ - FPGAによるコンピューター将棋「スーパー田舎将棋」作ってます!!

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の場合、指し手自体をメモリに残しておいても次回にそれらのうちベストスコアのものを選択するのにアービター(何段ものコンパレーターツリー)が必要になりますから、そういうのは効率が悪いということのようですね。なんとなくわかってきました。