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

引き続き「ミニマックス法」の改良についてです...

しらみつぶし検索の欠点として

 ① 検索途中で「既に結論が出ている局面」に再度遭遇しても律儀に最後まで検索します。(今回)
 ② 検索途中で「これ以上は無駄・不要」といった状況でも律儀に最後まで検索します。(次回)

が挙げられます。(他にもあるけどね)

「既に結論が出ている局面」に再度遭遇しても律儀に最後まで検索

以下のような棋譜があったとします。

(い) ▲2六歩 △8四歩 ▲7六歩 △3四歩
(ろ) ▲2六歩 △3四歩 ▲7六歩 △8四歩
(は) ▲7六歩 △8四歩 ▲2六歩 △3四歩
(に) ▲7六歩 △3四歩 ▲2六歩 △8四歩

仮に初手から10手検索するとします。上記の4例は手順は違えど4手後には同局面に収束しますね。最初に(い)を検索したとして、その結果が+100点するなら(ろ)、(は)、(に)も最後まで検索するまでもなく+100点に成るのは自明です。

これにより6手読みを3回節約できます...75%OFFってところですね。3手でも似た状況が出現します。

(い) ▲2六歩 △8四歩 ▲7六歩
(ろ) ▲7六歩 △8四歩 ▲2六歩

深読みをするときはこのような状況はゴロゴロ出現します...となると検索すべき領域はかなりの量で減少します。

「駒の得点を集計する」評価関数を使い5手読みをしてみると...

オリジナル浅読みくん

TIME: 14.597000
NODES: 20,632,087
RATE: 1,413,447.078167 nodes/sec

「覚える」浅読みくん

TIME: 7.832000
NODES: 2,371,729
RATE: 302,825.459653 nodes/sec

...検索時間は約半分、検索局面数は8分の1以下に減少しました!!!(注・なんか怪しい…良過ぎる!!!バグっているかもしれません)

(質問)「検索局面数は8分の1以下」なのになぜ「検索時間は約半分」なの?検索時間も8分の1程度に収まるのでは?

(お答え)

「検索局面数は8分の1以下」のお陰でかなりの時間を節約したのですが、「以前検索済みの局面の評価を覚える」ことに時間が掛かったので(評価関数を使うより遥かに時間を消費します)、その分ずれました。ここを改良すれば(余地多分にアリ)もっと実用性があがります。

「覚える」浅読みくんが6手・7手読みにチャレンジしてみました。

6手
TIME: 15.206000
NODES: 4,138,674
RATE: 272,173.747205 nodes/sec

賢い、賢い。(^^)

ところが...

7手
...メモリーが足らなくなってErrorです。

なかなかうまくいきませんね~~~。

深く読む程「覚える」局面が増加します。これも深く読めば読むほど爆発的に増加しますので遅かれ早かれ限界に達します。対処法としては①もっとメモリーを使う、②覚えられる局面数に制限を設け、一定数に達したら記録を(できれば再使用度の無いものを)いくらか削除しなければなりません。

(続)

投稿者: 紫外線 投稿日時: 日, 07/19/2009 - 13:16 categories [ ]

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

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

7手読み追記

ちょいと工夫して頑張ったら… (メモリーえらく消費しました)

TIME: 102.758000
NODES: 249,99,990
RATE: 243,289.962825 nodes/sec

…となりました。元祖浅読みくんは7手読みに 4800秒 = 80分(推定) なので成功と思えます。

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

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