SSS * es un algoritmo de búsqueda , introducido por George Stockman en 1979, que lleva a cabo una búsqueda en el espacio de estados atravesando un árbol de juego de la manera mejor primero , similar a la del algoritmo de búsqueda A * .
SSS * se basa en la noción de árboles de solución . De manera informal, se puede formar un árbol de solución a partir de cualquier árbol de juego arbitrario reduciendo el número de ramas en cada nodo MAX a uno. Dicho árbol representa una estrategia completa para MAX, ya que especifica exactamente una acción MAX por cada secuencia posible de movimientos realizados por el oponente. Dado un árbol de juego, SSS * busca en el espacio de árboles de solución parcial, analizando gradualmente subárboles cada vez más grandes, y finalmente produce un árbol de solución único con la misma raíz y valor Minimax que el árbol de juego original. SSS * nunca examina un nodo que se poda alfa-betapodaría y podría podar algunas ramas que alfa-beta no haría. Stockman especuló que SSS * puede, por lo tanto, ser un algoritmo general mejor que alfa-beta. Sin embargo, Igor Roizen y Judea Pearl han demostrado [1] que los ahorros en el número de posiciones que SSS * evalúa en relación con alfa / beta son limitados y, en general, no son suficientes para compensar el aumento de otros recursos (p. Ej., El almacenamiento y la clasificación de una lista de nodos necesarios por la naturaleza del algoritmo "best-first"). Sin embargo, Aske Plaat , Jonathan Schaeffer , Wim Pijls y Arie de Bruin han demostrado que una secuencia de llamadas alfa-beta de ventana nula es equivalente a SSS * (es decir, expande los mismos nodos en el mismo orden) cuando alfa-beta es utilizado con una tabla de transposición , como es el caso en todos los programas de juego de ajedrez, damas, etc. Ahora ya no era necesario almacenar y clasificar la lista ABIERTA. Esto permitió la implementación de (un algoritmo equivalente a) SSS * en programas de juego de calidad de torneo. Los experimentos demostraron que de hecho funcionó mejor que Alpha-Beta en la práctica, pero que no superó a NegaScout . [2]
La reformulación de un algoritmo del mejor primero como una secuencia de llamadas en profundidad primero dio lugar a la formulación de una clase de algoritmos alfa-beta de ventana nula, de los cuales MTD (f) es el ejemplo más conocido.
Algoritmo
Hay una cola de prioridad ABIERTA que almacena estados o los nodos, donde - identificador de nodo ( la notación de Dewey se utiliza para identificar nodos, es una raíz), - estado del nodo (L: el nodo está activo, lo que significa que aún no está resuelto y S: el nodo está resuelto), - valor del nodo resuelto. Los elementos de la cola ABIERTA se ordenan de forma descendente porvalor. Si más de un nodo tiene el mismo valor de, se elige un nodo situado más a la izquierda en el árbol.
OPEN: = {(e, L, inf)} while true do // repetir hasta que se detenga sacar un elemento p = ( J , s , h ) del encabezado de la cola OPEN si J = e y s = S entonces DETENGA el algoritmo y devuelva h como resultado de lo contrario, aplique el operador Gamma para p
operador para se define de la siguiente manera:
si s = L entonces si J es un nodo terminal entonces (1.) agregue ( J , S , min ( h , value ( J ))) a OPEN; de lo contrario, si J es un nodo MIN, entonces (2.) agregue (J. 1, L , h ) to OPEN else (3.) para j = 1..number_of_children ( J ) agregue (Jj, L , h ) to OPEN else si J es un nodo MIN entonces (4.) agregue (parent ( J ), S , h ) para ABRIR eliminar de OPEN todos los estados asociados con los hijos del padre (J) else if is_last_child ( J ) then // si J es el último hijo de parent (J) (5.) add (parent ( J ), S , h ) to OPEN else (6.) add (parent ( J ). ( K +1), L , h ) to OPEN // agrega el estado asociado con el siguiente hijo del padre (J) a ABRIR
Referencias
- ^ Roizen, Igor; Judea Pearl (marzo de 1983). "¿Un algoritmo minimax mejor que alpha-beta ?: Sí y No". Inteligencia artificial . 21 (1–2): 199–220. doi : 10.1016 / s0004-3702 (83) 80010-1 .
- ^ Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (noviembre de 1996). "Mejor primero algoritmos Minimax de profundidad fija". Inteligencia artificial . 87 (1–2): 255–293. doi : 10.1016 / 0004-3702 (95) 00126-3 .