と金倶楽部

前回紹介した「ミニマックス法」は「○手先をしらみつぶしに検索して一番良さそうな手を推奨」するのでど～しても将棋のように選択肢が多いゲームでは効率が良くありません。（と言うより無理です）

選択肢が多すぎるとき人間は「絞込み」

　①有望な選択肢に集中
　②見込みのなさそうな選択肢には早めに見切りをつける

．．．を行い、必ずしも最高・最善ではない（確認する時間がないので）けど十分満足できる回答を模索します。これを業界では「ヒューリスティクス」と呼び、将棋ソフトを構築する過程で必ず実装することになります。

ヒューリスティクス(Heuristic)
http://ja.wikipedia.org/wiki/%E3%83%92%E3%83%A5%E3%83%BC%E3%83%AA%E3%82%...

...これに対する「しらみつぶし検索」は確定的（Deterministic）アルゴリズムと呼ばれます。

wasabi様が提唱して下さった

「３手読みくらいまでで有力な手をいくつか抽出してそれ以外は切り捨てて、有力手だけを１０手くらい先まで読んでその中から最良のものを選ぶというのはできないのでしょうか？」

．．．は正にヒューリスティクスを用いた解決法となります。

まず考慮しなければならないのは如何にして「有力な手をいくつか抽出」するか？．．．ですが、この際「できた！」と仮定しましょう。

現在浅読みくんの演算速度（秒）は

　３手読み　0.141000
　４手読み　0.593000
　５手読み　5.897000
　６手読み　160.196000
　７手読み　4800　（推定）
　８手読み　4800 x 30 =　144,000 = 40時間　（推定）
　９手読み　4800 x 30 x 30 = 1200時間　（推定）

なので「３手読みくらいまでで有力な手をいくつか抽出してそれ以外は切り捨て」は0.141000秒掛かります。次は「有力手だけを１０手くらい先まで読んでその中から最良のものを選ぶ」です。「有力手」と言うくらいですから５手位に絞り込むのが妥当かと思われます。

そしてこの５有力手からスタートして１０手先を読むわけですが．．．チョットマテ～～～．．．これって９手読みを５回行うのと同じですね。上記の表から推定して　１２００時間　ｘ　５　＝　６０００時間　＝　２５０日掛かります。ボツです。

「しらみつぶし検索」は最初をいくら絞っても（仮に有力手を１手だけにしても）時間が掛かり過ぎます。仮に有力手を１手に絞れる位なら最初から検索する必要すらありませんね．．．

浅読みくんに「３手読みくらいまでで有力な手をいくつか抽出して．．．有力手だけを６手」を試してみた結果を以下に記します。

　TIME: 37.486000
　NODES: 119,271,442
　RATE: 3181759.643600 nodes/sec

．．．と予想通りに通常５手読みの～５倍強となります。これは通常６手読みよりは遥かに速い事は確かです。

この考え方を一歩進めて以下の様に変更します。

　①　局面から起きる候補手（３０～２００程度）を生成する際、「有力な手」のみを生成します。
　②　敵の応手も同様に敵にとって「有力な手」のみを生成。
　③　①と②を繰り返しミニマックス法の深読みを行います。

．．．この方法で「１０手読み」を行う場合、５の１０乗ですので、　５＾１０　＝　９、７６５、６２５　とお手軽サイズに収縮します。「１５手読み」すら射程距離に入ります。

残る課題はどうやって「有力な手をいくつか抽出」するかなのですが．．．残念ながら方法は（今のところ）存在しません。よって「絵に描いた餅」となります。残念。

（続）