La máquina invencible

Es raro que algún día me encuentre en la oficina con poco trabajo que hacer. También es raro que no ande por allí mi jefe Gaznápiro fustigándonos con su verborrea y sus dotes para convertir el proyecto más simple en un infierno. Sin embargo, que se den las dos cosas a la vez es un hecho tan estadísticamente improbable como que no te pille un gran atasco a la salida del trabajo.
Aquella mañana el azar había querido que el Sr. Lego y yo andáramos enfrascados tranquilamente en una conversación cinematográfica. Hablábamos de los gazapos informáticos que minaban la mayoría de las películas, lo cuales no son pocos, y quizás tan habituales como los gazapos científicos, pero esa es otra historia. Hablábamos de clásicos como Tron, Hackers o Conspiración en la red. Todo iba bien hasta que el Sr. Lego comenzó a criticar Juegos de Guerra, lo cual era demasiado para alguien como yo, que conocía al dedillo cada frase del diálogo y, siendo aún un adolescente, había descubierto en esta película las maravillas de la Inteligencia Artificial y el Hacking reunidos en una hora y media de metraje.

.- Menudo rollo ese del ordenador que habla como un humano -se quejaba el Sr. Lego- ni que los ordenadores pudieran pensar.

.- De hecho, Sr. Lego, ya en 1950 Alan Turing, en un artículo llamado Computing machinery and inteligence, propuso su famoso Test de Turing para evaluar la inteligencia de un ordenador. Básicamente sostiene que si una máquina se comporta en todos los aspectos como inteligente, entonces debe ser inteligente (no entraré en disquisiciones filosófica sobre si esto tiene o no sentido). Le recomiendo a usted que repase mentalmete la charla que tuvimos hace unos meses sobre Inteligencia Artificial en la que hablamos de cómo solucionar puzzles sencillos en un ordenador.

.- Cierto, pero una cosa es un puzzle de niños y otra que el ordenador hable y hasta sea capaz de ganarle a un humano jugando al tres en raya, las damas o el ajedrez.

.- Sr, Lego, ¿no ha jugado usted nunca a un juego de ajedrez? O es usted realmente bueno o se verá en complicaciones para ganarle al ordenador de su casa. Imaginese enfrentarse a ordenadores especificamente diseñados para jugar como el famoso Deep Blue, que ya tiene sus añitos.

.- Bueno, supongo que usaran técnicas similares a las que me enseñaste cuando hablamos de los puzzles ¿no?

.- Si y no -dije tras pensármelo un poco. Realmente hay varias estrategias que dependen mucho del juego al que se quieran aplicar, aunque básicamente se basan en lo mismo. En la búsqueda en un espacio de estados, como en el caso del puzzle (aunque se pueden utilizar otras técnicas como sistemas expertos, redes de neuronas, etc... pero de eso hablamos otro día). Una de las más conocidas y usadas es el llamado algoritmo minimax, que probablemente es el que hubiera usado la WOPR para jugar al tres en raya (o tic-tac-toe como lo llaman los angloparlantes).

.- Es decir, que el minimax ese no es más que una búsqueda en un árbol de estados.

.- Bueno, si quiere le cuento como funciona el algoritmo. Es más sencillo de lo que usted cree.
Cuando atacamos el problema de resolver el puzzle, estábamos enfrentándonos a lo que se denomina un juego sin contrincante. En el caso del 3 en raya o el ajedrez, sí hay un adversario, y por lo tanto, utilizaremos la estrategia minimax, que se adapta mejor a lo que se denomina juego con contrincante. Hay que tener en cuenta que usaremos esta estrategia en juegos en los que no influya el azar (como en juegos de cartas), sino en lo que denominaremos juegos perfectamente informados (es decir, que tenemos toda la información tanto de nuestra jugada como la del adversario). Como ejemplo tomaremos como modelo el juego del 3 en raya o tic-tac-toe por ser más sencillo.
El algoritmo minimax construye un árbol partiendo del estado actual del juego. Supongamos que en el siguiente turno le toca mover al ordenador. A partir del estado actual del juego (es decir, la disposición de las piezas en el tablero) construiremos un nodo hijo por cada posible movimiento legal que puede realizar el ordenador (llamaremos al ordenador jugador MAX). En el siguiente nivel, por cada posible movimiento del ordenador generaremos los posibles movimientos legales que podría realizar el jugador humano (llamaremos al usuario jugador MIN), y así sucesivamente hasta llegar a un nodo (que llamaremos nodo terminal) en el que haya un desenlace válido, es decir, que gane el ordenador, que gane el jugador o que haya empate. Es decir, que en cada nivel del árbol se van alternando el jugador MAX y el jugador MIN (de ahí el nombre de estrategia minimax). Si representamos con un cuadrado los nodos MAX y con un círculo los nodos MIN, un posible despliegue de un árbol minimax sería el siguiente.

Cada vez que llegamos a un nodo terminal usamos lo que llamaremos función de evaluación, que no es más que una función que sopesa qué tan buena es la solución a la que conduce ese nodo terminal, asignándole un valor numérico. En el caso del tic-tac-toe la función es muy sencilla. Por ejemplo, podríamos asignar un +1 a los nodos terminales en los que gana el ordenador, un 0 en los que se produce empate y un -1 en los que gana el jugador humano.
En el siguiente esquema vemos un posible despliegue minimax para el juego del tic-tac-toe.

El algoritmo evalúa cada nivel del árbol de abajo hacia arriba, y en los niveles MAX elegirá los caminos que conduzcan a puntuaciones más altas, que son las que favorecen al ordenador, y en los niveles MIN tratará de escoger aquellos caminos con menor puntuación, ya que penalizan al jugador humano.
Veámoslo con un ejemplo. En la figura de arriba se despliega un árbol a partir del estado actual de juego (nodo MAX). La función de evaluación recorre el árbol hasta llegar a los nodos terminales, y los puntúa con +1 para nodos donde gana el ordenador, 0 para empate y -1 para nodos donde gana el jugador humano. En la gráfica se marca con +1 el nodo inferior derecho y el inferior izquierdo (gana MAX) y con 0 los dos centrales (tablas).
Los nodos inmediatamente superiores son nodos MAX, por lo que puntuaremos los estados con el mayor valor de los hijos (en esta caso, los que tienen descendencia sólo tienen un hijo). Vemos que en este nivel hay dos nodos terminales en los que gana MIN, así que los marcamos con -1.
El siguiente nivel inmediatamente superior es el turno de MIN, por lo que seleccionaremos las menores puntuaciones de los nodos hijos. En el estado de la izquierda nos quedamos con -1 que es el menor, en el central con -1 y en el de la derecha con 0.
Finalmente, el nodo raíz es una nodo MAX por lo que seleccionará el mayor de los valores de los nodos hijos, en este caso el 0. Es decir, el siguiente movimiento del ordenador será el que está etiquetado con 0 por lo que pondrá la X en la casilla lateral izquierda de la línea central.

Una vez mueva el jugador humano realizará la misma operación para volver a elegir el siguiente movimiento.

El algoritmo es más o menos como sigue.

1. minimax(jugador, tablero)
2.     Si es nodo terminal devolver ganador.
3.    
4.     nodos_hijos=todos los movimientos legales desde el estado actual
5.     Si es el turno de MAX
6.         devolver valor máximo de la llamada a minimax() para cada nodo hijo.
7.     Sino
8.         devolver valor mínimo de la llamada a minimax() para cada nodo hijo.

Se trata, como se puede observar de una implementación recursiva de un recorrido en profundidad.

.- No parece un algoritmo muy complicado de implementar -dijo el Sr. Lego, sorprendiéndome de cómo habían evolucionado últimamente sus capacidades. Seguro que podría implementarlo -continuó.

.- Lo animo a usted a intentarlo Sr. Lego.

No habían pasado ni un par de horas cuando el Sr. Lego me presentó el siguiente código en Python.

1. #! /usr/bin/python
2. import sys
3.  
4. MAX = 1
5. MIN = -1
6. global jugada_maquina
7.  
8. def minimax(tablero, jugador):
9.     global jugada_maquina
10.  
11.     # Hay ganador o tablas? (nodo terminal)
12.     if game_over(tablero):
13.         return [ganador(tablero), 0]
14.  
15.     # generar las posibles jugadas
16.     movimientos=[]
17.     for jugada in range(0,len(tablero)):
18.         if tablero[jugada] == 0:
19.             tableroaux=tablero[:]
20.             tableroaux[jugada] = jugador
21.  
22.             puntuacion = minimax(tableroaux, jugador*(-1))
23.             movimientos.append([puntuacion, jugada])
24.  
25.  
26.     if jugador == MAX:
27.         movimiento = max(movimientos)
28.         jugada_maquina = movimiento[1]
29.         return movimiento
30.     else:
31.         movimiento = min(movimientos)
32.         return movimiento[0]
33.  
34.  
35. def game_over(tablero):
36.     # Hay tablas?
37.     no_tablas = False
38.     for i in range(0,len(tablero)):
39.         if tablero[i] == 0:
40.             no_tablas = True
41.  
42.     # Hay ganador?
43.     if ganador(tablero) == 0 and no_tablas:
44.         return False
45.     else:
46.         return True
47.  
48.  
49. def ganador(tablero):
50.     lineas = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]]
51.     ganador = 0
52.     for linea in lineas:
53.         if tablero[linea[0]] == tablero[linea[1]] and tablero[linea[0]] == tablero[linea[2]] and tablero[linea[0]] != 0:
54.             ganador = tablero[linea[0]]
55.  
56.     return ganador
57.  
58. def ver_tablero(tablero):
59.     for i in range(0,3):
60.         for j in range(0,3):
61.             if tablero[i*3+j] == MAX:
62.                 print 'X',
63.             elif tablero[i*3+j] == MIN:
64.                 print 'O',
65.             else:
66.                 print '.',
67.  
68.         print ''
69.  
70.  
71. def juega_humano(tablero):
72.     ok=False
73.     while not ok:
74.         casilla = input ("Casilla?")
75.         if str(casilla) in '0123456789' and len(str(casilla)) == 1 and tablero[casilla-1] == 0:
76.             if casilla == 0:
77.                 sys.exit(0)
78.             tablero[casilla-1]=MIN
79.             ok=True
80.     return tablero
81.  
82.  
83. def juega_ordenador(tablero):
84.     global jugada_maquina
85.     punt = minimax(tablero[:], MAX)
86.     tablero[jugada_maquina] = MAX
87.     return tablero
88.  
89.  
90. if __name__ == "__main__":
91.     print 'Introduce casilla o 0 para terminar'
92.     tablero = [0,0,0,0,0,0,0,0,0]
93.  
94.     while (True):
95.         ver_tablero(tablero)
96.         tablero = juega_humano(tablero)
97.         if game_over(tablero):
98.             break
99.  
100.         tablero = juega_ordenador(tablero)
101.         if game_over(tablero):
102.             break
103.  
104.     ver_tablero(tablero)
105.     g = ganador(tablero)
106.     if g == 0:
107.         gana = 'Tablas'
108.     elif g == MIN:
109.         gana = 'Jugador'
110.     else:
111.         gana = 'Ordenador'
112.  
113.     print 'Ganador:' + gana
114.  

El Sr. Lego hizo varios intentos infructuosos de ganar al ordenador. Siempre quedaban en tablas.
Sr. Lego, por mucho que lo intente, no conseguirá ganarle nunca -dije.

.- ¿Cómo puede ser eso? ¿quieres decir que si implemento un ajedrez o unas damas usando la estrategia minimax también será invencible?

.- Desgraciadamente no -contesté. En el caso del tic-tac-toe, el tablero de juego es tan pequeño que podemos desplegar el árbol completo de juego, es decir, que el ordenador conoce de antemano todas las posibles jugadas. Con lo cuál es imposible sorprenderlo.
Sin embargo, en juegos como el ajedrez o las damas las posibilidades se disparan exponencialmente. Por ejemplo, si quisiéramos desplegar un juego completo de las damas tendríamos nada más y nada menos que 10^40 nodos no terminales. Si nuestro ordenador procesara 1000 nodos por segundo tardaría 10000000000000000000000000000000000000 segundos, es decir, 3,171*10^23 millones de años. Teniendo en cuenta que la edad de universo se estima en 15.000 millones de años, si hubiéramos ejecutado nuestro juego el día del Big Bang, ahora mismo no llevaría ni un 1% del tablero completamente escrutado.

.- El sr. Lego me miraba con cara de incredulidad, así que me apresuré a explicarle cómo se utilizaba el algoritmo minimax en estos juegos.

.- Realmente Sr. Lego, hay formas de acelerar el proceso. Uno de los métodos que se utilizan es la poda alpha-beta, pero de esto hablaremos otro día si le apetece.
En la vida real, normalmente no se expanden más de 4 ó 5 niveles del árbol de juego. Los nodos que antes llamábamos terminales ahora los llamaremos nodos frontera, ya que no terminan el juego, pero no podemos permitirnos descender más (Si el juego está muy avanzado sí que podremos encontrar nodos terminales). El peso de la estrategia recae ahora de forma aplastante sobre la función de evaluación. La función de evaluación lo tiene fácil en los nodos terminales, pero en los nodos frontera tiene que ser capaz de evaluar lo bueno que es dicho nodo frontera y asignarle un valor numérico. Para ello se utilizan diferentes heurísticas y dependiendo de lo buena que sean, mejor jugará el programa. Ejemplos de heurísticas para un juego de ajedrez podrían ser: Las piezas que quedan en el tablero, la estructura de los peones, el control de la parte central del tablero, el avance a posiciones cercanas al rey contrario, la posibilidad de enroque, la seguridad del propio rey, etc...

.- Es decir, que en el fondo, los programas de ajedrez actuales no son capaces de ir más que a 4 ó 5 jugadas por delante ¿no?

.- Efectivamente, y por eso, un jugador muy adiestrado puede ganar a un ordenador. Además, en los juegos de ajedrez tradicionales no se suele ir más allá de un par de niveles en el modo fácil.
De todas formas, los programas de ajedrez utilizan una serie de recursos adicionales a las estrategias de búsqueda en árboles, como librerías de aperturas y otros mecanismos basados en sistemas expertos.

El Sr. Lego hizo un par de intentos adicionales de ganar a su propio programa, pero quedó en tablas.

.- Estúpido juego. La única forma de ganar es no jugar -sentenció el Sr. Lego.