La máquina invencible 2

No es que no valore ciertas virtudes como la tenacidad, pero en el caso del Sr. Lego la cosa va un paso más allá. No es el programador más brillante de la empresa, pero sin duda lo suple sobremanera. Y es que cuando se propone algo, nada ni nadie puede apartarlo de su objetivo.
Todo empezó unos días antes cuando tuvimos una charla sobre inteligencia artificial en juegos y el algoritmo minimax. Desde alquel día andaba obsesionado con hacer un juego al que él jugaba de pequeño: El Conecta 4. Un juego de dos jugadores en el que hay que insertar fichas y apilarlas verticalmente para conseguir hacer una línea de 4 fichas del mismo color, ya sea horizontal, vertical o en diagonal.
Recuerdo haber pasado horas en mi infancia jugando a aquél juego, pero creo que el nivel de obsesión del Sr. Lego, en relación al juego, era muy superior al mío.
Usando el algoritmo minimax, el Sr. Lego, había conseguido hacer jugar al ordenador de forma bastante decente, aunque como yo había podido ganarle un par de veces, el quería más. Quería que el programa fuera capaz de ganar siempre.

Sr. Lego, su programa juega bastante bien, le dije. pero si quiere que sea más inteligente, no le queda más remedio que llegar a un nivel más profundo en la exploración del árbol de estado del juego.
El Sr. Lego me miró con cara de frustración y me dijo que lo había intentado, pero que si subía en un nivel la profundidad de la exploración del árbol, el tiempo que tardaba en "pensar" una jugada subía exponenialmente.
Efectivamente Sr. Lego, como ya comentamos cuando hablamos del algoritmo minimax, expandir el árbol más allá de unos pocos niveles no es factible. Aun así, podemos recurrir a algunas técnicas para mejorar el algoritmo, de forma que podamos plantearnos desplegar algún que otro nivel más sin penalización de tiempo.
Al Sr. Lego se le iluminó la cara: ¿Cómo? ¿Cómo puede hacerse eso?
La respuesta a sus plegarias se llama poda alfa-beta, Sr. Lego. Además, todavía podemos hacer un poco más óptimo el algoritmo minimax.
Fíjese -continué- que cuando usamos el algoritmo minimax, cada vez que el ordenador ensaya una jugada (despliega un nodo hijo en el árbol) tiene que mirar si está en un nivel MIN o en un nivel MAX, y dependiendo de esto elegir el nodo sucesor con mayor o con menor valor. En un juego como el Conecta 4, que tiene un factor de ramificación de 7 implica que si desplegamos el árbol hasta una profundidad de 5 niveles tendremos que hacer esa misma comprobación 7+7^2+7^3+7^4+7^5=19607 veces. Si pudiéramos evitar esta comprobación nos ahorraríamos algunos ciclos de CPU.
- ¿Así podríamos usar ese tiempo para poder descender más niveles? ¿no? preguntó el Sr. Lego.
Bueno, -contesté- ahorramos algo de tiempo y para despliegues de pocos niveles quizás notemos alguna mejora, pero me temo que esa mejora de tiempo es despreciable en comparación a como crece el tiempo necesario de cálculo para descender un nivel más en el árbol. Aun así, como le explicaré más adelante, nos va a venir bien eliminar esas comprobaciones, ya que nos va a facilitar también la implementación de la poda alfa-beta.
- No se me ocurre como quitar esas comprobaciones, hay que saber siempre si estamos en un nivel MIN o MAX ya que si no, no podremos quedarnos con el valor adecuado.
Le dare una pista Sr. Lego, si se fija un poco, la siguiente igualdad matemática es fácilmente demostrable:

max(x, y) = -min(-x, -y)

Por ejemplo, estará de acuerdo conmigo en que

max(3,5) = -min(-3, -5) = -(-5) = 5

El Sr. Lego no respondió, estaba intentando desentrañar cómo esta igualdad matemática podía mejorar en algo el algoritmo minimax. Le dejé un poco de tiempo para pensar y en pocos segundos chasqueó los dedos y gritó: ¡lo tengo!
Si cada vez que descendemos un nivel en el árbol cambiamos el signo de la mayor de las puntuaciones obtendremos un resultado equivalente al del algoritmo minimax, sólo que como ahora siempre nos quedamos con el mayor valor de todos los hijos, no hace falta saber en qué nivel estamos, ya que siempre que estemos en un nivel MAX el valor de la función de evaluación será positivo y cuando estemos en un nivel MIN el valor será negativo.
Touché -respondí- acaba de dar en la diana Sr. Lego. De hecho este algoritmo es conocido como negamax, y su pseudocódigo sería el siguiente:

1. negamax(jugador, tablero)
2.     Si es nodo terminal o frontera devolver ganador.
4.     nodos_hijos=todos los movimientos legales desde el estado actual
5.         devolver valor máximo de la llamada a -negamax() para cada nodo hijo.
6.            
7.  

Como puede observar Sr. Lego, nos ahorramos una comparación y también la selección del máximo o el mínimo (más comparaciones).

- ¿Y en qué consiste esa poda alfa-beta? -preguntó el Sr. Lego visiblemente impaciente.
Vamos a verlo con un sencillo ejemplo. Imagine el siguiente despliegue de un árbol minimax (que como hemos visto es equivalente a un despliegue negamax).

Como puede observar, Sr. Lego, es un despliegue del árbol de juego en el que en los niveles MAX elegimos la mejor puntuación de los nodos hijos y en los nodos MIN, la menor.
Vamos a fijarnos en los dos nodos marcados con un asterisco rojo. Vamos a suponer que aún no los hemos evaluado, es decir, no tienen ningún valor asignado. Empecemos por el primero, el de más a la izquierda:
Se trata de un nodo MAX, por lo tanto, su padre es un nodo MIN. Es decir, el padre cogerá el valor menor entre 41 y el que salga de evaluar los dos nodos hijos (50 y 17). Cuando el algoritmo evalúe el primer hijo (50) ya sabemos dos cosas.
- Como el nodo marcado con el asterisco es un nodo MAX, su valor va a ser como mínimo 50 (si los otros hijos son menores serán descartados por tratarse de un nodo MAX).
- Como el padre del nodo marcado con el asterisco es un nodo MIN se quedará con el menor de los valores de sus hijos, es decir, elegirá entre 41 y (como mínimo) 50. Por lo tanto, no importa el valor del resto de hijos del nodo marcado con el asterisco, ya que va a elegir el nodo con valor 41 siempre.

Lo mismo sucede con el otro nodo de la derecha. Como es un nodo MIN y el primero de sus hijos tiene un valor de 23, este nodo tendrá como mínimo valor 23 o menor, pero nunca mayor. Como el nodo padre es MAX siempre elegirá al hijo con valor 41 antes que al otro que tendrá 23 o menor.

Esto nos permite desechar partes completas del árbol ahorrando el despliegue de un montón de ramas. Es como si las cortáramos, por eso llamamos a este algoritmo poda alfa-beta.
En la siguiente gráfica vemos el resultado de aplicar el algoritmo, señalando con una X las ramas que son podadas.

El algoritmo se llama poda alfa-beta porque vamos a utilizar dos variable (alfa y beta) para recordar y propagar hacia arriba el valor de los nodos. Si en un nodo concreto observamos que el valor de alfa es mayor o igual que el de beta, podamos la rama.
Se estima que este algoritmo mejora en un 30% el rendimiento de minimax o negamax.
El algoritmo es como sigue:

1. minimax_alfa_beta(jugador, tablero, alfa, beta)
2. Si es nodo terminal devolver ganador.
4. nodos_hijos=todos los movimientos legales desde el estado actual
5. Si es el turno de MAX
6.     por cada nodo hijo:
7.         puntuacion=minimax_alfa_beta(MIN, tablero_hijo, alfa, beta)
8.         si puntuacion>alfa entonces alfa=puntucaion
9.         si alfa>=beta entonces devolver alfa (poda)
10.  
11.     devolver alfa
12. Sino
13.     por cada nodo hijo:
14.         puntuacion=minimax_alfa_beta(MAX, tablero_hijo, alfa, beta)
15.         si puntuacion<beta entonces beta=puntucaion
16.         si alfa>=beta entonces devolver beta (poda)
17.  
18.     devolver beta
19.  

Hay que tener en cuenta que la primera llamada a la función minimax_alfa_beta() hay que hacerla con los valores:
alfa = -infinito
beta = +infinito

Para el algoritmo negamax la cosa es incluso más sencilla, ya que no hay que ir comprobando si es el turno de MIN o de MAX:

1. negamax_alfa_beta(jugador, tablero_hijo, alfa, beta)
2.     Si es nodo terminal o frontera devolver ganador.
4.     nodos_hijos=todos los movimientos legales desde el estado actual
5.     por cada nodo hijo:
6.         puntucion = -negamax_alfa_beta(-jugador, tablero, -beta, -alfa)
7.         si puntucion>alfa entonces alfa=puntuacion
8.         si alfa>=beta devolver alfa
9.  
10.     devolver alfa
11.  

El Sr. Lego siguió todo el día entusiasmado pensando cómo mejorar su juego Conecta 4. Al día siguiente llegó con el siguiente listado en Python y una cara de sueño que indicaba que se había pasado la noche en vela. No sé si implementando el juego o jugando con él.

1. import sys
2. import copy
3.  
4. MAX = 1
5. MIN = -1
6. MAX_PROFUNDIDAD=4    
7.  
8. def negamax(tablero, jugador, profundidad, alfa, beta):
9.     max_puntuacion = -sys.maxint-1    
10.     alfa_local = alfa  
11.     for jugada in range(7):
12.         # columna totalmente llena?
13.         if tablero[0][jugada] == 0:
14.             tableroaux = copy.deepcopy(tablero)
15.             inserta_ficha(tableroaux, jugada, jugador)
16.             if game_over(tableroaux) or profundidad==0:
17.                 return [evalua_jugada(tableroaux, jugador), jugada]
18.             else:
19.                 puntuacion = -negamax(tableroaux, jugador*(-1), profundidad-1, -beta, -alfa_local)[0]
20.             if puntuacion>max_puntuacion:
21.                 max_puntuacion = puntuacion
22.                 jugada_max=jugada
23.  
24.             # poda alfa beta
25.             if max_puntuacion >= beta:
26.                 break
27.             if max_puntuacion > alfa_local:
28.                 alfa_local = max_puntuacion
29.  
30.     return [max_puntuacion, jugada_max]
31.    
32.  
33. def evalua_jugada(tablero, jugador):
34.     n2=comprueba_linea(tablero, 2, jugador)[1]
35.     n3=comprueba_linea(tablero, 3, jugador)[1]
36.     n4=comprueba_linea(tablero, 4, jugador)[1]
37.     valor_jugada = 4*n2+9*n3+1000*n4
38.     return valor_jugada
39.  
40.  
41.  
42. def game_over(tablero):
43.     # Hay tablas?
44.     no_tablas = False
45.     for i in range(7):
46.         for j in range(7):
47.             if tablero[i][j] == 0:
48.                 no_tablas = True
49.  
50.     # Hay ganador?
51.     if ganador(tablero)[0] == 0 and no_tablas:
52.         return False
53.     else:
54.         return True
55.  
56.  
57.  
58. def comprueba_linea(tablero, n, jugador):
59.     # Comprueba si hay una linea de n fichas
60.     ganador = 0
61.     num_lineas = 0
62.     lineas_posibles=8-n
63.  
64.     # Buscar linea horizontal
65.     for i in range(7):
66.         for j in range(lineas_posibles):
67.             cuaterna = tablero[i][j:j+n]
68.             if cuaterna == [tablero[i][j]]*n and tablero[i][j]!=0:
69.                 ganador = tablero[i][j]
70.                 if ganador==jugador:
71.                     num_lineas=num_lineas+1;
72.  
73.     # Buscar linea vertical
74.     for i in range(7):
75.         for j in range(lineas_posibles):
76.             cuaterna=[]
77.             for k in range(n):
78.                 cuaterna.append(tablero[j+k][i])
79.             if cuaterna == [tablero[j][i]]*n and tablero[j][i]!=0:
80.                 ganador = tablero[j][i]
81.                 if ganador==jugador:
82.                     num_lineas=num_lineas+1;
83.  
84.     # Buscar linea diagonal
85.     for i in range(4):
86.         for j in range(lineas_posibles-i):
87.             cuaterna1=[]
88.             cuaterna2=[]
89.             cuaterna3=[]
90.             cuaterna4=[]
91.  
92.             for k in range(n):
93.                 cuaterna1.append(tablero[i+j+k][j+k])
94.                 cuaterna2.append(tablero[i+j][i+j+k])
95.                 cuaterna3.append(tablero[i+j+k][6-(j+k)])
96.                 cuaterna4.append(tablero[j+k][6-(i+j+k)])
97.  
98.             if cuaterna1==[cuaterna1[0]]*n and tablero[i+j][j]!=0:
99.                 ganador = tablero[i+j][j]
100.                 if ganador==jugador:
101.                     num_lineas=num_lineas+1;
102.  
103.             elif cuaterna2==[cuaterna2[0]]*n and tablero[i+j][i+j]!=0:
104.                 ganador = tablero[i+j][i+j]
105.                 if ganador==jugador:
106.                     num_lineas=num_lineas+1;
107.  
108.             elif cuaterna3==[cuaterna3[0]]*n and tablero[i+j][6-j]!=0:
109.                 ganador = tablero[i+j][6-j]
110.                 if ganador==jugador:
111.                     num_lineas=num_lineas+1;
112.  
113.             elif cuaterna4==[cuaterna4[0]]*n and tablero[j][6-(i+j)]!=0:                
114.                 ganador = tablero[j][6-(i+j)]                
115.                 if ganador==jugador:
116.                     num_lineas=num_lineas+1;        
117.  
118.     return (ganador, num_lineas)
119.  
120.  
121.  
122. def ganador(tablero):
123.     return comprueba_linea(tablero, 4, 0)
124.  
125.  
126.  
127. def ver_tablero(tablero):
128.     for i in range(7):
129.         for j in range(7):
130.             if tablero[i][j] == MAX:
131.                 print 'X',
132.             elif tablero[i][j] == MIN:
133.                 print 'O',
134.             else:
135.                 print '.',
136.         print ''
137.     print '-------------'
138.     print '1 2 3 4 5 6 7'
139.  
140.  
141.  
142. def inserta_ficha(tablero, columna, jugador):
143.     # encontrar la primera casilla libre en la columna
144.     # y colocar la ficha
145.     ok = False
146.     for i in range(6,-1, -1):
147.         if (tablero[i][columna] == 0):
148.             tablero[i][columna]=jugador
149.             ok=True
150.             break
151.  
152.     return ok
153.  
154.  
155.  
156. def juega_humano(tablero):
157.     ok=False
158.     while not ok:
159.         col = input ("Columna (0=salir)?")
160.         if str(col) in '01234567' and len(str(col)) == 1:
161.             if col==0:
162.                 sys.exit(0)
163.             ok=inserta_ficha(tablero, col-1, MIN)
164.         if ok == False:
165.             print "Movimiento ilegal"
166.  
167.     return tablero
168.  
169.  
170.  
171. def juega_ordenador(tablero):
172.     tablerotmp=copy.deepcopy(tablero)
173.     punt, jugada = negamax(tablerotmp, MAX, MAX_PROFUNDIDAD, -sys.maxint-1, sys.maxint)
174.     inserta_ficha(tablero, jugada, MAX)
175.  
176.     return tablero
177.  
178.  
179.  
180. if __name__ == "__main__":
181.     # tablero de 7x7
182.     tablero = [[0 for j in range(7)] for i in range(7)]
183.  
184.     ok=False
185.     profundidades=[3, 4, 6]
186.     while not ok:
187.         dificultad = input ("Dificulatad (1=facil; 2=medio; 3=dificil): ")
188.         if str(dificultad) in '123' and len(str(dificultad)) == 1:
189.             MAX_PROFUNDIDAD=profundidades[dificultad-1]
190.             ok=True        
191.            
192.  
193.     while (True):
194.         ver_tablero(tablero)
195.         tablero = juega_humano(tablero)
196.         if game_over(tablero):
197.             break
198.  
199.         tablero = juega_ordenador(tablero)
200.         if game_over(tablero):
201.             break
202.  
203.     ver_tablero(tablero)
204.  
205.     g = ganador(tablero)[0]
206.     if g == 0:
207.         gana = 'Tablas'
208.     elif g == MIN:
209.         gana = 'Jugador'
210.     else:
211.         gana = 'Ordenador'
212.  
213.  
214.     print 'Ganador:' + gana