PDF de programación - Algoritmo Minimax

INSTITUTO TECNOLOGICO DE NUEVO LAREDO

INGENIERIA EN SISTEMAS COMPUTACIONALES

INTELIGENCIA ARTIFICIAL



IMPARTE: ING. BRUNO LÓPEZ TAKEYAS

TEMA: ALGORITMO MINIMAX

EQUIPO1:

CENICEROS VAZQUEZ MARTHA DEYANIRA JAZMIN

RAMÍREZ RUIZ OCTAVIO

TORRES COLUNGA MARÍA DEL CARMEN

URIETA ACEVEDO BEATRIZ

VEGA HERNÁNDEZ MARGARITA ELIZABETH

NUEVO LAREDO, TAMAULIPAS., A 17 DE OCTUBRE DEL

2005

Motivación para el estudio de los juegos ………………………………………….....4
Características……………………………………………………………………….. 4
Elementos del juego…………………………………………………………………..5
Topologías del proceso de búsqueda …………………………………………………5
Búsqueda en el árbol………………………………………………………………….5
Representación del conocimiento…………………………………………………….6


INTRODUCCIÓN……………………………………………………………………………3

DEFINICIÓN…………………………………………………………………………………3

REPRESENTACIÓN DE LOS JUEGOS



EJEMPLO DE LA ESTRUCTURA DE UN ÁRBOL PARA EL ALGORITMO
MINIMAX……………………………………………………………………………………7

PASOS DEL ALGORITMO MINIMAX…………………………………………………….8

CALCULO DE VALORES DE LA FUNCIÓN DE UTILIDAD……………………………9

EJEMPLO DE APLICACIÓN.……………………………………………………………...10

BIBLIOGRAFIA…………………………………………………………………………….16



CONTENIDO



2



ALGORITMO MINIMAX

INTRODUCCIÓN


Los juegos son uno de los campos de trabajo más antiguos de la IA.

En 1950, casi, en cuanto fue posible programar las computadoras, Claude Shannon, inventor
de la teoría de la información Basado en la teoría de juegos de Von Neumann y O.
Morgenstern, y Alan Turing elaboró el primer programa de ajedrez en 1951. Desde entonces,
se han realizando continuos avances en el juego, al grado de que los sistemas actuales son
capaces de desafían a campeones mundiales humanos sin temor de que puedan hacer el
ridículo.

Los primeros investigadores eligieron para su trabajo al ajedrez por varias razones. Una
computadora capaz de jugar ajedrez seria la prueba viviente de una máquina que podía realizar
algo para la que se consideraba era necesario tener inteligencia. Además, la sencillez de las
reglas, y el hecho de que el programa pueda acceder totalmente al estado del mundo significa
que es fácil representará Juego como una búsqueda a través de un espacio de posibles
posiciones de juego.

La presencia de un oponente complica más el problema de decisión. El oponente introduce la
incertidumbre, puesto que es imposible saber qué va a hacer. El contrincante se esforzará todo
lo que pueda porque sus jugadas sean lo menos benignas para su oponente.

Pero lo que singulariza realmente a los juegos es que por lo común es excesivamente difícil
resolverlos. El ajedrez, por ejemplo, tiene un factor de ramificación promedio de 35; las
partidas frecuentemente llegan a 50 jugadas por cada contrincante, por lo que el árbol de
búsqueda tiene 35100 nodos (aunque haya "sólo" aproximadamente 1040 posiciones legales
distintas). La complejidad de los juegos trae aparejado un tipo de incertidumbre totalmente
nuevo, no visto hasta ahora; la incertidumbre no es consecuencia de la información faltante,
sino debido a que no hay tiempo suficiente para calcular las consecuencias exactas de una
jugada. Sólo se intenta deducir lo que seria lo mejor con base en experiencias pasadas y
proceder, sin estar completamente seguro de cuál seria la mejor acción. En este sentido, los
juegos se asemejan más al mundo real.



DEFINICIÓN


El algoritmo Minimax es un método de decisión para minimizar la pérdida máxima esperada
en juegos con adversario y con información perfecta.

El funcionamiento de Minimax puede resumirse como elegir mejor movimiento para ti mismo
suponiendo que tu contrincante escogerá el peor para ti.



3

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.

El funcionamiento de Minimax puede resumirse a como elegir el mejor movimiento para ti
mismo; suponiendo que tu contrincante escogerá el peor para ti.

Ofrece la siguiente gran ventaja matemática: supone que el adversario ha de jugar
óptimamente pero no suboptimamente. Como hay muchísimas maneras de jugar mal y sólo
una manera de jugar bien (aunque de vez en cuando puede haber dos jugadas indistinguibles
en su ventaja comparativa), esta postura quita toda incertidumbre a lo que va a hacer el
adversario.

El espacio de estados se representa mediante árboles alternados, donde:

• Nodo: representa una situación del juego
• Sucesores de un Nodo: Situaciones del juego a las que se accede por movimientos

legales aplicando sus reglas

• Nivel: Contiene todas las situaciones posibles para cada uno de los jugadores.


El algoritmo Minimax es un procedimiento recursivo y el corte de la recursión esta dado por
las siguientes condiciones:

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



REPRESENTACIÓN DE LOS JUEGOS


MOTIVACION PARA EL ESTUDIO DE LOS JUEGOS


• Crear programas de ordenador para jugar.
• Emular el razonamiento humano en un ordenador.
• Construir sistemas que sean capaces de tomar decisiones en un entorno adverso.


CARACTERISTICAS


• Juegos bipersonales.
• Los jugadores mueven alternativamente.
• La ventaja para un jugador es desventaja para el otro.
• Los jugadores poseen toda la información sobre el estado del juego.
• Hay un número finito de estados y decisiones.
• No interviene el azar (dados, cartas).



4



ELEMENTOS DEL JUEGO

Jugadores:

• MIN: Humanos.
• MAX: Maquinas.

Los juegos bipersonales se representan con:

• Estados iniciales. Que incluye la configuración inicial del tablero y una indicación del

• Un conjunto de operadores. Que definen los movimientos legales que los jugadores

jugador que comienza moviendo.

pueden realizar.

• Prueba terminal. que determina los casos en que el juego ha finalizado. Los estados en

los que el juego ha finalizado constituyen el conjunto de estados terminales.

• Función de evaluación estática. Asigna un valor numérico al resultado del juego.

Nodos:

• Tablero+jugador+valor

Movimientos:

• Generar movimientos.
• Verificar el movimiento humano.
• Procedimiento de decisión de la maquina.

TOPOLOGIAS DEL PROCESO DE BUSQUEDA

Dependiendo de la estructura que definan los operadores el espacio de estados puede ser:
Un árbol.

- más sencillo de manejar.
- Más consumo de memoria (estados duplicados).

Un gafo (con o sin ciclos).
- Ahorro de memoria.
- Generaciones complejas (comprobar existencia de estados).



BUSQUEDA EN EL ARBOL

Mecanismos de búsqueda:

Resulta necesario recorrer el árbol y existen dos formas básicas para hacer esto:
El recorrido en verde refleja una búsqueda a profundidad mientras que el recorrido azul refleja
una búsqueda hecha a amplitud primero.



5





Consideremos que el nodo ganador del juego es el verde y el rojo el perdedor.

Una solución más interesante es la de hacer una búsqueda con cierto conocimiento (una
implicación) más que con información, por que si ya sabemos como llegar no tiene sentido
que le ande dando vuelta por las ramas.

La forma de obtener conocimiento ya lo sabemos es a través de una función evaluadora
SUMATORIA ( c*X^n ) }que nos estime que tan lejos o que tan cerca estoy del lado bueno
como se muestra a continuación:

El diagrama como tal desea indicar que para llegar al nodo verde ganador debe ser posible
conocer que tan verde es nuestro camino, y por el otro lado que tan rojo es. Esto una vez mas
es conocimiento que inyecto al sistema por medio de la función que me indica entonces el



6

manejo de
IF x THEN y.

la

implicación: Ante un Antecedente Entonces un Consecuente

Representación del conocimiento.

Esto se logra por medio de estructuras de datos que almacenen cuando menos la siguiente
información:

• Para cada Estado
• Numero [ Integer ]
• Representación [ "oxo---xxo" ]
• Formula de evaluación [ Suma ( c X n ) ]
• Reglas de transferencia para otros estados [ p ---> px ]
• Tipo de Estado [ ganador, perdedor, prohibido ]
• Elementos [ jugadores, tablero ]

MINIMAX

Esta es solo una lista inicial, en realidad la forma genérica de esta representación es una
gramática libre de contexto



EJEMPLO DE LA ESTRUCTURA DE UN ÁRBOL PARA EL ALGORITMO



• El nodo raíz representa la posición de inicio del tablero.
• Cada nivel representa el turno.
• Cada círculo representa una jugada.



7



PASOS DEL ALGORITMO MÍNIMAX


1. Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado
terminal.
2. Cálculo de los valores de la función de utilidad para cada nodo terminal.
3. Calcular el valor de los nodos superiores a partir del valor de los inferiores.
Alternativamente se elegirán los valores mínimos y máximos representando los movimientos
del jugador y del oponente, de ahí el nombre de Minimax.
4. Elegir la jugada valorando los valores que han llegado al nivel superior.



alcanza.

• El algoritmo explorará los nodos del árbol asignándoles un valor numérico mediante
una función de utilidad, empez