SSS*法
概念とその効果
SSS*では、OPENリストと呼ばれるリストを用います。 まず最初にOPENリストに<n=ROOT, s=LIVE, h=+∞>というノードを入れ、 遷移規則に従ってOPENリストにノードを追加、削除していくことで探索を行います。 私が手に入れた資料には「StockmanのSSS*」と記されていて、 SSS*にはいくつかのバリエーションが存在するようです。 けれども私はこれしか手に入れられなかったので、 ここで言うSSS*とはStockmanのSSS*を指すこととします。
| a | |||||||||||||||||
 |
 |
 |
|||||||||||||||
| b | c | d | |||||||||||||||
-
現在のノードが葉ノードなら
- ノードを静的評価し、評価値順になるようにリストに登録する。
-
現在のノードaがNIMノードなら
- 最初の子ノードbをリストに入れ、ノードaをリストから取り除く。
- ノードbの探索が終了したら、次の子ノードcをリストに入れる。これを全ての子ノードに対して繰り返す。
- 全ての子ノードを探索し終わったら、元のノードaをリストに入れ、ノードaの探索を終了とする。このときノードaの評価値は、全子ノードの評価値のうち最小のものになる。
-
現在のノードaがMAXノードなら
- 全ての子ノードをリストに入れる。
- 子ノードの一つが探索終了したら、その子ノードの評価値をノードaの評価値とし、ノードaの探索を終了する。
- ノードaの子孫ノード全てをリストから取り除く。
| 状態 | 条件 | 処理 |
|---|---|---|
| - | s=SOLVED n=ROOT |
最終状態に到達したので、アルゴリズムを終了する。 |
| 1 | s=SOLVED n != ROOT type(n) = MIN |
OPENリストの先頭に<m = parent(n), s,h>を入れる。そのとき、mがkの先祖であるような<k,s,h>を取り除く |
| 2 | s=SOLVED n != ROOT type(n) = MAX next(n) != NIL |
<next(n),LIVE,h>をOPENリストの先頭に入れる。 |
| 3 | s=SOLVED n != ROOT type(n) = MAX next(n) = NIL |
<parent(n),s,h>をOPENリストの先頭に入れる。 |
| 4 | s=LIVE first(n) = NIL |
<n,SOLVED,min(h,f(n))>を、評価値順になるようにOPENリストの中に入れる。 |
| 5 | s=LIVE first(n) != NIL type(first(n)) = MAX |
<first(n),s,h>をOPENリスト(の先頭)に入れる。 |
| 6 | s=LIVE first(n) != NIL type(first(n)) = MIN |
nをfirst(n)に置き換える。 n != NILである間、{OPENリストの先頭に<n,s,h>を入れる。nをnext(n)に置き換える。} |
動きの例
まずは、現在自分の手番です。現在リストの先頭にあるのはノードaです。
| 自分の手番 | a | ||||||||||||||||
| リスト： | <a, LIVE, +∞> |
状態はLIVE、子ノードはMINノードなので、現在の状態は6です。 そのため、全ての子ノードをリストに登録し、ノードaをリストから削除します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
| リスト： | <b, LIVE, +∞>, <c, LIVE, +∞>, <d, LIVE, +∞> |
リストの先頭にあるノードbの状態はLIVE、子ノードはMAXノードなので、現在の状態は5です。 そのため、最初の子ノードだけをリストに入れます。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|||||||||||||||||
| 自分の手番 | e | ||||||||||||||||
| リスト： | <e, LIVE, +∞>, <c, LIVE, +∞>, <d, LIVE, +∞> |
ノードeでは、コンピュータにとってもう十分先読みしたと判断される深さ(first(n)=NIL)なので、状態4になります。 そのため、ノードeを静的に評価し、リストに再登録します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|||||||||||||||||
| 自分の手番 | e | ||||||||||||||||
| リスト： | <c, LIVE, +∞>, <d, LIVE, +∞>, <e, SOLVED, 5> |
ここでリストの先頭にあるのはノードcのため、ノードcが処理の対象になります。 ノードcの状態はLIVE、子ノードはMAXノードなので、現在の状態は5です。 そのため、最初の子ノードだけをリストに入れます。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|
||||||||||||||||
| 自分の手番 | e | h | |||||||||||||||
| リスト： | <h, LIVE, +∞>, <d, LIVE, +∞>, <e, SOLVED, 5> |
十分先読みした深さなので、ノードhを静的評価します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|
||||||||||||||||
| 自分の手番 | e | h | |||||||||||||||
| リスト： | <d, LIVE, +∞>, <e, SOLVED, 5>, <h, SOLVED, 1> |
同じように、ノードdを処理します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | e | h | k | ||||||||||||||
| リスト： | <k, LIVE, +∞>, <e, SOLVED, 5>, <h, SOLVED, 1> |
同じようにノードkを静的評価します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | e | h | k | ||||||||||||||
| リスト： | <e, SOLVED, 5>, <k, SOLVED, 5>, <h, SOLVED, 1> |
次のノードeは、状態がSOLVED、タイプがMAX、兄弟ノードが残っているので状態2になります。 そのため、リストに次の兄弟ノードfを登録します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|
|
|
||||||||||||||
| 自分の手番 | e | f | h | k | |||||||||||||
| リスト： | <f, LIVE, 5>, <k, SOLVED, 5>, <h, SOLVED, 1> |
現在、状態4なのでノードfを静的評価します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|
|
|
||||||||||||||
| 自分の手番 | e | f | h | k | |||||||||||||
| リスト： | <k, SOLVED, 5>, <h, SOLVED, 1>, <f, SOLVED, -2> |
次はノードkで状態2なので、次の兄弟ノードlを登録します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|
|
|
|
|||||||||||||
| 自分の手番 | e | f | h | k | l | ||||||||||||
| リスト： | <l, LIVE, 5>, <h, SOLVED, 1>, <f, SOLVED, -2> |
状態4なので、ノードlを静的評価します。
| 自分の手番 | a | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | b | c | d | ||||||||||||||
|
|
|
|
|
|||||||||||||
| 自分の手番 | e | f | h | k | l | ||||||||||||
| リスト： | <l, SOLVED, 5>, <h, SOLVED, 1>, <f, SOLVED, -2> |
状態2なので、次の兄弟ノードmをリストに登録します。
| 自分の手番 | a | |||||||||||||||||
|
|
|
||||||||||||||||
| 相手の手番 | b | c | d | |||||||||||||||
|
|
|
|
|
|
|||||||||||||
| 自分の手番 | e | f | h | k | l | m | ||||||||||||
| リスト： | <m, LIVE, 5>, <h, SOLVED, 1>, <f, SOLVED, -2> |
状態4なので、ノードmを静的評価します。
| 自分の手番 | a | |||||||||||||||||
|
|
|
||||||||||||||||
| 相手の手番 | b | c | d | |||||||||||||||
|
|
|
|
|
|
|||||||||||||
| 自分の手番 | e | f | h | k | l | m | ||||||||||||
| リスト： | <m, SOLVED, 4>, <h, SOLVED, 1>, <f, SOLVED, -2> |
ここで、ノードmの状態はSOLVED、種類はMAXで次の兄弟ノードがないので、状態は3になります。 そのため、現在の評価値を親ノードdの評価値とし、ノードdをリストに登録します。
| 自分の手番 | a | |||||||||||||||||
|
|
|
||||||||||||||||
| 相手の手番 | b | c | d | |||||||||||||||
|
|
|
|
|
|
|||||||||||||
| 自分の手番 | e | f | h | k | l | m | ||||||||||||
| リスト： | <d, SOLVED, 4>, <h, SOLVED, 1>, <f, SOLVED, -2> |
ノードdの状態はSOLVEDで種類はMINなので、状態は1になります。 つまり、ノードdの評価値を親ノードaの評価値とし、ノードaをリストに登録します。 またここで、ノードaの子孫ノード全てをリストから取り除きます。
| 自分の手番 | a | |||||||||||||||||
|
|
|
||||||||||||||||
| 相手の手番 | b | c | d | |||||||||||||||
|
|
|
|
|
|
|||||||||||||
| 自分の手番 | e | f | h | k | l | m | ||||||||||||
| リスト： | <a, SOLVED, 4> |
これで探索が終了し、この局面の評価値が4となりました。 このとき探索した結果を見ると、ノードg、i、jに相当するところが探索されていないことが分かります。 αβ法ではノードjに相当するところが探索されなかっただけなので、 今回の例ではαβ法よりも探索したノードが少なくなったことが分かりました。
