Teoría de juegos combinatorios

Abstract

En esta memoria se introducir´a al lector en la Teor´ıa de Juegos Combinatorios. La herramienta que nos permitir´a modelizar los juegos combinatorios ser´a un grafo dirigido: el grafo de estados. En particular, veremos que en estos grafos existe un conjunto de v´ertices caracter´ıstico, llamado n´ucleo y que ser´a fundamental para describir estrategias ganadoras en un juego. Usaremos la teor´ıa vista previamente para estudiar juegos como el NIM y el Chomp. A partir de dos juegos combinatorios, se puede definir uno nuevo denominado suma de los anteriores. Para el estudio de la suma de juegos veremos uno de los teoremas m´as importante de esta rama de las matem´aticas: el Teorema de SpragueGrundy. Generalizaremos los resultados obtenidos para la suma de dos juegos al caso de la suma de cualquier n´umero de juegos combinatorios. Finalmente, trataremos la complejidad computacional que tiene el problema de encontrar estrategias ganadoras para los juegos combinatorios.

In this text we will introduce the reader in the Combinatorial Games Theory. The tool that will let us model combinatorial games will be a directed graph: the state graph of a game. We will see that these graphs have a distingished set of vertices, called kernel that will be fundamental to describe winning strategies in a game. We will use the theory studied before to analize games like NIM and Chomp. Starting from two combinatorial games, one can define a new game called the sum of the previous games. To study the sum of two combinatorial games we will see one of the most important theorems of this part of mathematics: the Sprague-Grundy Theorem. We will generalize the results obtained for the sum of two games to the case where we have any number of combinatorial games. Finally, we wil study the computational complexity of the problem of finding winning strategies for the combinatorial games.