倶楽部入口倶楽部活動検索累計訪問者数
一年目 約９万３千 |
コンピューター将棋の構造 － 検索エンジン 「浅読みくん」 ②…前回は駄文を書き連ねましたが「浅読みくん」の検索方法はミニマックス法（戦略）と呼ばれ洗練された説明は以下のリンクからどーぞです。 http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%... ミニマックスは分解すると ☆ミニ － Minimize － 相手の手番では自分の評価が低くなるような手を推奨し、 これを繰り返し山のような候補手をふるいに掛けます。 （重要）全将棋ソフトの検索エンジンの基本はミニマックス法です。 …ですが、「基本」あれば「応用」ありで実際にはミニマックス法を改良・改造したアルゴリズム（当然速い）を使用しています。それは後ほど… この方法以外で現在の将棋ソフト以上のプログラムを書けるのは神のみです。（本気です。誓ってもいい。）
将棋は有限のゲームなので制限なしのマシン（神）なら全手を読み切り必勝手順を指す…ことは理論上は可能です。もちろん実際には無理ですね。将棋の全手組み合わせ数は全宇宙の原子数より多い（はず）なので恐竜の時代にさかのぼって計算しても追いつきません。 で、「浅読みくん」の実力は実際ところどの様なものでしょうか？浅読みくんの評価関数は単純なので検索時間の大半は○手先の局面にたどり着くことに費やされます。 NODESは生成した局面数（同一局面を含む）です。 ３手読み ４手読み ５手読み ６手読み …これ以上は時間がかかり過ぎるので当然パス。一手深く進むごとに局面数は最低３０倍に増えるので（「５手読み」と「６手読み」を比較）、「７手読み」は １６０ ｘ ３０ ＝ ４８００秒 ＝ ８０分 程かかると予想されます。 次回は「応用」の話です。（続）
投稿者： 紫外線 投稿日時： 水, 07/15/2009 - 13:57 categories [ ]
|
ＩＤ取得（無料）してログインすると広告は不表示掲示板更新状況
ＩＤ取得（無料）してログインすると広告は不表示最近のコメント
|
「浅読みくん」の実力 追試
上記の速度測定は…『評価関数は単純なので検索時間の大半は○手先の局面にたどり着くことに費やされます』…といった現実性が希薄な条件なのでちょいと改造して追試します。
評価関数に枷を付けます…１ミリ秒の「待ち」を加えます。実際の「待ち」時間はシステム次第なので厳密ではありません。この実験の意図は「評価関数に時間を掛け過ぎるとろくな事が無い」…を検証するものです。
１、０００、０００ マイクロ秒 ＝ １、０００ ミリ秒 ＝ １秒…です。
合法手生成に現在の所約０．１マイクロ秒掛かりますのでこれでも十分な負荷になります。
３手読み
TIME: 25.587000
NODES: 26400
RATE: 1031.773948 nodes/sec
あっと驚くタメゴロ～～の結果に成りました。
評価関数に時間を掛け過ぎると深読みを放棄しなければなりません。
鋭い！
おっ、wasabi様がいい所を突いてきました。次回の書き物にこのテクの解説と検証を行わせていただきます。
３手読みくらいまでで有力な手をいくつか抽出して・・・
それ以外は切り捨てて、有力手だけを１０手くらい先まで読んでその中から最良のものを選ぶというのはできないのでしょうか？