Departamento de Computación

La teoría de juegos (GT por sus siglas en inglés) es la ciencia de la toma de decisiones estratégicas, la cual es utilizada para estudiar las relaciones de competencia y cooperación entre entidades. En juegos de multijugador, GT es una poderosa herramienta para estudiar la toma de decisiones, donde varios jugadores deben tomar decisiones que potencialmente afectan a los intereses de los otros jugadores. En esta tesis, diseñamos e implementamos modelos formales matemáticos, basados en máquinas de estado finito para el béisbol, fútbol americano y Go. Además, implementamos métodos eficientes para el análisis de estrategias, para el béisbol y el fútbol americano, utilizamos el equilibrio de Nash y la eficiencia de Pareto, y para el juego Go, las redes neuronales y Monte Carlo Tree Search. El modelado de juegos de multijugador es de alta complejidad, y el análisis de estrategias de estos juegos, deben incluir un gran número de parámetros, para una correcta toma de decisiones [5]. Para el análisis de estrategias en el béisbol y en el fútbol americano, se usa el equilibrio de Nash y la eficiencia de Pareto. Estos métodos clásicos de la economía, son aplicados para el análisis de las interacciones entre actores en un contexto dinámico social. En el béisbol y en el fútbol americano, estos métodos son útiles para modelar el comportamiento estratégico, de varios jugadores en un partido. Para el uso de estos métodos, funciones de utilidad para la selección de perfiles de estrategias se construye utilizando datos empíricos. Los resultados de las simulaciones por computadora de partidos de béisbol y de fútbol americano muestran que, aunque la calificación de no-cooperación habitual para el equilibrio de Nash, es un calificativo relativo, sobre las circunstancia reales. En el con-texto de un partido de béisbol o de futbol americano, con varios parámetros fuera del control de los jugadores y del manager, el equilibrio de Nash permite identificar perfiles de estrategias para una cooperación eficaz en circunstancias reales. El uso de equilibrio de Nash evita realizar jugadas o estrategias con baja incidencia estadística, lo cual dis-minuye el riesgo de perder puntos, esto significa que, los perfiles de estrategia de equilibrio de Nash con asiduidad incluyen jugadas y estrategias con incidencia estadística grande, las cuales son más factibles de que ocurrirán en partidos reales. Por otro lado, la eficiencia de Pareto induce a elegir perfiles de estrategias teóricamente óptimos, pero observamos que las jugadas y estrategias óptimas tienen baja incidencia estadística, por lo que son poco probable de que ocurran en circunstancias reales de un partido de béisbol o futbol americano. Los perfiles de estrategia eficiente de Pareto son menos probable que ocurra que los de Nash. Las estrategias en los perfiles de Pareto pueden ser los más rentables, pero sus estadísticas de ocurrencia son bajas. El uso combinado de ambos, Nash y Pareto eficiencia, para la toma decisiones estratégicas en juegos de multijugador, es relevante en circunstancias de interacciones sociales complejas. Hoy en día, el análisis formal del juego de tablero Go, es paradigmático en la ciencia de la computación, debido a que el Go es un juego muy complejo y en la actualidad, diseñar e implementar métodos de aprendizaje para la automatización del él, escoden una enorme complejidad combinatoria, por lo que el reto es la creación de métodos eficien-tes, que den buenas estrategias para jugar el juego de Go. En esta tesis, dos métodos principales son analizados y cuantificados, para la automatización del juego de Go, las redes neuronales y Monte Carlo Tree Search. Las redes neuronales son usadas para el reconocimiento de tácticas del juego de Go, tales como, eyes, ladders and nets, y Mon-te Carlo Tree search es usado para evaluar el siguiente movimiento desde una configuración del tablero. Las principales observaciones del análisis cuantitativo desarrollado es que, el uso de las redes neuronales durante las etapas iniciales e intermedias de un partido de Go es la mejor opción, y en etapas finales, Monte Carlo Tree Search es el método preferido a ser usado.

Abstract

Game theory (GT) is the science of strategic decision making, which is used to study the competition and cooperation relationships among entities. In multi-player games, GT is a powerful tool to study the decision-making, where players should make choices that af-fect the interests of other players, and the whole team. In this thesis, we designed and implemented mathematical formal models, based on Finite State Machine for the Base-ball, American Football, and the game of Go. In addition, we implemented efficient methods for the strategic analysis, for Baseball and American Football, we use Nash equilibrium and Pareto efficiency, and for Go gaming automation, Neural Networks and Monte Carlo Tree Search. The multi-player game modeling is of a high complexity, and the strategic analysis of Baseball and American Football must include a large number of parameters for fairly automatized decision-making support [5]. The strategic analysis for Baseball and Ameri-can Football involves the use of Nash equilibrium and Pareto efficiency. These classical methods are used in economic, for analyzing the interactions among actors in a social dynamic context. In Baseball and American Football, they are used for modeling the strategic behavior of multiple players in a game match. To apply these methods, utility functions for the strategy profiles selection are constructed based on empirical data. The computer simulations results of Baseball and American Football matches show that, although the usual non-cooperative qualification to Nash equilibrium, it is a relative ad-jective, up to the real circumstance. In the context of Baseball or American Football matches, where several parameters out of the players’ and manager’s control, Nash equilibrium allows to identify strategy profiles, for effective cooperation in real circum-stances. The use of Nash equilibrium prevents to try plays or strategies with low statisti-cal occurrence, thereby decreasing the risk to lose points, i.e., the Nash equilibrium strategy profiles, frequently include plays and strategies with high statistical occurrence, thus these strategies are more feasible in real matches. On the other hand, Pareto effi-ciency induces to choose the theoretically optimum strategy profiles, however we observe that the optimal plays and strategies have low statistical occurrence, therefore they are impractical in real circumstances. The Pareto strategy profiles are less likely to occur than the Nash ones. The strategies in Pareto profiles may be the most profitable, but their probability of occurrences are low. The combined use of both, Nash and Pareto efficiency, for strategic choice on multi-player Baseball and American football games, it is relevant to circumstances with complex social interactions. Nowadays, the formal analysis of the board game of Go is paradigmatic for computer science, since this game is a top complex game and currently, design and implement learning methods for Go gaming automation, conceal a huge combinatorial complexity and the challenge is to create efficient methods, that give good strategies for playing Go. Two major methods are analyzed and quantified for the Go gaming automation in this thesis, Neural Networks and Monte Carlo Tree Search. The Neural Networks are used for pattern recognition of Go tactics, and Monte Carlo Tree Search is used for evaluating the next move from a board configuration. The main remarks from this analysis is that, the use of Neural Networks for pattern recognition of Go eyes, ladders and nets is the best option in the early and middle stages of a Go match, and in the end stages, Monte Carlo Tree Search is the preferred method to be used.