3.4 SSS$^*$ (Stockman 79)

Explora caminos tipo best-first (AO*).

Es superior a alpha-beta en el sentido que:

• No explora nodos que alpha-beta no explora.
• Puede no explorar nodos que alpha-beta si explora.

Idea: tomar el árbol de búsqueda globalmente, se puede ver como una versión de $AO^*$ y por lo mismo trata de encontrar la solución óptima.

Figura 3.4: Ejemplo de la estrategia SSS$^*$.

Desventaja: tiene que guardar mucha información para considerar siempre el mejor camino a explorar.

La figure 3.4 muestra un ejemplo de SSS$^*$ donde las letras dentro de los nodos indican el orden en que se evalúan los nodos y los números subrayados muestran los nodos terminales que son evaluados.

Se han propuesto varias pequeñas variantes de SSS$^*$ como InterSSS$^*$, RecSSS$^*$ y Mem$^*$, las cuales hacen un uso más eficiente de memoria.