Resumen—
La
capacidad de las maquinas para responder a la interacción con el ser
humano hacen que cualquiera caiga en el asombro. Hoy en día contamos
con sistemas muy inteligentes capaces de sostener conversaciones en
tiempo real imitando las respuestas humanas. En ese mismo campo
existen programas capaces de jugar con autonomía y proponer retos
para nosotros. El siguiente articulo contiene información sobre la
IA aplicada en el famoso juego Tic-tac toe o tres en raya.
Palabras
clave— Inteligencia
artificial, minimax, tic-tac toe.
-
INTRODUCCIÓN
En
siguiente trabajo presenta la aplicación del algoritmo Minimax para
la implementación del juego tic-tac toe. Si bien los juegos humanos
vs humanos pueden generan gran entretenimiento, una vez superada la
linea profesional ese entretenimiento suele caer al piso al no
encontrar adversarios dignos de nuestro nivel. Por ello se
desarrollaron dentro del mundo de la programación algoritmos capaces
de generar gran dificultad en los juegos y así nació la modalidad
humano vs maquina.
-
CONTENIDO
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.
MINIMAX
realiza una exploración del árbol de búsqueda, de manera que el
jugador que debe mover en primer lugar (MAX) tiende a elegir en cada
unos de sus movimientos aquel camino que le conduzca a un nodo
frontera con el mayor valor posible de la función de evaluación
heurística. La estrategia del otro jugador (MIN) es la contraria, ya
que tendrá que contrarrestar las decisiones de MAX.
Procedimiento
MINIMAX:
MINIMAX(m,profundidad,jugador)
-
Si m no tiene sucesores o si se considera que m ha alcanzado el limite de profundidad,devolver fev(m) si m es un nodo MAX. En las mismas condiciones anteriores, devolver -fev(m) si m es un nodo MIN.(Para nosotros fev(m) representa lo prometedor que es el nodo m para MAX, independientemente de si m es un nodo MAX o MIN).
-
Generar los sucesores m:
-
Asignar a la variable mejor el valor mínimo que fev pueda tener(puede ser un valor de referencia previamente establecido).
-
mejor = min{fev(j) para todo j}
-
-
Para cada sucesor n de m:
-
(1) M(n) = MINIMAX(n,profundidad+1,C(jugador)) - C(jugador) es una función que cambia de jugador.
-
(2) mejor = max(-M(n), mejor)
-
-
3.
Una
vez que se han analizado recursivamente todos los sucesores de un
determinado nivel(indicado por la variable profundidad),
se
devuelve el valor mejor.
A
groso modo este algoritmo lo que hace es generar un árbol de estado
posibles para saber que decisión es la más óptima para tomar
teniendo en cuenta las jugada anterior del oponente humano.
En
el juego tic-tac toe evaluamos el movimiento del jugador y generamos
el movimiento de la maquina de acuerdo los estados actuales.
def
evaluateMove(move, p=jugador):
try:
board.makeMove(move,
p)
if
board.gameOver():
return
evaluar(board.Ganar())
outcomes
= (evaluateMove(next_move, opponent[p]) for next_move in board.getValidMoves())
if
p == jugador:
min_element
= 1
for
o in outcomes:
if
o == -1:
return
o
min_element
= min(o,min_element)
return
min_element
else:
max_element
= -1
for
o in outcomes:
if
o == +1:
return
o
max_element
= max(o,max_element)
return
max_element
finally:
board.undoMove(move)
La
salida producida por consola es la siguiente:
A
medida que realizamos una jugada eliminamos la posibilidad de
movimiento sobre esa casilla, con eso logramos reducir la
construcción de árboles para la maquina en la jugada siguiente y
mejorar el perfomence del juego.
-
CONCLUSIONES
Este
algoritmo es muy eficiente para pequeños programas pero a grandes
cantidades de información la profundidad va generando complejidad y
por lo tanto se disminuye el rendimiento. Aun así para el juego
tic-tac toe es muy bueno.
REFERENCIAS
No hay comentarios:
Publicar un comentario