Dedicado a todos los que ahora están viendo la aclamada serie de televisión "The Queen's Gambit". Más términos de ajedrez en nuestra nueva traducción.
En este artículo, intentaremos comprender cómo funcionan los motores de ajedrez al portar el motor de ajedrez Sunfish a Go. Sunfish se destaca por su simplicidad y pequeño tamaño, pero aún es capaz de jugar un juego de ajedrez decente. Go, por otro lado, es conocido como un lenguaje de programación simple y legible, así que espero que juntos formen una gran pareja.
Para crear un motor de ajedrez, primero debe decidir sobre tres puntos importantes:
- ¿Cómo representar un tablero de ajedrez (cuadrados, piezas, movimientos permitidos)?
- ¿Cómo califica a la junta (quién tiene más probabilidades de ganar)?
- ¿Cómo encontrar el movimiento óptimo?
Los fragmentos de código de esta publicación están simplificados y contienen solo las partes más importantes. Puede encontrar el código completo del motor en github.com/zserge/carnatus (carnatus es el nombre latino de la lubina, especie Sebastes carnatus).
Celdas y formas
Es importante encontrar una representación conveniente del tablero que no ocupe mucho espacio, ya que miles de variaciones del tablero se almacenarán en la memoria mientras se busca el movimiento óptimo.
Por lo general, un tablero es una colección de celdas. Agregaremos relleno alrededor del tablero estándar de 8x8 para que los movimientos de piezas no válidas caigan en esta área. Esto nos permitirá evitar la verificación de límites y simplificar enormemente el código.
Usaremos una matriz lineal. La mayor distancia que puede moverse una pieza de ajedrez es el movimiento de un caballo de 2 casillas. Por supuesto, otras piezas deslizantes pueden moverse largas distancias, pero tales movimientos se evaluarán secuencialmente a medida que se cruza cada casilla, lo que significa que los límites del tablero se detectarán antes de que una pieza pueda ir más allá.
Por lo tanto, necesitamos un espacio de dos celdas a lo largo de los bordes del tablero. Podríamos crear un tablero de 12x12, pero como lo estamos representando como una matriz de líneas, necesitamos un tablero de 12x10 porque el cuadrado de sangría más a la derecha en la línea anterior se puede usar como el cuadrado de sangría más a la izquierda en la siguiente línea (× = sangría):
×××××××××× ×××××××××× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×××××××××× ××××××××××
En nuestra notación, "a1" se vería como 9 × 10 + 1 = 91, y "a8" se vería como "2 × 10 + 1" = 21.
Cada celda en la matriz del tablero representaría una pieza de ajedrez, un cuadrado vacío o una zona de sangría. podría haber utilizado constantes numéricas para estos valores, pero para facilitar la depuración, utilizamos caracteres legibles por humanos. Las letras mayúsculas y minúsculas representan formas, los espacios representan zonas de sangría y los puntos representan celdas vacías:
| | RNBQKBNR | PPPPPPPP | ........ | ........ | ........ | <- ........ | ........ | ........ | pppppppp | rnbkqbnr | | |
Decodificación de abreviaturas
R — rook —
N — knight —
B — bishop —
Q — queen —
K — king —
N — knight —
B — bishop —
Q — queen —
K — king —
Finalmente, podemos empezar a escribir código:
type Piece byte
func (p Piece) Value() int { ... }
func (p Piece) Ours() bool { ... }
func (p Piece) Flip() Piece { ... }
type Board [120]piece
func (b Board) Flip() Board { ... }
type Square int
func (s Square) Flip() Square { ... }
Las formas tienen cierto valor. Estos valores son necesarios para evaluar las posiciones en la junta y comprender quién está ganando. Por lo general, un peón = 100, un caballo = 280, un alfil = 320, una torre = 479, una reina = 929 y un rey es tan valioso que vence a 8 reinas (peones convertidos en reinas) junto con pares de caballos, alfiles y torres. Si tenemos toda esta riqueza, pero perdemos al rey, el conteo seguirá demostrando que perderemos.
Cada tipo tiene un método Flip () que devuelve el mismo valor después de voltear el tablero antes de que el oponente se mueva. Para las formas, cambia el caso del símbolo de forma. En los cuadrados, devuelve 119 cuadrados (contando desde el otro extremo del tablero). En cuanto al tablero, copia todas las piezas de los cuadrados en orden inverso, cambiando su caja.
Generador de golpes
Entonces, ya tenemos los bloques de construcción para el motor y ahora podemos pensar en las posiciones del juego. La posición es un tablero con piezas y estados adicionales en el juego, como una casilla de paso, una casilla errante y posibilidades de enroque. Si quisiéramos simplificar el juego, podríamos reutilizar el tipo de tablero, pero crearemos un tipo de posición separado para los movimientos y la evaluación del tablero.
¿Qué es un movimiento? Esta es una combinación de dos celdas: la celda donde estaba la pieza antes del movimiento y la celda donde se movió la pieza. La posición es un tablero de ajedrez con puntuación, reglas de enroque para cada jugador y casillas de paso / errantes. Ambos tipos también tienen un método Flip () para los movimientos del oponente.
type Move struct {
from Square
to Square
}
func (m Move) Flip() Move { ... }
type Position struct {
board Board //
score int // — ,
wc [2]bool //
bc [2]bool //
ep Square // ,
kp Square // ,
}
func (p Position) Flip() Position { ... }
Ahora podemos escribir el primer método grande: el generador de movimientos permitidos. Solo nos importan las piezas blancas, ya que para jugar con negras volveremos el tablero y volveremos a mover las blancas.
Para generar todos los movimientos válidos, necesitamos:
- haga una lista de todos los movimientos de un paso en cada dirección para cada pieza;
- haga lo mismo con todas las celdas, ignorando las piezas que no sean blancas;
- designar un movimiento en todas las direcciones posibles para cada pieza blanca;
- Si la longitud del movimiento de una pieza no está limitada (torre, alfil, reina), continúe moviéndola hasta que encuentre un obstáculo en el camino: una pieza del oponente o una muesca detrás del borde del tablero.
Este es un código simplificado que no tiene en cuenta la captura y el enroque. Puede encontrar la implementación completa en Github , no es muy diferente.
Para hacer que la aritmética de direcciones sea más legible, usaremos las constantes de dirección N / E / S / W:
const N, E, S, W = -10, 1, 10, -1
var directions = map[Piece][]Square{
'P': {N, N + N, N + W, N + E},
'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
'B': {N + E, S + E, S + W, N + W},
'R': {N, E, S, W},
'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}
func (pos Position) Moves() (moves []Move) {
for index, p := range pos.board {
if !p.ours() {
continue
}
i := Square(index)
for _, d := range directions[p] {
for j := i + d; ; j = j + d {
q := pos.board[j]
if q == ' ' || (q != '.' && q.ours()) {
break
}
if p == 'P' {
if (d == N || d == N+N) && q != '.' {
break
}
if d == N+N && (i < A1+N || pos.board[i+N] != '.') {
break
}
}
moves = append(moves, Move{from: i, to: j})
if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
break
}
}
}
}
return moves
}
Estas son todas las reglas del juego de ajedrez que debemos tener en cuenta para realizar movimientos válidos. El siguiente paso es aplicar un movimiento a la posición para crear una nueva posición de juego. Sin tener en cuenta la captura en ruta, la promoción de peones y el enroque, el método se vería así:
func (pos Position) Move(m Move) (np Position) {
np = pos
np.board[m.to] = pos.board[m.from]
np.board[m.from] = '.'
return np.Flip()
}
Simplemente mueve la pieza, marca la celda en la que antes estaba vacía y da la vuelta al tablero. La implementación completa del método se puede encontrar en Github , maneja correctamente todos los movimientos especiales de peón y rey.
En esta etapa, puedes jugar al ajedrez "hombre contra hombre", controlando el proceso y haciendo solo movimientos legales. O puede crear un motor de ajedrez primitivo que realiza movimientos aleatorios hasta que pierde.
Pero, ¿cómo entendemos que estamos perdiendo?
Calificación de la junta
Se otorgan puntos por cada posición en el tablero. Inicialmente, la puntuación es cero, ya que ambos jugadores comienzan en igualdad de condiciones. Después de completar un movimiento, la puntuación cambia según las piezas que se capturaron y cómo las piezas cambiaron de posición en el tablero.
En el caso más simple, podemos contar las piezas del tablero y sumar su valor (menos las piezas del oponente). Tal cálculo mostrará si el rey es declarado jaque y jaque mate. Pero este es un sistema de evaluación muy débil.
Un enfoque mucho más preciso y sorprendentemente simple son las tablas de proporción de forma a cuadrado ( PST- Mesas Cuadradas). Para cada pieza, se crea una tabla del mismo tamaño que un tablero de ajedrez, donde se asigna un valor correspondiente a cada cuadrado. Estos valores son empíricos, así que los tomé del motor Sunfish.
De hecho, los motores de ajedrez más avanzados actualizan los PST durante el juego porque el valor de las piezas cambia (es decir, los peones se vuelven más valiosos hacia el final del juego). Pero tendremos un motor sencillo.
Para evaluar la posición después del movimiento, necesitamos:
- determinar la calificación de la posición actual,
- restar el valor de la pieza que se mueve,
- agregar un nuevo valor de cifra de acuerdo con la tabla PTS,
- agregue el valor de la pieza capturada, si corresponde.
Además, necesitamos ajustar en la tabla PST el valor de la torre durante el enroque y el valor del peón durante la promoción o captura en el pase. Pero aquí no consideraremos esto:
var pst = map[Piece][120]int{
'P': { ... },
'N': { ... },
'B': { ... },
'R': { ... },
'Q': { ... },
'K': { .... },
}
func (pos Position) value(m Move) int {
i, j := m.from, m.to
p, q := Piece(pos.board[i]), Piece(pos.board[j])
// PST-
score := pst[p][j] - pst[p][i]
if q != '.' && q != ' ' && !q.ours() {
// PST-
score += pst[q.Flip()][j.Flip()]
}
return score
}
Ahora podemos hacer un motor un poco más avanzado que elegirá el mejor movimiento posible, en lugar de cualquiera de los válidos.
Pero los motores de ajedrez reales hacen un análisis más profundo e iteran sobre las ramas de posibles movimientos en cada lado para encontrar el mejor movimiento posible a largo plazo.
Algoritmo de búsqueda
El algoritmo de búsqueda más común en los motores de ajedrez es más simple: la búsqueda en profundidad primero, que comienza en la raíz y desciende hasta un límite de profundidad determinado, repitiendo todos los movimientos posibles antes de regresar. Para cada posición de trazo, el valor se calcula utilizando un algoritmo minimax (minimax) c poda alfa-beta (poda alfa-beta ).
Minimax es una regla que se utiliza para minimizar las posibles pérdidas en el peor de los casos: el jugador considera todos los mejores movimientos del oponente y elige tal movimiento para que la mejor estrategia del oponente traiga tantos puntos como sea posible.
Un simple algoritmo minimax sería demasiado lento para el ajedrez y requeriría repetir demasiados movimientos para encontrar uno bueno.
La poda alfa-beta se utiliza para acelerar el algoritmo minimax al eliminar nodos que no vale la pena considerar. El recorte alfa-beta se basa en la siguiente lógica: imagina que estás jugando al ajedrez y encuentras una muy buena jugada A. Sigues mirando el tablero y encuentras una jugada aún mejor B. Pero luego analizas la situación más profundamente y entiendes que si eliges en el movimiento B, el enemigo declarará jaque y jaque mate en unos pocos movimientos. Ahora descarta B y no pierdas el tiempo analizando otras combinaciones posibles después de B.
Tanto el minimax como el recorte alfa-beta son importantes para comprender cómo funciona el motor de ajedrez. El motor Sunfish utiliza un algoritmo de búsqueda avanzada MDF (f) , que también es una variante del algoritmo minimax combinado con el recorte.
En nuestro motor, aumentaremos gradualmente la profundidad de búsqueda y llamaremos al algoritmo MDF (f) para encontrar los límites inferior y superior del resultado óptimo. El algoritmo MDF (f) utilizará una iteración de recorte alfa-beta con una caché de transposición.
El efectivo de transposición es un caché donde para cada posición del tablero memorizamos la profundidad, el conteo y el movimiento que nos llevó a esa posición. Luego, al considerar una nueva posición, primero se compara con la tabla de transposición.
No publicaré el código del algoritmo de búsqueda aquí, ya que son solo unas pocas líneas de búsqueda recursiva, pero siempre puede encontrar el código fuente completo para el motor de ajedrez en GitHub .
¿Que sigue?
Si está interesado en motores de ajedrez simples, le recomiendo que juegue con Sunfish. Por cierto, Sunfish se basa en el motor Micromax y viene con una excelente documentación del autor, que definitivamente vale la pena leer.
Para nuestro motor en Go, agregué una pequeña implementación del protocolo UCI para que pueda usarse con la interfaz de usuario de PyChess. Lo más probable es que todavía contenga un montón de errores y mucho potencial de mejora, pero fue un camino interesante: desde la idea de desarrollar un motor de ajedrez hasta un programa de ajedrez informático terminado y funcional.
Sí, es débil, ¡pero juega al ajedrez de verdad!
Espero que hayas disfrutado de este artículo. Puedes seguirme en Github , Twitter o suscríbase a través de rss .