PDF de programación - MiniMax - Inteligencia Artificial - Ingeniería en sistemas computacionales

INSTITUTO TECNOLOGICO DE NUEVO LAREDO

Ingeniería en Sistemas Computacionales



Inteligencia Artificial



Ing. Bruno López Takeyas



Arturo Alejandro Castro

Nadia Alejandro Castro
Graciela Teresa García Vizcaya

Maria de los Ángeles Hernández
Maria Luisa Torres Lara



01100157
01100158
01100214
01100227
01100310

Nuevo Laredo, Tam., a 17 de Octubre del 2005.



AAllggoorriittmmoo



IInnttrroodduucccciióónn

Los juegos han ocupado la atención de las facultades intelectuales del ser
humano, en ocasiones en grado alarmante. Juegos de tablero, como el
ajedrez y el Go, en parte son interesantes debido a que en ellos se libra una
lucha pura, abstracta, sin tener que pasar los trabajos y penas que implica
organizar dos ejércitos y, con ellos, librar batallas. Esta característica de
abstracción es los que hace atractivos a los juegos para la Inteligencia
Artificial.

Al hablar de estrategias de búsqueda de soluciones, consideramos al
algoritmo Minimax como uno de los más importantes y de éste existen
muchas variaciones donde intervienen diversos factores dependiendo de la
naturaleza del juego y sus reglas.

A continuación se verá una explicación de ¿qué es el algoritmo Minimax? Y
así como la estructura utilizada, sus funciones y una descripción de su
funcionamiento.

También se verá de manera mas clara este funcionamiento aplicando el
algoritmo en un juego imaginario.

Más adelante se encuentra una sección donde se muestran ejemplos de
juegos donde se aplica el algoritmo Minimax.


IInntteelliiggeenncciiaa AArrttiiffiicciiaall

22

AAllggoorriittmmoo



RReesseeññaa hhiissttóórriiccaa

TTeeoorrííaa ddee jjuueeggooss

Para hablar de la historia de minimax hay que empezar con la teoría de juegos, por
que de ahí se deriva este algoritmo de búsqueda para juegos de dos participantes.

La teoría de juegos o solo se refiere a juegos de tablero o de cartas, puede referirse
a situaciones donde hay algo que negociar, o inclusive la guerra.

Un juego puede ser cualquier situación en la que intervienen dos actores o
jugadores, en donde los intereses de los mismos están interconectados o
interdependientes.

Los jugadores, se asume que son racionales ya que buscan maximizar sus
utilidades, esto quiere decir que en un juego un jugador tratará de actuar de la
manera que más le convenga y vaya de acuerdo con sus intereses, y de igual
manera lo hará su oponente.

La teoría de juegos es usada incluso por los militares para resolver problemas de
logística o tácticos. Pero la teoría de juegos va mucho más allá, puede ser
considerada descriptiva y positiva, capaz de explicar y predecir. Puede aplicarse a
conducta humana, conducta social, economía, milicia o política.

En teoría de juegos se consideran pioneros a Emile Borel, Oskar Morgenster y John
Von Neumman, este último es el creador del teorema Minimax.

La teoría de juegos tiene un teorema fundamental, que es el teorema de Minimax
cuyo creador es John Von Neumman.



Teorema Minimax

John Von Neumman, en un famoso artículo publicado en 1928, presento una
solución aplicable a una amplia clase de juegos. Considérese el juego que se
ejemplifica en la figura de abajo, que involucra a dos jugadores. Las interacciones
que realizan son conocidas como juegos de suma cero, por que la suma de los
puntos de cada resultado es igual a cero. John Von Neumman estudio estos juegos
y probó que pueden ser resueltos en la misma manera.



R1

R2

R3



C1

-2,2

-1,1

-8,8

C2

1,-1

2.-2

0,0

C3

10,-10

0,0

-15,15


IInntteelliiggeenncciiaa AArrttiiffiicciiaall

33



La solución propuesta por Von Neumman esta basada en la idea de que cada
jugador debe maximizar el valor del peor resultado posible. De esa manera:

AAllggoorriittmmoo

oo Si R escoge R1, el peor resultado es -2, que ocurre cuando C juega con C1.
oo Si escoge R2, el peor resultado es -1 cuando C escoge C1.
oo Finalmente, el peor resultado para R si escoge R3 es –a5 cuando C opta por

C3.

De estos malos resultados, el mejor de R es el -1 que se obtiene cuando juega con
R1. Esto es llamado la estrategia maximin de E, esto es, R maximiza su mínimo.
Debido a esto, la estrategia maximin de R es dada por R1 con un resultado de -1.
Investigando las opciones de C para la misma perspectiva, obtenemos la estrategia
C1 como su maximin con un resultado de +1.

Hay que hacer notar que la suma de los valores maximin de los dos jugadores es
igual a cero. Debido a esto el teorema de John Von Neumman esta en todos los
juegos de suma cero, esto es en cada juego de dos personas con interacción de
suma cero, la suma de los valores maximin de los jugadores es igual a cero.

La razón por la que Von Neumman pensó que los jugadores podían racionalmente
escoger ser tan pesimistas esta relacionada con su teorema. Hay que recordar que
en un juego de suma cero tu triunfo es el fracaso del otro y viceversa. Ser
pesimista significa, en el contexto de los juegos de suma cero que el jugador es
realista y que esta conciente de el hecho de que su oponente siempre tratará de
hacer el máximo daño posible a él. ¿Por qué? , por la razón de que el triunfo de uno
significa la pérdida del otro.

John Von Neumman estaba convencido de que ningún jugador racional jugaría por
menos de lo que le permita tener el resultado maximin mejor, y que si los dos
jugadores estaban determinados a evitar un resultado debajo de su maximin,
ninguno esperaría recibir o trataría de recibir más que su resultado maximin.



Teoría del Equilibrio

Hay que hacer notar que la solución maximin es la misma que el la teoría del
equilibrio de Nash, ya que la suma de los valores maximin de los jugadores debe
ser igual a cero. Siempre habrá un positivo y un negativo.

John Nash a los 21 años escribió una tesis de menos de treinta páginas en la que
expuso por primera vez su solución para juegos estratégicos no cooperativos, lo
que desde entonces se llamó "el equilibrio de Nash", que tuvo un inmediato
reconocimiento entre todos los especialistas.

El punto de equilibrio de Nash es una situación en la que ninguno de los jugadores
siente la tentación de cambiar de estrategia ya que cualquier cambio implicaría una
disminución en sus pagos. Von Neumann y Oskar Morgenstern habían ya ofrecido
una solución similar pero sólo para los juegos de suma cero. Para la descripción


IInntteelliiggeenncciiaa AArrttiiffiicciiaall

44



formal del problema y su solución, Nash utilizó funciones de mejor respuesta y el
teorema del punto fijo de los matemáticos Brouwer y Kakutani.

AAllggoorriittmmoo

En los años siguientes publicó nuevos escritos con originales soluciones para algunos
problemas matemáticos y de la teoría de juegos, destacando la "solución de regateo de
Nash" para juegos bipersonales cooperativos. Propuso también lo que se ha dado
en llamar "el programa de Nash" para la reducción de todos los juegos cooperativos
a un marco no cooperativo.



Claude Shannon

Claude Shannon es considerado el principal en utilizar el concepto de Minimax,
además de la teoría de información y la negentropía.

Claude Elwood Shannon (30 de abril de 1916 (Michigan) - 24 de febrero de 2001)
recordado como "el padre de la teoría de la información".

Los primeros años de su vida los pasó en Gaylord, donde se graduó de la
secundaria en 1932. Desde joven, Shannon demostró una inclinación hacia las
cosas mecánicas. Resaltaba respecto a sus compañeros en las asignaturas de
ciencias. Su héroe de la niñez era Edison, a quien luego se acercó bastante en sus
investigaciones.

En 1932 ingresó en la Universidad de Michigan, siguiendo a su hermana Catherine,
Doctora en matemáticas. En 1936 obtuvo los títulos de ingeniero eléctrico y
matemático. Su interés por las matemáticas y la ingeniería continuó durante toda
su vida.

En 1936 aceptó la posición de asistente de investigación en el departamento de
ingeniería eléctrica en el Instituto de Tecnología de Massachusetts (MIT). Su
situación le permitió continuar estudiando mientras trabajaba por horas para el
departamento, obteniendo como resultado la calculadora más avanzada de esa era.

En ese momento surgió su interés hacia los circuitos de relevadores complejos,
sumado a su gusto por la lógica y el álgebra boleana. Estos nuevos intereses pudo
desarrollarlos durante el verano de 1937, que pasó en los laboratorios Bell en la
ciudad de Nueva York.

En su tesis doctoral en el M.I.T., demostró cómo el álgebra boleana se podía utilizar
en el análisis y la síntesis de la conmutación y de los circuitos digitales. La tesis
despertó un interés considerable cuando apareció en 1938 en las publicaciones
especializadas. En 1940 le fue concedido el Premio a ingenieros americanos del
Instituto Americano Alfred Nobel de Estados Unidos, una concesión dada cada año a
una persona de no más de treinta años. Un cuarto de siglo más tarde H. H.
Goldstine, en su libro "Las computadoras desde Pascal hasta Von Neumann", citó su
tesis como una de las más importantes de la historia... que ayudó a cambiar el
diseño de circuitos digitales.


IInntteelliiggeenncciiaa AArrttiiffiic