FPGAでコンピュータ将棋を作る(かも)


実は、かねてよりFPGAを使ったコンピュータ将棋を少しずつ作っている。どうせなら、公式対局でプロ棋士に勝ちたいので、(FPGAの進化を待つ意味で)3,4年後に完成すればいいやというのんびりペースだが。


以下、コンピュータ将棋関係者向けに私の思考の断片&妄想(?)。




・開発言語にはC#を使う。


・思考ルーチンはFPGAで動作させるためVHDLで記述する。


論理回路の世界は、足し算ひとつにしてもとても奥が深い*1。multi-operand adderは、ARITH*2で生成したものを使わせてもらおうと思っている。


・評価関数は、部分的な評価関数の足し合わせでやろうと思う。評価値は有効桁8桁ぐらいとして、(ビットの値が1である)最上位のビットが同じ位のものをひと固まりにして、tableのlook upで済むところはそうして、済まないところはmulti-operand adderで4つずつぐらい加算していくのが効率が良さげ。


id:yaneurao:20070304 で、コンピュータ将棋の思考ルーチンには乗算が大量に出てくると書いてしまったが、このように部分的な評価値を足し合わせるだけなら乗算なんてひとつもいらない。


・評価関数を計算するVHDLのコードは、別の言語から半自動生成しないとやってられない。Bonanzaのようにαβで数手ほど探索させて、プロの指し手との一致度を最大化するようにパラメータを自動チューンする。このときαβで探索する部分はC#からC++のコードを自動生成して実行する。


Bonanzaのように多くのパラメータを用意する必要はないかも知れない。たくさん先読みするなら、評価関数は簡素化されてくる。あとBonanzaの場合、開発者の保木さんがあまり将棋に詳しくないため、あまりうまく特徴パラメータが選べていないように思う。


・パラメータのチューンはBonanza最急降下法を用いていたが、最急降下法は収束性が良くないと思うので出来れば使いたくない。以前考えたコードは、以下のコードだ。下に凸っぽい関数に対して、最急降下法よりはうまく収束するかも。(要テスト)


// f(x,y)を最小化する(x,y)を求める場合。

float x = 0.0f, xs = 1000.0f;
float y = 0.0f, ys = 1000.0f;

for(;;)
{
float k1 = f(x - xs, y);
float k2 = f(x + 0, y);
float k3 = f(x + xs, y);
// ループ初回を除き、この3つのうち1つか2つはすでに
// 既知なので実際に使うときは結果をcacheするか
// 再計算しなくていいように以下を書き換えるべし。

if (k1 > k2 && k2 > k3)
{
x += xs;
xs *= 2;
}
else if (k1 < k2 && k2 < k3)
{
x -= xs;
xs *= 2;
}
else
{
xs /= 2;

// k1==k2==k3のときはlocal minimumの可能性もあるので
// 収束後にも確率的にそこから抜けだすための処理を入れたほうがよさげ。
}

// 以下、yについても同様。
}


FPGAのほうは、SystemCかSystemVerilogで開発しようかと思ったが、FPGAで書く将棋の思考ルーチンなんてそれほど複雑なものではないし(複雑なものは書けないし)、足し算ひとつにしても高速化を追い求めるなら、将棋の評価関数をチューンするためにC#で書いた環境から、直接VHDLのソースを生成する。


・2年後にはいまのパソコンが2,3倍に速くなっているとしてトップ集団のコンピュータ将棋はシングルスレッド換算で 6Mp/s(秒間600万局面)ぐらいの探索能力があるはず。FPGAのほうは小細工はほとんど出来ないので、10倍ぐらい局面を読んでも互角にすらならないと思う。2年後に60Mp/sぐらいの性能しかないのでは到底かなわない。せめて100Mp/s。欲を言えば500Mp/sぐらいは無いと。


・仮に1万パラメータの特徴からなる局面の評価値を求めるためには、$\Sigma$ Pi・Bi (i=1,…,10000)のような計算が必要になる。(Piは有効桁8bitの整数、Biはboolとする) 高速化しようと思うと1パラメータにつきFPGAのLE(Logic Elements)を50ぐらい消費すると思うので、この評価値を求める部分だけでも 50万LE ぐらい欲しい。そう考えるとBonanza相当の将棋の思考ルーチンをそのまま(?)FPGAに落とし込んだ場合、トータルで100万LEぐらい必要になりそう。(現状のFPGAではやや足りない) (要検証)


・局面を保存しておくためのハッシュ表は用いないかも。探索局面数に対してハッシュが小さすぎると効果がないと思われるため。しかし千日手のように循環して同一局面に戻ってくるような手の生成は防がなくてはならない。root局面から探索中の局面までのそれぞれのzobrist hashを求めておいて同一のzobrist hashになる手の生成を除外(連続王手による同一局面への突入は負けの評価値を返す)する。


・futility pruningなども用いないかも。FPGA化するときに面倒だ。


・指し手のorderingはやる。どうやってやるかは考え中。


FPGAは指し手の生成などは速いので、意外とMTD(f)で並列化したときの効率が良かったりして。(要テスト)


・思考ルーチンが複雑化する場合は、VHDLで命令のOoO(Out of Order)実行をするRISCコアを自作して、思考ルーチン記述の補助に使うかも知れない。