Programación de Juegos: Métodos y Niveles de Algoritmo

 

Los métodos de programación de juegos no se suelen aplicar de la misma manera dado que la estructuración de los mismos puede variar categóricamente. En este caso, se dividen en aspectos de compañía e interacción, los cuales se componen en juegos con o sin adversario.

Métodos Utilizados en Juegos Sin Adversario

Para algoritmos de juegos unipersonales (por ejemplo los puzzles o el solitario) suelen utilizarse los algoritmos más comunes de búsqueda heurística, aunque realmente las soluciones a un juego unipersonal pueden encontrarse con cualquier algoritmo de fuerza bruta sin heurística alguna, siempre y cuando se disponga del tiempo y memoria necesarios.

Te puede interesar:

De entre los algoritmos de búsqueda heurística, suele utilizarse o bien el algoritmo A, que se describe en esta sección, o bien el algoritmo IDA (según los recursos del computador).

El algoritmo A* (Hart, 1968) implementa una búsqueda primero el mejor (best-first). En otras palabras, se basa en intentar encontrar todos los movimientos necesarios para llegar del estado inicial al estado final, usando preferiblemente aquellos movimientos que sean más favorables. Así, entre otras cosas, se puede lograr minimizar los pasos de la solución, o el tiempo de cálculo.

Para conocer qué movimiento es mejor se utiliza una función de evaluación estática formada descompuesta como:

f = g + h

Donde “f” será el valor numérico del movimiento estudiado, la función “g” es una función del coste de llegar del estado inicial al estado actual, y la función “h” es una estimación del coste de llegar desde el estado actual al estado final o objetivo. Lógicamente, “h” es una estimación porque no conocemos a priori el camino exacto hacia la solución.

El algoritmo A*, simplificado y con sintaxis imprecisa, viene a ser el siguiente:


Algoritmo A*
Estados_pendientes.insertar(Estado_inicial); Actual = Estados_pendientes.primero();
Mientras(no_es_final(Actual) y (no Estados_pendientes.vacio)) hacer Estados_pendientes.borrar_primero(); Estados_ya_estudiados.insertar(Actual);
Sig_movimientos = generar_sucesores(Actual);
Sig_movimientos = eliminar_repetidos(Sig_movimientos,
Estados_ya_estudiados, Estados_pendientes);
Estados_pendientes.insertar(Sig_movimientos);
Actual = Estados_pendientes.primero();
fMientras fAlgoritmo


Métodos Utilizados en Juegos Con Adversario

Pero la chicha de los algoritmos de juegos se encuentra en los juegos con adversario. Aquí es donde estos algoritmo se diferencian de los demás algoritmos de búsqueda típicos.

A continuación se presentan los más importantes y las técnicas de mejora también más conocidas. Aún así existen muchísimos algoritmos más que quedaron fuera de este documento, como podrían ser DUAL, Mem, o B*.

Algoritmo MiniMax

El algoritmo MiniMax es el algoritmo más conocido (y utilizado) para problemas con exactamente 2 adversarios, movimientos alternos (“ahora tú ahora yo”), e información perfecta. Además tiene un nombre la mar de ilustrativo, como veréis en los siguientes párrafos.

Identificaremos a cada jugador como el jugador MAX y el jugador MIN. MAX será el jugador que inicia el juego, el cual supondremos que somos nosotros, y nos marcaremos como objetivo encontrar el conjunto de movimientos que proporcionen la victoria a MAX (nosotros) independientemente de lo que haga el jugador MIN.

Etiquetar los jugadores como máximos y mínimos plasma perfectamente la dualidad de los objetivos de cada uno, además de que así se puede contabilizar perfectamente cómo una situación que mejora para un jugador hace que empeore para el otro. Matizar que no importa qué jugador deseemos ser, pues bajo nuestro punto de vista siempre calcularemos jugadas positivas a nuestro favor y negativas para el oponente.

Y todo ésto nos lleva a que por convenio una jugada vencedora del jugador MAX (lo que vendría a ser un “jaque mate”) tendrá valor infinito, y una jugada del jugador MIN tendrá valor menos infinito.

Deberá existir para el juego a resolver una función de evaluación heurística que devuelva valores elevados para indicar buenas situaciones, y valores negativos para indicar situaciones favorables al oponente. Ahora ya podemos ver como para cada movimiento conoceremos su valor numérico en función de su “grado de bondad”, y podremos ser capaces de identificar nuestro mejor movimiento.

Estrategia a utilizar

Además de utilizar la anterior función heurística, usaremos una estrategia DFS de profundidad limitada para explorar el conjunto de jugadas. Como es imposible hacer una exploración exhaustiva de todas las jugadas, se hace una búsqueda limitada en profundidad. Significa que en lugar de estudiar todas las posibles situaciones hasta el fin de la partida, se buscarán por ejemplo todas las situaciones hasta de aquí 3 turnos.

Aunque esto limitará lo que veamos del espacio de búsqueda, y quizás nos incitará a realizar unas jugadas que a la larga sean nefastas. La calidad de nuestras jugadas vendrá determinada por la profundidad a la que lleguemos en cada exploración. Cuanto más profunda sea, mejor jugaremos, pero mayor coste tendrá el algoritmo.

Por lo tanto, situados todos los elementos del algoritmo, veamos cómo es MiniMax:


Función MiniMax(estado) retorna movimiento mejor_mov: movimiento;
max, max_actual: entero; max = -infinito;
para cada mov en movimientos_posibles(estado) hacer
max_actual = valorMin(aplicar(mov, estado);
si max_actual > max entonces
max = max_actual; mejor_mov = mov;
fpara
fsi
retorna mejor_mov;
fFunción
Función valorMax(estado) retorna entero valor_max:entero;
si estado_terminal(estado) entonces retorna evaluación(estado);
sinó
valor_max := -infinito;
para cada mov en movimientos_posibles(estado) hacer
valor_max := max(valor_max, valorMin(aplicar(mov, estado));
fsi fFunción
fpara
retorna valor_max;
Función valorMin(estado) retorna entero valor_min:entero;
si estado_terminal(estado) entonces retorna evaluación(estado);
sinó
valor_min := +infinito;
para cada mov en movimientos_posibles(estado) hacer
valor_min := min(valor_min, valorMax(aplicar(mov, estado));
fsi fFunción


El algoritmo tiene una función principal (MiniMax) que será la que usemos (y la que nos devolverá la mejor realizable). A su vez, tiene dos funciones recursivas mutuas (valorMax y valorMin) que determinan el valor de las jugadas dependiendo de si es el turno de MAX o de MIN. De este modo cada nivel elegirá el valor que propaga a su ascendiente dependiendo de qué jugador es.

Niveles de MAX

En lo que a programación de juegos respecta, en los niveles de MAX se elegirá el valor mayor de todos los descendientes. Por su lado, en los niveles de MIN se elegirá el menor. Tras esto, la máquina supone que todo jugador elige siempre su mejor jugada, cosa que no siempre será.

La función “estado_terminal” determina si el estado actual es una solución o pertenece al nivel máximo de exploración. La función “evaluación” calcula el valor heurístico del estado. Pero esta versión, aunque sea sencilla, no es la más inteligente a la hora de tratar juegos bipersonales.

Por eso al algoritmo MiniMax se le pueden aplicar una serie de técnicas para mejorarlo, buscando siempre una decisión más segura del movimiento, y un tiempo de cálculo menor. Para analizar más afondo otros temas de videjuegos puede visitarnos en la pagina web aprendeinformaticas. Si conoce alguna otras fuentes que podamos compartir contigo en este post, puedes dejar tu aporte en la caja de comentarios.