Towards Strategic Kriegspiel Play with Opponent Modeling

Este es un artículo en el que muestran el uso del modelado del oponente en una situación en que no se conoce el estado actual del oponente como sucede en algunos tipos de problemas. Para lo anterior emplearon Kriegspiel que es una versión modificada del ajedrez tradicional en la cual cada jugador no conoce la ubicación de las piezas del contrario y los movimientos son evaluados por un árbitro que indica si estos son legales o no y que consecuencias producen.

Debido al costo computacional de llevar a cabo el modelado se decidió reducir tanto el tamaño del tablero (a tan solo una dimensión de cuatro por cuatro casillas) y el número de piezas (se empleo solo el rey y la reina). Aun con esta reducción se obtiene alrededor de 74 mil posibles combinaciones de estados a lo largo del juego.

Para el desarrollo del juego se emplean I-POMDP (Interactive Partially Observable Markov Decision Processes) para cada agente, lo cual está formalmente definido por:

I-POMDP = {IS, A, T, Ω, O, R}

• IS – Es el estado interactivo el cual está definido por el cruce entre los estados físicos (configuraciones del tablero S) y los posibles modelos del oponente.
• A – Es el cruce entre las acciones posibles del agente propio y el oponente.
• T: S x A x S --> {0,1} – Es la función de transición que representa la influencia de los agentes con el ambiente.
• Ω - Es el conjunto que contiene las respuestas posibles del referee.
• O: S x A x Ω -->{0,1} – Es la función de observación del referee que dicta que respuesta debe brindar.
• R: S x A --> R – Es la función de recompensa asociada a uno de los estados finales del juego (victoria, empate o derrota).

Se emplea una red bayesiana para elegir la jugada que realizara el agente teniendo en cuenta las probabilidades y los pesos de elegir una opción respecto a que el oponente pueda elegir otra de forma que se cuantifica cada posibilidad.

Del Giudice, A., & Gmytrasiewicz, P. (2007). Towards Strategic Kriegspiel Play with Opponent Modeling. AAAI Spring Symposia. Stanford, California: AAAI.