Factor de Ramificación & Conteo de Nodos
Un árbol de juego modela cada secuencia posible de movimientos desde una posición inicial. Cada nodo representa un estado del tablero. Cada arista representa un movimiento legal. La estructura del árbol determina si la búsqueda permanece viable.
Parámetros Clave
Factor de ramificación b: número de movimientos legales disponibles en una posición típica.
Profundidad d: número de semimovimientos (movimientos medios) para buscar hacia adelante.
Conteo de nodos a profundidad d: b^d
Total de nodos en todas las profundidades: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Para b y d grandes, el total ≈ b^d (dominado por el nivel de hojas).
Tic-Tac-Toe 4×4×4
El árbol de juego completo: b ≈ 64 (cuadrados legales), d = 64 (movimientos totales). Conteo de nodos completo ≈ 64^64 ≈ 10^115. El universo observable contiene aproximadamente 10^80 átomos. La búsqueda por fuerza bruta es físicamente imposible.
Computando el Tamaño del Árbol
El ajedrez proporciona números más realistas. Factor de ramificación promedio b ≈ 35. Una búsqueda de 6 semimovimientos (3 movimientos cada lado) requiere aproximadamente 35^6 nodos.
Poda Alfa-Beta: Reduciendo el Exponente
La poda alfa-beta elimina subárboles que no pueden afectar el resultado minimax. La idea clave: si ya sabes que una rama da valor V, puedes podar cualquier rama hermana cuyo valor demostrablemente caiga por debajo de V (para el jugador maximizador) o por encima de V (para el jugador minimizador).
Geometría del Mejor Caso
Bajo ordenamiento óptimo de movimientos (movimientos mejores buscados primero), la poda alfa-beta reduce el factor de ramificación efectivo de b a √b. La profundidad de búsqueda efectivamente se duplica para el mismo presupuesto de nodos:
Búsqueda completa: b^d nodos
Mejor caso alfa-beta: b^(d/2) nodos
Ejemplo: b=35, d=6. Completa: 35^6 ≈ 1.84 × 10^9. Alfa-beta: 35^3 = 42,875. Factor de reducción: ~43,000.
En la práctica, el ordenamiento de movimientos es imperfecto. Reducción típica: b^(d×0.75) — factor de ramificación equivalente ≈ b^0.75.
Dualidad Centro-Esquina
Hamming nota una dualidad geométrica en el cubo 4×4×4: existe una inversión que envía las 8 posiciones de esquina a las 8 posiciones centrales (el cubo interior 2×2×2) & vice versa, mientras preserva todas las 76 líneas ganadoras.
Contando Líneas a Través de una Posición
En un cubo 4×4×4, las posiciones difieren en cuántas líneas ganadoras pasan a través de ellas:
Posiciones de esquina: 7 líneas cada una (4 diagonales de cara, 2 líneas de arista, 1 diagonal de espacio)
Posiciones de centro de arista: 4 líneas cada una
Posiciones de centro de cara: 6 líneas cada una
Posiciones de centro del cuerpo (cubo interior 2×2×2): 7 líneas cada una
La dualidad mapea esquinas (7 líneas) a centros del cuerpo (7 líneas). Ambos conjuntos forman 'puntos calientes.'
Por Qué los Puntos Calientes Importan Geométricamente
Un jugador controlando más posiciones de conteo alto de líneas controla más líneas ganadoras potenciales. Este es un argumento geométrico directo: la maximización de cobertura de líneas guía la selección de movimientos sin búsqueda alguna.
Funciones de Evaluación
Cada programa de juego necesita una función de evaluación: una función que mapea estados del tablero a valores numéricos (positivo = bueno para el jugador maximizador, negativo = bueno para el jugador minimizador). La función de evaluación proporciona la condición de frontera en las hojas del árbol de búsqueda.
Funciones de Evaluación Lineales
Una función de evaluación lineal asigna un peso w_i a cada característica f_i de la posición:
E(position) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Para tic-tac-toe 4×4×4: las características podrían incluir líneas abiertas controladas, posiciones en cuadrados de conteo alto de líneas, bifurcaciones amenazadas. Para ajedrez: conteo de material, control del centro, seguridad del rey, estructura de peones.
Esta es una función lineal en espacio de características — un hiperplano en ℝ^n. Dos posiciones con los mismos valores de características obtienen la misma evaluación independientemente de todas las otras diferencias. La geometría de la función de evaluación determina qué el programa 've.'
El programa de verificadores de Samuel mejoró ajustando el vector de peso w — descenso de gradiente en el espacio de funciones de evaluación lineal.
Geometría & la Frontera de la Formalización
El árbol de juego tiene una estructura geométrica limpia: crecimiento exponencial a profundidad d, reducible a b^(d/2) por alfa-beta, reducible aún más restringiendo a posiciones de alto valor (puntos calientes reducen b efectivo). La función de evaluación define un hiperplano en espacio de características.
Todo esto es limpio, preciso, formalmente completo. Describe el centro del problema de juego — la región donde la estructura matemática proporciona orientación clara.
La frontera — dónde cambiar de aplicación de reglas a exploración, cuándo comerciar ventaja posicional por oportunidad táctica, cómo reconocer patrones emergentes más allá de la función de evaluación — resiste esta formalización. El conocimiento tácito de Hamming vive en esa frontera.
La geometría te permite computar cuánta búsqueda puedes permitirte. No te dice qué buscar.