Minimax

Aunque existen evidencias de que Charles Babbage ya había trabajado antes sobre una idea similar,[1]​ fue el matemático francés Émile Borel el primero en ofrecer en 1921 un tratamiento riguroso a los juegos competitivos y en estudiar las estrategias aplicables a los juegos de suma cero.

Tal estrategia es llamada óptima para ambos jugadores sólo en caso de que sus minimaxes sean iguales (en valor absoluto) y contrarios (en signo).

En los juegos de suma no nula, existe tanto la estrategia minimax como la maximin.

Pasos del algoritmo minimax: El algoritmo explorará los nodos del árbol asignándoles un valor numérico mediante una función de evaluación, empezando por los nodos terminales y subiendo hacia la raíz.

En el caso del ajedrez los posibles valores son (+1,0,-1) que se corresponden con ganar, empatar y perder respectivamente.

Esta optimización se basa en evitar el cálculo de ramas cuya evaluación final no va a poder superar los valores previamente obtenidos.

Hablando del minimax: Suponiendo que existe min() que devuelve el menor y max() que devuelve el mayor, Negamax se basa en la siguiente igualdad matemática: A este algoritmo también se le pueden aplicar podas y heurísticas para acortar su tiempo de ejecución, además existe una mejora de este algoritmo llamado negascout.