FPGA用コンピューター将棋で一番難しいのは指し手生成 - FPGAによるコンピューター将棋「スーパー田舎将棋」作ってます!!

Hydraの解説を読んでいて、だいたい作りが理解できました。

1) 探索は状態マシンで、たいした状態数ではないので普通に実装すれば問題なさげ。

2) 評価関数はFPGAらしく並列で計算して問題なさげ。

3) 指し手に従って局面を進める / 戻す

4) 指し手生成～オーダリング～1手選択

1),2)をパイプライン化することで性能は変わりそうですが、それはあとでもやろうと思えば出来るでしょうし、そこは難しい部分ではないのであまり問題にはならないです。3) は簡単なので説明を要しません。

問題は4)ですね。いかにして超並列的に指し手を生成し、オーダリングして1手選択するか。どうもコンピューター将棋やチェスではこの部分の設計が非常に難しく、そしてボトルネックになりうるようです。

半面、評価関数のほうは、評価因子をいくら増やそうと内蔵メモリに評価関数テーブルが載る限りはルックアップは並列化できますし、どんどん増やすことが出来ます。

ゆえに、指し手生成を並列的に高速に出来た時点でFPGAのコンピューター将棋のうちの半分は完成したようなものではないかと思います。(PC版のコンピューターをFPGA化することを前提に話をしていますので、評価関数および探索アルゴリズム自体はすでに確定しているものとします)

Hydraプロジェクトに学ぶ

http://fpgashogi.hateblo.jp/entry/2012/11/17/200418

Hydraの指し手生成を将棋にこれをこのまま応用できるかですが、意外と将棋でもうまくいくような気がします。なぜなら、空いているマスには駒が打てるはずで、生成される指し手は駒種(二歩と打ち歩詰めを除く)だけあるはずですし、空いていないマスに自駒があればその自駒を移動させる指し手があるはずだからです。残念ながら敵駒のあるマスに対して生成される指し手はないわけですが。

あと、1マスから生成される指し手は、空のマスの場合、駒打ちですから最大7通り。移動の場合、敵陣にいる飛車が左右と上下で16箇所に対して成りと不成がありますね。飛車の不成って生成する必要があるのかどうかはわかりませんが。ともかく32が最大ですね。後段に7段のコンパレーターが必要ですが、この7段のコンパレーターは1クロックで実行するとしまして、飛車に関して32回クロックも使って指し手生成をしていいのかということにはなりそうですね。飛車が敵陣に出てくるノードに遭遇するごとにこのような生成をするのはさすがに効率が悪そうです。

Bonanzaのように飛車の不成は生成しないとしましても16回。16って多いですね。駒打ちの最大が7ですから、ここも7ぐらいになって欲しい気はします。それに龍だと16+4 = 20ですか。大きいですね。この部分、100MHzぐらいで合成できたとしても毎ノード、20クロックも指し手生成に必要だと探索も評価関数もなしで指し手生成しかなくとも5Mnpsしか出ません。そもそも7段もコンパレーターがあって100MHzで合成できるのかよくわかりません。

裏を返せば指し手生成器を20倍に増やして、コンパレーターツリーをあと数段増やせば1クロックで指し手生成～選択まで可能だということですか。81×20 = 1620個の指し手生成器..。どうも何か間違っている気がしなくはないですね。どう考えてもLEを消費しすぎます。

1クロックでそれぞれのマスの担当がそのマスで生成する指し手のうちベストなものを出力するというのはアリのような気はします。飛び利きを持つ駒ですとLMRなどでオーダリングしようと思いますと20個指し手があるので大変ですが、この部分、オーダリングがないならばアリなんでしょうね。もう少し考えてみます。

「アマ4段を超える―コンピュータ将棋の進歩〈4〉」に書かれている指し手生成

「アマ4段を超える―コンピュータ将棋の進歩〈4〉」にFPGAによる将棋の指し手生成の論文が掲載されていたと思うので引っ張りだしてきたのですが、複数クロックで生成するようになっています。当たり前と言えば当たり前かも知れませんが。

指し手生成にこんなにクロック数が必要なのならばコンパレーターツリーの最後の段のほうで、1位～8位まで確定させて、それをメモリにbufferしておくのはアリなのではないかと思います。

FPGAで書かれたコンピューターチェスの指し手生成

あとFPGA型のchessの指し手生成のソースコードがあったのでそちらも見てみたのですが、そちらはVHDLで書かれていて読めませんでした。VHDLで書かれている大切な記事も結構あるので、こういうときのためにverilogだけではなくVHDLも勉強したほうがいいのかも知れませんね。

「A級リーグ指し手1号」の指し手生成

「A級リーグ指し手1号」はどうしてあるのだろうと思い、ソースコードを見たのですが規模が大きすぎてよく理解できませんでした。

→　理解できた範囲で説明を書いておきます。

mecellというのが盤面のマス目に対応する指し手生成器のようです。geninst.plがこれから不要な部分を除去したりしながら(よく読んでいません)81個複製するPerlのソースコードのようです。これによりinst_mecells.vというソースコードが生成されます。これはmeall.vのなかでincludeしています。

生成された指し手を選択するのはselectmv.vのようです。cmp3x3が3×3個のデータ2組を比較するコンパレーターのようです。

私の考える指し手生成その1

1サイクルですべての指し手を生成し、それぞれの指し手のhistoryの値でオーダリングするとしますと、そのオーダリングする値を8ビットの数値としまして、各マス64×龍の移動20 = 1280個程度の指し手生成器が必要になります。まあ盤の端では龍の移動は20ではありませんので実際は1000ぐらいかと思います。そのあとコンパレーターによるバイナリーツリーがありますのでコンパレーターもそれくらいの数だけ必要だということになるかと思います。

1つの指し手生成器が100LEぐらいで実現されるとしまして、これだけで100k LEを消費することになります。指し手生成でオーダリングを欲張ってしようとするのが悪いのだと思うのですが、それにしてもさすがに大きすぎます。

一方、評価関数のほうはメモリに収まらないのは気がかりですが、足し合わせる評価項目としては500程度に収まると思いますので、評価値を足し合わせる16ビット加算器(上流ではそこまで大きな値にはなりませんので最初は8ビット加算器ぐらいで事足りるはずです)が並ぶだけですから、たぶん1項目当たり2,30LE程度ではないかと思います。

仮にBonanzaと同等の評価関数を考えたとしましても足し合わせる数は1200程度。テーブルが内蔵RAMに収まらないという問題はありますが、それはいまおいておくとしますと、1項目50LEずつだとしても60k LEです。

そう考えますと指し手生成の高速化がいかに大きな規模の回路が必要になるかがわかります。

私の考える指し手生成その2

そこで、別の案としまして、飛・龍・角・馬に関してはそれ専用の指し手生成器を用意し、各マス用の指し手生成器では生成しないというのが考えられます。飛車と龍はセットで考えるとしまして、また、角と馬もセットで考えるとします。

つまり、(角 or 馬) + (飛 or 龍) は、盤上に4枚しかありません。この4枚に対しては最大20通りの指し手(注:成りと不成は生成するフェーズが異なるので別々にして考えることができます。また香のことはいま無視して考えます)が生成されますので80個の指し手生成器を用意します。

これを除きますと各マスでは最大でも8近傍の指し手のみで済みますから、8つで済みます。角・馬・飛・龍に関しても8近傍への移動に関してはここで生成してしまいましょう。そうすれば最大でも12通りで済みます。

81マスのうち、辺は8近傍ではなく5近傍ですし、かどは3近傍です。ゆえに8×81 - 4辺×7箇所×3 - 4隅×4 = 548個。大駒4駒×12 = 48個。合計596個の指し手生成器で済みます。1個の指し手生成器が100LEで構成されるとしまして、596個×100LE = 59.6k LE。DE0 nanoには到底載りませんが、現在20万円ぐらいのFPGAボードであれば200k LE程度内蔵されていますのでそこそこ現実的な範疇ではないかと思います。(香のことは考えていませんが、香は9段目では成りしかないので、通常移動としては8段目まで。しかし8段目での不成は打ち歩詰め回避のときしか意味がないので実際は7段目まで。つまり生成される指し手は最大で6通り。ゆえに、これは専用の指し手生成回路は用意しないものとします。)

しかし大駒は移動があり、移動させたときに飛び利きを指し手生成器は、その移動後の周辺のマスの情報を保持して更新しないといけませんから、これが結構大変かも知れません。

私の考える指し手生成その3

さらにもう少し考えかたを変えまして、もし各駒用の指し手生成器があればどうかという考えに至ります。つまり、40駒用のそれぞれの専用の指し手生成器があるとしたら…。歩などは前しか行きません。ただし成っていることもあるので6方向の指し手が最大で生成されます。そう考えますと、角・飛が20通り、それ以外の駒は6方向、王は8方向。ゆえに、34枚×6 + 4枚×20 + 8 = 292。292個の指し手生成器で済みます。あーっと、駒打ちを忘れておりました。駒打ちが残りの空いてるマスに対してありますので…全然駄目ですね。

よく考えますとチェスの指し手には駒打ちがありませんので空いているマスは何も出力しません。そこで、たとえば大駒を移動させる手であれば隣接するマスに移動するよという情報を伝播していき、そして、自分のマスが空のマスであれば移動できるものとして、この指し手を生成するという方法があります。(何かの論文で見た気がします)　この方法は結構理にかなっていると思うのですが、将棋では駒を打つ手があり、空いているマスは打つ手の生成に忙しいのでそれどころではありません。

私の考える指し手生成まとめ1

結局のところ、81マスの指し手生成器をたとえば上記に書いた596個の指し手生成器を用意した場合、回路規模は8倍近くになります。8倍の回路規模で8倍速になれば良いですが、実際は3倍速にすらならないのではないかと思います。であれば、ここで指し手生成を頑張ってもあまり意味はなく(その豊富なLEを生かして評価関数の改善を行なうか、探索コアを複数載せて並列探索をしたほうがマシ)、ここが最終的にどうしてもボトルネックになったときに考えたほうが良いのではないでしょうか。いきなり、大きな規模の回路を作ってしまいますと論理合成に時間がかかりすぎて開発がままなりませんので得策とは思えません。

指し手生成を1クロックで行わなくて良いならばそこそこパイプライン化も出来るはずですので効率面ではかなり良くなるはずです。

私の考える指し手生成その4

FPGAのチェスの論文を見ていて、何故セル間を捕食情報を伝播するのか(たとえば飛車が他の駒をとるために移動できる先にある駒を探す処理において、飛車が移動できる経路を隣のマスに次々と伝播していくこと)意味がずっとわからなかったのですが、意味がやっとわかりました。同じ方向からの飛び利きが重複することはありえないので捕食のされかたというのは、8通しかないのです。

逆に言えば、通常の駒もこの移動経路に従って情報を伝播した場合、1つのセルにおいて生成される指し手は8通り。桂を含めても10通り。最大で1つのマスに10通りの駒しか利かないのでこのことは当然でしょう。また桂の移動は伝播していく必要がないので伝播しなくてはならないのは8方向だけ。

ゆえに、たとえば銀の移動を考えるときに、銀の移動先情報として斜め上、上、右上、左下、右下に「銀が移動できるよ」という情報を伝播します。情報を伝播されたセルは、これは銀なので(飛び利きではないので)これ以上他のセルには情報を伝播させません。また、このセルは指し手を生成しますが、このセルから最大で10通りの指し手が生成されるだけです。コマ打ちを生成するセルとは分離しておくことが出来るとしますと、このセルから生成される指し手は10×91。(盤面の端のほうではもう少し少なくなりますが)

つまり、最大でもこのセルからの出力は10回しかありません。(成りと不成は別のフェーズで生成することとし、同時にカウントしないものとします) また、飛車の移動であれば行き先のマスを担当するmoduleが指し手をそれぞれ生成するので飛車があるから16サイクル必要ということもなく、最大でも1つのマスから生成される組み合わせのサイクルで終了します。駒打ちとは分離するのであればこの数は最大で10通りです。ひとつの局面で1箇所に利いている自駒は多くとも4か5程度でしょうから、どちらかと言えば駒打ちの指し手生成のほうがボトルネックになることが多いでしょう。また、駒打ちのほうがボトルネックになるのであれば、歩・香・桂・銀と金・角・飛とを別々の指し手生成器を使うだとかそういう感じの並列化は可能かと思います。

完全に指し手並列を並列化するとしまして、その場合は81マス×10通り + 81マス駒打ち×7通り = 1377ですね。組み合わせは意外と多いですが、しかし他のセルの情報は保持しなくて済むようになりますのでロジックは単純化できそうです。

私の考える指し手生成その5

「私の考える指し手生成その4」で1377個の指し手生成器を用意するところまで話を進めました。仮に2クロック要していいならばおおよそこの半分の数の指し手生成器とコンパレーターで済むのではないでしょうか。

つまり、各マスについて

・上下方向

・左右方向

・斜め+45度方向

・斜め-45度方向

・桂馬跳び

・駒打ち　歩・香

・駒打ち　桂・銀

・駒打ち　金・角

・駒打ち　飛

のようになります。81×9=729の指し手生成器ですね。3クロックの場合どうでしょうか。

・左右上

・斜め+45度方向と桂馬右跳び

・斜め-45度方向と桂馬左跳び

・駒打ち　歩・香・桂

・駒打ち　銀・金・角

・駒打ち　飛と下移動

81×6の指し手生成器ですね。駒打ちと下移動が混じっているのが少し気持ちわるいですね。しかし512以下に抑えられるのでコンパレーターツリーが8段で済みますね。

4クロックではどうでしょうか。

・上下左右(4)

・斜め方向(4)

・桂馬跳び(2)

・駒打ち歩香桂(3)

・駒打ち銀金角飛(4)

81×5で、指し手生成器の数は言うほど減りません。桂馬跳びが端数を生み出していて嫌な感じですね。指し手生成器が大きくなってきますと、アービターも大きくなりますね。

いや、必ず4クロック使用して良いのであればアービターは不要ですが…。かならず4方向のいずれかの指し手はあるでしょうから、この場合アービターは入れるだけ無駄ですかね。

あと打ち歩詰めと王手が回避できているかにつきましては局面を進めてみないと判定できませんね。まあ、それはそれでいいのではないかと思います。少し無駄ですが、打ち歩詰めとか王手がかかっている局面はそれほど多くないと思うのでそれはそれで良いのではないかと思います。

そんなわけでLEが余ればこのへん消費クロック数を減らしてもう少しなんとか出来るのかも知れませんが。そもそも8bit値であろうとコンパレーターツリーがそんなに大きくなっていいのかどうか私にはよくわかりません。

指し手はfrom,to,成り/不成・打ちの情報は少なくとも必要ですから10bit必要です。コンパレーターツリーで8bitの数値を比較して行き、最後に残った指し手に関するこの10bitの情報が必要です。これにどれくらいのLE数が必要なのか想像もつきませんが…。

結局、1マスから生成される指し手の最大数は17(10方向 + 駒打ち7種)なので3で割って6サイクルで処理するのが一番キリがいいのかも知れませんね。81×3なら256に収まるので7段のコンパレーターで済みますし。

// ここに何かいいアイデアが浮かべば追記するかも知れません

実験項目

このあと、小さな指し手生成器2つ程度とコンパレーター1つを実際に作ってみて、どれくらいのLEを消費するのか見てみたいと思います。

// 指し手生成について何か思いついたらここに追記します。