Algoritmos alternativos

El algoritmo MINIMAX, aún con los refinamientos descriptos, contiene algunos aspectos problemáticos:

• No considera el tiempo
• Confía fuertemente en la suposición de que el oponente elija el camino óptimo

En esta sección se explican dos alternativas que consideran cuestiones por separado.
Minimax dependiente de adversario
Según realiza la exploración del árbol de juego, el algoritmo MINIMAX supone que el oponente siempre elige el camino óptimo. Si se está frente a un adversario muy inteligente, éste podría llegar a explorar más capas que las exploradas por el algoritmo y por lo tanto tomar otra decisión que la supuesta. Aún suponiendo que el algoritmo siempre explora a una mayor profundidad que el adversario, éste último puede equivocarse y no elegir el camino óptimo. La consecuencia es que el algoritmo elige el movimiento basándose en una suposición errada.
Ante una situación de derrota, según sugiere Berliner (1977), podría ser mejor asumir el riesgo de que el oponente puede cometer un error.
En el ejemplo de la figura 6, se debe elegir entre dos movimientos B y C que conducen a la derrota siempre que el oponente elija el movimiento óptimo. Según Minimax, se debería elegir el movimiento menos malo de los dos, es decir, el C con una valor de -4. Suponga que el movimiento menos prometedor lleva a una situación muy buena para nosotros si el oponente comete un único error. En el ejemplo, el nodo B resulta el menos prometedor por tener un valor de -5, sin embargo, si el oponente comete un error elegirá F, el cual lleva a una situación muy ventajosa para nosotros. Dado que frente a un oponente que no cometa errores no resulta mucho mejor una derrota que otra, se puede asumir el riesgo de que el oponente cometa un error ya que esto conduciría a una situación muy ventajosa.

 

FIGURA 6 Análogamente, cuando se debe elegir entre dos movimientos buenos, uno ligeramente mejor que el otro, podría resultar mejor elegir el menos mejor si al asumir el riesgo de que el oponente se equivoque nos conduce a una situación muchos más ventajosa. Para tomar esta clase de decisiones correctamente, el algoritmo debería modelar el estilo de juego de cada oponente en particular. Esto permitiría estimar la probabilidad de que cometa distintos errores. Sin lugar a dudas, esto es muy difícil de lograr y se necesita contar con técnicas de aprendizaje para que el algoritmo obtenga conocimiento sobre su oponente a lo largo del juego.
Profundización iterativa
La profundización iterativa es una idea que se utilizó por primera vez en un programa llamado CHESS 4.5 (Slate y Atkin, 1977). El nombre profundización iterativa hace referencia a que se realizan iteraciones de búsquedas cada vez más profundas.
La principal razón para realizar iteraciones de búsquedas de diferentes profundidades incrementales, en lugar de realizar una búsqueda a la profundidad deseada, es que los programas de juegos pueden estar sujetos a restricciones de tiempo. Mediante esta técnica la primera iteración realiza una búsqueda de profundidad uno, la segunda iteración realiza una búsqueda de profundidad dos, etc. hasta que el tiempo destinado al movimiento se agote.
Puede parecer que se pierde una gran cantidad de tiempo al efectuar los análisis de los niveles menos profundos. Sin embargo, está demostrado que aproximadamente se necesita 1/(b-1) evaluaciones extras para realizar la exploración iterativa en un árbol de un factor de ramificación igual a b (por ej., si b=16 la profundización iterativa necesita 1/15 del total de exploraciones de los nodos hijos del último nivel).
La técnica de profundización iterativa puede aplicarse con éxito tanto a búsquedas con agente único o juegos unipersonales como a juegos bipersonales.

Profundización iterativa en juegos bipersonales: MINIMAX
Si se aplica el algoritmo MINIMAX puro descripto puede suceder que se encuentre fuera de tiempo cuando aún no ha recorrido todo el árbol y por lo tanto no tiene ninguna decisión tomada. Mediante la profundización iterativa puede cortarse la búsqueda en cualquier momento dado que siempre se tiene una solución resultado de la última iteración completada.
Otra ventaja de la profundización iterativa es que cada iteración proporciona un valor para los movimientos, y por lo tanto esto puede proporcionar un orden. Es decir, si un movimiento es superior a sus hermanos puede explorarse primero en la siguiente iteración. Con este ordenamiento, según ya se mencionó, el procedimiento de poda alfa-beta puede podar mayor cantidad de ramas y con esto reducirse el tiempo total.

Profundización iterativa en juegos unipersonales
 

• Profundización iterativa en la búsqueda Depth-First Search (DFID)

El algoritmo Depth-First Iterative Deepening o DFID, combina los mejores aspectos de la búsqueda DFS (depth-first search) y la búsqueda BFS (breadth-first search). Por una parte, la primera resulta más eficiente en términos de espacio pero necesita algún corte en la profundidad a fin de forzar una vuelta atrás cuando no se encuentra ninguna solución. Por otra parte, la segunda garantiza encontrar el camino más corto hasta la solución pero necesita grandes cantidades de espacio para mantener todo el árbol explorado en memoria. El algoritmo DFID es el siguiente:
Función DFID retorna Solución
comienzo

Solución := NULA; Profundidad := 0;mientras (Solución = NULA) AND (Profundidad < MAXPROF)
Profundidad := Profundidad + 1; Solución := DFS (EstadoInicial, Profundidad).CAMINO;
fin mientras;devolver Solución;

fin DFID; Claramente DFID encuentra el camino más corto hasta el estado solución utilizando una cantidad máxima de memoria proporcional al número de nodos del camino solución. Es el algoritmo óptimo en términos de espacio y tiempo para una búsqueda sistemática.
Ejercicio1: implementar DFS de manera que retorne también el camino solución y tome como parámetro adicional la profundidad.
Ejercicio2: aplicar DFID a uno de los siguientes problemas: jarras de agua, caníbales o 8-puzzle.
 

• Profundización iterativa A* (IDA*)

En búsquedas sistemáticas heurísticas, como por ejemplo el algoritmo A*, puede usarse la profundización iterativa para mejorar el rendimiento. La principal dificultad práctica del algoritmo A* es la gran cantidad de memoria que necesita para mantener las listas de nodos. El algoritmo Iterative Deepening A* o IDA* mejora la eficiencia de la búsqueda heurística A*.
El algoritmo IDA* fue el primer algoritmo de búsqueda heurística en encontrar una solución con restricciones de espacio y tiempo razonables al juego 15-puzzle (una versión 4x4 de un 8-puzzle).
Una descripción del algoritmo IDA* es la siguiente:
 

1- Se asigna a UMBRAL la evaluación heurística del estado inicial 2- Se realiza una búsqueda DFS podando las ramas cuya función f=g+h exceda el UMBRAL. Si durante la búsqueda se encuentra un camino a una solución devolverlo y terminar. 3- Si no se encontró una solución, incrementar UMBRAL con la menor diferencia encontrada en el paso anterior, y volver al paso 2.

El algoritmo IDA* puede describirse de la siguiente manera: Función IDA* retorna CAMINO
comienzo

// FUmbral se utiliza para acotar la búsqueda en una iteración dada // NuevoFUmbral será devuelta luego de cada iteración indicando el nuevo // valor de umbral para la siguiente búsqueda (> FUmbral)// NuevoFUmbral se inicializa con la evaluación del estado inicial NuevoFUmbral := F (EstadoInicial); // FUmbral se inicializa con un valor ficticio menor que NuevoFUmbral FUmbral := NuevoFUmbral - 1; // La solución se inicializa como Nula // Si de una iteración a otra no se ha encontrado solución y FUmbral es // igual a NuevaFUmbral, la búsqueda debe terminar pues no hay solución Solución := NULA; mientras (Solución = NULO) AND (FUmbral < NuevoFUmbral)
FUmbral := NuevoFUmbral; retorna := DFS (EstadoInicial, FUmbral); Solución := retorna.CAMINO; NuevoFUmbral := retorna.UMBRAL;
fin mientras;devolver Solución;

fin IDA*; DFS (EstadoActual,Umbral) retorna CAMINO + UMBRAL+ ENCUENTRA: bool
Comienzo

    resultado.CAMINO := NULO;    Si EstadoFinal(EstadoActual) entonces     // se encontro solución
resultado.UMBRAL := F(EstadoActual); resultado.ENCUENTRA := TRUE; devolver resultado;
    Sino
resultado.UMBRAL := Umbral; resultado.ENCUENTRA := FALSE;Sucesores := CalcularSucesores (EstadoActual); Si EstaVacia(Sucesores) entonces // el estado no es solucion y no tiene sucesores, acaba sin solucion
 devolver resultado;
Sino
MinUmbral := Umbral;por cada sucesor de Sucesores
// Calcular la función heurística FSucesor := F (sucesor);Si FSucesor > Umbral entonces // se poda el sucesor pues su f excede el umbral
Si FSucesor < MinUmbral entonces  // se actualiza el minimo umbral mayor que Umbral
  MinUmbral := FSucesor;
Fin si;
 Sino // se explora sucesor que no excede umbral
resultSuc = DFS (sucesor, Umbral);Si resultSuc.ENCUENTRA entonces  // devolver solucion encontrada
resultado.CAMINO := sucesor + resultSuc.CAMINO; resultado.ENCUENTRA := TRUE; devolver resultado;
Sino Si (resultSuc.UMBRAL<MinUmbral) AND (resultSuc.UMBRAL >Umbral) entonces  // actualizar el minimo umbral
MinUmbral := resultSuc.UMBRAL;
Fin sino si;
Fin sino;
 Fin por; resultado.UMBRAL := MinUmbral; devolver resultado;  
Fin Sino;
    Fin Sino;

Fin DFS; NOTA: este algoritmo es ligeramente diferente al dado en la teórica. En primer lugar devuelve una estructura que contiene la variable booleana ENCUENTRA. Esta versión contempla que se llegue a un estado que no es solución y que no tiene sucesores, en cuyo caso se debe retornar un valor FALSE en el campo ENCUENTRA
La función F devuelve la evaluación de la función heurística f=g+h de un estado.
Siendo h una heurística admisible, al igual que A* el algoritmo IDA* garantiza que se encuentra la solución óptima si esta existe.