Killer-Heuristik - Killer heuristic
In kompetitiven Zwei-Spieler-Spielen ist die Killer-Heuristik eine Zugordnungsmethode, die auf der Beobachtung basiert, dass ein starker Zug oder ein kleiner Satz solcher Züge in einer bestimmten Stellung in ähnlichen Stellungen beim gleichen Zug (Lage) in der gleich stark sein kann Spielbaum. Das Beibehalten solcher Bewegungen vermeidet den Aufwand, sie in Geschwisterknoten wiederzuentdecken.
Diese Technik verbessert die Effizienz des Alpha-Beta-Prunings , was wiederum die Effizienz des Minimax-Algorithmus verbessert . Alpha-Beta-Beschneidung funktioniert am besten, wenn die besten Züge zuerst in Betracht gezogen werden. Dies liegt daran, dass die besten Züge diejenigen sind, die am wahrscheinlichsten einen Cutoff erzeugen , eine Bedingung, bei der das Spielprogramm weiß, dass die in Betracht gezogene Stellung unmöglich aus dem besten Spiel beider Seiten resultieren kann und daher nicht weiter betrachtet werden muss. Dh das Spielprogramm wird immer den besten verfügbaren Zug für jede Position machen. Es muss nur die möglichen Reaktionen des anderen Spielers auf den besten Zug berücksichtigen und kann die Bewertung von Reaktionen auf (schlechtere) Züge überspringen, die es nicht machen wird.
Die Killer-Heuristik versucht, einen Cutoff zu erzeugen, indem sie davon ausgeht, dass ein Zug, der einen Cutoff in einem anderen Zweig des Spielbaums in der gleichen Tiefe erzeugt hat, wahrscheinlich einen Cutoff in der gegenwärtigen Position erzeugt, d Ein guter Zug aus einer anderen (aber möglicherweise ähnlichen) Position kann auch in der aktuellen Position ein guter Zug sein. Durch das Ausprobieren des Killerzuges vor anderen Zügen kann ein Spielprogramm oft einen frühen Cutoff erzeugen, was sich die Mühe erspart, alle legalen Züge aus einer Position heraus in Betracht zu ziehen oder sogar zu generieren.
In der praktischen Umsetzung verfolgen Spieleprogramme häufig zwei Killerzüge für jede Tiefe des Spielbaums (größer als Tiefe 1) und sehen, ob einer dieser Züge, falls zulässig, einen Cutoff erzeugt, bevor das Programm den Rest generiert und berücksichtigt der möglichen Bewegungen. Wenn ein Nicht-Killer-Move einen Cutoff erzeugt, ersetzt er einen der beiden Killer-Moves in seiner Tiefe. Diese Idee kann in eine Reihe von Widerlegungstabellen verallgemeinert werden .
Eine Verallgemeinerung der Killer-Heuristik ist die History-Heuristik Die History-Heuristik kann als Tabelle implementiert werden, die durch einige Merkmale des Zuges indiziert ist, zum Beispiel "von"- und "zu"-Felder oder Figurenbewegungen und "zu"-Feldern. Bei einem Cutoff wird der entsprechende Eintrag in der Tabelle inkrementiert, beispielsweise durch Hinzufügen von d² oder 2 d, wobei d die aktuelle Suchtiefe ist. Jenseits einer inkrementellen Tiefe von etwa 2 degenerieren Verlaufsinformationen schnell zu "Rauschen".