コンピューター将棋の構造 - 検索エンジン 「浅読みくん」 ⑦

今回のトピックは「並列化」です... これには2通りありますね。

①マルチコアのCPUを使用し検索作業を分担する。我のラップトップはインテルのCore2Duoなので2コアあります。「理論上」はこれで検索時間が半分になるはずですがそうは行きません。

②複数のマシンを使用し検索作業を分担する。

現在はマルチコアのマシンが主流と成りつつあるので②は

 「複数のマルチコアのCPUマシンを使用し検索作業を分担する」が現実ですね。

マルチコアのCPUを使用し検索作業を分担する

2コアは「2倍の計算能力」が有りますが「2倍の処理能力」は現実には無理です。各コアがマシンのリソース(メモリー等)を共有しているため片方がメモリーをアクセスしている時は待たなければならない等の無駄が生じます。現実には40%演算時間を軽減できれば万歳です。

複数のマシンを使用し検索作業を分担する

マシンを買う資金を調達する方が技術的問題よりもハードルが高いです。

上記のマルチコアの場合は各コアの検索結果を簡単に共有できますが、独立マシンの場合には情報の共有化・同期化、負荷の分担、等の問題を解決しないといけません。これも40%演算時間を軽減できれば万歳です(と思う)。

ここまできたら「全部入り」浅読み君で検証するのみです。

 「全部入り」 = ミニマックス・アルファ・ベータ・記憶装置付き...ですね。

1コア使用

5手読み TIME: 0.733000 sec. RATE: 880904.502046 nodes/sec
6手読み TIME: 2.683000 sec. RATE: 1425467.014536 nodes/sec
7手読み TIME: 9.703000 sec. RATE: 1858920.230856 nodes/sec
8手読み TIME: 42.947000 sec. RATE: 1845649.963909 nodes/sec
9手読み TIME: 225.046000 sec. RATE: 1927935.066609 nodes/sec

2コア使用

5手読み TIME: 0.562000 sec. RATE: 1148790.035587 nodes/sec
6手読み TIME: 1.810000 sec. RATE: 2113126.519337 nodes/sec
7手読み TIME: 6.256000 sec. RATE: 2905542.838875 nodes/sec
8手読み TIME: 24.710000 sec. RATE: 3215555.847835 nodes/sec
9手読み TIME: 147.966000 sec. RATE: 3240505.568847 nodes/sec

比較してみると...

7手読み 6.256000 / 9.703000 = 0.644749
8手読み 24.710000 / 42.947000 = 0.575360
9手読み 147.966000 / 225.046000 = 0.580154

...約4割の検索時間短縮に成功しました。4コアマシンなら更に短縮が可能でしょう。実際にコンピュータ将棋選手権の上位ソフトはハイスペックのマシンばかりです。

http://www.computer-shogi.org/wcsc19/team.html

...でも検索高速化はまだまだ奥がふか~いのですよ。我がまだ試していないテクはまだまだあります。それは後程に...ですね。

(続)

投稿者: 紫外線 投稿日時: 土, 08/15/2009 - 10:26 categories [ ]

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。

調理時間

棋譜データを分解して検索用に一次処理するのに(今のところ)一局辺り約0.25秒かかります。

28万局を処理すると

0.25 x 28,000,000 = 70,000秒 = 1,1666.666分 = 19.4444時間

...定跡ライブラリを作るのも楽じゃないですね。

ちょいとコードを改良して、データベースを別のものに換えて実験してみます。

棋譜倉庫

かなりの数でエラーが出るので調べてみたら「駒落ち」棋譜でした...ナルホド。

現在トータル28万余局...

絞込み

おっ!鋭きコメントに座布団2枚進呈です。

定跡ライブラリは定跡をなぞる事に使用するのはもちろんですが、

浅読み君高速化計画の次なるステップ、「Principal Variations」(主要変化...現在勉強中の科目です)の材料にもなります。

>無名・浅読みくん

無明で~す。

棋譜データですが...240,375局あり、3局の棋譜データがみょうちくりんなので(直すのは面倒)それは無視することにしました。

定跡

>この後データを「調理」したら使える定跡ライブラリになると...願っているところです。

この定跡データを、「無名・浅読みくん」の検索高速化・指し手の絞込みに活用することはできないんでしょうかね・・・。

定跡読み込み

「最強の棋譜データベース」に収集してある24万余局の読み込みに成功しました...

読み込みそのものは数分で終わりますが、フォーマット(棋泉)を理解して我用のデータに変換するプログラムを書くのは面倒~~です。

この後データを「調理」したら使える定跡ライブラリになると...願っているところです。

次は「将棋の棋譜貼り専門スレッド倉庫」からの読み込みとなります...

価値判断

過分な評価、ありがとうございます。

現在の所、価値判断は超原始的に出来ています。各駒に以下の点数を振り分けて

 歩 10
 香・桂 30
 銀 50
 金・成金 60
 飛 100
 角 80
 玉 500
 竜 110
 馬 90

 評価値 = (自分の総駒点) - (敵の総駒点)

...たったこれだけです。これだけで詰みに収束する自体ちょとした驚きです。

プログラムはとにかく3手内で見つけられる最大評価値の手筋を選びます。従ってあまりにお間抜けな駒得ばかりを追求しがちです。

プログラムに「詰み」の概念は仕込まれていません。評価値の最大化を追求した結果、最大駒点の玉を取ろうとする行動が結果として「詰み」になります。

無明くんの対局。

観ましたよ~ 実に素晴らしい! スピード感のある対局です。

雑感を述べるとすれば、飛び道具の着手がとても多いですね。金、銀がほとんど着手されていない。これって、無明くんが強い駒を動かしたがる、ということなのでしょうか? 価値判断がどうなっているのかが興味深いです。 チェスの弱いレベルだと、NとBばかり動かしてRをほとんど遣ってきません。少し強くなるとPの連携や手損をしなくなった印象です。 たぶんこのようなこともプログラムされているのでしょうね。

擬似マルチマシン

現時点ではマルチマシンを使役できる状態では無いため(マシン無し、プログラム無し)擬似的にマルチマシンでのシナリオを検証してみます。

((方法))検索を2台で分担すると言うことは初手から検索した場合(初手は30手ある)、15手のみを検索する...事で実験です。実際にはマシン間での通信等が有りますが今回は無視します。3台で分担するなら一台あたり10手担当です。

ベンチマークです...

1マシン2コア使用

5手読み TIME: 0.483000 sec. RATE: 1336122.153209 nodes/sec
6手読み TIME: 1.498000 sec. RATE: 2552488.651535 nodes/sec
7手読み TIME: 5.210000 sec. RATE: 3496885.796545 nodes/sec
8手読み TIME: 20.561000 sec. RATE: 3861992.412820 nodes/sec
9手読み TIME: 125.954000 sec. RATE: 3808498.991695 nodes/sec
(注)前回のベンチマークより少々速くなりました。ハッシュの使い方が改善しましたのです。

1マシン2コア使用 - 初手15手から検索

5手読み TIME: 0.499000 sec. RATE: 720705.410822 nodes/sec
6手読み TIME: 1.029000 sec. RATE: 1910692.905734 nodes/sec
7手読み TIME: 3.822000 sec. RATE: 3016193.615908 nodes/sec
8手読み TIME: 15.023000 sec. RATE: 3333467.216934 nodes/sec
9手読み TIME: 93.272000 sec. RATE: 3563496.537010 nodes/sec

1マシン2コア使用 - 初手10手から検索

5手読み TIME: 0.484000 sec. RATE: 529270.661157 nodes/sec
6手読み TIME: 0.967000 sec. RATE: 1529441.571872 nodes/sec
7手読み TIME: 3.541000 sec. RATE: 2547128.212369 nodes/sec
8手読み TIME: 11.903000 sec. RATE: 3419904.897925 nodes/sec
9手読み TIME: 79.575000 sec. RATE: 3485865.699026 nodes/sec

...一応の効果は出ていますが三分の一はむりですね。

仮に(我が湯水のように資金を使えて)30台!!並列で動かしても現在のシステムでは「9手読み」を「8手読み」x30に置き換えるだけなので約20秒が限界となります。

検索時間短縮率が思った程伸びなかったのは局面量の減少により(皮肉にも)浅読み君の「記憶装置」があまりその効果を発揮出来なかったことにあります。局面量の減少により「前回に遭遇した局面からの検索を打ち切る」回数が減少したのが原因です。

...しかし!これはマシン間の検索結果の共有・統合により改善可能(かもしれない...かな?)

インテルの「i7」CPUは4コア内臓、各コアが「2コア」に相当する機能があるので(Hyper Threading)、都合8コアCPUとなります。ほちいです。

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。