La mayoría de los juegos de mesa y una gran cantidad de problemas informáticos pueden resolverse mediante una adecuada modelización en estados y aplicar un algoritmo de búsqueda entre estos estados.
Para acotar el problema, pensemos en un juego de tablero de 2 jugadores, por ejemplo, las tres en raya, las damas, el ajedrez, el othello, etc. ¿Cómo podría programarse un juego de este tipo?:
Bien, en primer lugar, un tablero es una estructura de datos de tipo matriz donde cada elemento puede ser ocupado por el jugador 1, ocupado por el jugador 2, ó vacio (en juegos como el ajedrez donde cada jugador tiene diferentes fichas habría que completar el enfoque). Una partida es una secuencia de estados por los que pasa un tablero. Ahora veamos cómo debería actuar nuestro sistema inteligente para ganarnos en una partida.
Una primera aproximación podría ser tener todas las posibles partidas en memoria y aplicar solo los movimientos que han llevado a partidas victoriosas.
Otro enfoque sería actuar en cada turno, teniendo en cuenta ciertas reglas estáticas (ej: ciertos if). Un ejemplo de reglas en las tres en raya puede ser: si tengo dos fichas alineadas entonces ocupa el último lugar vacío y gana la partida, si el oponente tiene 2 fichas alineadas ocupa el lugar vacío y evita la victoria del oponente, en cualquier otro caso mueve de manera aleatoria.
En general, para este tipo de juegos se utiliza la estrategia minimax que imita el comportamiento humano de examinar por anticipado un cierto número de jugadas, explorando el grafo de tableros que se generarían tras un movimiento dado. En este enfoque existe una función de evaluación que da un valor a cada posible movimiento.
Para ilustrar la implementación de estos enfoques recomiendo instalar el paquete tictactoe que implementa las 3 en raya con 2 niveles de dificultad easy (implementa reglas tontas) y hard (implementa minimax). Dejo el código de las funciones clave al lector:
Ejemplo 1. Extracto de código de tictactoe
# implements a simple win/block/random-move AI
def move_ai_easy
if (m = blockWin) >= 0
@gamefield.field[m] = 2
else
# set random point
while true
x = rand(3)
y = rand(3)
if @gamefield.get(x,y) == 0
@gamefield.set(x,y)
break
end
end
end
@nmoves += 1
end
# implements a more clever AI using the negamax tree search method
def move_ai_hard
best = -Inf
besti = -1
@gamefield.player = 1
order = [4,0,2,6,8,1,3,5,7] # see text
0.upto(8) do |ctr|
i = order[ctr]
if @gamefield.field[i] == 0
@gamefield.field[i] = 2
value = -@gamefield.negamax
@gamefield.field[i] = 0
if value > best
best = value
besti = i
end
end
break if (@nmoves == 0) && (best == 0) # see text
end
@gamefield.player = 2
@gamefield.field[besti] = 2
@nmoves += 1
end
|
De este modo, queda brevemente ilustrado el modo en que se pueden aplicar técnicas de Inteligencia Artificial en los juegos.