Trasladar el pedido

El ordenamiento de movimientos se refiere a la práctica de seleccionar primero los movimientos más prometedores durante la búsqueda en el árbol de juego (especialmente en ajedrez por computadora ). ^{[ 1 ] [ 2 ]} En búsquedas minimax con poda alfa-beta , un buen ordenamiento de movimientos es importante, ya que examinar los movimientos más fuertes al principio provoca cortes que eliminan subárboles, reduciendo enormemente el número de nodos buscados. En el caso ideal de un ordenamiento de movimientos perfecto, la complejidad de la búsqueda disminuye de${\displaystyle O(b^{d})}$aproximadamente${\displaystyle O(b^{d/2})}$, reduciendo efectivamente a la mitad el factor de ramificación efectivo a${\displaystyle {\sqrt {b}}}$y permitiendo aproximadamente el doble de profundidad de búsqueda para un esfuerzo computacional dado. ^{[ 3 ]} Claude Shannon observó que, si bien una posición típica de ajedrez puede tener alrededor de 30 movimientos legales, la poda efectiva y las heurísticas reducen el factor de ramificación útil a solo unos pocos. ^{[ 4 ]}

La idea de ordenar los movimientos surgió antes que las computadoras. En su artículo fundamental de 1950, "Programando una computadora para jugar ajedrez", ^{[ 5 ]} Claude Shannon señaló el enorme tamaño del árbol de juego completo (estimado en${\displaystyle 10^{120}}$nodos) y sugirió que una evaluación simple junto con la búsqueda de todas las variaciones a una profundidad fija sería poco práctica. Shannon vio que cualquier programa de ajedrez necesitaría centrarse en movimientos seleccionados y podar agresivamente para ser útil. El algoritmo formal alfa-beta apareció a finales de la década de 1950 y en la de 1960 como una forma de podar ramas sin cambiar el resultado minimax. Desde el principio, se observó que el poder de poda de alfa-beta depende completamente del orden en que se examinan los movimientos. En 1963, Alexander Brudno describió de forma independiente la búsqueda tipo alfa-beta y observó que los recuentos de nodos del mejor caso ocurren cuando los movimientos se prueban en el orden correcto; para la década de 1970, investigadores como Donald Knuth y Ronald Moore habían analizado matemáticamente alfa-beta y demostrado que bajo un ordenamiento perfecto su tiempo es${\displaystyle O(b^{d/2})}$. ^{[ 6 ]}

En las décadas de 1970 y 1980 se introdujeron las principales heurísticas prácticas para la ordenación de movimientos. El uso de la profundización iterativa se redescubrió en los programas de ajedrez y se encontró que mejoraba significativamente la ordenación de movimientos para búsquedas más profundas. La idea era usar el mejor movimiento encontrado a poca profundidad como el primer movimiento en la siguiente búsqueda más profunda. ^{[ 7 ]} Las tablas de transposición ( Mac Hack de Richard Greenblatt en 1966 usó por primera vez un hash ) permitieron al programa almacenar el mejor movimiento para cada posición y reutilizarlo como la primera opción en visitas posteriores. ^{[ 8 ]} En 1968, Barbara Liskov y otros sugirieron independientemente almacenar movimientos que causaban cortes beta. Esto eventualmente se conoció como la heurística asesina . En 1983, Jonathan Schaeffer propuso la heurística del historial . Schaeffer demostró que las puntuaciones del historial superaban a las heurísticas más simples.

La eficiencia de la búsqueda de un motor de ajedrez depende casi por completo de su capacidad para ignorar los movimientos "malos" lo más rápido posible. Teóricamente, si un motor pudiera examinar siempre primero el mejor movimiento, el espacio de búsqueda se reduciría efectivamente a su raíz cuadrada. ^{[ 1 ]} Esto se logra mediante una combinación de teoría de juegos y poda heurística. ^{[ 9 ]}

Una búsqueda en árbol de juego minimax pura explora todos los movimientos hasta una profundidad fija, lo cual es exponencialmente costoso. ^{[ 10 ]} La poda alfa-beta mejora esto al incorporar dos límites: Alfa (α) y Beta (β). ^{[ 11 ]} Alfa es la puntuación mínima que el jugador que maximiza tiene asegurada, y Beta es la puntuación máxima que el jugador que minimiza puede permitirse. Siempre que el valor de un nodo no pueda influir en la decisión final porque es peor que un movimiento examinado previamente, la rama se corta. Esto tiene una probabilidad de tener el mismo resultado que el minimax completo, pero con menos nodos.

La búsqueda en profundidad iterativa es de uso común. El motor busca repetidamente con límites de profundidad crecientes, utilizando el mejor movimiento desde la profundidad${\displaystyle d}$como primer movimiento para intentar en profundidad${\displaystyle d+1}$[ ^{12 ] Esto casi produce un límite inicial fuerte (alfa o beta) en el primer movimiento, lo que reduce la ventana para el resto de la búsqueda} . La profundización iterativa convierte una búsqueda en profundidad en algo similar a una búsqueda primero en amplitud aprovechando los resultados anteriores. Cuando una tabla de transposición contiene una entrada para la posición actual, se intenta primero su mejor movimiento almacenado. ^{[ 13 ]} Después de considerar un movimiento de transposición, las heurísticas de ordenación típicas priorizan las capturas y los controles, ya que forzar movimientos tácticos a menudo conduce a grandes ventajas o cortes inmediatos. ^{[ 14 ]}

Los motores ordenan los movimientos de captura según la heurística de Víctima Más Valiosa-Agresor Menos Valioso (MVV-LVA). ^{[ 8 ]} Para evitar intercambios obviamente perdedores, a menudo se aplica una evaluación de intercambio estática (SEE) para podar las capturas que reducen el balance material. Si los movimientos forzados no producen un corte, el motor prueba sus movimientos asesinos almacenados, que se prueban en profundidad temprana. Si un movimiento que no es asesino causa un corte, se convierte en un nuevo asesino. Finalmente, cualquier movimiento silencioso restante se ordena según sus puntuaciones heurísticas históricas, que acumulan bonificaciones cuando un movimiento causa un corte. ^{[ 15 ]} Cada vez que un movimiento causa un corte en cualquier parte de la búsqueda, su puntuación histórica aumenta. Por lo tanto, los movimientos que históricamente han causado cortes se clasifican más arriba en el ordenamiento futuro.

Los investigadores han desarrollado varios refinamientos más allá de los esquemas básicos. La heurística de contramovimiento asume que muchos movimientos tienen una respuesta "natural", independientemente de la posición real. ^{[ 16 ]} Otras técnicas diversas como los "tableros mariposa" ^{[ 17 ]} y las heurísticas de "última mejor respuesta" son ideas relacionadas que explotan el historial de búsqueda local. Algunos motores utilizan aprendizaje automático ; los primeros trabajos de Kocsis et al. y Greer aplicaron redes neuronales para predecir valores u ordenamientos de movimientos. La mayoría de los motores robustos aún se basan en el conjunto simple de movimientos PV, movimientos hash, ordenación de captura MVV-LVA, kill y tablas de historial.

• Minimax
• Poda alfa-beta
• Búsqueda en profundidad iterativa
• Búsqueda de quiescencia
• Heurística asesina