Poda alfa-beta
Una optimización de minimax que se salta las ramas que demostrablemente no pueden cambiar el resultado: misma respuesta, una fracción del trabajo.
La búsqueda lleva dos cotas: alfa, lo mejor que ya tienes garantizado, y beta, lo mejor que ya tiene garantizado el rival. En cuanto una rama resulta peor que una alternativa ya encontrada, no hace falta examinar el resto; el rival nunca te dejaría llegar ahí. La respuesta es exactamente la misma que la de un minimax completo.
Varios grupos dieron con la idea de forma independiente en los años cincuenta, y Donald Knuth y Ronald Moore la analizaron en 1975: con una ordenación de jugadas perfecta visita aproximadamente la raíz cuadrada de los nodos, lo que en la práctica duplica la profundidad alcanzable. Por eso los motores de ajedrez se esfuerzan tanto en probar primero las jugadas más probables, a menudo con ayuda de una tabla de transposición. Deep Blue se basaba en el mismo principio.