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

…前回は駄文を書き連ねましたが「浅読みくん」の検索方法はミニマックス法(戦略)と呼ばれ洗練された説明は以下のリンクからどーぞです。

http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%...

ミニマックスは分解すると

☆ミニ - Minimize - 相手の手番では自分の評価が低くなるような手を推奨し、
☆マックス - Maximize - 自分の手番では自分の評価が高くなるような手を推奨

これを繰り返し山のような候補手をふるいに掛けます。

(重要)全将棋ソフトの検索エンジンの基本はミニマックス法です。

…ですが、「基本」あれば「応用」ありで実際にはミニマックス法を改良・改造したアルゴリズム(当然速い)を使用しています。それは後ほど…

この方法以外で現在の将棋ソフト以上のプログラムを書けるのは神のみです。(本気です。誓ってもいい。)

将棋は有限のゲームなので制限なしのマシン(神)なら全手を読み切り必勝手順を指す…ことは理論上は可能です。もちろん実際には無理ですね。将棋の全手組み合わせ数は全宇宙の原子数より多い(はず)なので恐竜の時代にさかのぼって計算しても追いつきません。

で、「浅読みくん」の実力は実際ところどの様なものでしょうか?浅読みくんの評価関数は単純なので検索時間の大半は○手先の局面にたどり着くことに費やされます。

NODESは生成した局面数(同一局面を含む)です。

3手読み
TIME: 0.141000
NODES: 26,400
RATE: 187,234.042553 nodes/sec

4手読み
TIME: 0.593000
NODES: 746,131
RATE: 1,258,231.028668 nodes/sec

5手読み
TIME: 5.897000
NODES: 20,632,087
RATE: 3,498,742.920129 nodes/sec

6手読み
TIME: 160.196000
NODES: 569,884,569
RATE: 3,557,420.715873 nodes/sec

…これ以上は時間がかかり過ぎるので当然パス。一手深く進むごとに局面数は最低30倍に増えるので(「5手読み」と「6手読み」を比較)、「7手読み」は 160 x 30 = 4800秒 = 80分 程かかると予想されます。

次回は「応用」の話です。(続)

投稿者: 紫外線 投稿日時: 水, 07/15/2009 - 13:57 categories [ ]

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

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

「浅読みくん」の実力 追試

上記の速度測定は…『評価関数は単純なので検索時間の大半は○手先の局面にたどり着くことに費やされます』…といった現実性が希薄な条件なのでちょいと改造して追試します。

評価関数に枷を付けます…1ミリ秒の「待ち」を加えます。実際の「待ち」時間はシステム次第なので厳密ではありません。この実験の意図は「評価関数に時間を掛け過ぎるとろくな事が無い」…を検証するものです。

 1、000、000 マイクロ秒 = 1、000 ミリ秒 = 1秒…です。

合法手生成に現在の所約0.1マイクロ秒掛かりますのでこれでも十分な負荷になります。

3手読み
TIME: 25.587000
NODES: 26400
RATE: 1031.773948 nodes/sec

あっと驚くタメゴロ~~の結果に成りました。

評価関数に時間を掛け過ぎると深読みを放棄しなければなりません。

鋭い!

おっ、wasabi様がいい所を突いてきました。次回の書き物にこのテクの解説と検証を行わせていただきます。

3手読みくらいまでで有力な手をいくつか抽出して・・・

それ以外は切り捨てて、有力手だけを10手くらい先まで読んでその中から最良のものを選ぶというのはできないのでしょうか?

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

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