En juegos competitivos de dos jugadores, la heurística asesina es una técnica para mejorar la eficiencia de la poda alfa-beta , que a su vez mejora la eficiencia del algoritmo minimax . Este algoritmo tiene un tiempo de búsqueda exponencial para encontrar el próximo movimiento óptimo, por lo que los métodos generales para acelerarlo son muy útiles. Barbara Liskov creó la heurística general para acelerar la búsqueda de árboles en un programa de computadora para jugar finales de ajedrez para su doctorado. tesis. [1]
La poda alfa-beta funciona mejor cuando se consideran primero los mejores movimientos. Esto se debe a que los mejores movimientos son los 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 tanto, no es necesario considerarla más a fondo. 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 movimientos (peores) 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 probablemente producirá un corte en la posición actual, es decir, que un movimiento que fue muy Un 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 ver si alguno de estos movimientos, si es legal, produce un corte antes de que el programa genere y considere el resto. de los posibles movimientos. 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 del asesino es la heurística de la historia . La heurística de la historia se puede implementar como una tabla que está indexada por alguna característica del movimiento, por ejemplo "desde" y "a" casillas o pieza en movimiento y la casilla "a". Cuando hay un límite, se incrementa la entrada correspondiente en la tabla, por ejemplo, agregando d² o 2 d donde d es la profundidad de búsqueda actual. Esta información se utiliza al realizar pedidos de mudanzas.
Referencias
- ^ Huberman (Liskov), Barbara Jane (1968). "Un programa para jugar partidas finales de ajedrez" (PDF) . Departamento de Ciencias de la Computación de la Universidad de Stanford, Informe técnico CS 106, Memorando del proyecto de inteligencia artificial de Stanford AI-65. Cite journal requiere
|journal=
( ayuda )