Marcの３つの論文のうち、一番最初の CICCpaper.pdf の訳文を公開する。なお、テキストのみとしたので、図表については原論文を参照のこと。興味を持たれた方は、是非、MBThesis.pdf : An FPGA Move Generator for the Game of Chess も熟読されることをお奨めする。
CICCpaper.pdf : An FPGA Based Move Generator for the Game of Chess
概要
この論文は、チェス指手生成器のFPGAアーキテクチャを詳述します。その設計はDeepBlueの指手生成器を基にしています。ASICとFPGAの本質的な差は、頻繁な設計変更が出来るか否かにあります。FPGAの重要な特徴（ルックアップテーブルを基にしたロジックや配線資源、DistributedRAM[*1]やBlockRAM）を利用した改良を提案します。
1. はじめに
性能が上がり、より多くのゲート数を持つようになったFPGAは、ASICや専用ICからゆっくり置き換わろうとしています。新世代のFPGAは、チップ内のRAM、多くのI/O規格、マイクロプロセッサや高度なクロック制御回路といった資源を統合して持っています。この論文では、コンピュータチェスの中で使用されるαβ枝刈探索アルゴリズムの処理速度を上げることで、コンピュータチェスが巧くプレイ出来るよう改善するために、FPGAがどのように使用されるかをお見せします。FPGAアーキテクチャの特徴を利用することで、設計によってチェスの指手生成器がどのくらい改善するかをご覧に入れます。
1977年に、Belleチェスシステムは、そのプレイする強さを高めるために、最初に専用ディジタル回路を使用しました。チェスプログラムの中で、最も時間を消費する処理は指手生成です。他のチェスハードウエアを加えて、Belleはその探索速度を毎秒200局面から毎秒160,000局面に引き上げることが出来ました。ざっと1,700個のICがそのチェスマシンを構築するために使われました。Belleの中で使用された指手生成器は、より強力なチェスマシンの出発点として役立ちました。1997年にカスパロフを破ったDeepBlueは、480個のチェスチップを30台のIBM RS-6000 SPプロセッサに繋ぎました。このマシンは、Belleより計算上100万倍速い毎秒２億局面の速度を達成しました。
私たちは、チェスプログラムMBChessを改善するためのFPGA指手生成器の設計について記述します。指手生成器はゲーム中の探索の要です。BelleやDeepBlueの指手生成器の重要な詳細については第３章の中で示します。私たちのFPGA指手生成器の記述は第４章へ続きます。指手生成の鍵となるハードウエアアービタの設計によって、FPGAアーキテクチャがどのような影響を及ぼすかが判るでしょう。更に、柔軟なチップ内のRAM資源が、指手をマスクするための斬新な回路実装を可能にします。また、FPGAの実装結果は第５章で示します。
ASICの伝統的に大きな工数を不要にし、且つ開発コストを数分の１にすることを成功させ、FPGAチェス探索加速装置として使用できることを示します。再プログラムの容易さとチップ内のRAMがFPGAを成り立たせ、チェスアプリのための理想的なターゲットになります。
2. 指手生成器
チェスプログラムの中で使用される基本的なメカニズムは、最善手を求めるための深さ優先αβ探索です。この探索アルゴリズムで良い手の順に読むことは、探索量削減とより速い探索になることで報いられます。強いチェスマシンは、必ずと言ってよいほど最良から最悪の順に指手を生成しています。チェスの良い手の順位の例は次の通りです（最良が最初）：
A1：王手、直接および発見された手
A2：もしあれば、成る手
A3：最も価値のある敵駒を、最も価値がない自駒で取る手で並び替えた順
A4：駒を取らない手
αβアルゴリズムの注目すべき振る舞いはβ枝刈です。β枝刈が生じる場合、現在のノードからすぐに引き返し、残っている枝を調べる必要はありません。効率的な探索のために、指手生成器は全体的に固定された指手順を決め、更に一回に一つの着手を生成することが出来なければなりません。これは、探索が戻ってきた時、未だ調べていない次の手を探索することが出来るように、既に生成した手をノードが忘れてはならないということです。
3. 以前の設計
3.1. Belle
Belleでは、チェス盤はロジックブロックを組み合わせた8x8個の配列です。Belleの主なハードウエア構造は、チェスの桝間の通信です。各桝は、発信器、受信器および駒レジスタを持ち、現在の駒を表します。駒が置かれた桝は、ナイトの飛び越える利きを除いて、８つの隣接する桝に送信します。空桝は、駒の進む方向に沿って利きを伝えます。
チェスでは、移動元の駒は適切な送信線をアクティブにし、移動先の桝では入ってきた利きを受け取って（言わば立候補し）、アービトレイションを申し込みます。２つの主な通信ブロックは送信器と受信器です。各桝は各々１つ持っています。
チェスの指手は、移動元桝から移動先桝への（駒の）移動です。指手を構築するために、２つのサイクルが実行されます。最初の敵駒発見(find-victim)サイクルは移動先の桝を見つけます。次に自駒発見(find-aggressor)サイクルは移動元の駒を見つけます。敵駒発見(find-victim)過程中、動かせる自駒はすべてそれらの発信器をアクティブにします。対する敵駒および空桝の全ては、アービトレイション網へそれらの受信器の出力を送ります。２レベルの優先木はクイーンから空桝(キングは取ることができません)までに命じられ、取る敵駒（あるいは移動先の桝）を選択します。アービトレイションの第１レベルは4x4桝のブロック上で終っています。第２レベルは、これらのサブグループのうちの１つを選択します。一旦最も価値のある敵駒(MVV)が選択されていれば、自駒発見(find-aggressor)サイクルが実行されます。ここで、最初のサイクルで見つかった桝は全ての駒種の利きの結合を送信し、ポーンからキングまで命じられ、動ける駒の受信器が最も価値の低い自駒(LVA)を選ぶためにアービトレイションを行います。このようにしてMVV/LVA順で指手を生成しています。Belleの指手をマスクする能力は、64ビット(各桝１ビット)が、ある指定された桝へ動き終わった自駒をマスクするか、あるいは完全に探索された移動先をマスクするためにあります（桝は移動先(victim)か移動元(aggressor)のいずれかです）。深さ優先探索のために、64レベルのスタックが、これらのマスクビット記憶用に使われます。指手マスクがあることで、Belleは第２章のA3（駒を取る手）およびA4（駒を取らない手）の生成を行えます。
3.2. DeepBlue
Belleの受信器・発信器構造は、DeepBlueの指手生成器の出発点でした。DeepBlueでは、第１レベルのアービトレイションは桝の段(rows)の上で終っています。また、第２レベルは段(rows)の間を選択します。一旦桝がビットマスクにより無効になれば、以降（アービトレイションに）参加しません。また、同じ優先度を持った他の桝は選ばれるために申し込みを続けます。あらゆる指手が生成されるまでこの処理は継続します。
移動先と移動元をマスクする過程は、DeepBlueアーキテクチャでは完全に異っています。64レベル64ビットのスタックを使用する代わりに、マスクビットはそのノードで以前に生成された指手から算出されます。このマスキング法は、ロジックとデコーダを犠牲にしてメモリを必要としません。DeepBlueのVLSI設計では、このアプローチは有利でした。DeepBlueのアービトレイションと桝マスクをFPGA用に専用設計し、第4章の3および第4章の4の中で示します。
DeepBlueの指手生成器の最初の大改造は、王手の指手を最優先で生成する問題の解決から始まりました。指手生成順で、王手を高い優先度にすることは非常に重要で、MBChessの初期バージョンで気づきました。この特徴を実装するために、２個の発信器が入力数の倍を備えた受信機と同様に使用されます。王手発見(find-check)過程中、手番側の移動すべき駒は、それらの敵駒発見(find-victim)発信器をアクティブにします。また敵キングは、その自駒発見(find-aggressor)発信器をアクティブに（全駒種で結線）します。適切に（敵キングを）攻撃する桝は、王手することができる桝（と駒種）を示すでしょう。この論文では、これらを軸(pivot)桝と呼び、そのサイクルは軸桝発見（find-pivot)サイクルと呼ぶことにします。軸桝が超駒(super-piece)[*2]として放射し、王手を生成するのに必要な第２のサイクルは、通常の自駒発見(find-aggressor)サイクルです[*3]。
4. FPGA指手生成器
この章は、FPGAの重要なチェス指手アーキテクチャを含めた指手生成器を提案します。隣接する桝間の通信の基本は変わりませんが、駒の情報を伝える方法が異なります。
4.1 チェス盤表現
チェス盤は桝回路8x8個の配列として表現されます。チェス桝のブロックダイヤグラムは図1で示されます。発信器(TX)および受信器(RX)の中のＬ形の矢印は、２ビット（×８方向）のナイト用バスです。直線状の矢印は５ビット（×８方向）の隣接する桝とのバスです。各桝は、図の左上で示された信号を受け取ります。（図の中の）破線は、発信器と受信器の多くの関係のうちの２つを示します。更に32個の第１レベルアービタのうちの１つと16個の第２レベルアービタのうちの1つが見えます。６ビットの深さレジスタは、５ビットの書き込みバスを用いて更新され、駒を移動させることに使います。
全体的な情報は、駒利き伝搬の出力を除いて、すべての桝へ配線させます。これらの信号網によって要求されるファンアウト[*4]は、64個のチェス桝があることで信じ難いほど大きくなります。FPGA実装では、桝への値の送り込み(loading)および遅延を減らすために８つの桝をグループ化し、駆動するためにバッファ[*5]を付けます。バッファが論理合成によって削除されるのを防ぐために適切な制約を設けなければなりません。影響を受ける信号は指手データ、５ビットの書き込みバスとマスクおよび状態の情報です。
DeepBlueでは、マスクおよびアービトレイションバスも、駒レジスタ読み書きバスとして使用されます。この設計では、書き込みバスは異なる桝に駒値を書くために使用されます。書くべき駒値はすべての桝へ送られます。しかし、２つの桝選択線によって選択された桝だけが、その駒レジスタに駒値を書き込めます。また別の選択した桝（移動元）の駒レジスタをクリアするために使用されます。キャスリングを行う、あるいはアンパサンでポーンを取る手も、通常の指手生成と同じサイクルで行われます。指手生成器の重要な特徴は、移動しない駒の桝は駒レジスタを読む必要がないということです。このことは、必要となる配線量を減らし、設計の動作速度を上げます。
4.2. チェスの桝 - 曖昧な王手の解決
桝の発信器出力は図１で示されます。通常の指手生成中、これらの信号線は、以前に議論された敵駒発見(find-victim)および自駒発見(find-aggressor)の振る舞いに従います。
DeepBlueの中に潜在的な制限があることに気づきました。DeepBlueの設計で使用される発信器では、対角方向でヒットした時、軸桝はクイーンとビショップを区別することができません。軸桝に到着するクイーンは水平あるいは垂直にあるキングに王手するかもしれません。しかし、ビショップであれば王手になりません。そのような王手を考慮する場合、私たちの内部結線策は解決可能性を充分に実現します。軸桝発見(find-pivot)サイクル中、桝はどの種類の駒を移動させれば王手を正しく生成できるか判っています。
送信線は、付加的な意味を持っています。すべての駒種の利きの結合は、更に自駒発見(find-aggressor)サイクル中に送信されることができます。この目的（正しく王手を掛けること）を達成するために、６ビットの拡張駒ワードが、４ビットの駒レジスタからデコードされます。ビットフィールドは表１の中で示されます。例えば、111000は白クイーンを表わします。また、011111は、（全ての利きを）結合した駒を放射する桝を表わします。ナイトビットおよび色（敵・味方）判別ビットがナイトの到達可能な桝へ送られている一方、上位５ビットは８つの隣接する桝へ送られます。その結果、チェス桝回路は２個の発信器および二重入力の受信器を必要としません。それでも、内部結線の合計はDeepBlueと同じです。通常の敵駒発見(find-victim)および自駒発見(find-aggressor)サイクル中に、敵味方を判別することは不要です。しかしながら軸桝発見(find-pivot)サイクル中は、敵・味方を正しく判断することで王手を示すでしょう。この表現は、より一定の内部結線パタンにし情報分配の効率を最大にします。王手発見演算は、自駒発見(find-aggressor)サイクルが後に続く軸桝発見(find-pivot)サイクルになります。王手の指手は、それを命じるMVV/LVAによる指手順に従わず、暗黙のうちに指手生成器によって（優先的に）生成されている点がミソです。初めてノード（の探索に）に入る時、王手を見つけるループ（処理）が実行されるでしょう。マスクビットは、規則的ではないやり方（軸桝が使い尽くされた時に終了するように、それがマークされる)で生成された指手からマスクするでしょう。通常の指手生成ループに入る時にマスクビットがリセットされ、王手でない場合、古い軸桝は生成されないでしょう。この解決策は、２つの過程の間マスクビットをリセットし、それらが通常の過程中に生成される時、王手の指手は無視することです。
4.3. アービトレイションの２分木
ルックアップテーブル(LUT)を基にしたFPGAは、この設計中で多くの物理的な制約を課されたまま使用されます。DeepBlueの受信器の出力には大量の配線がありましたが、（本設計では）６つの優先レベル判断用の6*64の網が不要であることを表します。ASIC設計では、もしデコードや演算に必要となる論理ゲート数を更に減らせるならば、格子状に構成される大量の配線は有利になりえます。しかしながらFPGAでは、論理ファンクションは違った風に作用します。５入力のXORゲートは任意の5つの入力機能（2つのLUT）と同じエリアを占有します。受信器出力は、３ビットの値（比較するためにアービタが使用する）の中でエンコードされます。１つのアービタは２つの桝（のどちらか）を選択することができます。最終結果は、６レベルの２分木構造を通って出力されます。各アービタは、決定し選んだ桝の座標を切り替えて出力する６つのLUTのために、4つのLUT(任意の６入力)を使用します。この設計は、筋・段(row/column)に基いた幾何学的位置・距離（topology）より短い伝搬時間になります。
4.4. 指手マスク
Virtexデバイスでは、BlockRAMは4,096ビットの同期式メモリです。それは、1、2、4、8あるいは16ビット(4,096～256)の可変幅を備え、デュアルポートで使用することができます。私たち（が使っているFPGA）の場合、28個のRAMブロックが利用可能です。専用で用意されている配線は、これらのブロックへ信号を送ることを助けます。但し、それはチップの端に強制されます。対照的にDistributedRAMは、LUTをRAMとして使用することを可能にします。1つのLUTは、16x1(1ビット幅)の同期式または非同期式メモリを実装することができます。２つのLUTを組み合わせて、32x1、16x2あるいは16x1のデュアルポートメモリを作ることもできます。小さな多数の局所的なデータを保持する必要がある場合、この種類のメモリは有用です。BlockRAMはチップ全体に渡って用いる必要のない大量のデータを格納するために使用されます。
元々Belleの指手マスキング法は、このアーキテクチャで実装されています。各桝１ビットおよび64手分の深さの同期式メモリ（２つのRAM32x1Sを使用）は、マスクビット記憶用に使用されます。駒値を書くために使用されるバッファを介した信号線も、各桝の深さレジスタを更新するために併用されます。この設計ではフリップフロップを殆ど使わないので、各桝は配線を減らすために６ビットの深さレジスタを持っています。メモリベースのマスクビットスタックを使うことによって、DeepBlueでは指手をマスクするデコーダの意味を持っていた全てのロジックは不要です。
BlockRAMは、専用に用意された配線があっても、この場合マスクビットを格納するメモリとして最良の解決にはなりません。このメモリとの（データの）行き来によって４～８nsに及ぶ遅延が回路内で観察されました。局所的なメモリを使えば、前述した遅延は事実上除くことができます。しかしながらBlockRAMは、探索木中の各深さで生成された指手を格納する（メモリとして）理想的な候補です。２つのメモリが32ビットの指手を格納するために必要です。チェス盤を制御するステートマシンは、チップの（BlockRAMに接近している）傍近くに置かれます。これは、設計の中で適切なRAM資源の種類を選ぶことが重要だということです。
4.5. 例外手
チェスの例外的な指手にどのように対処するのか、チェスハードウエア探索の論文中滅多に言及されません。５ビットの全方向出力は、ポーンとキングが２つの桝の距離を伝搬することを可能にします。第４・第５段が２桝分ポーンが進めることができるように、第３・第６段の桝はポーンビットを広めます。更に、目的（移動先）桝をキャスリングする手を示せるように、桝f1、f8、d1およびd8にはキングビットを広めます。
水平のポーン出力は、取って移動するアンパサン用に使われ、またこのポーンの例外的な指手は、良い指手（優先手）として扱われます。ポーンが成ることがMVV/LVA順と単純な関係を持たないので、これらの手は、最上段へのポーンが進む手だけを生成する特殊な敵駒発見(find-victim)-成サイクルで扱われます。無駄を省くために、通常の指手生成はこれらのポーンを進める手を生成しません。これは無秩序に成る手のためにマスクビットを回復しなければならないからです。敵駒あるいは移動先桝（victims）は、マスクされてオフになる前に完全に探索されます。これは、最初の成生成と非互換で、通常の指手生成と共に継続しています。
5. 実装および結果
FPGA設計はVHDLで行いました。また、チェスプログラムはCでコード化しました。デバイスドライバは、チェスソフトウエアとPCIカード上に置かれたFPGAを接ぎます。64個のチェス桝の実体と63のアービタの実体を内部結線させるVHDLファイルを生成するために、Cプログラムを作成しました[*6]。使用したチップはXCV800-4です。また実装ツールはXilinx製です。フロアプランナは、チェス盤が8x8配列であることを配置配線ツールに知らせるために使用しました。
これは実行時間を縮め、より高い性能を備えた設計が行えます。この場合、17%の速度増加が得られました。図2は、チェス盤とアービタのために使用された間取り図です。アービタは、配線遅延を最小限にするために入力として使用されるブロック間に置かれます。全設計は、およそ7,000のLUT、1,000のFF、2つのBlockRAMを使用し、33MHzで走ります。
チェス指手生成器は、MBChessを実行するコンピュータに接続するPCIインタフェースを含んでいます。様々な異なるコマンドがあることで通信オーバヘッドを減らしています。例えば、カードからの単一の読み取りでは、指手生成器は、現在格納されている指手を取消し、次の指手を生成し、それを返し、ハードウエアチェス盤上の指手を実行するように命じることができます。アドレスの一部が、メモリ位置ではなくコマンドを渡すために使用される時、この読み書きの両立は可能です。
表2は、33MHzのPCIバス速度で得られた結果を示します。Hsuの論文と同じ計測法で数えた時、およそ毎秒800万手を生成することができます。著者のプログラム（MBChess）のプレイする強さへのハードウエア指手生成器の影響は、チェストーナメントによって評価されるでしょう。期待される改善は、チェスのレイティングで数百点の範囲内にあります。
6. 結論と将来の作業
このプロジェクトは、コンピュータチェスでのFPGAの活用を提案しています。ASICとFPGAの資源の基本的な違いが、FPGAによく適している解決策を生みました。現行のFPGAで見られる、予め埋め込まれたRAMが重要な役割を果たすことを示しました。フロアプランナは、更に設計の動作速度を上げることに貢献しました。より単純な内部結線策によって、チェスの例外手、および王手する駒を区別する問題を解決しました。FPGAの中にプロセッサが標準で入ることが近い将来起きると共に、集積回路とプログラムコードの統合は、FPGAを完成させ更に強力なソリューションとなるでしょう。
これを書いている今、次の人対計算機のチェスの大試合は、2002年の第1四半期に予定されています。それは現在の世界チャンプであるVladimir KramnikとDeepFritzの対局になるでしょう。そのチェスハードウエアは、専用ハードを付けないマルチプロセッサ型スパコンでしょう。その完成システムは、毎秒400万手以上を読むことが出来ます。DeepFritzは（DeepBlueと比べ）処理速度を欠いていても、チェスの棋理と最適化されたプログラミングで武装しています。私たちは、そのコストの僅か数分の１で同様のことを行うために、FPGA指手生成器が使われると信じています[*7]。
[*1] :XilinxのFPGAのみにある小規模RAMのことで、LUTを代替して用いる。
[*2] super-pieceとは巧い表現だが、ここではポーンからクイーンまでの利きを合わせ持つ仮想的な駒のことを意味している。
[*3] この項は、何が書いてあるのか非常に判り難い。要は「王手を掛ける手を見つけ出すハードウエア的アルゴリズム」がテキストで説明されているだけで無理がある。このあたりは、MBThesis.pdf の記述の方が図を加えて説明されていて判り易い。
[*4] ファンアウトとは、あるゲートの出力が、他のゲートの入力へ同時に幾つ分岐しているかを言う。
[*5] ファンアウトが極端に大きい（一般に10以上の）場合、バッファと呼ばれる回路を介して充分な電流を流せるようにし、他のゲートを正しく駆動する必要がある。但し、最近の論理合成では、このあたり自動的に判断してバッファを入れてくれるので、あまり深く考えなくても構わない。
[*6] Cプログラムを用いて、VHDLの文法で記述されたソースファイルを作っている。具体的には、以前紹介したMarcのソース MoveGenVHDL.zip の中の、 chess_board_auto_genフォルダの中にある、cb_gen.cpp のことを言っている。なお、このソースの拡張子はC++だが中身はＣである。何故そんなことをやったのかといえば、多数の部品間配線について人間がVHDLコードを手で書くと、手間がかかる上に間違いが極めて多くなるからで、それを回避したかったのだと思われる。
[*7] と、取りあえず日本語（になってない気がする言語）に訳したが、一度原文の方も読まれることを強くお奨めする。どのようなことが書いてあるのか大筋を知った上で原文を読まれた方が、より正確に理解し易いと思われる。