El algoritmo fundamental es, en su forma más simple, algo así como Negamax – Wikipedia. En palabras, es así:
- Calcular todos los movimientos legales en la posición actual.
- Mirar todos mis movimientos posibles. Dibuja un árbol donde la raíz es la posición actual, y cada movimiento posible es una rama que lleva a otro nodo – esas son las posibles posiciones siguientes.
- Intenta cada movimiento posible – imagina hacer ese movimiento y calcula la nueva posición. Ahora vuelva al paso 1 y continúe expandiendo el árbol.
Se dará cuenta de que esto nos permite ver todas las partidas de ajedrez posibles, pero tardará básicamente una eternidad. Así que tenemos que modificar el paso 1 limitando la profundidad a un determinado # de movimientos, D:
- Calcular todos los movimientos legales en la posición actual. PERO si ya hemos alcanzado la profundidad D en el árbol, evaluar la posición actual. Registra el resultado en el árbol.
Ahora glosaré la parte crítica ya que está bien explicada en otro lugar: en cada nivel del árbol antes de los nodos «hoja» terminales de profundidad D, miramos todas las evaluaciones en la siguiente posición. Asumimos que quien sea el turno hará la mejor jugada posible para él, así que registramos esa puntuación de la evaluación (y la mejor jugada a realizar) y la propagamos de vuelta (recursivamente) a través del árbol hasta la raíz. El resultado final de esto es que hemos imaginado que en cada posición posible, el jugador a mover hace la mejor jugada posible (asumiendo que pueden ver por delante las evaluaciones en la profundidad D). La mejor jugada posible en la posición raíz original es la que usted haría, asumiendo que su oponente hará las mejores jugadas posibles. El algoritmo Negamax es una forma recursiva superelegante de implementar este algoritmo en sólo unas pocas líneas de código.
Para evaluar una posición y asignarle una puntuación: puede simplemente calcular la cantidad de material de cada bando, y asignar, digamos, +4 si las blancas están por delante con un caballo y un peón. También puede calcular factores posicionales (seguridad del rey, colocación de piezas menores, estructura de peones, etc.) y añadirlos a la puntuación.
Hay toneladas de refinamientos del algoritmo básico Negamax. El principal de ellos es la búsqueda alfa-beta, que ayuda a eliminar las ramas inútiles del árbol del juego. Otros, como la búsqueda de quiescencia, ayudan a evitar el «efecto horizonte», en el que un ordenador hace jugadas que parecen estupendas hasta la profundidad D, pero luego pierde una dama, digamos, en la profundidad D+1 (sin una solución para el efecto horizonte, los ordenadores a menudo empiezan a volverse locos regalando piezas, ya que piensan que la partida termina en la profundidad D). En la búsqueda de quiescencia, el árbol se extiende cuando una posición está llena de jugadas críticas como jaques de rey y capturas.
Por último, hay toneladas de trucos de velocidad (tablas de hash para recordar posiciones previamente vistas; tableros de bits para el cálculo locamente eficiente de las jugadas legales – cosas realmente hermosas y sorprendentes aquí, con tableros representados usando esquemas binarios con 1 bit para cada una de las 64 casillas, ¡que funciona muy bien con los procesadores modernos de 64 bits!tablas de finales que tienen finales para 5 o 6 piezas completamente precalculados, tablas de aperturas con las mejores jugadas seleccionadas de la práctica de los grandes maestros, etc.)
Si usted es un programador, es divertido codificar 1) el generador de jugadas legales, y 2) el algoritmo Negamax, con una simple función de evaluación. Eso es todo lo que usted necesita para hacer un motor de ajedrez básico!
Edición: AlphaZero vino después de que yo contestara originalmente esta pregunta. La búsqueda de árbol monte carlo y la configuración de aprendizaje de refuerzo profundo es diferente de lo que describí anteriormente y merece una respuesta de quora separada, aunque los fundamentos de la búsqueda de árbol siguen siendo importantes. Yo recomendaría aprender sobre la búsqueda tradicional Negamax/alpha-beta primero, y luego aprender sobre AlphaZero.