Game Player Strategy Pattern Recognition and How UCT Algorithms Apply Pre-Knowledge of Player’s Strategy to Improve Opponent AI

En este artículo se habla sobre el reconocimiento de patrones de estrategia sobre un juego en el que el jugador usa a un gato que debe esquivar a dos perros para salir del lugar donde se encuentra y así ganar el juego como se ilustra en la siguiente figura.

Para llevar esto a cabo se hizo uso de los siguientes pasos:

• Se recolectaron los atributos usados para el PSPR (Player Strategy Pattern Recognition).
• Se recolectaron muestras de distintas estrategias de jugadores según los atributos definidos.
• Se crearon subconjuntos de acuerdo a los datos obtenidos en la muestra para mejorar el desempeño del sistema.
• Se proceso el ruido.
• Se entreno y se evaluó un clasificador KNN (k-nearest-neighbors) con el conjunto de datos de la muestra.

El resultado de lo anterior arrojo los siguientes datos:

Después se empleo el algoritmo UCT que se encuentra basado en el problema conocido como multi-armed bandit que a su vez se encuentra basado en la analogía de una maquina tragamonedas (estilo casino) pero con varias palancas. El objetivo del apostador se centra en obtener la mayor recompensa de emplear dichas palancas a lo largo de varias iteraciones.

En el caso de este dominio se considero a cada perro como una maquina y cada una de las posibles direcciones a las que se puede mover (norte, sur, este y oeste) como un brazo o palanca. En cada paso se reduce el número de movimientos posibles que puede llevar a cabo el perro podando el árbol de movimientos posibles reduciendo así el espacio de búsqueda.

Al final con el uso de este sistema se pudo logran un porcentaje de 52.17% de victorias sobre un jugador que solo utiliza UCT sin llevar a cabo el reconocimiento previo con KNN para catalogar las distintas estrategias que se pueden llevar a cabo.

He, S., Wang, Y., Xie, F., Meng, J., Chen, H., Luo, S., Liu, Z., et al. (2008). Game Player Strategy Pattern Recognition and How UCT Algorithms Apply Pre-knowledge of Player’s Strategy to Improve Opponent AI. 2008 International Conference on Computational Intelligence for Modelling Control & Automation, 1177-1181. Ieee. doi:10.1109/CIMCA.2008.82