Movimientos Asesinos (killer moves)

La heurística de "movimientos asesinos" es utilizada en la mayoría de los programas de ajedrez con el objetivo de identificar rápidamente buenos movimientos. Jim Gillogly [45] utilizó esta técnica en su programa TECH en 1972. Esencialmente, cuando es encontrado un movimiento que refuta cierta variante en el nivel de profundidad k dentro del árbol de búsqueda, éste es almacenado en la lista de movimientos "killer" (Existe una lista de movimientos asesinos por cada nivel de profundidad de búsqueda en el árbol). Luego cuando se generan nuevos movimientos en el árbol de variantes la lista de movimientos asesinos es consultada en cada nivel y si un movimiento es encontrado entonces es ordenado con prioridad en la lista de movimientos a analizar.



La figura ilustra el funcionamiento de esta heurística. Si es el turno de mover de las blancas éstas intentarían el movimiento 1.Cxh6 debido a que captura la torre. Luego de examinar las réplicas del negro encontrará que este movimiento es refutado por la respuesta 1... Ta1 mate. Entonces, cuando el programa examine nuevos movimientos para el blanco el primer movimiento negro que tomará como respuesta sera 1... Ta1 debido a que es un movimiento legal que genero un corte en una variante anterior y existen chances de que lo haga en la actual variante. La heurística le enseña al programa que el movimiento 1...Ta1 es una seria respuesta a considerar luego de cada jugada del blanco.

Varias estrategias existen para guardar los movimientos asesinos. Lo más simple es mantener una lista bastante corta de a lo más dos movimientos de profundidad. Sólo las más recientes refutaciones son mantenidas en el arreglo. Alternativamente cada refutación en el arreglo puede mantener un contador de cuantas veces ha causado cortes en los análisis. Cuando un nuevo movimiento killer es agregado este reemplaza al ultimo movimiento guardado en el arreglo. Utilizando esta técnica el número de cortes es mayor y la eficiencia del algoritmo alfa-beta aumenta. En lugar de la lista de movimientos killer el programa PHOENIX de Jonathan Schaeffer utilizaba dos arreglos de 64x64 los cuales mantenían todos los movimientos de cada bando que causaban una refutación o corte. El arreglo con la continuación principal también podía ser considerado una buena fuente de movimientos killer, tal como acotaran Selim Akl y Newborn en 1977.