Next: El concepto de Posición
Up: Técnicas de Búsqueda
Previous: La necesidad de Buscar
  Índice General
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.
Next: El concepto de Posición
Up: Técnicas de Búsqueda
Previous: La necesidad de Buscar
  Índice General
Santiago de Chile, Julio 2003