手損検出

テーマ:

置換表を用いて探索効率を向上させる為のアイデアはいろいろ考えられる。但し、アイデアとしては一見良さそうでも企画倒れ的状況に陥ることも良くある話だ。置換表に関する設計を行っていた頃、置換表を使って手損検出が出来るのではないか、と検討してみたのだが、これがなかなか単純ではないことだけが判り、決定版と言える手損検出の手法を見つけることが出来なかった。


例えば囲碁にしろオセロにしろ、恐らくチェスにしてもパスする手が最善になる局面があり得る。つまりは1手損なのだが、将棋だけが例外と考え難いし、実際に「パス出来ないなら投了以外の手がない局面」を作ることは出来る。そうでなくても、一見手損に見える手が(プロ棋士が結論を出した)最善手であったりすることもあることを考えれば、人間が認識する「手損」が本当に損であるかどうかを正しく判断するのは、計算機的に極めて難しいのではないかと考えている。


さて、過去に手損について検討した際、手損を「1手損」と「2手損」に分けて検出法を考えたことがある。具体的には次のような手法だ。


【2手損】

2回パスしているのと同じという意味で、ここでは「相手に千日手を選ぶ権利を与える損」という意味で使っている。相手が千日手を選ばないなら相手にとっては2手得になり得るところから暫定的にそう呼んでいる。この検出は、既に前稿で示した千日手検出の手法を用い、検出したノードから返す引き分けの結論値を工夫することできめ細かい対処が可能である。例えば、先手と後手で結論値に差を付けたり、千日手を選ぶことが歩損より大きいペナルティがあるとすれば、歩損してでも千日手を打開する手を指させるようにすることが出来る。


【1手損】

これには2種類あり、一つは「1手で指せる手を2手掛けて指す」ような手順。具体的には、例えば先手59に玉がある状態から▲58玉~▲68玉といった手順で、1手で▲68玉と玉を移動できる局面であるにも関わらず58を経由して68に移動すれば、これは人間の感覚なら損だと感じる。但し、あらゆる局面で「1手で指せる場所へ2手掛けている」こと自体が、勝敗が決するほどの致命的な損になるとは限らない。合法的に強制された手順でそうなる場合もあるし、その手が最善ということもあり得る。従って、単純な方法では検出不可能という結論に達し、アイデアを検討している段階で実装を見送った。


またもう一つは、例えば左図の局面から▲24歩▽同歩▲同飛▽23歩▲28飛と5手進めて「手番放棄」、即ち完全な1手損になる。このような手順がパスになっているか否かの「チェックのみ」を行いたいのであれば難しくはない。恐らく最も簡単な対処方法は、探索前にルート局面の手番反転局面を「1手損局面」として置換表に予め登録しておくことで、5手目の▲28飛を指させないようにする(強制的にこの手を読まないようにする)ことは可能だ。しかし先に書いた通り、将棋のありとあらゆる局面で、この手法が通用するかどうか疑問だと感じ、一旦実装はしたものの結局現謎電ではこの処理を外している[*1]


現時点での私的結論としては、「その手損が、勝敗に直接結びつく程の損であるか否か」を判断するのは、単に置換表を利用した技術だけの方法では解決できない、ということである。このあたりは、今後更に時間を掛けて研究すべきテーマであるかどうかすら(つまりは実を結ぶ研究になるかどうか)判断が難しい、と考えている。逆に言えば、この問題が現実的実用的な方法で解決できるとすれば相当画期的なことなのではないかと思う。


[*1] 正確に書けば、 初期局面からの経過局面に関しても手番を反転した局面を手損局面として判定できるようにしていたのだが、何か微妙に不安というか嫌な予感があって、今はコメントアウト状態になっている。手損は駒損と異なり、表面的には同一盤面とは言え、間違いなく損であることの根拠に欠けるからだ。 少なくとも、この手法で手損を検出した時点で探索を終端し、定数の結論値を返すと明らかにおかしくなる場合がある。
AD

持駒の優劣関係判定 (3)

テーマ:

こんにちは。持駒の優劣関係判定とその関連処理を語らせたら、私の右に出るのは私しかいないと思っている謎電の作者です(笑) 前回の記事には思いの他かレスがあり、まさかコンピュータ将棋や囲碁の掲示板で紹介されるとは夢にも思わなかった。ので、ちょっと余談的続編を書いてみることにする。とは言え、神吉六段には突っ込みを入れることは出来ても、大学教授に突っ込みを入れるのは憚られるので、それはおいておくことにして、詰探索ではなく通常の指将棋探索への応用例を挙げることにする。


既に実装済の方もいらっしゃるのではないかと思われる。それは探索中の同一盤面ノード再入時の対処である。指将棋の場合、完全同一局面(持駒同一)の場合は千日手と判断し、手番側にとって劣位(完全駒損)であれば負け、優位(完全駒得)であれば勝ちの結論値を返すという手法が考えられる。
但し、千日手検出時には微妙な対処が必要だ。詰探索での千日手は、指将棋でいう連続王手の千日手と同く、(攻方基準で)不詰結論を即返して問題はないし駒損であれば尚更である。しかし指将棋で千日手(持駒同一)を検出した場合は、基準となる局面までの手順が王手の連続であるか否かを別途判定する必要がある。


謎電では、初手から手順(王手を掛けている手であるか否かを含めて)を常時リスト管理すると共に、置換表にも探索に入る前に初期局面からの経過局面を予め(経過局面であることを示すフラグを立てて)登録しておき[*1]、千日手検出局面から(千日手開始の)基準局面に向かって遡って王手の連続になってないかどうかを判定している。この判定で連続王手になっていることを検出した場合は、「王手を掛けている方が負け、その逆の場合は勝ち」の結論値を返すことで実現できる。この判断処理を実装することで、最短で勝つ手を瞬時に見つけることが出来たのが、第13回選手権一次予選▲宗銀▽謎電戦 である。


因みに、(詰探索用の置換表を実装していても)同一盤面ノード再入判定を実装していなかった時代の謎電では、次のような簡単な判定が出来なかった事があり、また置換表を用いた判定の限界を示す例として、第11回選手権ニ次予選▲大二郎(おおじろう)▽謎電戦を挙げておく。


左図は、その129手目。本譜はここから▲42歩▽31金▲41歩成で、▽同金が「駒得同一盤面」となるので即刻指して欲しいところだ。しかし実戦では52秒の長考?後に▽同銀で非同一局面を作っているし17手詰の頓死になっている。


とは言え、もともとこの左図には既に▲31銀以下21手詰があって後手負けと言えば負けなのだ。従って、後手にとって駒得同一局面を作れるとしても「真の勝ちが保証されているわけではない」ことを心に留めておく必要があることになる。


しかしながら、この処理を入れておくことによって、少なくとも「過去に経過した局面と比べれば、間違いなく自分が損する手」を排除することは可能であるし、探索量も多少なりとも減らせるので実装しておいて損のない手法である。


[*1] なお、もし棋譜上の経過局面に「持駒に包含関係のある同一盤面(局面)」が存在する場合は、最新局面の方を上書き登録するようにしている。但し、持駒が非同一の場合はその限りではない。

AD

持駒の優劣関係判定 (2)

テーマ:

ハッシュキーは盤上の駒のみを基準にし、置換表レコード上に持駒データを持たせて、同一盤面の時に持駒の優劣関係から判定して詰・不詰を引用するアイデアは、恐らく古くから多くの計算機将棋開発者が持っていたのではないかと思う。コンピュータチェスの世界には前例・参考例が全くない(そもそも持駒の概念がない)ので、そのアイデアをどのように巧く実装するかが課題だったのではないかと思われる。

私が置換表の実装に踏み切れなかったのもその点の解決案がなかったからで、脊尾さんの手法を知った当時、相当真剣に優劣関係判定法について検討したものである。

脊尾さんの手法では先に書いた通り、ビットを立てていくクッション処理が入り、これが正直どうしても気に入らなかった。無論、そのやり方は論理的に正しいことが直感で判るし、2進数のままでまとめて引き算を行うやり方は「原理的に無理がある」と思い込んでしまっていたのも確かだ。例えば、


・対象局面は持駒なし: 0x00000000
・被対象局面が歩1枚:0x00000001

なら、対象から被対象を引くと、0xffffffff になり、他フィールドへドミノ倒し(将棋倒しとは書かないところがミソ)的にボロウを引き起こして全く話にならない、と感じてしまう。その演算結果を用いて「歩以外の各持駒が何枚あるか」を求めたいのであれば使えない手法であることは事実。であるが故に私自身、一時的に不可能だと勘違いしていた。

米長会長流に言えば、ここで「計算機将棋の神様の御告げ」があった。元々私は諦めが悪い方であるし、これが将棋なら「探せば手はある」筈だ[*1]。ポイントとなるのは、「各持駒の枚数を並列計算したい」のではなく、あくまで「優劣関係の判定を行いたい」だけである。つまりは{完全同一、優位、劣位、非同一}の4つの何れであるかを正しく判断できれば、どのようなやり方であっても速いなら問題ない。対象持駒をA、被対象持駒をBとした時、


・完全同一:A.歩=B.歩 ∧ A.香=B.香 ... A.角=B.角 ∧ A.飛=B.飛 
・A優位  :A.歩≧B.歩 ∧ A.香≧B.香 ... A.角≧B.角 ∧ A.飛≧B.飛 ∧ 完全同一でない
・B優位  :A.歩≦B.歩 ∧ A.香≦B.香 ... A.角≦B.角 ∧ A.飛≦B.飛 ∧ 完全同一でない
・非同一 :上記以外

これらを正確に判定できれば良いわけで、結局互い違いに算術減算を行って各フィールドのMSBを検査して全てのフィールドでボロウが起きないなら、等しいか包含関係にあることが保証されることに着目し、そのフィールド長が本来使う値の範囲より1ビットでも長いなら、2進数表現であっても優劣関係の判定は出来ることが判ったのである。

結論が最後になってしまったが、具体的なコード(マクロ)例を次に示す(引数はHand型とする)。


#define    Dominate( a , b )    ( ( ( ( a.h - b.h ) & 0x88888880 ) ? 2 : 0 ) + \
                                  ( ( ( b.h - a.h ) & 0x88888880 ) ? 1 : 0 ) )

このマクロの演算結果が示す値の意味は、次の様になる。


0:完全同一(どっちからどっちを引いても全くボロウが起きない)
1:aが優位 ( b - a の時のみボロウが起きる)
2:bが優位 ( a - b の時のみボロウが起きる)
3:非同一 (どちらでもボロウが起きる)

余談だが、このマクロには3項演算子を用いている。VisualC/C++の場合、最適化を効かせてない場合でも条件分岐命令が生成されず、それなりに高速な実行コードを吐き出してくれる。インラインアセンブラを使っている方には参考になると思うので、一度ニモニックを確認されることをお奨めする[*2]


[*1] 私の将棋の場合には、そういう事はほとんどなく、本来の将棋の神様には見放されているようである。
[*2] 個人的に最も参考になるのはWatcomCで、コレのx86コード最適化技術は気合が入っていると思う。
AD

持駒の優劣関係判定 (1)

テーマ:

つい最近、コンピュータ将棋や囲碁の掲示板で「持駒の優劣関係判定」についてコメントしたのだが、この件について以前から最先端計数将棋学で取り上げようと思いつつ、すっかり忘れてしまっていた。脊尾さんの手法について最初に知った時は、なるほどと思ったのだが、私が掲示板に書いた方法は、「もっと(謎電にとっては)シンプルで巧い方法があるのではないか」と考えているうちに気付いたやり方である。謎的独自手法にたどり着くまでに紆余曲折があり、その流れを含めて簡単に(と書きつつ2回に分けて)解説しようと思う。


初期の謎電では、局面(盤+持駒)のデータ管理を次の様に行っていた。


typedef unsigned char    byte;

typedef struct {
    ...
    byte sHand[8];      // ▲持駒([0]:歩~[6]:飛の各枚数)
    byte gHand[8];      // ▽持駒([0]:歩~[6]:飛の各枚数)
    ...
    byte sq[9][16];     // 桝[筋/0-8][段/0-8] で盤を表現
    ...
} Board;                // 局面構造体型定義

上記構造体型定義は、局面情報の一部だが、最低限局面を表現するのに必要なもののみ示した。持駒は飛~歩までの7種類しかないので、配列の大きさは7でもよいのだが、ダブルワードバウンダリに合わせたかったので8としている。


その後、持駒データを32ビット(4バイト)ビットフィールド構造とし、次の様な構造体/共用体型定義とした[*1]


typedef struct {
    int fu  :8;         // 歩(8ビット):0~18まで
    int kyo :4;         // 香(4ビット):0~4まで
    int kin :4;         // 金(4ビット):0~4まで
    int kei :4;         // 桂(4ビット):0~4まで
    int kaku:4;         // 角(4ビット):0~2まで
    int gin :4;         // 銀(4ビット):0~4まで
    int hi  :4;         // 飛(4ビット):0~2まで
} HandFields;           // 持駒32ビットフィールド構造体型定義

typedef union {
    int        h:32;    // 32ビットintでアクセスしたい時に使用
    HandFields bf;      // 各フィールドを任意に指定したい時に使用
} Hand;                 // 持駒データ共用体型定義

これは脊尾さんの手法のようにビットを立てていくやり方ではなく、純粋に算術加算可能な2進数表現の管理である。駒の並びを見ると、歩香金桂角銀飛、という一見訳の判らない順序だが、これにはちょっと理由があってそうしている。一言でいえば、旧8バイトの持駒データ配列と、新32ビット(4バイト)持駒データ構造を、相互に高速変換できるようにしたかった為で、それ以外の意味はない。


これにより、旧メンバの byte sHand[8] と byte gHand[8] が Hand sHand と Hand gHand に変更された。このあたりの改造は、謎電が初めて置換表を実装する段階で一斉に行ったもので、2000年頃の話である。但し、構想だけは5年を費やしている[*2]

-- 続く --


[*1] なお、ビットフィールド構造体定義の結果は、完全に処理系依存だ。どのようにメンバがメモリ上に配置されるかは、コンパイラによって異なるので注意が必要。

[*2] 選手権に参加する前から、ということになるが、単に「ものぐさ」してただけ、とも言える。いろいろと置換表に持たせる機能について考えているうちに、内容が壮大になり過ぎた、ということもあるにはあるのだが。

左図は、不詰物である。ある程度将棋を嗜んだ者なら見た瞬間(1手も読むことなく)詰まないと判るが、計算機的には単純ではない。一般的なアルゴリズムなら恐らく、▲12歩▽同玉▲13歩▽同玉▲14歩▽同玉▲15歩▽同玉▲16歩▽同玉▲17歩▽同玉▲18歩▽同玉▲19歩▽同玉と16手先を読み、17手目に全く王手が掛からない段階で「不詰」と判断するだろう。因みに謎電でこの図を探索すると、72nodesの探索の後に「不詰」となる。


ここで、(歩で王手を掛けられた時は)玉は千鳥に逃げろ、というヒューリスティクス[*1]を使うと、▲12歩▽22玉▲23歩▽13玉と進めて5手後の手がないことが判り、この場合に限れば約1桁高速化できる。のだが、それはあくまでこの場合であって、詰物、あるいは実戦では、そのヒューリスティクスは通用しない。


詰探索を高い効率で行いたいならば、詰まない王手を掛けられ、それが「詰まない」ことを如何に早い段階で悟るかにある、と考えている。以前「図巧8番の自虐的探索 」でも書いたが、玉方の手の優先付けは、少しくらいコストが掛かっても、精密な優先付け評価を行うことで猛烈に速くなることがある。例えば、無双85番(55手詰)は、玉が逃げる手しかない局面で、その玉の逃げ方の優先付けを僅かに変更するだけで、ほんの数秒で解けたり、逆に数分掛けても解けない[*2]、といった現象が起きることを確認できる。


なお、この図を効率悪く読む手順(例)は、▲12歩▽21玉▲22歩▽31玉▲32歩▽41玉▲42歩▽51玉▲52歩▽61玉▲62歩▽71玉▲72歩▽81玉▲82歩▽91玉▲92歩▽同玉▲93歩▽82玉▲83歩▽72玉▲73歩▽62玉▲63歩▽52玉▲53歩▽42玉▲43歩▽32玉▲33歩▽22玉▲23歩▽12玉▲13歩▽同玉などと読むことで、この場合で35手、36手後にはじめて不詰だと判る。最短手順の詰を調べるために証明数を使わない古典的な探索法を用いている場合、このような「詰まない局面の無意味な探索」をやってると全く使い物にならない。


時々暇な時間を見つけては、このような「不詰物を解図させ、如何に早く『不詰』の結論を出させるか」に凝っているのだが、こういう改良が結構面白いと感じるようになった。


[*1] これがヒューリスティクスと呼べるか甚だ疑問だが、別の呼び方を思いつかないので取りあえず。
[*2] 余談だが、置換表がオーバフロを起こし出しても解けないとなると、ますます効率が悪化するので踏んだり蹴ったりになってしまう。


(追補) 【猫でも判る、不詰物の創りかた講座】

1.何かしら持駒のある詰物(完全作)を用意します。

2.その持駒の中から、どれか1つ駒を減らします。

実はこのネタで、いっこアーティクルを起こそうと思ったんですが、顰蹙を買いそうなので止めたのでした。

Cコードで永久ループを作りたい時、do { ... } while(1) とか while(1) { ... } といった書き方を目にすることがある。たまたま今日、そういうコードを見た。それらは文法として間違ってないし、意図通りに動くか否かどっちなんだ、と訊かれれば、間違いなく「動く」のだが、人間に厳しいコンパイラなら警告が出る。

さて、C言語の文法書(K&R)をよくよく読めば、一応「正統な永久ループの書き方」があることが判る。15年ほど前、あるプログラマが書いたコードを見ていて、そのことに気付いた。具体的には次の様なコードだ。


--
#define     ever    (;;)

void    main( void ) {
    for ever {
        process();
    }
}
--

この書き方は処理系依存ではなく、あらゆる(ANSI)Cコンパイラ(プリプロセッサ含む)が正しく記述されたCソースとして扱ってくれる。文法として正しい以上、そうでなければCコンパイラと言えなくなってしまうからだ。ひとひねり入っているが、このようなコーティングには、何か心に感じるものがある。

Cは高水準言語とは少し言い難い。しかしながら、こういうコードに出会うと、アルゴリズム表現の潜在的可能性を垣間見た気がする。結局、書き手次第で「言語の水準(レベル)が決まる」ということだ。

双玉詰試験図

テーマ:

第6回選手権での出来事だったと思う。1手詰で勝ちという局面で、確かに詰んではいるのだが、その手が「自玉で敵玉に直接王手を掛けた反則手で負け」という将棋を観戦した時、笑うに笑えないものがあり、選手権終了後、自宅に着くなり速攻で自分のプログラムのテストを念入りにやった記憶がある。稀に玉頭戦になった場合に起き得る話ではあるが、双玉共に自爆判定を行っておけば回避できる問題ではあるものの、そのような大逆転反則負けは悲し過ぎるのでやはりキッチリ試験しておきたいところである。

そういうわけで、正しく解けるようにしておきたい双玉問題についていくつか例を挙げておく。なお、一般的な双玉の詰物を大量に試験されたいならば、(また神吉ネタだが)次の作品集をお奨めする。そして、本の表紙に向かって「ここでも全身ピンクかよ!」と突っ込みを入れてみるのも一興だ[*1]


カンキの双玉詰将棋傑作選〈上巻〉

カンキの双玉詰将棋傑作選〈下巻〉


さて通常は、次の詰物が実用時間で正しく解ければ、ほぼ問題なしと言えそうである。

左図は、将棋世界付録「神吉宏充双玉詰将棋集」の39番、また右図は、そのVol.4の47番から引用。どちらも「選手権の実戦で現れたならサクっと詰ましたい難易度」だ。


また、以前、解けない詰将棋 でも採り上げたような、実戦では殆ど現れそうもない局面ではあるものの、出来れば作意通りに解きたい、ちょっと落とし穴のある図を2問ほど挙げておく。

左図は、出典不明だが、攻め方玉に王手が掛かっている状態から連続逆王手で詰ます問題。また右図は、おもちゃ箱「加藤徹 全作品」3手詰 No.11aから引用した詰物で、計算機将棋プログラマ泣かせの作品だ。作意通りに解けるならば、相当の工数を掛けてプログラムを作っていると窺い知ることが出来る。因みに現謎電では、右図を詰ますことは出来ても作意通りには解けない。


以上の4局は、何かしら解図アルゴリズムに改造を掛けた時、必ず試験する問題集に含ませて頂いている。


[*1] 無論、私はここぞとばかり間髪を入れずそうした。

神吉宏充六段

テーマ:

計算機将棋関係者が、今最も注目しているプロ棋士は竜王でもなければ名人でもない、ズバリ神吉六段ではないだろうか[*1]。それは単に、瀬川アマのプロ入り試験対局2局目の相手だからという意味ではない。とはいえ、本日その対局があることを考えれば、最先端計数将棋学で採り上げる機会としては、これ以上はないと思えるので、「計算機将棋開発者の好敵手」としてアーティクルを起こしてみることにする。


私が最初に神吉を見たのは先崎とセットで10年以上前の話だ。言うまでもなく「先崎・神吉の将棋パトロール」なのだが、当初、神吉も先崎もプロ棋士だとは全く思わなかった。特に神吉の方は、そのド派手な衣装から、どう見ても関西芸人以外の何者にも見えなかった。その後、先崎をNHK杯で見た時に初めて、神吉もプロ棋士である事が判った時には非常に驚いたものである。


さて、(何年後になるかは判らないが)計算機将棋史上、初めて平手で公式にプロに勝った相手として、その歴史に未来永劫名を残すカモシレナイ棋士、という意味からも、瀬川アマとの対局は、関係者にとって相当興味深い一局だと思われる(確信はない)。瀬川アマの普段の実力が発揮できれば良い勝負になると思われるが、あくまで普段通りに指せればの話であって、「あの派手な衣装に平常心を保てるか否かが勝負を決めるのではないか」と勝手に分析している。棋士という職業を完全にナメているかのように見えてしまうあの衣装こそが神吉のアイデンティティであり、そこにトンでもない落とし穴が潜んでいるように感じるからだ。


ここで、BIGLOBEストリームの2局目予告編とインタビューを見て私なりに感じたことを書く。


まず、神吉の穴熊宣言。「穴熊以外の何があるの?」と、ブラウザに向かって思わず突っ込みを入れてしまいました。衣装宣言についても同様。毎度のことなので、知っている人間にとっては全く驚きようがない。

次に内藤関西本部長の言。「自分の弟子は誉めにくい」と仰っているが、内藤先生、おもいきし誉めてるじゃないですか。「プロのトップクラスが嫌がる、互角なんですね」って、NHK杯1999年9月5日放送の森内戦のこと言ってますね。その対局の感想戦の時、そこでも「神吉くん、強いなあ」って全国放送で誉めてたじゃないですか、心の底から、自分の弟子を。神吉にとっては言葉通りに聞こえたかもしれない。しかしながら、ソバにいた森内にはどう聞こえたであろうか。その翌日、森内が放心状態で将棋会館に現れた[*2]と伝え聞いている。


森内をそこまで凹ませる神吉穴熊が、果たして計算機将棋に通用するものなのか見てみたいと思うのは私だけだろうか。その時には、是非とも、実況:古館伊知郎、解説:内藤國雄、でお願いしたいところである。


[*1] と思ってるのは私だけかもしれないが(笑) 平成8年度の将棋年鑑でのアンケート回答の真意は、言葉通りではなく「私が最初に平手で相手してあげますよ」と受け取ることができるのではないだろうか。

[*2] 神吉談だが、オリジナルソースは不明。

Marcの3つの論文のうち、一番最初の 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万倍速い毎秒2億局面の速度を達成しました。
私たちは、チェスプログラムMBChessを改善するためのFPGA指手生成器の設計について記述します。指手生成器はゲーム中の探索の要です。BelleやDeepBlueの指手生成器の重要な詳細については第3章の中で示します。私たちのFPGA指手生成器の記述は第4章へ続きます。指手生成の鍵となるハードウエアアービタの設計によって、FPGAアーキテクチャがどのような影響を及ぼすかが判るでしょう。更に、柔軟なチップ内のRAM資源が、指手をマスクするための斬新な回路実装を可能にします。また、FPGAの実装結果は第5章で示します。
ASICの伝統的に大きな工数を不要にし、且つ開発コストを数分の1にすることを成功させ、FPGAチェス探索加速装置として使用できることを示します。再プログラムの容易さとチップ内のRAMがFPGAを成り立たせ、チェスアプリのための理想的なターゲットになります。


2. 指手生成器
チェスプログラムの中で使用される基本的なメカニズムは、最善手を求めるための深さ優先αβ探索です。この探索アルゴリズムで良い手の順に読むことは、探索量削減とより速い探索になることで報いられます。強いチェスマシンは、必ずと言ってよいほど最良から最悪の順に指手を生成しています。チェスの良い手の順位の例は次の通りです(最良が最初):
A1:王手、直接および発見された手
A2:もしあれば、成る手
A3:最も価値のある敵駒を、最も価値がない自駒で取る手で並び替えた順
A4:駒を取らない手
αβアルゴリズムの注目すべき振る舞いはβ枝刈です。β枝刈が生じる場合、現在のノードからすぐに引き返し、残っている枝を調べる必要はありません。効率的な探索のために、指手生成器は全体的に固定された指手順を決め、更に一回に一つの着手を生成することが出来なければなりません。これは、探索が戻ってきた時、未だ調べていない次の手を探索することが出来るように、既に生成した手をノードが忘れてはならないということです。


3. 以前の設計
3.1. Belle
Belleでは、チェス盤はロジックブロックを組み合わせた8x8個の配列です。Belleの主なハードウエア構造は、チェスの桝間の通信です。各桝は、発信器、受信器および駒レジスタを持ち、現在の駒を表します。駒が置かれた桝は、ナイトの飛び越える利きを除いて、8つの隣接する桝に送信します。空桝は、駒の進む方向に沿って利きを伝えます。
チェスでは、移動元の駒は適切な送信線をアクティブにし、移動先の桝では入ってきた利きを受け取って(言わば立候補し)、アービトレイションを申し込みます。2つの主な通信ブロックは送信器と受信器です。各桝は各々1つ持っています。
チェスの指手は、移動元桝から移動先桝への(駒の)移動です。指手を構築するために、2つのサイクルが実行されます。最初の敵駒発見(find-victim)サイクルは移動先の桝を見つけます。次に自駒発見(find-aggressor)サイクルは移動元の駒を見つけます。敵駒発見(find-victim)過程中、動かせる自駒はすべてそれらの発信器をアクティブにします。対する敵駒および空桝の全ては、アービトレイション網へそれらの受信器の出力を送ります。2レベルの優先木はクイーンから空桝(キングは取ることができません)までに命じられ、取る敵駒(あるいは移動先の桝)を選択します。アービトレイションの第1レベルは4x4桝のブロック上で終っています。第2レベルは、これらのサブグループのうちの1つを選択します。一旦最も価値のある敵駒(MVV)が選択されていれば、自駒発見(find-aggressor)サイクルが実行されます。ここで、最初のサイクルで見つかった桝は全ての駒種の利きの結合を送信し、ポーンからキングまで命じられ、動ける駒の受信器が最も価値の低い自駒(LVA)を選ぶためにアービトレイションを行います。このようにしてMVV/LVA順で指手を生成しています。Belleの指手をマスクする能力は、64ビット(各桝1ビット)が、ある指定された桝へ動き終わった自駒をマスクするか、あるいは完全に探索された移動先をマスクするためにあります(桝は移動先(victim)か移動元(aggressor)のいずれかです)。深さ優先探索のために、64レベルのスタックが、これらのマスクビット記憶用に使われます。指手マスクがあることで、Belleは第2章のA3(駒を取る手)およびA4(駒を取らない手)の生成を行えます。


3.2. DeepBlue
Belleの受信器・発信器構造は、DeepBlueの指手生成器の出発点でした。DeepBlueでは、第1レベルのアービトレイションは桝の段(rows)の上で終っています。また、第2レベルは段(rows)の間を選択します。一旦桝がビットマスクにより無効になれば、以降(アービトレイションに)参加しません。また、同じ優先度を持った他の桝は選ばれるために申し込みを続けます。あらゆる指手が生成されるまでこの処理は継続します。
移動先と移動元をマスクする過程は、DeepBlueアーキテクチャでは完全に異っています。64レベル64ビットのスタックを使用する代わりに、マスクビットはそのノードで以前に生成された指手から算出されます。このマスキング法は、ロジックとデコーダを犠牲にしてメモリを必要としません。DeepBlueのVLSI設計では、このアプローチは有利でした。DeepBlueのアービトレイションと桝マスクをFPGA用に専用設計し、第4章の3および第4章の4の中で示します。
DeepBlueの指手生成器の最初の大改造は、王手の指手を最優先で生成する問題の解決から始まりました。指手生成順で、王手を高い優先度にすることは非常に重要で、MBChessの初期バージョンで気づきました。この特徴を実装するために、2個の発信器が入力数の倍を備えた受信機と同様に使用されます。王手発見(find-check)過程中、手番側の移動すべき駒は、それらの敵駒発見(find-victim)発信器をアクティブにします。また敵キングは、その自駒発見(find-aggressor)発信器をアクティブに(全駒種で結線)します。適切に(敵キングを)攻撃する桝は、王手することができる桝(と駒種)を示すでしょう。この論文では、これらを軸(pivot)桝と呼び、そのサイクルは軸桝発見(find-pivot)サイクルと呼ぶことにします。軸桝が超駒(super-piece)[*2]として放射し、王手を生成するのに必要な第2のサイクルは、通常の自駒発見(find-aggressor)サイクルです[*3]


4. FPGA指手生成器
この章は、FPGAの重要なチェス指手アーキテクチャを含めた指手生成器を提案します。隣接する桝間の通信の基本は変わりませんが、駒の情報を伝える方法が異なります。


4.1 チェス盤表現
チェス盤は桝回路8x8個の配列として表現されます。チェス桝のブロックダイヤグラムは図1で示されます。発信器(TX)および受信器(RX)の中のL形の矢印は、2ビット(×8方向)のナイト用バスです。直線状の矢印は5ビット(×8方向)の隣接する桝とのバスです。各桝は、図の左上で示された信号を受け取ります。(図の中の)破線は、発信器と受信器の多くの関係のうちの2つを示します。更に32個の第1レベルアービタのうちの1つと16個の第2レベルアービタのうちの1つが見えます。6ビットの深さレジスタは、5ビットの書き込みバスを用いて更新され、駒を移動させることに使います。
全体的な情報は、駒利き伝搬の出力を除いて、すべての桝へ配線させます。これらの信号網によって要求されるファンアウト[*4]は、64個のチェス桝があることで信じ難いほど大きくなります。FPGA実装では、桝への値の送り込み(loading)および遅延を減らすために8つの桝をグループ化し、駆動するためにバッファ[*5]を付けます。バッファが論理合成によって削除されるのを防ぐために適切な制約を設けなければなりません。影響を受ける信号は指手データ、5ビットの書き込みバスとマスクおよび状態の情報です。
DeepBlueでは、マスクおよびアービトレイションバスも、駒レジスタ読み書きバスとして使用されます。この設計では、書き込みバスは異なる桝に駒値を書くために使用されます。書くべき駒値はすべての桝へ送られます。しかし、2つの桝選択線によって選択された桝だけが、その駒レジスタに駒値を書き込めます。また別の選択した桝(移動元)の駒レジスタをクリアするために使用されます。キャスリングを行う、あるいはアンパサンでポーンを取る手も、通常の指手生成と同じサイクルで行われます。指手生成器の重要な特徴は、移動しない駒の桝は駒レジスタを読む必要がないということです。このことは、必要となる配線量を減らし、設計の動作速度を上げます。


4.2. チェスの桝 - 曖昧な王手の解決
桝の発信器出力は図1で示されます。通常の指手生成中、これらの信号線は、以前に議論された敵駒発見(find-victim)および自駒発見(find-aggressor)の振る舞いに従います。
DeepBlueの中に潜在的な制限があることに気づきました。DeepBlueの設計で使用される発信器では、対角方向でヒットした時、軸桝はクイーンとビショップを区別することができません。軸桝に到着するクイーンは水平あるいは垂直にあるキングに王手するかもしれません。しかし、ビショップであれば王手になりません。そのような王手を考慮する場合、私たちの内部結線策は解決可能性を充分に実現します。軸桝発見(find-pivot)サイクル中、桝はどの種類の駒を移動させれば王手を正しく生成できるか判っています。
送信線は、付加的な意味を持っています。すべての駒種の利きの結合は、更に自駒発見(find-aggressor)サイクル中に送信されることができます。この目的(正しく王手を掛けること)を達成するために、6ビットの拡張駒ワードが、4ビットの駒レジスタからデコードされます。ビットフィールドは表1の中で示されます。例えば、111000は白クイーンを表わします。また、011111は、(全ての利きを)結合した駒を放射する桝を表わします。ナイトビットおよび色(敵・味方)判別ビットがナイトの到達可能な桝へ送られている一方、上位5ビットは8つの隣接する桝へ送られます。その結果、チェス桝回路は2個の発信器および二重入力の受信器を必要としません。それでも、内部結線の合計はDeepBlueと同じです。通常の敵駒発見(find-victim)および自駒発見(find-aggressor)サイクル中に、敵味方を判別することは不要です。しかしながら軸桝発見(find-pivot)サイクル中は、敵・味方を正しく判断することで王手を示すでしょう。この表現は、より一定の内部結線パタンにし情報分配の効率を最大にします。王手発見演算は、自駒発見(find-aggressor)サイクルが後に続く軸桝発見(find-pivot)サイクルになります。王手の指手は、それを命じるMVV/LVAによる指手順に従わず、暗黙のうちに指手生成器によって(優先的に)生成されている点がミソです。初めてノード(の探索に)に入る時、王手を見つけるループ(処理)が実行されるでしょう。マスクビットは、規則的ではないやり方(軸桝が使い尽くされた時に終了するように、それがマークされる)で生成された指手からマスクするでしょう。通常の指手生成ループに入る時にマスクビットがリセットされ、王手でない場合、古い軸桝は生成されないでしょう。この解決策は、2つの過程の間マスクビットをリセットし、それらが通常の過程中に生成される時、王手の指手は無視することです。


4.3. アービトレイションの2分木
ルックアップテーブル(LUT)を基にしたFPGAは、この設計中で多くの物理的な制約を課されたまま使用されます。DeepBlueの受信器の出力には大量の配線がありましたが、(本設計では)6つの優先レベル判断用の6*64の網が不要であることを表します。ASIC設計では、もしデコードや演算に必要となる論理ゲート数を更に減らせるならば、格子状に構成される大量の配線は有利になりえます。しかしながらFPGAでは、論理ファンクションは違った風に作用します。5入力のXORゲートは任意の5つの入力機能(2つのLUT)と同じエリアを占有します。受信器出力は、3ビットの値(比較するためにアービタが使用する)の中でエンコードされます。1つのアービタは2つの桝(のどちらか)を選択することができます。最終結果は、6レベルの2分木構造を通って出力されます。各アービタは、決定し選んだ桝の座標を切り替えて出力する6つのLUTのために、4つのLUT(任意の6入力)を使用します。この設計は、筋・段(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ビット幅)の同期式または非同期式メモリを実装することができます。2つのLUTを組み合わせて、32x1、16x2あるいは16x1のデュアルポートメモリを作ることもできます。小さな多数の局所的なデータを保持する必要がある場合、この種類のメモリは有用です。BlockRAMはチップ全体に渡って用いる必要のない大量のデータを格納するために使用されます。
元々Belleの指手マスキング法は、このアーキテクチャで実装されています。各桝1ビットおよび64手分の深さの同期式メモリ(2つのRAM32x1Sを使用)は、マスクビット記憶用に使用されます。駒値を書くために使用されるバッファを介した信号線も、各桝の深さレジスタを更新するために併用されます。この設計ではフリップフロップを殆ど使わないので、各桝は配線を減らすために6ビットの深さレジスタを持っています。メモリベースのマスクビットスタックを使うことによって、DeepBlueでは指手をマスクするデコーダの意味を持っていた全てのロジックは不要です。
BlockRAMは、専用に用意された配線があっても、この場合マスクビットを格納するメモリとして最良の解決にはなりません。このメモリとの(データの)行き来によって4~8nsに及ぶ遅延が回路内で観察されました。局所的なメモリを使えば、前述した遅延は事実上除くことができます。しかしながらBlockRAMは、探索木中の各深さで生成された指手を格納する(メモリとして)理想的な候補です。2つのメモリが32ビットの指手を格納するために必要です。チェス盤を制御するステートマシンは、チップの(BlockRAMに接近している)傍近くに置かれます。これは、設計の中で適切なRAM資源の種類を選ぶことが重要だということです。


4.5. 例外手
チェスの例外的な指手にどのように対処するのか、チェスハードウエア探索の論文中滅多に言及されません。5ビットの全方向出力は、ポーンとキングが2つの桝の距離を伝搬することを可能にします。第4・第5段が2桝分ポーンが進めることができるように、第3・第6段の桝はポーンビットを広めます。更に、目的(移動先)桝をキャスリングする手を示せるように、桝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と比べ)処理速度を欠いていても、チェスの棋理と最適化されたプログラミングで武装しています。私たちは、そのコストの僅か数分の1で同様のことを行うために、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++だが中身はCである。何故そんなことをやったのかといえば、多数の部品間配線について人間がVHDLコードを手で書くと、手間がかかる上に間違いが極めて多くなるからで、それを回避したかったのだと思われる。

[*7] と、取りあえず日本語(になってない気がする言語)に訳したが、一度原文の方も読まれることを強くお奨めする。どのようなことが書いてあるのか大筋を知った上で原文を読まれた方が、より正確に理解し易いと思われる。

今週(というか正確には先週ですね)は、夏休みだったので日刊ペースで書いてみたわけですよ。しかも以前のノリで。そしたら、FPGA・ハード探索ネタやってた頃の3倍ですよ、訪問者数が(笑)

最先端計数将棋学的に、最先端の、というより更にそれを突き抜けたネタやってて訪問者様が減った時は、やっぱそうだろうなあ、という感じではあったんですが、それよりごく一般的な話の方がウケは良いんですね。


しかし、ここであきらめちゃダメ。くじけちゃダメ。有史以来、どれだけの数の若者が指将棋のハード探索に挑戦しては破れ去っていったか定かではない、ていうより、誰もいないじゃん?挑戦したのが(てか私は若者じゃないんですけど、激指の鶴岡さんくらいに若く見えるよね、ね、ね)。

そういうわけで、Marcの論文の一番最初の量の少ないヤツを、今翻訳していて、ごく近い将来公開しようと思ってるんですよ。


論文自体は高々4頁に過ぎないのだけども、これがまた非常に日本語に訳しにくい。専門用語もそうだが勝手な造語(恐らくHsuの論文からの引用あるいは継承)もあって、意味は判っても「こんなん、どう訳せっての?」みたいな単語もあるし、スペリングの間違いではなく、どう読んでも記述自体に誤りがあるんじゃないの?と思う部分もあって困難を極めてます。なるべく原文に沿ってリライトはしますが。


夏休みの最後はこれを仕上げて、また週刊ペースに戻ると思います。謎電のオープン戦参加も微妙に難しくなってきました。