2017年6月
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  

tweet

  • tweets

トップページ | 評価ボード調達進捗状況 »

将棋プロセサ 「A級リーグ指し手1号」開発中

ルート局面から全てハードで探索を行い、終わると指し手を返す、という完全独立型将棋プロセサ、「A級リーグ指し手1号」をFPGAで開発してます。他に類例を聞いたことがないので、たぶん世界初じゃないかな、と思っています。

[ハード概要と性能]

まず、どのFPGAを使うか、ですが、まあverilogで書いているので、どれでもいいと言えばどれでもいいです。今お試しで合成やP&Rを試しているのは Xilinx Virtex5 です。合成結果で 37MHz でした。P&Rで少し落ちるかもしれませんが、30MHzは越えると思います。局面を進めるのと戻すのにそれぞれ1クロックかかるので、30MHzなら15M局面/秒になります。

Virtex 5 の XC5VLX85 に1プロセサが収まります。XC5VLX330 を使えば4プロセサは入るでしょう。仮に4チップつなげて並列に動かすソフトを書けば、Deep Blue の2億局面/秒は越えられそうです。

[プロジェクト状況]

今はverilogでのコーディングを終え、Simulationが動いている段階。 上記のとおり、お試しレベルでは合成とP&Rは実施済。 実チップへの焼き込みはこれからです。評価ボードを用意したり、ホストI/Fのソフトを作ったり、と作業が多いので、来年5月の選手権参加を目標にしてはいますが、果たして間に合うか…というところ。

[動作サンプル波形]

Simulation の波形のサンプルを以下に示します。こんな感じか、というのがわかっていただけると幸いです。

Aleagwavesmall_2

ソフト屋の方は見慣れないかもしれませんが、ハードのデバッグは通常このような「波形ビューア」で行います。

forward/rewind が、局面を進める/戻す、です。動作中は必ず毎クロックfwdかrwdのどちらかが出るようになってます。この図はちょうど探索が終わったところで、カーソルの線で終わってます。

この例は「コンピュータ将棋の進歩2」の問題集37番を解かせた例で、終了時bestMvが"20552"(5二角打、正解)を返しています。今はPCでソフト的にsimulationしているので、速度は数サイクル/秒と遅く、深い探索はできません。今は全幅1手、静止6手の設定で動かしています。問題37はこの深さでも正解が出るため使用しています。

探索が終わるとstoppedがつきます。stoppedは外部へ出力され、ホストPCに伝えます。ホストはこれを見るとcmdReadをプロセサへ送ります。するとプロセサは指し手とあと若干の情報を数サイクルかけてcmdReadDataに載せてホストに伝える、という動きになります。

なお最初の起動の時は、ホストがcmdWriteを立てた後、数サイクルかけてルート局面、α、β、depth を cmdWriteData で送ります。プロセサ側では、cmdWrite でステートマシンを起動し、受け取ったデータを然るべきflip flopに設定した後、stoppedを落として自分で起動して探索を開始します。α、β、depth も送るのは、並列化を視野に入れてのことです。

実マシンでホストへ接続する際は、クロックの違いによる同期化の問題等あるので、これよりもう少し複雑になりそうです。ただ、基本的な動きは変わらない予定です。

[今後の予定]

・まずは、何はともあれ「早く焼きたい!」。そのためには評価ボードや、 I/F ソフトを…

・今はまだ簡単な例しかやってませんので、regressionの環境を作ったり、 もう少し深い探索をやらせてみたり、もしないと。

・今までは「まず最初は、簡単でいいからとにかく動くものを」というスタンス でやってきたので、チューニングはぜんぜんできていません。たぶん37MHzより はかなり高速化できるだろう、とは思っているので、これもやりたいところ。

・ちょい(かなり?)先ですが、並列化も…

・フリーハードウェアとして FPGA netlist (NGC等)を公開しようかともくろんで ます。ただ、これはこれで、いろいろと環境整備をしないといけないので、 なかなか手がまわらないのですが。誰でも勝手にNGCダウンロードしてFPGAに 焼ける、ようになると面白いかな、と。

・このHPのメンテ:まめに更新したいのは山々なんですが、なんせ仕事の合間 にやってるのでなかなか時間がとれず…でも何とかできる範囲でやっていこうと 思っております。

[コンピュータ将棋としての動作]

全般に、ソフトなら簡単にできるがハードでは難しいこと、というのがけっこうあります。それを考慮した結果、現状は以下のようになってます。(すぐ変わるかもしれませんが)

・全幅探索です。元々Bonaの成功を見て、「全幅やったらFPGAでできるんちゃうか」 と思ったのが始めたきっかけです。それまでは Deep Purple という、1次予選を 通るか通らないか、くらいのソフトを作っていたのですが、ハードに転向しました。

・深さが一定以下になると静止探索になります。といっても全幅と静止の差はほとんど なく、生成する手が全部か、取り+パスか、が唯一の違いです。詰将棋はありません。

・多重反復深化します。前のループのα更新した手を2つまで覚え、次のループで 最初にトライします。

・ハッシュはありません。反復深化があれば必須ではないかな、と思っています。 ただ、ハッシュコードがないため、今はループ(千日手)のチェックができて いません。もしかしたら将来このためだけにハッシュコード入れるかもしれま せん(あまりやりたくないが…)

・手生成には3種類あります:1)全幅、2)取り+パス、3)王手防ぎ。 それぞれのカテゴリの中では、機械的な順序で生成し、たとえばSEEでソート、 なんてことはしてません。これも、まあ反復深化があるからいいだろ、と自分に 言い訳してます。 ただ、全幅時もまず取りから、くらいはやります。

・評価は、今のところかなりいいかげんです。各マスの両王との相対位置、 個々の利き、を考慮して適当に線形和、という感じ。(評価のチューンって つまんないんですよね^^;)進行度は連続で持ってます。

・基本は普通のαβ探索。NULLMOVE PRUNINGはありません(全幅ではパスしないし)。 が、「ベスト手以外全部PRUNE」をやります。YSSの0.5手延長、みたいな感じ? FUTILITY PRUNINGも今はやってないです。ただ、「静止探索、深さ一定以下で、 手番側がβ以上ならβカット」くらいでお茶濁そうかな、などと考えてます。

トップページ | 評価ボード調達進捗状況 »

将棋プロセサ」カテゴリの記事

コメント

さっそくうちのブログに登場していただきました。ハードは素人ゆえ、変なことを書いておりましたらツッコミをお願いいたします。
世界コンピュータ将棋選手権は近いうちに来年の募集を開始いたします。LAN対応やGUIなどの実装はUSIツールを活用するなどして効率的に行っていただいてもよいと思いますので、是非お会いできることを祈っております。

伊藤さん、復活おめでとうございます。
>・ハッシュはありません。反復深化があれば必須ではないかな、と思っています。

ですが、反復深化だからHashが必要になると思うんです・・・。 それが、手の並び替えの必要性をなくすので。 DepBlueのLSIも残り深さ3手程度の探索のため、Hashがなくてもうまくいきましたが、深さ0からハードで読む場合には、Hashは必要かと思います。

山田さん、ブログ読ませていただきました。あんな大々的に書かれるとなんというか恐縮です。
なお、中終盤はたしかに汎用PCは必要ないんですが、序盤の定跡部はたぶんソフトに頼ることになると思います。

yさん、ハッシュはおっしゃるとおり、「ないよりはあった方がいい」です。ただハードにハッシュ入れて1クロックで動かすのは難しいんですよ。なので入れてないことの言い訳でああいうふうに書いている、とお考えください^^; 

柿木さんの記事では効果数%とか書いてたと記憶してます。私のソフト時代の経験でもそんなものだったはずと思っています。

いずれ並列化することを考えると、ハッシュ表はコヒーレンシの確保も大変そうですね。千日手の問題がなければ、反復深化ではハッシュを省くオーバヘッドは少なそう。ただ、詰将棋のように枝分かれ数が少ない場合はハッシュ表が有効と思われますので、詰将棋の実装にまで発展したらチャレンジかな?

とても興味深いです。
名前が出てきたのでコメントしますが、ハッシュの効果数%というのは、10年以上前のかなり手を絞った、しかも反復深化でない探索でした。
今、全幅の反復深化では、ハッシュの効果は2倍以上あります。
ただ、今回のものは、「前のループのα更新した手を2つまで覚え」ということで、ハッシュと同様の効果を持たせたのだと思います。

10年以上前、かぁ… たしかにそうですね。
2倍以上ってことは、十数%くらいでしょうか。

しかし、柿木さんも全幅トライされたのですか。
大流行なんですね。全幅でどんなサーチがよいの
か、そのうち方向見えてこないかなあ。

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/507007/9302635

この記事へのトラックバック一覧です: 将棋プロセサ 「A級リーグ指し手1号」開発中:

» コンピュータ将棋専用機がやってくる [コンピュータ将棋協会blog]
現存するコンピュータ将棋のほとんどは、パソコンソフトとして開発されています。しかし将棋もほかのアプリケーションと同様、汎用コンピュータ用のソフトとして作るよりも、将棋専... [続きを読む]

トップページ | 評価ボード調達進捗状況 »