lunes, 1 de marzo de 2010

Ajedrez. Hombre vs máquina. ¿Intuición o fuerza bruta?

"En lugar de un ordenador que pensaba y jugaba ajedrez como un ser humano, con la creatividad y la intuición humanas, consiguieron uno que jugaba como una máquina, evaluando sistemáticamente 200 millones posibles movimientos por segundo y ganando por pura fuerza bruta." Garry Kasparov sobre Deep Blue.
"Los programas de ajedrez son como motosierras talando el Amazonas" Nigel Short Gran Maestro británico.
Ambos comentarios se hacen eco de una apreciación clásica desde que existen los ordenadores. Estos aplican la fuerza bruta, mientras los humanos somos inteligentes. E intuitivos.
El conocimiento acaba con el misterio. Dejemos la intuición para más adelante. Respecto de los programas de ajedrez, hay múltiples sitios que enseñan como construirlos y desvelan su funcionamiento, su enigma. Y como es de suponer, no hay tal misterio. Un programa de ajedrez realiza un conjunto de instrucciones que el programador ha escrito. Como un programa de contabilidad o una nómina. Y depende del conocimiento que el programador tenga de contabilidad, de nóminas o de ajedrez el que haga un programa bueno o no. Veamos someramente cómo funciona.
El ajedrez es un juego de grandes números. Es finito y teóricamente se puede resolver. En la practica esto no es posible. El mejor ordenador actual tardaría millones de años. En el primer movimiento las blancas tienen 20 jugadas legales (cada peón una o dos casillas (8x2=16) y cada caballo dos casillas (2x2=4)). A su vez las negras pueden jugar otras 20 jugadas. Deep Blue calcularia los 3 primeros movimientos (3 jugadas por bando, es decir, 6 jugadas) en menos de 1 segundo. En cambio, los 4 primeros movimientos los calcularía en ¡2 horas! y los 5 primeros en ¡853 horas! Más adelante el juego se complica y las jugadas posibles son en torno a 35 por bando.
Dejando de lado la entrada/salida, la interfaz de usuario o la representación interna, el programa tiene dos funciones básicas: la evaluación y la búsqueda.
Evaluación
El programa evalúa cada posición de manera estática. Dependiendo de las piezas presentes en el tablero y de su posición, el programa devuelve un número que representa la calidad de la posición. Evalúa en primer lugar el material asignando unos valores equivalentes a Peón=1, Caballo o Alfil=3, Torre=5 y Dama=10. Es decir, de la misma forma que lo haría un humano. Si el programa no es muy malo, usará unos criterios adicionales: el centro ocupado suma puntos, los peones avanzados suman puntos, los caballos en los lados restan puntos, los peones doblados restan puntos, la movilidad de las piezas suma puntos... De nuevo igual que hacen los humanos.
Sumamos los puntos del blanco, restamos los puntos del negro y obtenemos un valor único para la partida. Por ejemplo, -3 significa que las negras tienen una ventaja que equivale a un caballo, con +1 las blancas van ganando el equivalente a un peón.
Búsqueda
El ajedrez es un juego de suma 0. Lo que va bien a las blancas va mal a las negras y viceversa. Por eso no hay un valor para blancas y otro para negras. Un único valor resume el estado de ambas piezas.
Lo primero que hace el programa es buscar las jugadas legales. Para ello recorre cada casilla. Por cada pieza propia que encuentra anota la posición de origen y recorre de nuevo el tablero buscando posibles casillas de destino. ¿Mecánico? Desde luego. A su vez hace múltiples comprobaciones rutinarias ¿hay una pieza en medio? ¿ha sido jaque y no puedo mover? ¿está la pieza clavada y no la puedo mover?... Todo ello sólo para averiguar las jugadas legales, no si son buenas o malas. La ventaja del ordenador es que lo hace con suma rapidez.
Minimax. Para cada jugada legal el programa busca las respuestas del contrario. A su vez, para cada respuesta, busca la propia. Esto crea un árbol de jugadas. Al final llama al módulo de evaluación de posiciones y decide la mejor jugada.
De esta forma el programa analiza todas las jugadas posibles (legales) con la profundidad que le hayamos indicado. Pero como hemos visto, enseguida son demasiadas, astronómicas. Si se limita a 3 jugadas por bando, tendremos un programa bastante malo pero que ganará a muchos jugadores inexpertos. Por otro lado, la profundidad debe de ser variable para enfrentar el llamado problema del horizonte. En el intercambio de piezas, debe seguir aumentando la profundidad hasta llegar a una posición estable. De otro modo puede comer un peón con la dama (con lo que cree que gana un peón) y no analizar la siguiente jugada en la que un caballo se come su dama (con lo que pierde la dama).
Al analizar todas las jugadas posibles a una determinada profundidad, el programa analiza millones de jugadas que un jugador medio descartaría como muy malas. Por ejemplo: el primer movimiento de las blancas ha sido mover el caballo hacia adelante. A nadie (pero al ordenador sí) se le ocurriría en la segunda jugada volver el caballo a su posición inicial. El humano descarta decenas de variantes y millones de jugadas en un instante. Para competir, el ordenador debe también realizar este descarte, esta poda del árbol. Es la función heurística que nos permite hallar una de las mejores soluciones, aunque no sepamos con certeza si es la mejor.
Esto se consigue con el algoritmo alfa-beta. El programa evalúa una posición. Si cuando evalúa la siguiente no encuentra buenas perspectivas de que sea mejor, la descarta sin analizarla por completo. Así, es posible que pierda la mejor jugada, pero descartará la inmensa mayoría de las malas y de este modo dedicará todos los recursos a analizar con mayor profundidad (quizá 9 o 10 movimientos) las jugadas más prometedoras.
El algoritmo alfa-beta funciona mejor si la primera jugada elegida, con la que comparar las demás, es una de las mejores. Aquí, de nuevo, el conocimiento de ajedrez que tenga el programador (y su habilidad para trasladar el conocimiento a líneas de código) será esencial. El programa debería empezar de forma parecida a como lo hace un humano: primero los movimientos que llevan capturas (intercambio de piezas), después amenazas, después movimientos hacia el centro y hacia adelante y al final movimientos hacia atrás.
El ordenador cuenta por último con una poderosa herramienta en la que de nuevo bate a los humanos sin compasión: las bases de datos para las aperturas y para los finales. Existe una amplia teoría de las aperturas en las que están registradas todas las aperturas buenas conocidas hasta el momento. El jugador experto y el ordenador jugarán mecánicamente las primeras jugadas hasta que el contrario o uno mismo se salga de la teoría. En algunos casos las aperturas pasan del movimiento diez. La memoria del ordenador supera con creces a la del humano y será mucho más eficiente en saber si una posición está o no en su base de datos y como responder a ella. Parecido es el caso de los finales. Casi todos los finales de 6 piezas o menos han sido analizados por completo y son almacenados en el ordenador. Eso significa que el programa sabe cual es la linea a seguir y si ganará o perderá (si el contrario juega bien) la partida. Además, si en el medio juego descubre una linea que lleve a un final ganador que tenga almacenado, detendrá el análisis y optará por dicha línea.
Intuición
(RAE) intuición.
1. f. Facultad de comprender las cosas instantáneamente, sin necesidad de razonamiento.
4. f. Fil. Percepción íntima e instantánea de una idea o una verdad que aparece como evidente a quien la tiene.
Magnus Carlsen es la estrella rutilante del ajedrez de hoy. El jugador más joven en conseguir el número uno mundial. Nacido en Noruega ha jugado siempre con máquinas y hoy es entrenado por Kasparov que dice de él que su destreza se arraiga en una profunda intuición que ninguna máquina puede enseñar. Magnus por su parte dice: "Es difícil de explicar. A veces siento como bueno un movimiento"
Al contrario que en el ordenador, en la mente sí hay misterio. Desvelar sus secretos no es algo que esté próximo. El proceso mental parece ser: un número grande de posibilidades se calculan inconscientemente. De ellas sólo unas pocas pasan el umbral y se hacen conscientes. A este proceso inconsciente se le llama intuición. En él intervienen recuerdos, reconocimiento de patrones (alfiles en diagonales, reyes enrocados...) y otros procesos que desconocemos. Después, las posibilidades sobrevivientes se analizan conscientemente en el proceso clásico de si muevo el caballo, las negras moverán el peón... En el proceso inconsciente interviene el aprendizaje y es de una gran economía. Los buenos jugadores piensan menos las malas jugadas.
Hombre vs máquina
Fuerza bruta. Parece la gran descalificación de las máquinas. Sin embargo, un programa que no usara todos los recursos del HW sería un programa malo. Lo mismo ocurre con los humanos. Un jugador de ajedrez usa toda la fuerza de que dispone para ganar. Exprime su cerebro al máximo. Utiliza para ello millones de neuronas. ¿Existe diferencia?
Rapidez. Es la gran ventaja del ordenador. Hace menos cosas que el humano y hace cosas muy poco eficientes. Pero lo compensa con la velocidad.
Intuición. Es la gran ventaja del humano. En ajedrez descartar malas jugadas, podar el árbol es la clave. El humano lo hace de forma enormemente eficaz. Implementar mecanismos de poda en los programas de ajedrez es la forma de mejorarlos y en general trasladar el conocimiento ajedrecístico al programa es hacerlo más inteligente.
Enigma.  Desconocemos en gran medida los mecanismos de la mente. Por ello el funcionamiento del cerebro es enigmático. No así el de las máquinas. Las hemos hecho nosotros y sabemos como funcionan. Y lo hacen implementando las estrategias humanas de la mejor forma que el programador ha podido. Podríamos enseñarles a equivocarse, como hacemos los humanos, pero eso es otro juego.
Entrada relacionada: Metáforas de Ajedrez. Comentario de Garry Kasparov

2 comentarios:

  1. Interesante.No se como,pero llegé aquí mirando cosas del cubo de rubik.
    Una pregunta:¿Alguna vez alguna persona en todo el mundo ha superado el máximo nivel de una máquina de ajedrez bien programada?

    ResponderEliminar
    Respuestas
    1. El mejor jugador del mundo es desde hace muchos años una máquina

      Eliminar