Aplicación: El Juego del Gato

• Dos jugadores MIN y MAX
• Los jugadores colocan fichas
en un tablero de 3 X 3
• MAX usa las fichas X
• MIN usa las fichas O

• Reglas:
• Inicialmente el tablero está
vacío
• MAX empieza y se alternan
los movimientos

 • MAX gana si obtiene una
línea de 3 X’s
• MIN gana si obtiene una
línea de 3 O’s
• Existe la posibilidad de
empate





Espacio de estados para el juego del gato

Procedimiento
• Se desarrolla una búsqueda por niveles, generando los nodos del cada nivel
• Se aplica una función de evaluación a cada nodo
• La función de evaluación considera los siguientes factores:
            o Número de casillas restantes
            o Posición de casillas vacías
• La función de evaluación devolverá los siguientes valores:
            o Positivos altos: Si la situación de uno de los jugadores es ventajosa
            o Negativos altos: Si la situación del otro jugador es ventajosa
            o Cero: Si ninguno de los jugadores tiene ventaja

Función de evaluación para el juego del gato
• Si s no es ganadora para cualquiera de los jugadores (MAX o MIN),
-->Si s es ganadora para el jugador MAX
           f(s)=No. filas abiertas para MAX - No. Filas,
                   columnas o diagonales abiertas para MIN
-->Si s es ganadora para el jugador MIN
           f(s)= No. Líneas que no contiene una “O” – No.
                    Líneas que no contienen una “X

esto es:  

Si s es ganadora para el jugador MAX

           f(s)= -∞ (mayor número negativo posible)

Si s es ganadora para el jugador MIN

           f(s)= -∞ (mayor número negativo posible)

-->MAX elegirá los nodos de mayor
evaluación 

--> MIN elegirá los nodos de menor
evaluación

tomado de: http://www.itnuevolaredo.edu.mx/takeyas

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.

Refinamientos adicionales

Espera del reposo
Cuando la condición de corte de la recursión del algoritmo MINIMAX está basada sólo en la profundidad fija del árbol explorado, puede darse el llamado efecto horizonte. Esto ocurre cuando se evalúa como buena o mala una posición, sin saber que en la siguiente jugada la situación se revierte.
La espera del reposo ayuda a evitar el efecto horizonte. Una de las condiciones de corte de recursión en el algoritmo MINIMAX debería ser el alcanzar una situación estable. Si se evalúa un nodo de un árbol de juego y este valor cambia drásticamente al evaluar el nodo después de realizar la exploración de un nivel más del árbol, la búsqueda debería continuar hasta que esto dejara de ocurrir. Esto se denomina esperar el reposo y nos asegura que las medidas a corto plazo, por ejemplo un intercambio de piezas, no influyen indebidamente en la elección.


FIGURA 4.a                   FIGURA 4.b                 FIGURA 4.c En la figura 4.a la evaluación del nodo B tiene el valor 6 explorando sólo un nivel del árbol. Si se explora un nivel más, la evaluación da un valor de -4, como se muestra en la figura 4.b. Esto denota un cambio muy drástico de evaluación del nodo B. Por esto, se decide explorar un nivel más el árbol (figura 4.c) resultando en una evaluación de 6.2, la cual no difiere mucho de la evaluación inicial. En este nivel podría determinarse abandonar la exploración debido a la situación de reposo alcanzada.

Búsqueda secundaria
Otra manera de mejorar el procedimiento MINIMAX es realizar una doble comprobación del movimiento elegido, para asegurarnos que no hay una trampa algunos movimientos más allá de los que exploró la búsqueda inicial.
Luego de haber elegido un movimiento en concreto con un procedimiento MINIMAX que explora n niveles, la técnica de búsqueda secundaria realiza una búsqueda adicional de d niveles en la única rama escogida para asegurar que la elección sea buena.
Extensiones singulares
Cuando una captura es inminente, a menudo sólo una jugada tiene sentido y por esto se denomina forzada. En situaciones de jugada forzada, el nodo hijo que implica la captura tiene en general un valor estático que sale del resto.
La heurística de extensión singular establece que la búsqueda debe continuar mientras que el valor estático de la jugada indique una probable captura. Si se considera que un nodo hoja es muy diferente a sus hermanos, el nodo se expande una capa más.


En la figura 5.a el nodo B tiene claramente un valor superior al resto de sus hermanos, indicando una probable captura de piezas. En el movimiento siguiente, nuevamente hay una captura de piezas pero esta vez por parte del oponente, según se muestra en la figura 5.b en donde el nodo E contiene un valor muy diferente al de sus hermanos. En la figura 5.c se muestra un nivel más del árbol, en el cual no existe una jugada forzada puesto que todos los movimientos tienen valores estáticos comprendidos en un intervalo estrecho. Por tanto, la heurística de extensión singular recomienda que no se efectúe más la búsqueda.
La computadora de propósito especial DEEP THOUGHT (Anantharaman, 1990) juega al ajedrez utiliza un esquema de búsqueda con extensiones singulares. Normalmente es capaz de buscar hacia abajo hasta alrededor de 10 niveles. Mediante la heurística de extensiones singulares la computadora va más allá, buscando combinaciones de mate en mitad del juego que incluyen hasta 37 movimientos. El evaluador estático considera conteo de piezas, colocación de éstas, estructura de peones, peones perdidos y ordenamiento de peones y torres en columnas
 
Uso de movimientos de libro
La solución ideal de un juego sería seleccionar un movimiento consultando la configuración actual en catálogo y extrayendo el movimiento correcto. Naturalmente en juegos complicados esto es imposible de realizar, pues la tabla sería muy grande y además nadie sabría construirla.
Sin embargo, este enfoque resulta razonable para algunas partes de ciertos juegos. Se puede usar movimientos de libro en aperturas y finales, combinando con el uso de búsqueda MINIMAX para la parte central de la partida, mejorando el rendimiento del programa. Por ejemplo, las secuencias de apertura y los finales del ajedrez están altamente estudiados y pueden ser catalogados.
Búsqueda sesgada
Una forma de podar un árbol de juegos es hacer que el factor de ramificación varíe a fin de dirigir más esfuerzo hacia las jugadas más prometedoras.
Se puede realizar una búsqueda sesgada clasificando cada nodo hijo, quizás mediante un evaluador estático rápido y luego utilizando la siguiente fórmula:
R(hijo) = R(padre) - r(hijo)
donde R es el número de ramas de un nodo y r es el lugar que ocupa un nodo entre sus hermanos ordenados según la evaluación estática rápida.

Refinamientos adicionales

Refinamientos adicionales

La efectividad del procedimiento alfa-beta depende en gran medida del orden en que se examinen los caminos. Si se examinan primero los peores caminos no se realizará ningún corte. Pero, naturalmente, si de antemano se conociera el mejor camino no necesitaríamos buscarlo.

La efectividad de la técnica de poda en el caso perfecto ofrece una cota superior del rendimiento en otras situaciones. Según Knuth y Moore (1975), si los nodos están perfectamente ordenados, el número de nodos terminales considerados en una búsqueda de profundidad d con alfa-beta es el doble de los nodos terminales considerados en una búsqueda de profundidad d/2 sin alfa-beta. Esto significa que en el caso perfecto, una búsqueda alfa-beta nos da una ganancia sustancial pudiendo explorar con igual costo la mitad de los nodos finales de un árbol de juego del doble de profundidad.

En esta sección se describen otras modificaciones del procedimiento MINIMAX que también mejoran su rendimiento.

2.3.3.1. Poda de inultilidades

La poda de inutilidades es la finalización de la exploración de un subárbol que ofrece pocas posibilidades de mejora sobre otros caminos que ya han sido explorados.


En el ejemplo de la figura 3, después de examinar el nodo B el jugador maximizante se asegura un valor de 3. Al examinar el nodo G se obtiene un valor 3.1 que es sólo algo mejor que 3. Puesto que si se exploran los nodos H e I no lograremos mejorar este valor desde el punto de vista del jugador maximizante, sería mejor podarlos y dedicar más tiempo a explorar otras partes del árbol donde se puedan obtener más ventajas.

Poda alfa-beta de la búsqueda Minimax

Poda alfa-beta de la búsqueda Minimax

Los procedimientos de búsqueda en profundidad (DFS) pueden mejorar su eficiencia usando una técnica de branch and bound (ramificación y acotación), con la cual una solución parcial se abandona cuando se comprueba que es peor que otra solución conocida o umbral.

La estrategia de poda del algoritmo Minimax es llamada poda alfa-beta, puesto que dado que existen dos jugadores maximizador y minimizador, existen dos valores umbral alfa y beta para acotar la búsqueda de cada uno respectivamente.


El valor alfa representa la cota inferior del valor que puede asignarse en último término a un nodo maximizante.
El valor beta representa la cota superior del valor que puede asignarse en último término a un nodo minimizante.

La figura 2 muestra la aplicación de la poda alfa-beta al ejemplo de la figura 1. La evaluación del nodo E asegura al oponente (jugador minimizante) una cota superior con valor 7, es decir, el oponente obtendrá 7 o un valor menor en la evaluación de B (dado que los valores están en relación al jugador maximizante, los valores menores a 7 son mejores para el oponente). En este caso, 7 representa el valor beta. A continuación, cuando se examina el nodo N cuyo valor es 8, dado que es mayor que beta (7), los nodos hermanos de N (en este caso el nodo O) pueden podarse (dado que nos hallamos en un nivel maximizante, el nodo F tendrá un valor igual o superior a 8, y por lo tanto no podrá competir con la cota asegurada beta en el nivel minimizante anterior).

Luego de evaluar los sucesores de B, se concluye que este nodo asegura al jugador maximizante una cota inferior con valor 3, es decir, obtendrá 3 o un valor mayor en la evaluación de A. En este caso, 3 representa el valor de alfa. A continuación, cuando se examina el nodo H cuyo valor es 0, dado que es menor que alfa (3), los nodos hermanos de H (en este caso el nodo I) pueden podarse (dado que nos hallamos en un nivel minimizante, el nodo C tendrá un valor menor o igual a 0, y por lo tanto no podrá competir con la cota asegurada alfa en el nivel maximizante anterior).
FIGURA 2

En un nivel dado, el valor de umbral alfa o beta según corresponda, debe actualizarse cuando se encuentra un umbral mejor. En el ejemplo anterior, al obtenerse el valor 8 del nodo D se puede actualizar el valor de alfa (3) a alfa (8). Esto tendría sentido en el caso de que existieran otros nodos hermanos de D que pudieran ser podados utilizando este valor de alfa. Análogamente, al obtenerse un valor de 3 en el nodo G se puede actualizar el valor de beta (7) a beta (3). Esto tendría sentido en el caso de que existieran otros nodos hermanos G que pudieran ser podados utilizando este valor de beta.

El algoritmo MINIMAX_ALFABETA evita esta diferenciación utilizando dos valores de umbral, uno que usa efectivamente como umbral (umbralUSO) y otro que debe pasar al nivel siguiente para ser usado (umbralPASO). En un nivel dado, uno de los valores es usado para realizar posibles podas de nodos hijos (umbralUSO), y mientras tanto se va actualizando el valor de umbral del nivel anterior (umbralPASO).

La primera llamada a la función recursiva será:

MINIMAX_ALFABETA (posiciónactual, 0, JUGADOR-UNO, MAXINT, MININT)

El algoritmo MINIMAX con poda ALFABETA es el siguiente:

MINIMAX_ALFABETA( posición, profundidad, jugador, umbralUSO, umbralPASO)
comienzo

Si SUFICIENTE (posición, profundidad) entonces
resultado.VALOR := ESTATICA (posición, jugador);
resultado.CAMINO := NULO;
return resultado; sino
Sucesores := GENMOV (posición, jugador);
Si EstaVacia (Sucesores) entonces
resultado.VALOR := ESTATICA (posición, jugador);
resultado.CAMINO := NULO;
return resultado; sino
por cada sucesor de Sucesores
resultadoSucesor := MINIMAX_ALFABETA (sucesor, profundidad+1, CONTRARIO(jugador), -umbralPASO, -umbralUSO);

// el mejor resultado se va guadando en umbralPASO
Si umbralPASO < - resultadoSucesor.VALOR entonces umbralPASO := - resultadoSucesor.VALOR; resultadoMejor.CAMINO := sucesor + resultadoSucesor.CAMINO; fin si; // umbralUSO se usa para podar los hermanos Si umbralPASO >= umbralUSO entonces
resultadoMejor.VALOR := umbralPASO;
return resultadoMejor; finsi; fin por;
resultadoMejor.VALOR := umbralPASO;
return resultadoMejor; fin sino; fin sino;

fin MINIMAX_ALFABETA;

Pseudocodigo simple para el algoritmo minimax

El algoritmo MINIMAX es el siguiente:
MINIMAX( posición, profundidad, jugador)
comienzo

Si SUFICIENTE (posición, profundidad) entonces
resultado.VALOR := ESTATICA (posición, jugador); resultado.CAMINO := NULO; return resultado;
sino
Sucesores := GENMOV (posición, jugador); Si EstaVacia (Sucesores) entonces
resultado.VALOR := ESTATICA (posición, jugador); resultado.CAMINO := NULO; return resultado;
sino
resultadoMejor.VALOR := MININT; por cada sucesor de Sucesores
resultadoSucesor := MINIMAX (sucesor, profundidad+1, CONTRARIO (jugador)); Si resultadoMejor.VALOR < - resultadoSucesor.VALOR entonces
resultadoMejor.VALOR := - resultadoSucesor.VALOR; resultadoMejor.CAMINO := sucesor + resultadoSucesor.CAMINO;
fin si;
fin por; return resultadoMejor;
fin sino;
fin sino;

fin MINIMAX;

Explicacion sencilla de en qué consiste el algoritmo minimax

En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento de búsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada.
La idea consiste en comenzar en la posición actual y usar el generador de movimientos plausibles para generar las posibles posiciones sucesivas hasta un cierto límite de niveles. A continuación se aplica la función de evaluación estática a las posiciones obtenidas y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores.
Se supone una función de evaluación estática que devuelve valores elevados para indicar buenas situaciones y valores negativos para indicar buenas situaciones para el oponente. Visto de esta manera, la meta es maximizar el valor de la función estática de la siguiente posición de tablero.
El nombre del algoritmo deriva de considerar que, dada una función estática que devuelve valores en relación al jugador maximizante, éste procura maximizar su valor mientras que su oponente procura minimizarlo. En un árbol de juego donde los valores de la función estática están en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro. La figura 1 muestra un ejemplo donde  la elección del siguiente movimiento según la búsqueda Minimax de tres niveles sería el nodo D.
El algoritmo Minimax es un procedimiento recursivo, y el corte de la recursión está dado por alguna de las siguientes condiciones:

• Gana algún jugador
• Se han explorado N capas, siendo N el límite establecido
• Se ha agotado el tiempo de exploración
• Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro

En el algoritmo MINIMAX detallado en breve la función de corte de recursión SUFICIENTE (posición, profundidad) sólo considera las dos primeras condiciones de corte.




El algoritmo MINIMAX( posición, profundidad, jugador) usa dos funciones:
 

• GENMOV (posición, jugador): devuelve la lista de movimientos posibles para el jugador a partir de la posición
• ESTÁTICA (posición, jugador): devuelve un número que representa la bondad de la posición desde el punto de vista de jugador.

A diferencia de los valores mostrados en el ejemplo de la figura 1, la función ESTÁTICA devuelve valores en relación al jugador actual en vez del jugador maximizante. Por esta razón, en lugar de realizar maximización y minimización alternativas, siempre se maximiza el valor que devuelve esta función. El algoritmo MINIMAX no necesita tratar diferente a los niveles maximizante y minimizante dado que invierte los valores de un nivel a otro.
La función Minimax devuelve una estructura con

• VALOR: valor propagado de la función estática
• CAMINO: camino para llegar a la solución desde la posición

La primera llamada a la función recursiva será: MINIMAX (posiciónactual, 0,  JUGADOR-UNO)