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

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

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

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

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

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

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

wasabi様が提唱して下さった

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

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

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

現在浅読みくんの演算速度(秒)は

 3手読み 0.141000
 4手読み 0.593000
 5手読み 5.897000
 6手読み 160.196000
 7手読み 4800 (推定)
 8手読み 4800 x 30 = 144,000 = 40時間 (推定)
 9手読み 4800 x 30 x 30 = 1200時間 (推定)

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

そしてこの5有力手からスタートして10手先を読むわけですが...チョットマテ~~~...これって9手読みを5回行うのと同じですね。上記の表から推定して 1200時間 x 5 = 6000時間 = 250日掛かります。ボツです。

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

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

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

...と予想通りに通常5手読みの~5倍強となります。これは通常6手読みよりは遥かに速い事は確かです。

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

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

...この方法で「10手読み」を行う場合、5の10乗ですので、 5^10 = 9、765、625 とお手軽サイズに収縮します。「15手読み」すら射程距離に入ります。

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

(続)

投稿者: 紫外線 投稿日時: 木, 07/16/2009 - 12:00 categories [ ]