Math
Árbol de juego y alfa-beta
Un árbol de juego en el que cada bloque es tan alto como su valor: un nodo MAX tan alto como su hijo más alto, un nodo MIN tan bajo como su hijo más bajo. Minimax lee cada hoja; alfa-beta salta lo que no puede cambiar la respuesta, y cuánto salta depende del orden de las jugadas.
Qué ocurre
Cada bloque es tan alto como su valor, así que la regla se ve antes de nombrarla: un nodo MAX es tan alto como su hijo más alto, un nodo MIN tan bajo como su hijo más bajo, y la raíz es el valor del juego. Minimax lee las b^d hojas. Alfa-beta las lee en orden y deja de mirar un nodo en cuanto un hermano ya visto vuelve irrelevante el resto - las ramas en las que nunca entra quedan a oscuras. La respuesta nunca cambia por ello, solo el recuento, y el recuento depende del ORDEN de las jugadas, no del árbol: con la mejor jugada primero en cada nodo necesita exactamente el mínimo de Knuth y Moore, cerca de la raíz cuadrada de b^d; con la peor primero ve todas las hojas - pero solo hasta profundidad 3, porque desde la 4 el alfa levantado en la raíz baja y poda incluso eso. Qué mirar: las ramas podadas, el camino dorado de la variante principal y las tres barras del fondo - minimax, esta búsqueda, el mínimo.
Ecuaciones del módulo
Ecuaciones nodo MAX: v = max sobre los hijos; nodo MIN: v = min sobre los hijos; el minimax lee las b^d hojas alfa-beta: se corta el resto de los hijos de un nodo en cuanto alfa >= beta - la respuesta es la misma, la cuenta no ordenación perfecta: N_min = 2·b^(d/2) − 1 para d par, b^((d+1)/2) + b^((d−1)/2) − 1 para d impar (Knuth - Moore, 1975) peor ordenación en cada nodo: N = b^d para d <= 3; desde d = 4 el alfa de la raíz llega al tercer nivel y poda de todos modos ordenación s en [−1, 1]: los hijos de un nodo se ordenan por valor exacto cuando su propia moneda hash es menor que |s| - el mejor primero para s > 0, el peor primero para s < 0
