と金倶楽部

風邪も退治できた様なので続行させて頂きます。（読んでいる人まだいるのかな？）

しらみつぶし検索の欠点として挙げられた

　②　検索途中で「これ以上は無駄・不要」といった状況でも律儀に最後まで検索します。

...を掘ってみましょう。

ウィキペディアには．．．

アルファ・ベータ法
http://ja.wikipedia.org/wiki/%CE%91-%CE%B2%E6%B3%95

．．．色々専門的に記述されていますが．．．一寸単純化しましょう。

因みに「アルファ・ベータ法」はAI・ゲーム検索の教科書には「ミニマックス法」の次ページが指定席となっています。

ミニマックス法では

　①自分の手番では自分に都合良い手を高く評価する
　②敵の手番では敵に都合良い手を高く評価する

①と②を交互に行うため、仮に３手目に物凄く良い手を見つけても一手（２手目）逆登った時にハネられてしまいます。

（例）３手目に詰みを発見しても敵が「はい、そうですか」とその前提となる２手目を指してくれる筈がありませんね。（当然見落としを除く）

で・す・が、

　①「３手目に詰み」が存在する
　②敵は絶対に前提となる２手目は指さない。別の手を考える

．．．となれば他の３手目に存在する候補手は実現性ゼロに成り、検討する必要はゼロとなります。よって検索量が減ります。（これが１０手読みの途中なら節約量は大した物になりますね）

このようにして検索量を減らすことを業界では「枝刈り」と呼びます。

前回と同じ「駒の得点を集計する」評価関数を使い５手読みをしてみると．．．

「ミニマックス」浅読みくん
TIME: 14.679000
NODES: 20,632,087
CUT: 0
RATE: 1,405,551.263710 nodes/sec

「アルファ・ベータ」浅読みくん
TIME: 0.609000
NODES: 1,059,027
CUT: 881,106
RATE: 1,738,960.591133 nodes/sec

．．．「あっと驚くタメゴロ～」的に時間が短縮されました。”CUT”は「枝刈り」でハネられた「枝」の数です。本格的な将棋ソフトではもっと複雑な評価関数を使うのでこのような劇的な数字は無理です。

６手読み
TIME: 2.043000
NODES: 4,656,782
CUT: 1,361,460
RATE: 2,279,384.238864 nodes/sec

７手読み
TIME: 15.381000
NODES: 51,861,290
CUT: 39,473,945
RATE: 3,371,776.217411 nodes/sec

８手読み
TIME: 74.895000
NODES: 210,705,827
CUT: 51,271,500
RATE: 2,813,349.716269 nodes/sec

読みの深さを増やしても以前のミニマックスに比べ倍率が一桁台に落ち着いていますね。

（質問）　前回の「覚える」浅読みくんと組み合わせれば相乗効果で天下無敵の検索エンジンに成るのかな？？？

（お答え）　それは次回に検証しましょう。

（続）