SSS*

SSS*は、1979 年に George Stockman によって導入された検索アルゴリズムです。A * 検索アルゴリズムと同様に、ゲームツリーを最良優先方式で横断する状態空間検索を実行します。

SSS* は、ソリューションツリーの概念に基づいています。非公式には、任意のゲームツリーから、各MAXノードのブランチの数を1 つに刈り込むことによってソリューションツリーを形成できます。このようなツリーは、対戦相手の行うすべての可能な手順に対して 1 つの MAX アクションを指定するため、MAX の完全な戦略を表します。ゲームツリーが与えられると、SSS* は部分ソリューションツリーの空間を検索し、徐々に大きなサブツリーを分析して、最終的に元のゲームツリーと同じルートとミニマックス値を持つ単一のソリューションツリーを生成します。SSS* は、アルファ-ベータプルーニングで刈り込まれるノードを検査することはなく、アルファ-ベータでは刈り込まれないブランチも刈り込む可能性があります。そのため、ストックマンは、SSS* の方がアルファ-ベータよりも優れた汎用アルゴリズムではないかと推測しました。しかし、Igor RoizenとJudea Pearl は、 SSS ^*がalpha/beta と比較して評価する位置の数の節約には限界があり、一般に他のリソース (たとえば、アルゴリズムのベストファーストの性質によって必要になるノードのリストの保存とソート) の増加を補うのに十分ではないことを示しました [ 1 ]。しかし、^Aske Plaat、Jonathan Schaeffer、Wim Pijls および Arie de Bruin は、チェス、チェッカーなどのすべてのゲームプレイプログラムの場合のように、alpha–beta が転置テーブルで使用される場合、null ウィンドウの alpha–beta 呼び出しのシーケンスは SSS* と同等 (つまり、同じノードを同じ順序で展開する) であることを示しました。これで、OPEN リストの保存とソートは不要になりました。これにより、トーナメント品質のゲームプレイプログラムで SSS* (と同等のアルゴリズム) を実装できるようになりました。^{[ 2 ]}

最良優先アルゴリズムを深さ優先呼び出しのシーケンスとして再定式化したことにより、ヌルウィンドウアルファ-ベータアルゴリズムのクラスの定式化が促進され、その中でMTD(f)が最もよく知られた例です。

アルゴリズム

ノードの状態を格納する優先キューOPENがあります。-ノード識別子（ドット付き10進表記はノードの識別に使用され、ルートです）、- ノードの状態（L - ノードはライブ、つまりまだ解決されていない、S - ノードは解決されている）、- 解決されたノードの値。OPENキュー内の項目は、値の降順でソートされます。複数のノードが同じ値を持つ場合、ツリーの最も左のノードが選択されます $(J,s,h)$ $J$ $\epsilon$ $s\in \{L,S\}$ $J$ $h\in (-\infty ,\infty )$ $h$ $h$

OPEN := { (e, L, inf) } while true do // 停止するまで繰り返すOPENキューの先頭から 要素p =( J , s , h )をポップする。J = eかつs = Sの場合 アルゴリズムを停止し、結果としてhを返す それ以外の場合はp にガンマ演算子を適用する

$\Gamma$ 演算子 forは次のように定義されます。 $p=(J,s,h)$

s = Lの場合、Jが終端ノードの場合は (1.) ( J、S、 min( h、 value( J ))) を OPEN に 追加します。そうでない場合、Jが MIN ノードの場合は (2.) (J.1、L、h ) を OPEN に 追加します。そうでない 場合、(3.) j =1..number_of_children( J ) の場合、(Jj、L、h ) を OPEN に 追加します。そうでない場合、Jが MIN ノードの場合は (4.) (parent( J )、S、h ) を OPEN に追加します。 OPENから親(J)の子に関連付けられたすべての状態を削除します。 else if is_last_child( J ) then // J が parent(J) の最後の子である場合(5.) OPENに (parent( J ), S , h )を追加する。そうでない場合は (6.) OPENに(parent( J ).( k +1 ), L , h )を追加する。 // OPENに親(J)の次の子に関連付けられた状態を追加する。

参考文献

^イゴール・ロイゼン、ジュデア・パール（1983年3月）「ミニマックスアルゴリズムはアルファ・ベータよりも優れているか？：イエスとノー」人工知能21 ( 1-2 ) : 199-220 . doi : 10.1016 / s0004-3702(83)80010-1
^プラート、アスク;ジョナサン・シェーファー。ヴィム・ピルス。アリー・デ・ブルーイン（1996年11月）。「ベストファースト固定深さミニマックスアルゴリズム」。人工知能。87 ( 1–2 ): 255–293 .土井: 10.1016/0004-3702(95)00126-3。

外部リンク

[1] イゴール・ロイゼン、ジュデア・パール（1983年3月）「ミニマックスアルゴリズムはアルファ・ベータよりも優れているか？：イエスとノー」人工知能21 ( 1-2 ) : 199-220 . doi : 10.1016 / s0004-3702(83)80010-1

[2] プラート、アスク;ジョナサン・シェーファー。ヴィム・ピルス。アリー・デ・ブルーイン（1996年11月）。「ベストファースト固定深さミニマックスアルゴリズム」。人工知能。87 ( 1–2 ): 255–293 .土井: 10.1016/0004-3702(95)00126-3。

*が

[ 2 ]