Inteligencia artificial para videojuegos/Búsqueda con adversarios

Introducción

Este apartado trata de la resolución de problemas que tienen un enfoque más realista. A diferencia de los problemas de búsqueda del "modelo clásico", no asumen simplificaciones como visibilidad completa del problema y dominios de trabajo conocidos cuya solución es una secuencia de operadores discretos.

Hay varios problemas los cuales no pueden ser resueltos por el modelo clásico y es necesario técnicas e implementaciones especiales para resolverlos. Algunos ejemplos de estos problemas son: la exploración y evaluación de una ruta de manera no sistemática, búsquedas desconociendo el dominio o el espacio de búsqueda o incluso la existencia de otro resolutor que dificulte nuestra resolución del problema.

Puntos claves

Hay cinco ideas clave en la resolución de estos problemas:

Definición (matemática) de juego

Existe una rama de la Economía dedicada a estudiar la teoría (matemática) del juego. En dicha rama no se diferencia entre resolución competitiva o resolución cooperativa. Sin embargo, en el ámbito de la inteligencia artificial, si que se diferenciará entre ambas resoluciones, interesándose más por la resolución competitiva en esta sección.

Relacionado con la inteligencia artificial se destacan los juegos abstractos deterministas, por turnos, de dos jugadores (dos resolutores), suma cero (solución final con dos medidas de éxito opuestas) y con conocimiento completo del estado del juego. Por ejemplo el ajedrez.

Busqueda con adversarios

Resolución difícil en la que se van a tener que tomar decisiones aunque no sean óptimas. En este tipo de algoritmos la eficiencia y velocidad de resolución es clave debido a que, por ejemplo, puede haber otro resolutor cambiando la configuración del problema en nuestra contra. Por ello, los resolutores se encontrarán ante situaciones difíciles de predecir. Tienen en cuenta: el estado inicial, los jugadores (MAX y MIN), movimientos, modelo de transición, comprobación de si es el estado final y la puntuación. Por ejemplo en un juego de 3 en raya MAX juega primero e intenta maximizar suponiendo que MIN jugará lo más óptimamente posible.

Algoritmo Minimax

Método de toma de decisiones que minimiza la pérdida máxima (o maximiza la ganancia mínima) esperada de utilidad. Sus características son:

Se basa en recorrer un árbol de juego con una búsqueda en profundidad (DFS).

La complejidad espacial es de O(R*M) o O(M) es caso de que se vayan expandiendo los movimientos uno a uno.
La complejidad temporal es O(R^M).
Es un algoritmo elegante pero es más útil a nivel teórico que a nivel práctico.

A continuación se muestra una implementación en pseudocódigo:

función DECIDE-MINIMAX (estado) devuelve movimiento
    devolver argmaxmov∈Mov(estado)VALOR-MIN(resultado de aplicar mov al estado)
    // Aquel mov, de los aplicables a estado, que maximize el resultado de VALOR-MIN

función VALOR-MAX (estado) devuelve utilidad
    si estado es terminal entonces devolver utilidad(estado)
    valor ← -∞
    para cada mov en Mov(estado) hacer
        valor ← max(valor, VALOR-MIN(resultado de aplicar mov al estado)
    devolver valor

función VALOR-MIN (estado) devuelve utilidad
    si estado es terminal entonces devolver utilidad(estado)
    valor ← ∞
    para cada mov en Mov(estado) hacer
        valor ← min(valor, VALOR-MAX(resultado de aplicar mov al estado)
    devolver valor

Destacamos dos variantes:

Poda Alfa-Beta

El algoritmo MINIMAX se considera útil en la teoría y no en una solución práctica. Por ello se han creado nuevas versiones como la Poda Alfa-Beta, versión mejorada del Minimax donde se mantiene la complejidad exponencial pero se puede reducir en gran medida el tiempo y el espacio. Se basa en podar ramas enteras del árbol para poder expandir primero las más prometedoras. "Alfa" es la utilidad más alta encontrada por ahora en cualquier punto de elección de MAX y "Beta" es la utilidad más baja encontrada por ahora en cualquier punto de elección de MIN.

A continuación se muestra una implementación en pseudocógido:

función VALOR-MAX (estado, alfa, beta) devuelve utilidad
    si estado es terminal entonces devolver utilidad(estado)
    valor ← -∞
    para cada mov en Mov(estado) hacer
        valor ← max(valor, VALOR-MIN(resultado de aplicar mov al estado, alfa, beta)
        si valor ≥ beta entonces devolver valor
        alfa ← max(alfa, valor)
    devolver valor

función VALOR-MIN (estado, alfa, beta) devuelve utilidad
    si estado es terminal entonces devolver utilidad(estado)
    valor ← ∞
    para cada mov en Mov(estado) hacer
        valor ← min(valor, VALOR-MAX(resultado de aplicar mov al estado, alfa, beta)
        si valor ≤ alfa entonces devolver valor
        beta ← min(beta, valor)
    devolver valor

Decisión en tiempo real

Debido a que los estados terminales siguen estando a demasiada profundidad en un árbol de juego, se intenta optimizar con diferentes técnicas como:

Con una prueba de corte para saber cuando conviene parar la búsqueda y evaluar el estado.

Con poda hacia delante, eliminando de raíz movimientos que estimas (o recuerdas) como malos.

Con consultas a tablas de aperturas y finales.

Juegos estocásticos

Contienen elementos aleatorios. Se añaden nodos de azar a métodos como Minimax. Se usan técnicas como calculas el valor esperado haciendo la media de las probabilidades o hacer un estudio estadístico y luego usar esos datos en la implementación.

También mencionar que incluir azar y elementos aleatorios complica en gran medida la implementación de los algoritmos y la poda de los mismos. Se hace uso de diferentes técnicas, tratando de podar al máximo los nodos de los algoritmos. Un ejemplo de ello sería realizar simulaciones siguiendo el método Monte Carlo, el cual trata de jugar muchas veces, sacando estadísticas de los resultados para, posteriormente, podar aquellos nodos con menores probabilidad.

Juegos parcialmente visibles

Ofrecen información imperfecta o incompleta al jugador. Son juegos en los que se puede intentar engañar al jugador haciendo faroles o haciendo movimientos simplemente para obtener información del contrincante y no para conseguir una victoria, por ejemplo: "hundir la flota". Se suelen resolver mediante árboles AND/OR y, sobre todo, probabilidad.