PDF de programación - Jugador Inteligente de Backgammon

Centro de Investigaci´on y de Estudios

Avanzados

del Instituto Polit´ecnico Nacional

Unidad Zacatenco

Departamento de Computaci´on

Jugador Inteligente de Backgammon

Tesis que presenta

Oscar Irineo Fuentes

para obtener el Grado de

Maestro en Ciencias

en Computaci´on

Director de la Tesis: Francisco Rodr´ıguez Henr´ıquez

Codirector: Nareli Cruz Cort´es

M´exico, D.F.

8 de diciembre de 2006

ii

Resumen

Durante muchos a˜nos se han realizado diversas investigaciones en el ´area
de la inteligencia artificial, entre las cuales destacan las que han propuesto
nuevos mecanismos para tratar de simular la inteligencia humana por medio
de computadoras. Entre uno de varios problemas relevantes destacan los jue-
gos de mesa, y en espec´ıfico para nuestro trabajo de investigaci´on, el juego
de backgammon.

En esta tesis se ha dise˜nado un algoritmo gen´etico capaz de aprender y
jugar el juego de backgammon, ´unicamente proporcion´andole las estrategias
b´asicas del juego. Esencialmente, nuestro algoritmo gen´etico ajusta un con-
junto de pesos que se utilizan para decidir qu´e estrategia es la mejor para
determinada posici´on de las fichas en el tablero.

Existe un evaluador aut´omata est´andar de nivel intermedio llamado Pu-
beval, con el cual, otros aut´omatas han competido para comparar su desem-
pe˜no. El objetivo principal de esta tesis es que nuestro aut´omata compita en
contra de Pubeval y obtenga porcentajes de victorias por encima del 50 %.

Aunque ya existen aut´omatas para jugar el juego de backgammon, no
existen reportes en la literatura que utilicen ´unicamente algoritmos gen´eticos
y reporten resultados en contra de Pubeval, ya que s´olo han sido utilizados
para probar algunas t´ecnicas de aprendizaje.

Se realizaron varias pruebas, modificando par´ametros del algoritmo gen´eti-
co, as´ı como la forma de interpretaci´on de las estrategias, para lograr cum-
plir con el objetivo. Los resultados comparativos al poner a competir nuestro
aut´omata en contra de Pubeval se reportan al final del documento, mostrando
tambi´en los resultados de otros aut´omatas previamente publicados.

iii

iv

Abstract

During many years, several research works have been conducted in the
area of artificial intelligence, where new methods have been proposed for
attaining some sort of human intelligence simulation through computers. In
this respect, one important line of research is board games, and in particular
for this work we are interested in studying the backgammon game.

For that matter, in this thesis we designed a genetic algorithm able to
learn and play the backgammon game by a continuous refining of a set of basic
game strategies. In essence, our genetic algorithm adjusts a set of weights in
order to decide which one is the best strategy to follow given a specific board
position.

In order to evaluate the performance of any given backgammon automata,
it is customary to measure its level by playing several thousand games against
Pubeval, an open source publicly available standard benchmark. In this thesis
we aimed to produce a player able to obtain winning percentages above 50 %
when confronted against Pubeval.

It was not before that we performed many experiments, and that we
changed several genetic algorithm parameters as well as the way that the
game strategies were interpreted by our automata, that we were able to
accomplish our goal. Comparative results when our backgammon player plays
against Pubeval are reported in the manuscript. Also, we compare our results
against other backgammon players previously reported.

v

vi

Agradecimientos

Al Centro de Investigaci´on y de Estudios Avanzados
del Instituto Polit´ecnico Nacional

Al Consejo Nacional de Ciencia y Tecnolog´ıa

Al proyecto 45306y del Consejo Nacional de Ciencia
y Tecnolog´ıa

viii

´Indice general

Resumen

Abstract

´Indice de Figuras

´Indice de Tablas

1. Introducci´on

1.1. Planteamiento del problema . . . . . . . . . . . . . . . . . . .
1.2. Motivaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

III

V

XIII

XV

1
1
2
3

2. Antecedentes

2.1. Teor´ıa de juegos1

. . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Historia de la teor´ıa de juegos . . . . . . . . . . . . . .
2.1.2. Conceptos b´asicos . . . . . . . . . . . . . . . . . . . . .
2.1.3. Tipos de juegos . . . . . . . . . . . . . . . . . . . . . .
2.1.4. Representaci´on . . . . . . . . . . . . . . . . . . . . . .
2.1.5. M´etodos para la soluci´on de juegos

5
5
6
7
8
9
. . . . . . . . . . . 11
. . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2. Trabajo previo
2.2.1. Ajedrez
. . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2. Othello . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3. Damas . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.4. Backgammon . . . . . . . . . . . . . . . . . . . . . . . 16

3. Juego de backgammon

19
3.1. Historia del backgammon . . . . . . . . . . . . . . . . . . . . . 19
3.1.1. Or´ıgenes del backgammon . . . . . . . . . . . . . . . . 19

ix

x

´INDICE GENERAL

3.1.2. Artefactos utilizados
. . . . . . . . . . . . . . . . . . . 20
3.1.3. Backgammon Romano . . . . . . . . . . . . . . . . . . 20
3.1.4. El backgammon en Asia . . . . . . . . . . . . . . . . . 21
3.1.5. Proliferaci´on y estandarizaci´on del backgammon . . . . 22
3.1.6. Diferentes nombres . . . . . . . . . . . . . . . . . . . . 22
3.1.7. La historia del backgammon moderno . . . . . . . . . . 23
3.2. Reglas del backgammon . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1. Objetivo del juego . . . . . . . . . . . . . . . . . . . . 25
3.2.2. Movimiento de las fichas . . . . . . . . . . . . . . . . . 26
3.2.3. Capturando e introduciendo las fichas . . . . . . . . . . 28
3.2.4. Retirando fichas . . . . . . . . . . . . . . . . . . . . . . 29
3.2.5. Doblado . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.6. Tipos de victoria . . . . . . . . . . . . . . . . . . . . . 31
3.3. Estrategia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4. Algoritmos gen´eticos

33
4.1. Conceptos b´asicos . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2. Algoritmo gen´etico b´asico . . . . . . . . . . . . . . . . . . . . 34
4.3. Representaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3.1. Representaci´on binaria . . . . . . . . . . . . . . . . . . 35
4.3.2. Representaci´on binaria con c´odigos de Gray . . . . . . 35
4.3.3. Representaci´on para n´umeros reales . . . . . . . . . . . 36
4.3.4. Otros tipos de representaci´on . . . . . . . . . . . . . . 37
4.4. Aptitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5. Selecci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5.1. Selecci´on proporcional
. . . . . . . . . . . . . . . . . . 38
4.5.2. Selecci´on mediante torneo . . . . . . . . . . . . . . . . 42
4.5.3. Selecci´on de estado uniforme . . . . . . . . . . . . . . . 43
4.6. Cruza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.6.1. Cruza de un punto . . . . . . . . . . . . . . . . . . . . 44
4.6.2. Cruza de dos puntos
. . . . . . . . . . . . . . . . . . . 44
4.6.3. Cruza uniforme . . . . . . . . . . . . . . . . . . . . . . 44
4.6.4. Otros tipos de cruza . . . . . . . . . . . . . . . . . . . 45
4.7. Mutaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.8. Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.9. Micro algoritmo gen´etico . . . . . . . . . . . . . . . . . . . . . 47

´INDICE GENERAL

xi

5. Aut´omatas de backgammon

49
5.1. Sistema Heinze-Ortiz . . . . . . . . . . . . . . . . . . . . . . . 49
5.2. Representaci´on del problema . . . . . . . . . . . . . . . . . . . 53
5.2.1. Vector de reglas . . . . . . . . . . . . . . . . . . . . . . 54
5.3. Algoritmo gen´etico . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3.1. Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . 57
. . . . . . . . . . . . . . . . . . 60
5.4.1. Diferencia Temporal y TD-Gammon . . . . . . . . . . 60
5.4.2. Ensamble de redes neuronales . . . . . . . . . . . . . . 62

5.4. Soluci´on por redes neuronales

6. Experimentos y resultados

65
6.1. Algoritmo gen´etico . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2. Redes neuronales . . . . . . . . . . . . . . . . . . . . . . . . . 72

7. Conclusiones y trabajo futuro

75

xii

´INDICE GENERAL

´Indice de figuras

11
2.1. Matriz de recompensas para el juego del dilema del prisionero
2.2. ´Arbol para el juego del dilema del prisionero . . . . . . . . . . 11
2.3. Soluci´on al juego del dilema del prisionero por el m´etodo mi-

nimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4. M´etodo geom´etrico . . . . . . . . . . . . . . . . . . . . . . . . 14

. . . . . . . . . . . . . . . . . . . 26
3.1. Posici´on inicial de las fichas
. . . . . . . . . . . . . 27
3.2. Direcci´on del movimiento de las fichas
3.3. Dos formas distintas de jugar
. . . . . . . . . . . . . . . . . . 28
3.4. Forma de introducir una ficha . . . . . . . . . . . . . . . . . . 29
3.5. Retirando las fichas . . . . . . . . . . . . . . . . . . . . . . . . 30

4.1. Representaci´on de un cromosoma . . . . . . . . . . . . . . . . 35
4.2. Representaci´on binaria . . . . . . . . . . . . . . . . . . . . . . 35
4.3. Representaci´on con c´odigos de Gray . . . . . . . . . . . . . . . 36
4.4. Representaci´on real con el est´andar IEEE . . . . . . . . . . . . 37
4.5. Representaci´on real con los n´umeros en cada gen . . . . . . . . 37
4.6. Representaci´on real utilizando n´umeros enteros
. . . . . . . . 37
4.7. Cruza de un punto . . . . . . . . . . . . . . . . . . . . . . . . 44
4.8. Cruza de dos puntos
. . . . . . . . . . . . . . . . . . . . . . . 45
4.9. Cruza uniforme con P c = 0.5 . . . . . . . . . . . . . . . . . . 45

5.1.
Interacci´on entre las clases del sistema . . . . . . . . . . . . . 51
5.2. Esquema de la red neuronal usada p