Wie man Transpositionstabellen mit MTD verwendet (f)

Question

Ich schreibe eine KI für ein Kartenspiel und nach einigen Tests habe ich entdeckt, dass MTD (f) auf meinem Alpha Beta-Algorithmus - eine Reihe von Null-Fenster-Suchen - ist schneller als nur Alpha-Beta allein zu verwenden.

Die MTD (f) Algorithmus ist gut hier http://people.csail.mit.edu/plaat/mtdf.html

beschrieben Das Problem, das ich ist haben, dass für jeden Durchgang in der MTD (f) Suche (für jede Vermutung) wiederverwendet wird nicht einer der vorhergehenden Positionen Ich habe gespeichert, obwohl das Schreiben auf dem Link suggeriert, dass ich sollte (in der Tat die Tabelle zwischen Iterationen zu beschleunigen beschleunigt den Algorithmus).

Mein Problem ist, dass wenn ich eine Position und einen Wert in meiner Transpositionstabelle speichern ich auch die Alpha- und Beta-Werte, für die es gültig ist. Daher kann ein zweiter Durchlauf durch den Baum mit einer anderen Schätzung (und daher Alpha und Beta) möglicherweise keine Information wiederverwenden. Ist das zu erwarten oder fehlt mir hier etwas Grundlegendes?

Zum Beispiel, wenn für Alpha = 3 Beta = 4 wir zu einem Ergebnis von 7 kommen (offensichtlich ein Cut-off) sollte ich das in der Tabelle als gültig für Alpha = 3 bis Beta = 6 speichern? Oder Beta = 7?

Answer 1

Ihr Problem hängt mit dem konzeptionellen Verständnis der Verwendung einer Transpositionstabelle neben einer Alpha-Beta-Suche zusammen. Dies war ein riesiges Problem, dem ich auch begegnete, und nachdem ich mich umgesehen hatte, fand ich this discussion, was mir das Konzept natürlicher erklärte als jedes Papier, das ich zu diesem Thema gelesen hatte.

Grundsätzlich können Sie nicht alle Alpha-Beta-Ergebnisse gleich behandeln, denn wenn ein Cutoff auftritt, repräsentiert das Ergebnis nur einen gebundenen und nicht den wahren Minimax-Wert. Es wurde bewiesen, dass die Verwendung von Schranken Ihnen immer noch den gleichen nächsten Zustand gibt, aber möglicherweise ohne die genaue Punktzahl zu haben. Wenn Sie den Status von einem Cutoff speichern, müssen Sie ihn als eine Grenze behandeln und versuchen, ihn beim nächsten Durchlauf zu verbessern. Dies wird oft den gleichen Knoten mehrmals bewerten, aber es wird bei Bedarf die tatsächliche Punktzahl kontinuierlich verbessern.

Here is a good example einer vollständigeren Implementierung der Konzepte in dem zuvor verknüpften Artikel aufgeführt. Blättern Sie auf Seite 14.