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

Principal Variations - 主要変化 - 読み筋

将棋ソフトを組むにあたって一番の問題は膨大な量の盤面変化をいかにして速く検索することです。その為には利用できるもの、再利用出来るものは何でも使います。検索中に一度訪れた局面の評価値を「覚え」、再訪問時に時間を節約するするのはその一例です。

以下のリンクから画像を見てから続きをど~ぞ。
http://upload.wikimedia.org/wikipedia/en/5/56/Principle_variation_16bit....

既に紹介済みのミニ・マックス検索は「ゲームの木」(Game Tree)を最下層まで訪れ、そして最上層に戻っていきます。「最上層に戻っていく」過程でその時点における最善手を選ぶわけですが...これは即ち(評価関数が正しいと仮定すると)将来の対局の展開を予測・予言していることになります。これって人間の「あ~したら、こ~する」的読み筋を逆に並べている事と同等になります。

今までの浅読み君は自分の手番の最善手一手だけ使い上記の重要な情報を廃棄・無視していました。これは将棋ソフトの世界ではかなりの重罪ですね。

読み筋が有ると...

(1)人間にはごく自然ですが、相手の応手が予想・予測できるので相手の考慮時間に手を絞って検索できます。こうなると考慮時間は2倍(自分の持ち時間 + 相手の持ち時間)になり、手を絞って検索することにより検索密度が上がります。

(2)未だ紹介していませんが、アルファ・ベータ検索以上に高速な検索には読み筋の存在が前提条件となります。

投稿者: 紫外線 投稿日時: 土, 08/29/2009 - 12:35 categories [ ]

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

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

組み立て中

...なのですが、手持ちのグラフィクスカードで合う物が無し!!(涙)

予算かなりオーバーですが仕方がありません。無念。

あら、やだ~

検索エンジンをも~一回見直したら最上層でやるべきことをしていなかった事を発見。

これで八手読みが我のラップトップで約10秒に短縮!!!...でもまた後で間違いを発見するのだろう。嗚呼。

新しいPCのパーツ注文

...しました。我のラップトップでは役不足なので援軍を要請することにしました。

CPU
http://www.intel.co.jp/ja_JP/Consumer/Learn/Desktop/corei7-detail.htm

マザーボード
http://www.asus.co.jp/products.aspx?l1=3&l2=179&l3=815&l4=0&model=2853&m...

メモリー
12GB乗っけます。

ケース
とにかく安いもの

...残りは(ハードディスク・グラフィクスカード)は手持ちのスペアを流用。

このクラスのマシンだとハイエンドのグラフィクスカード乗っけてゲーム用って感じだけど我はその気はないので信じられないほど貧弱なグラフィクスカードが乗ります。

読み筋の例

初手から8手読んだ例です。評価関数がポンコツなので結果は無茶苦茶です。

7g7f(-10): [[P2][FU (1,3)=>(1,4) ..], [P1][KA (8,8)=>(5,5) ..], [P2][FU (1,4)=>(1,5) ..], [P1][KA (5,5)=>(4,6) ..], [P2][FU (3,3)=>(3,4) ..], [P1][KY (9,9)=>(9,8) ..], [P2][KA (2,2)=>(9,9) ..]]

9g9f(-20): [[P2][FU (1,3)=>(1,4) ..], [P1][FU (4,7)=>(4,6) ..], [P2][FU (5,3)=>(5,4) ..], [P1][FU (9,6)=>(9,5) ..], [P2][FU (3,3)=>(3,4) ..]]

8g8f(-20): [[P2][FU (1,3)=>(1,4) ..], [P1][FU (4,7)=>(4,6) ..], [P2][FU (5,3)=>(5,4) ..], [P1][FU (8,6)=>(8,5) ..], [P2][FU (3,3)=>(3,4) ..], [P1][FU (6,7)=>(6,6) ..]]

検索の結果第一位は「7六歩」(7g7f)...と出ました。

鋭い読者はお気付きかと思われますが「八手読んだのに読み筋の長さが八手無いものがある」...これは「盤面評価記憶」により検索が打ち切られたためです。盤面を記憶するときに読み筋の断片を同時に記憶して繋げることもできますが、

 ①そんなに先の展開を知っていても役に立ちそうも無い
 ②メモリーを節約したい、遅くなることはあっても速くはならない
 ③面倒

...といった理由で現在は我感知セズです。

むかりんこん

浅読み君の「局面評価覚え」機能に異常発見。問題箇所摘出。修復終了。

...ですがテストしたら以前と比較して遅くなりました。がっくん。

(補足)考えてみたら「読み筋記録」を追加していたのでそのままでは比較できませんね。そこまで考慮すればなんとか納得できる数字です。

賢いPC

>人間とは大きく違うのでしょう。

人間は自然に候補手を絞れますがソフトにとっては「全ての手は平等だ」的扱いとなるので何処かで差を付けて検索領域を削る努力が要ります。中・終盤では候補手が150~200手にもなりますので速度と密度はいくら上げても足りませんね。

>PCが‘賢い’と将棋も強くなることがあるんですか?!

「PCが‘賢い’」...これは「より速い、よりメモリーの多いPC」と理解します。

最善のお答えは「ソフト次第で有りえる」...ですね。

ソフトの強さはある程度読みの深さと連動しますので

 ①深く読めたほうがよろしかろう
 ②一手一分等の時間制限があるなら速いPCの方が当然深く読める

...なのでPCは速いことに越したことは有りません。

ですが、

 ③ある程度の深さに達したら時間の有無にかかわらず検索を中止する

が実装されているといくら速いPCを使っても打ち止めになりますのでこれまでですね。でも検索はその分早く終了するので得は有ります。

チェスソフトの場合、同じソフトなのですが「1CPU用」,「マルチCPU用」と別々に売り出され、「マルチCPU用」は確実に「1CPU用」より強いです。

難しいです。

浅読み君(=無明君?)もいろいろたいへんですね。人間とは大きく違うのでしょう。

管理人さん;
相手の応手が予想・予測できるので相手の考慮時間に手を絞って検索できます。こうなると考慮時間は2倍(自分の持ち時間 + 相手の持ち時間)になり、手を絞って検索することにより検索密度が上がります。

以前、駒音掲示板だったと思いますが、1分将棋や終盤で時間が無くなって‘悪手を指して負ける’ことに対する議論がありました。私は「中盤でしっかり読んで納得のいく手を指してきたのだから、終盤に時間が無くなって悪手を指して負けてもしかたがない」という投稿をしたのですが、少なくとも投稿なさった人々(一部のファン)には同意を得ることが難しかったように思います。

ずいぶん昔ですが、私が試合に出ていた時にも最終盤に両者1分将棋というのはよくありました。1分将棋というのは、実は‘ほぼ2分将棋’なんです。相手の考慮中にも脳ミソはフル回転しています。私くらいの棋力でも相当考えることができます。 たいがいは、どうやって詰めろを掛けるか(7手詰みくらいの)、と、自玉に詰みが無いか、詰めろ逃れの詰めろは無いか、などです。 勝った時は何とも言えない爽快さ、負ければ一気に血圧が下がる感じ・・・

別板でのコメントですが、PCが‘賢い’と将棋も強くなることがあるんですか?! Mac時代の柿木将棋でそう感じたことがありますが・・・

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

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