Heurística asesina

En los juegos competitivos de dos jugadores, la heurística asesina es un método de ordenamiento de movimientos basado en la observación de que un movimiento fuerte o un conjunto pequeño de tales movimientos en una posición particular pueden ser igualmente fuertes en situaciones similares. posiciones en el mismo movimiento (ply) en el árbol del juego. Retener tales movimientos evita el esfuerzo de redescubrirlos en nodos hermanos.

Esta técnica mejora la eficiencia de la poda alfa-beta, que a su vez mejora la eficiencia del algoritmo minimax. La poda alfa-beta funciona mejor cuando se consideran primero los mejores movimientos. Esto se debe a que las mejores jugadas son las que tienen más probabilidades de producir un corte, una condición en la que el programa de juego sabe que la posición que está considerando no podría haber resultado de la mejor jugada de ambos lados y por lo que no es necesario considerarlo más. Es decir. el programa de juego siempre hará su mejor movimiento disponible para cada posición. Solo necesita considerar las posibles respuestas del otro jugador a ese mejor movimiento y puede omitir la evaluación de las respuestas a (peores) movimientos que no hará.

La heurística asesina intenta producir un corte asumiendo que un movimiento que produjo un corte en otra rama del árbol del juego a la misma profundidad es probable que produzca un corte en la posición actual, es decir que un movimiento que fue un muy buen movimiento desde una posición diferente (pero posiblemente similar) también podría ser un buen movimiento en la posición actual. Al intentar el movimiento asesino antes que otros movimientos, un programa de juego a menudo puede producir un corte temprano, ahorrándose el esfuerzo de considerar o incluso generar todos los movimientos legales desde una posición.

En la implementación práctica, los programas de juego con frecuencia realizan un seguimiento de dos movimientos asesinos para cada profundidad del árbol del juego (mayor que la profundidad de 1) y ven si cualquiera de estos movimientos, si es legal, produce un corte antes de que el programa genere y considera el resto de movimientos posibles. Si un movimiento no asesino produce un corte, reemplaza uno de los dos movimientos asesinos en su profundidad. Esta idea se puede generalizar en un conjunto de tablas de refutación.

Una generalización de la heurística asesina es la heurística histórica. La heurística de historial se puede implementar como una tabla indexada por alguna característica del movimiento, por ejemplo, "desde" y "a" casillas o pieza en movimiento y el "to" cuadrado. Cuando hay un corte, se incrementa la entrada correspondiente en la tabla, por ejemplo, agregando d² o 2^d donde d es la profundidad de búsqueda actual. Más allá de una profundidad incremental de alrededor de 2, la información histórica degenera rápidamente en "ruido".