Explicación de como funciona un motor de ajedrez

Para cualquier persona que haya jugado ajedrez por computadora le sera bastante claro que la pc(en cualquiera de sus variedades) juega muy distinto a como juega un humano. El porque de esto lo abordare en otra entrada, en esta explicare como es que la computadora juega.

Hay muchos programas de ajedrez como son stockfish, komodo, gnuchess, houdini, sjeng por mencionar algunos. Bastante distintos entre si en sus detalles, pero el principio general con el que funcionan es el mismo. Para entender como funciona un programa de ajedrez necesitamos entender el concepto de árbol(en el sentido computacional, no el que se planta).

En pocas palabras esto tiene bastante que ver con el factor de ramificación  en si es una estructura llamada árbol que nos permite revisar las posibles jugadas, por ejemplo:

Al inicio del juego tenemos 20 posibles jugadas para las blancas(16 de peones y 4 de caballo) y lo mismo para las negras

Lo que hay que notar en este juego aparentemente sin gracia es que tras la primera jugada es solo 1 de los posibles 400 que pudo ocurrir, tras solo 4 jugadas este numero se dispara a mas de 288 mil millones entonces resolverlo revisando todas las jugadas es imposible(para el que este interesado en como se haría esto la manera se llama BFS) entonces necesitamos recurrir a una heurística(en pocas palabras una manera de revisar el árbol sin checar todas las posibilidades) uno se preguntaría ¿Como? Esa es la parte importante.

Para decidir que partes buscar y cuales no a cada pieza se le asigna un valor numérico donde por ejemplo el rey vale infinito(o un numero arbitrariamente grande) la dama vale 9, un peón vale 1(tabla completa aquí) y como la pieza con menor valor es el peón y la posición también es importante  se tiene una medida fraccionaria que vale centésimas(o milésimas de peón) en base a esto se toman las decisiones.

La razón de los valores numéricos es que las computadoras solo manejan 0 y 1, así que para poder calcular cualquier cosa(quien va ganando, la siguiente jugada etc…)  se necesita una medida que las computadoras puedan entender.

El valor de las piezas en cada motor de ajedrez suele ser el mismo(aunque nada nos impide crear un motor con valores distintos) debido a que son valores que funcionan. Donde suele variar es a los valores que se le da a una posición, a las combinaciones de piezas etc.

Existen bastantes algoritmos que se ocupan en el ajedrez para determinar que jugadas vale la pena explorar (el código de stockfish es abierto para el que quiera ver los detalles algorítmicos de como funciona un motor de ajedrez) y cuales no, en base a un conjunto de reglas se define una función de evaluación y en base a esa función de evaluación se decide cuales ramas del árbol(o sea posibles jugadas) analizar y la jugada que se mueve al final es la que nos haya regresado mejor puntuación en la función de evaluación.

En general los distintos niveles de un motor de ajedrez es decidir que reglas se ocupan para la función de evaluación, donde el nivel 0(o mono en algunas) es no ocupar ninguna regla y tirar al azar, y el nivel máximo es ocupar todas las reglas. En base a esas reglas una computadora actual puede analizar millones de jugadas en pocos segundos.

En pocas palabras se podría decir que es similar a la fuerza bruta en el sentido de que se revisan millones de posibles jugadas, pero distinto en el hecho de que se tiene una idea de donde buscar.

Una analogía bastante tonta(y no 100% correcta) pero que deja claro el punto seria que la fuerza bruta es como tratar de escribir el quijote usando letras al azar, y usar una función de evaluación seria como ocupar palabras completas, una función de evaluación burda es como ocupar palabras de muchos idiomas(por ejemplo árabe, chino, ingles, español) una función de evaluación buena seria solo ocupar palabras de el español y una función de evaluación muy buena seria solo ocupar palabras del español que se ocupan en el quijote. Claramente es posible escribir el quijote completo con cualquiera de estas 3 estrategias, sin embargo bajo estas restricciones es obvio porque una buena función de evaluación tardaría mucho menos que teclear letras al azar.

Escribir buenas reglas para la función de evaluación es una tarea bastante difícil y ahí es donde difieren los distintos motores de ajedrez, cada motor de ajedrez tiene un conjunto de reglas distintas(puede que algunas coincidan pero no todas), por supuesto que también hay otros factores mas relacionados con la eficiencia en la programación y las distintas maneras en la que se puede calcular la función, como se guarden las posibles jugadas entre muchos otros.

Pero lo importante(y aunque sea una simplificación algo inexacta) es que cada pieza tiene un valor, y en base a esos valores se crea una función que ocupa unas reglas, se toma el mejor valor de la función y esa es la jugada que se mueve.

Esta es solo la idea principal de como funciona un motor de ajedrez sin tablas syzygy ni nalimov ni explicar el problema del horizonte ni las técnicas especificas para calcular cuales reglas sirven y cuales no. Ya abra mas entradas sobre eso.

También hay que notar que esto solo explica como funciona un buen motor de ajedrez bajo las nociones estándar,  también es posible crear motores de ajedrez sin funciones de evaluación y solo ocupando reglas o  motores de ajedrez que su objetivo sea perder todas las piezas(para jugar losing chess por ejemplo) pero su funcionamiento es muy parecido. O algún motor de ajedrez que funcione radicalmente distinto, sin embargo esos actualmente son la excepción y no la regla.