Ordenando los movimientos

La eficiencia en la búsqueda bajo Minimax depende del orden de los movimientos en que se realiza esta operación. Las ventajas y desventajas relacionadas con un "buen" orden de los movimientos no son triviales: Un buen orden, definido como uno que causará el mayo número de cortes, resultará en un árbol de búsqueda de un tamaño aproximado a la raíz cuadrada del tamaño total del árbol asociado al peor orden de jugadas posible.

Desafortunadamente, ordenar los movimientos de la mejor forma implica encontrar los mejores y buscar primero sobre estos, lo cual es una tarea bastante difícil de lograr. Por ejemplo, el orden podría iniciarse con capturas, coronaciones de peón (las cuales cambian dramáticamente el balance de material) o jaques (los cuales a menudo permiten pocas respuestas legales), siguiendo con movimientos que causaron recientes cortes en otras variantes a la misma profundidad (denominadas movidas-asesinas, killer-moves)y entonces observar el resto de los movimientos. Esta es la justificación para la utilización del algoritmo de poda alfa-beta, así como el uso de tablas históricas.

En 1975 Donald Knuth y R.E.Moore demostraron que para un árbol uniforme de profundidad 2 en el cual las posiciones terminales son asignadas con un score aleatorio, de las B^2 posiciones terminales en promedio B^(2)/(log(B)-0.923) son evaluadas. Dos años mas tarde Newborn demostró que para los mismos árboles uniformes de profundidad 2 y factor de anchura B si el score de cada posición terminal corresponde a la suma de los scores aleatorios de posiciones previas a partir de la posición raíz entonces menos cantidad de evaluaciones son realizadas. Este modelo de dependencia de las ramas del árbol para asignar evaluaciones a las posiciones terminales pareciese modelar al juego de una mejor forma que los primeros modelos. En ajedrez el score de una posición terminal está dominado por el material, y éste es muy dependiente de las capturas realizadas en los movimientos precedentes. Newborn demostró que para este modelo en promedio 2B/log(B) posiciones son evaluadas.

Un programa que utiliza el algoritmo alfa-beta puede buscar en un árbol con el doble de profundidad que uno que no lo implementa. En búsquedas con árboles de ajedrez reales el número de posiciones terminales es bastante menor que el número predecido por los modelos aleatorios.

En 1986 P. Bettadapur demostró que las capturas deben ser ordenadas por aquellas que capturan la pieza de mayor valor del rival hasta las de menor valor obteniendo mejores resultados en la búsqueda. Asimismo, la captura de la ultima pieza que movió el rival es también un buen tipo de ordenamiento.

Nótese que esta técnica no tiene relación con búsqueda selectiva puesto que todos los movimientos serán examinados en alguna instancia, siendo examinados al final aquellos que aparentan ser "malos".

Una observación final, dentro de los movimientos generados algunos de estos resultan ser ilegales debido a que dejan al rey en jaque. El problema de validar la legalidad de los movimientos durante su generación es demasiado costoso comparado con evaluar como corte las "capturas de Rey", es decir, si luego de cierto movimiento es posible realizar la captura del Rey entonces dicho movimiento es ilegal y se produce un corte en la variante. Por su puesto que si el corte se produce antes de examinar el movimiento ilegal este nunca es revisado.