Cap. 6 - Contar las hojas sin tasarlas
cap. 6 Prueba · Generador
Contar las hojas sin tasarlas
Alfa-beta elige. Perft cuenta. Dada una posición y una profundidad, ¿cuántas partidas legales hay si cada bando juega todas las jugadas legales hasta ese ply? No se evalúa. No se poda. No se ordena. Solo hacer, filtrar jaque, recursión, deshacer. Si el número no coincide con las tablas conocidas del mundo, el generador está roto.
Lo escribí en 2012 en perft.c. No he reescrito el algoritmo. Este artículo empieza por para qué sirve un contador, no por el récord de nodos por segundo.
Por qué contar sin jugar
Analogía: contar cuántas puertas hay en el edificio, no decidir cuál es la mejor vivienda. Un error de un peón al paso, un enroque a través de jaque o una promoción mal empaquetada se come (o infla) millones de hojas a profundidad 5. La evaluación no lo delata: el motor juega, pero el árbol está cojo. Perft sí lo delata, porque el número es un entero seco que se compara con Wikipedia, con Crafty, con cualquier motor que ya pasó la prueba.
En consola: perft n. Arranca el cronómetro, llama a perft(0, n) y al terminar imprime nodos, milisegundos y un desglose.
El recuento
Profundidad 0 es una hoja: se devuelve 1. No se genera nada. Eso es el convenio de Perft: las hojas son posiciones, no jugadas.
uint64 perft(int capa, int profundidad)
{
if (profundidad == 0) return 1;
generarTodosMov(...);
for (cada candidata) {
hacerMovimiento(mov);
if (!esAtacadoPor(rey_propio, rival))
numNodos += perft(capa + 1, profundidad - 1);
desHacerMovimiento(mov);
}
return numNodos;
}
El generador es pseudo-legal. El filtro es el mismo que en la búsqueda: si el rey propio queda atacado, esa rama no existe. Por eso Perft valida a la vez el bitboard, el empaquetado de 28 bits, hacer/deshacer y esAtacadoPor. Un fallo en cualquiera de los cuatro miente el total.
El desglose DATA_PERFT
En el último ply (profundidad == 1) se incrementan contadores: capturas, al paso, promociones, enroque corto, enroque largo, y si esa hoja deja al rival en jaque. No hace falta para el número de nodos. Sirve para cazar dónde se rompió el generador: si el total cuadra pero las capturas no, el bug está en comer, no en el silencio.
| Campo | Qué cuenta (en el último ply) |
|---|---|
InvCaptura |
Capturas |
InvPeonPaso |
Al paso |
InvPromocion |
Promociones |
InvEnroqueOO / OOO |
Enroques |
InvJaqueContrario |
Hojas que dejan al rival en jaque |
Analogía: no solo cuántas puertas. Cuántas son de captura, cuántas de enroque. Si el edificio tiene 20 puertas y usted cuenta 19, mira el sótano del al paso: ahí suele estar la que falta.
Perft no usa hash ni orden. Si los usara, un bug de transposición podría esconder un bug del generador. Aquí el árbol es honesto y caro: es una prueba, no una partida.
Qué archivos leer
| Archivo | Qué hay |
|---|---|
perft.c |
perft(): hoja = 1; hacer / jaque / recursión / deshacer |
comandos.c |
Comando perft n; impresión de nodos y desglose |
tipoDatos.h |
DATA_PERFT |
El repositorio del motor: GitHub.
Cierre
Perft no juega. Cuenta. Profundidad 0 es una posición. Cada ply legal suma las de abajo. El número seco caza bugs que la evaluación no ve. Encaja con hacer/deshacer (el carrete) y con el filtro de jaque. Ese filtro es esAtacadoPor. La siguiente entrada.
Correo de contacto: comprasmangocomputer@gmail.com
Comentarios
Publicar un comentario