Parte II
Bot generalizado para cualquier juego
Barney Darryl Pell en su investigación de PhD
enfoca en programas en vías de desarrollo que podrían jugar juegos directamente de las reglas, sin
asistencia humana. Pell llamó esta idea Metajuegos, y también llevó a cabo el primer programa en este nuevo paradigma.
El programa toma como entrada las reglas de un juego específico y analiza esas reglas para construir para ese juego una representación eficaz y una función de
evaluación, ambos para el uso con un artefacto o motor de búsqueda genérico.
Koller y Pfeffer extendieron esa idea en 1997
para dos juegos de información imperfecta, póquer y el juego del inspector.
La teoría de
los juegos es la teoría del comportamiento racional aplicada a problemas
interactivos de decisión. En un juego hay varios agentes los cuales intentan
maximizar su índice de utilidad esperada eligiendo opciones o ramas de conducta
particulares; el logro de su utilildad para cada agente depende del perfil de
las líneas de conducta elegidas por todos los agentes.
La situación interactiva, especificada por el
sistema de participantes, las líneas de conducta posibles de cada agente y el
sistema de todos los logros de utilidad posibles, se llama "Juego".
Los agentes que "juegan" un juego
se llaman Jugadores.
En Teoría de Juegos se usa un equilibrio en
sentido amplio. Este concepto que necesitamos se llama Equilibrio de Nash.
Si hay un sistema de estrategias con las características que ningún jugador se
puede beneficiar cambiando su estrategia mientras los otros jugadores mantienen
sus estrategias sin cambios, entonces ese sistema de estrategias y las
rentabilidades correspondientes constituyen el equilibrio de Nash.
En su artículo "Galapaper" o
"Representatoin and solution for game-theoretic problems", Koller y
Pfeffer se proponen dos juegos de información imperfecta:
- El "juego del inspector", sin azar,
referido a un inspector que debe controlar que no se viole una disposición
internacional enfrentando a un eventual violador a esa misma ley. El
inspector inspecciona porque estima que se está violando la ley o no
inspecciona porque estima que se está respetando la ley mientras que el
eventual violador está violando la ley porque estima que no viene el
inspector o respetando la ley porque estima que el inspector calcula venir.
- El póquer, un juego de barajas y por ello de
azar.
Gala
El sistema Gala permite la especificación y la solución eficaz de juegos
de información imperfecta. El sistema contiene la primer aplicación de un
algoritmo reciente, debido a Koller, Megiddo y Von Stengel. Los resultados experimentales del sistema demuestran que el algoritmo es exponencialmente más rápido que el algoritmo
standard en la práctica, no solo en teoría. El sistema también provee un nuevo
lenguaje para representar los juegos sólida y naturalmente por sus reglas. En general, el sistema
Gala proporciona la capacidad para automatizar la teoría de juegos análizando situaciones
complejas del mundo real.
El sistema Gala está formado por tres subsistemas principales:
- Entrada, introducción o especificaciones de
las reglas de juego en Gala y por consiguiente interpretables.
- Tragamonedas con sus tres subsistemas. (El
intérprete de Gala que se refiere a fijar el estado del sistema; El
productor del árbol del juego; y El tomador de decisiones de un sólo
disparo, modelado moviendo la palanca del tragamonedas, cada movimiento de
palanca, una decisión)
- Procesadores de árboles para hallar rutas
óptimas.
Intérprete Gala
- El intérprete en Prolog recibe una plantilla
tipificada con las reglas del juego en lenguaje Gala.
- Mantiene actualizado el juego descrito en la
pantilla según los datos que va recibiendo.
- Actualiza el estado local de los agentes,
parte del estado total.
- Al llegar a un punto de selección
("choose") explora las distintas posibilidades por delante del
árbol de ejecución, usando BPP.
- Mientras explora el árbol de ejecución,
genera el árbol de juego.
- El árbol de juego sólo muestra los nodos en
que se presentan estados que son opciones para tomar decisiones de un sólo
tiro entre las bifurcaciones que están a continuación.
- El árbol de ejecución contiene además
información para gestionar en forma determinista el estado del juego, por
ejemplo cambiando el valor de las variables o transformando una oración
compleja en otras más simples.
- Al llegar a choose genera en el árbol de
juego un nuevo nodo. El nodo se agrega al conjunto de información adecuado.
- Ese conjunto de información incluye todos los
nodos en que el estado local del agente es el mismo.
- En resumen, el intérprete de Gala posee
habilidades para interpretar juegos presentados según las platillas en
lenguaje Gala, para asignarle valores a los parámetros de la plantilla,
afrontar indeterminismo, identificar la posición actual de un juego y, con
esta información, crear nodos a partir de dicha posición en un árbol de
juego (más abstracto) o en un árbol de ejecución (más detallado).
Estado del juego
- El estado del juego es el observado justo
antes de tomar una decisión que bifurca las posibilidades del futuro.
Abarca el estado de todos los agentes que participan.
- La componente principal de la dificultad de
los juegos no es resultado del azar sino de la información incompleta. Esto
se generaliza señalando que un problema markoviano (MDP), esto es con
información completa, es mucho más fácil de resolver que un problema
decisional markoviano parcialmente observable (POMDP).
- En el caso del Gala el lenguaje permite lograr
una descripción de alto nivel de cada uno de los estados de la realidad de
un juego. Esto resulta útil, entre otros motivos, para acumular
información sobre las fallas sistemáticas del adversario y jugar en
consecuencia.
Árbol de juego
- Como se ha visto, en el lenguaje Gala cuando
aparece la voz "choose" el sistema interpreta un dado estado y
arma un árbol.
- El sistema Gala permite generar árboles de
juego automáticamente y los resulve según el teorema de Von Stengel,
"los equilibrios de un juego a suma cero de dos personas en forma
extensiva con recuerdo perfecto, son las soluciones de un algoritmo de PL
con una matriz de rentabilidades en forma secuencial, junto con dos matrices
de restricciones definidas de manera especial".
- Ubicado el equilibrio de Nash sabemos el juego
óptimo.
