Chess AI
Un juego de ajedrez de escritorio donde juegas contra un motor que escribí en Python. Busca con minimax y poda alfa-beta con límite de tiempo, y evalúa las posiciones con material, tablas por casilla y algunas heurísticas extra. Abajo, una versión para el navegador repite una apertura, compara ambos modos de búsqueda y te deja tomar el control con blancas.
- Rol
- Desarrollador único
- Año
- 2022
- Stack
- Python, python-chess, Pygame
- Búsqueda
- Minimax + alfa-beta
Una versión en TypeScript de la evaluación y la búsqueda de minimax.py, corriendo en tu navegador. El original es una app de escritorio con Pygame que usa python-chess para las reglas; aquí el generador de jugadas está escrito desde cero para esta versión y verificado con los conteos perft estándar.
01
Aprender búsqueda adversaria construyéndola
Quería entender la búsqueda adversaria construyéndola, no solo leyendo sobre ella. python-chess se encarga de las reglas y las jugadas legales, Pygame dibuja el tablero y la toma de decisiones es mía.
02
Mirar adelante y suponer la mejor respuesta
El motor mira un número fijo de jugadas hacia adelante y supone que el rival siempre responde con su mejor jugada. La poda alfa-beta descarta ramas que no pueden cambiar la decisión final, así la misma profundidad cuesta menos evaluaciones.
La búsqueda también vigila el reloj. Cuando se acaba el tiempo, devuelve la mejor jugada encontrada hasta ese momento en vez de congelar el juego. El panel junto al tablero muestra los nodos visitados y las ramas podadas en cada jugada.
Al portarlo a TypeScript me di cuenta de que la rama minimizadora nunca actualiza beta, así que el código original casi nunca poda. El tablero alterna entre el original y la actualización de beta: una búsqueda completa elige la misma jugada con menos nodos. El motor juega por su cuenta y los controles permiten tomar el control con blancas o comparar ambos modos.
minimax.py
Alpha-beta, rama por rama
- alpha
- 3
- beta
- ·
- Nodos visitados
- 10/13
- Hojas podadas
- 3/9
- Mejor jugada
- e4
Árbol y puntajes ilustrativos. Mismo orden y regla de poda que el motor con la actualización de beta.
Python puro es lento, así que el diseño gira en torno a gastar bien un presupuesto de búsqueda pequeño.
03
Cuánto vale una posición
En las hojas el motor suma el material más un bono por casilla para cada pieza, 10 por dar jaque, infinito por jaque mate y una pequeña recompensa por cada jugada legal que cae en una casilla central.
evaluate
Lo que el motor suma en una hoja
Valor base de las piezas
- 10
- 30
- 30
- 50
- 90
El rey vale 9000, así que perderlo pesa más que todo lo demás.
Bono de casillas buenas
Bono por jugadas al centro: +2
Bono por cada jugada legal que cae en la casilla: 1 en las cuatro casillas centrales y 0.5 en el anillo que las rodea.
Ejemplo: un caballo solo en f3 tiene ocho jugadas legales; dos caen en casillas centrales.
Decisiones
- 01
Búsqueda corta con presupuesto de tiempo
Mantuve la profundidad baja y agregué un límite de tiempo para que el juego responda rápido. El README indica profundidad 2 con un límite de 10 segundos; el código actual busca a profundidad 3.
- 02
Heurísticas escritas a mano
Las tablas y reglas simples son fáciles de leer y ajustar, a cambio de menos fuerza que los motores modernos.
- 03
Una librería para las reglas
python-chess se encarga de las jugadas legales, el jaque y el mate, así el proyecto se pudo enfocar en la búsqueda y la evaluación.
Míralo jugar
Hay un video demo y el código completo en GitHub. El tablero de arriba juega por su cuenta. Los controles permiten tomar el control con blancas, comparar los modos de búsqueda y reanudar la reproducción automática.