¿ COMO “PIENSAN” LAS COMPUTADORAS QUE JUEGAN AJEDREZ ?
(2ª parte)
**************************************
**************************************
Comentarios a. herguz.ajedrez@gmail.com
Hoy continuamos tratando de explicar en el lenguaje más sencillo la forma cómo se implementa un programa para jugar ajedrez, al menos la base matemática usada por estos programadores, para hacer que un programa seleccione una jugada y que esta selección sea capaz de solucionar el problema que la posición exige en ese momento o también que cree la mayor cantidad de problemas a su rival. Dividiré el asunto de jugar ajedrez, como siempre se ha hecho a lo largo de la historia ajedrecística, enfocándonos por separado en tres sub-problemas clásicos: la apertura, el medio juego y el final.
En la apertura los programas más fuertes hacen uso de una gran base de datos de aperturas (libro de aperturas), lo que simplemente haría el programa es seleccionar la mejor jugada siguiendo el libro de aperturas, entendiendo por “mejor” la jugada que estadísticamente le dé mayor probabilidad de ganar, así que para un programador esta selección que no depende de ninguna función de evaluación ni algoritmo refinado de selección es relativamente fácil, y solo requiere de mecanismos que puedan administrar y ordenar correctamente una base de datos, previamente creada. Hay programas más avanzados que pueden ser configurados para jugar una determinada línea de apertura con fines de entrenamiento, de esta manera “le hace caso“ al usuario entrando en la línea que le pidieron y jugando según lo recomendado en el libro, hasta el momento que no consigue respuesta posible en el libro, disponiéndose ahora a usar los algoritmos de búsqueda y selección de jugadas (generalmente MiniMax y poda alphaBeta que explicaré mas adelante) y jugar como lo haría en el medio juego. Hasta aquí, esto no se diferencia mucho a como piensa un Gran Maestro con un gran bagaje de conocimientos teóricos de apertura.
En el caso de los finales el problema se puede resolver de manera similar si hacemos uso por ejemplo de las Tablas de Nalimov, que también son unas bases de datos que tienen guardada la información del número de jugadas necesarias para que se dé el jaque mate, en finales de 3, 4, 5 y 6 piezas, contando como una pieza al rey.
Lo podemos entender mejor, si consideramos la siguiente posición (5 piezas), que fue puesta en el Fritz 11 con las tablas de Nalimov cargadas, al pedirle que analice la posición jugando las blancas, Fritz devuelve la evaluación:
1) Ta2(#28) 1) Rd4(#28) 1) Rd3(#29) 1)Tf2(#34) el número entre paréntesis indica la cantidad de jugadas necesarias para alcanzar el jaque mate de parte de las blancas, a estos cuatro movimientos los antecede con el símbolo + -
es decir, son jugadas ganadoras para las blancas, mientras que las jugadas 1) Th2(-#18) y 1) Tc6(-#17) las acompaña con el símbolo -+ pues obviamente son errores graves y regalan el final a las negras. Todas las demás jugadas de las blancas las evalúa como 0.00, pues no hay ganancia posible con un juego correcto de ambos bandos, y lleva a tablas.
Así, como conclusión las Tablas de Nalimov nos dice que la posición es ganadora si juegan las blancas cualquiera de las cuatro primeras jugadas, en caso contrario es tablas o pierde.
En realidad no es difícil entender la filosofía de resolver el problema de los finales usada por las Tablas de Nalimov, actualmente las T.N. solucionan sin ningún error cualquier final hasta de 6 piezas, y se están desarrollando las bases de datos para 7 o más piezas; cabría hacernos entonces la siguiente pregunta: Si las Tablas de Nalimov se pueden desarrollar hasta 32 piezas, en teoría un programa de ajedrez sería capaz de decidir, “juego 1) e4 con las blancas y obtengo el jaque mate en la jugada 165 aunque mi rival plantee cualquier Siciliana, Francesa o Caro-kan de manera perfecta” ó “Si realizo 1)d4 la partida es tablas jugando correctamente las blancas y negras.
Si un programa de ajedrez, fuera capaz de plantear y responder de manera acertada preguntas como estas, entonces estaríamos siendo testigos de la muerte del ajedrez como disciplina intelectual humana, y los jugadores y aficionados nos convertiríamos en simples espectadores para saber cuál de los programas resuelve el problema de ganar la partida de la manera más rápida y eficiente, ó en su defecto estaríamos buscando alternativas al ajedrez clásico, como la modalidad 960 de Fischer, para poder encontrar alguna motivación en competencias entre humanos, con todos nuestros errores o diferencias de criterios teóricos, estratégicos o tácticos, muy propios de la naturaleza humana, formando parte esencial de la belleza de nuestro arte.
Afortunadamente esta hipotética situación está bastante lejana en el tiempo, pues hoy en día las T.N. para seis piezas, necesitan 7 Gb de espacio de almacenamiento y una buena velocidad del procesador y memoria, y esta cantidad de recursos computacionales crece de manera exponencial a medida que agregamos una pieza más a la base de datos, es necesario tener discos duros de miles de Terabytes de capacidad y procesadores mucho más potentes que los actuales, por lo que esta muerte del ajedrez no la viviremos al menos en esta generación.
Así que exceptuando la apertura y el final, el problema de jugar correctamente una partida de ajedrez por parte de un programa, sigue siendo un problema de inteligencia artificial más que de manejo eficaz de una base de datos.
A continuación voy a tratar de explicar la manera como se enfoca el medio juego, por parte de los programas ajedrecísticos, para ello debo definir previamente algunos conceptos como árbol de juego, profundidad y ramificación del árbol, nodos y caminos, y evaluación de los nodos, trataré como hasta ahora de usar el lenguaje más básico posible, apoyándome en la matemática mas “light” necesaria, así como algunos conceptos elementales de estructura de datos, con la finalidad que esta monografía sea accesible a todos.
Partiremos de un concepto esencial manejado por los estudiosos de la teoría de juegos, el ajedrez está catalogado como “un juego bipersonal de suma cero y de información perfecta” ¿Qué significa esto?, sencillamente es así porque el ajedrez es jugado por dos rivales con intereses diametralmente opuestos respecto a la finalidad, uno de ellos gana y el otro pierde, ó entablan los dos (juego bipersonal), donde para que uno de ellos gane el otro debe perder o en su defecto, repartirse la ganancia en partes iguales (de suma cero), esta última cualidad excluye resultados imposibles como, los dos ganaron o los dos perdieron. Y además es de información perfecta porque ambos jugadores saben las reglas del juego y conocen los movimientos que ha efectuado el contrario antes de decidir su próxima jugada. No todos los juegos tienen esta triple cualidad, piensen por ejemplo en el dominó o el póquer.
Un árbol de juego es un conjunto de elementos llamados nodos del árbol, los cuales están enlazados mediante líneas llamados caminos y que permiten pasar de un nodo a otro, mediante la aplicación de reglas llamadas jugadas válidas.
Para no “teorizar” más de lo necesario, observemos el siguiente gráfico donde se ilustra un árbol de juego del ajedrez, que abarca en cada nodo diferentes estados del tablero empezando con la posición en que se jugó 1) e4 por parte de las blancas:
Vemos que los nodos son simplemente los círculos ajedrezados que representan una posición del tablero, desde la posición inicial (nivel cero), observamos que en este árbol de juego podemos pasar del nivel cero al uno, mediante la jugada de las blancas 1) e4, así que el nodo que está en el nivel uno, representa la posición del tablero después de efectuado este movimiento, entonces un camino, representado por una flecha es simplemente una jugada válida que permite pasar de un estado del tablero a otro. Si observamos un nivel más abajo (nivel dos), tendríamos varias jugadas posibles (4 caminos), bien sea si las negras se deciden en su primer movimiento por la defensa siciliana, peón rey, francesa o caro-kan (se han obviado algunos movimientos jugables con el fin de hacer más sencilla la explicación del árbol de juego), a este nivel decimos que el árbol presenta una ramificación igual a cuatro, es decir la ramificación del árbol en un determinado nivel es el número de nodos presentes en él, y la máxima ramificación del árbol de juego, es el mayor valor de ramificación en todos los niveles, en nuestro ejemplo, la máxima ramificación es cuatro. Y la profundidad del árbol, es el número de niveles necesarios que hay que bajar para llegar a los nodos terminales, en este árbol la profundidad es tres.
Ya hemos hablado en la entrega anterior de las funciones de evaluación, que son capaces de valorar cada nodo (posición del tablero), y asignarle un número positivo o negativo, tomado en cuenta elementos estratégicos y/o tácticos presentes en determinada posición. Hablaremos la próxima semana de cómo se implementan estas funciones así como también la forma que el programa recorre el árbol de juego y de qué manera decide la jugada “mejor”, maximizando las ganancias para su propia causa y minimizando las de su oponente (algoritmo MiniMax).
Hablaremos también que el programa debe hacer una búsqueda heurística (es decir una búsqueda inteligente), para descartar nodos en el árbol y así reducir su profundidad, su ramificación o ambas cosas, pues recordemos que ya hicimos un análisis donde se establece que el número de posiciones posibles durante una partida de solo 40 jugadas es más alto que el número de átomos del universo, por lo tanto un programa que trate de construir y valorar cada nodo en un árbol de 40 niveles de profundidad, tomando en cuenta todas las jugadas posibles en cada nivel (ramificación máxima), estaría haciendo un análisis prácticamente infinito para todos los fines prácticos.
Es necesario entonces implementar mecanismos para descartar nodos en el árbol, cuando las jugadas que los generan (caminos), sean de poco valor estratégico-táctico o sean claramente errores garrafales, uno de estos mecanismos es la poda alpha-beta, llamada así por su similitud física del hecho de podar un árbol y cortar sus ramas excedentes.
No hay comentarios:
Publicar un comentario