倶楽部入口倶楽部活動検索投票累計訪問者数
一年目 約９万３千 |
コンピューター将棋の構造 － 検索エンジン 「浅読みくん」 ⑦今回のトピックは「並列化」です... これには２通りありますね。 ①マルチコアのCPUを使用し検索作業を分担する。我のラップトップはインテルのCore2Duoなので２コアあります。「理論上」はこれで検索時間が半分になるはずですがそうは行きません。 ②複数のマシンを使用し検索作業を分担する。 現在はマルチコアのマシンが主流と成りつつあるので②は 「複数のマルチコアのCPUマシンを使用し検索作業を分担する」が現実ですね。 マルチコアのCPUを使用し検索作業を分担する ２コアは「２倍の計算能力」が有りますが「２倍の処理能力」は現実には無理です。各コアがマシンのリソース（メモリー等）を共有しているため片方がメモリーをアクセスしている時は待たなければならない等の無駄が生じます。現実には４０％演算時間を軽減できれば万歳です。 複数のマシンを使用し検索作業を分担する マシンを買う資金を調達する方が技術的問題よりもハードルが高いです。 上記のマルチコアの場合は各コアの検索結果を簡単に共有できますが、独立マシンの場合には情報の共有化・同期化、負荷の分担、等の問題を解決しないといけません。これも４０％演算時間を軽減できれば万歳です（と思う）。 ここまできたら「全部入り」浅読み君で検証するのみです。 「全部入り」 ＝ ミニマックス・アルファ・ベータ・記憶装置付き...ですね。 １コア使用 ５手読み TIME: 0.733000 sec. RATE: 880904.502046 nodes/sec ２コア使用 ５手読み TIME: 0.562000 sec. RATE: 1148790.035587 nodes/sec 比較してみると... ７手読み 6.256000 / 9.703000 ＝ 0.644749 ...約４割の検索時間短縮に成功しました。４コアマシンなら更に短縮が可能でしょう。実際にコンピュータ将棋選手権の上位ソフトはハイスペックのマシンばかりです。 http://www.computer-shogi.org/wcsc19/team.html ...でも検索高速化はまだまだ奥がふか～いのですよ。我がまだ試していないテクはまだまだあります。それは後程に...ですね。 （続）
投稿者： 紫外線 投稿日時： 土, 08/15/2009 - 10:26 categories [ ]
|
ＩＤ取得（無料）してログインすると広告は不表示掲示板更新状況ＩＤ取得（無料）してログインすると広告は不表示最近のコメント
|
調理時間
棋譜データを分解して検索用に一次処理するのに（今のところ）一局辺り約０．２５秒かかります。
２８万局を処理すると
０．２５ ｘ ２８，０００，０００ ＝ ７０，０００秒 ＝ １，１６６６．６６６分 ＝ １９．４４４４時間
...定跡ライブラリを作るのも楽じゃないですね。
ちょいとコードを改良して、データベースを別のものに換えて実験してみます。
棋譜倉庫
かなりの数でエラーが出るので調べてみたら「駒落ち」棋譜でした...ナルホド。
現在トータル２８万余局...
絞込み
おっ！鋭きコメントに座布団２枚進呈です。
定跡ライブラリは定跡をなぞる事に使用するのはもちろんですが、
浅読み君高速化計画の次なるステップ、「Principal Variations」（主要変化...現在勉強中の科目です）の材料にもなります。
＞無名・浅読みくん
無明で～す。
棋譜データですが...240,375局あり、３局の棋譜データがみょうちくりんなので（直すのは面倒）それは無視することにしました。
定跡
>この後データを「調理」したら使える定跡ライブラリになると...願っているところです。
この定跡データを、「無名・浅読みくん」の検索高速化・指し手の絞込みに活用することはできないんでしょうかね・・・。
定跡読み込み
「最強の棋譜データベース」に収集してある２４万余局の読み込みに成功しました...
読み込みそのものは数分で終わりますが、フォーマット（棋泉）を理解して我用のデータに変換するプログラムを書くのは面倒～～です。
この後データを「調理」したら使える定跡ライブラリになると...願っているところです。
次は「将棋の棋譜貼り専門スレッド倉庫」からの読み込みとなります...
価値判断
過分な評価、ありがとうございます。
現在の所、価値判断は超原始的に出来ています。各駒に以下の点数を振り分けて
歩 １０
香・桂 ３０
銀 ５０
金・成金 ６０
飛 １００
角 ８０
玉 ５００
竜 １１０
馬 ９０
評価値 ＝ （自分の総駒点） － （敵の総駒点）
...たったこれだけです。これだけで詰みに収束する自体ちょとした驚きです。
プログラムはとにかく３手内で見つけられる最大評価値の手筋を選びます。従ってあまりにお間抜けな駒得ばかりを追求しがちです。
プログラムに「詰み」の概念は仕込まれていません。評価値の最大化を追求した結果、最大駒点の玉を取ろうとする行動が結果として「詰み」になります。
無明くんの対局。
観ましたよ～ 実に素晴らしい！ スピード感のある対局です。
雑感を述べるとすれば、飛び道具の着手がとても多いですね。金、銀がほとんど着手されていない。これって、無明くんが強い駒を動かしたがる、ということなのでしょうか？ 価値判断がどうなっているのかが興味深いです。 チェスの弱いレベルだと、NとBばかり動かしてRをほとんど遣ってきません。少し強くなるとPの連携や手損をしなくなった印象です。 たぶんこのようなこともプログラムされているのでしょうね。
擬似マルチマシン
現時点ではマルチマシンを使役できる状態では無いため（マシン無し、プログラム無し）擬似的にマルチマシンでのシナリオを検証してみます。
（（方法））検索を２台で分担すると言うことは初手から検索した場合（初手は３０手ある）、１５手のみを検索する...事で実験です。実際にはマシン間での通信等が有りますが今回は無視します。３台で分担するなら一台あたり１０手担当です。
ベンチマークです...
１マシン２コア使用
５手読み TIME: 0.483000 sec. RATE: 1336122.153209 nodes/sec
６手読み TIME: 1.498000 sec. RATE: 2552488.651535 nodes/sec
７手読み TIME: 5.210000 sec. RATE: 3496885.796545 nodes/sec
８手読み TIME: 20.561000 sec. RATE: 3861992.412820 nodes/sec
９手読み TIME: 125.954000 sec. RATE: 3808498.991695 nodes/sec
（注）前回のベンチマークより少々速くなりました。ハッシュの使い方が改善しましたのです。
１マシン２コア使用 － 初手１５手から検索
５手読み TIME: 0.499000 sec. RATE: 720705.410822 nodes/sec
６手読み TIME: 1.029000 sec. RATE: 1910692.905734 nodes/sec
７手読み TIME: 3.822000 sec. RATE: 3016193.615908 nodes/sec
８手読み TIME: 15.023000 sec. RATE: 3333467.216934 nodes/sec
９手読み TIME: 93.272000 sec. RATE: 3563496.537010 nodes/sec
１マシン２コア使用 － 初手１０手から検索
５手読み TIME: 0.484000 sec. RATE: 529270.661157 nodes/sec
６手読み TIME: 0.967000 sec. RATE: 1529441.571872 nodes/sec
７手読み TIME: 3.541000 sec. RATE: 2547128.212369 nodes/sec
８手読み TIME: 11.903000 sec. RATE: 3419904.897925 nodes/sec
９手読み TIME: 79.575000 sec. RATE: 3485865.699026 nodes/sec
...一応の効果は出ていますが三分の一はむりですね。
仮に（我が湯水のように資金を使えて）３０台！！並列で動かしても現在のシステムでは「９手読み」を「８手読み」ｘ３０に置き換えるだけなので約２０秒が限界となります。
検索時間短縮率が思った程伸びなかったのは局面量の減少により（皮肉にも）浅読み君の「記憶装置」があまりその効果を発揮出来なかったことにあります。局面量の減少により「前回に遭遇した局面からの検索を打ち切る」回数が減少したのが原因です。
...しかし！これはマシン間の検索結果の共有・統合により改善可能（かもしれない...かな？）
インテルの「i7」CPUは４コア内臓、各コアが「２コア」に相当する機能があるので（Hyper Threading）、都合８コアCPUとなります。ほちいです。