Im Computerschach und den anderen Computerspielen werden Umstellungstische verwendet, um die Suche des Spielbaums zu beschleunigen. Umstellungstische sind in erster Linie in vollkommenen Informationsspielen nützlich, bedeutend, dass der komplette Staat des Spiels allen Spielern zu jeder Zeit bekannt ist.

Spielende Spielprogramme arbeiten durch das Analysieren von Millionen von Positionen, die in den nächsten paar Bewegungen des Spiels entstehen konnten. Gewöhnlich verwenden diese Programme Strategien, die Tiefensuche ähneln, was bedeutet, dass sie alle Positionen analysiert bis jetzt nicht nachgehen. In vielen Spielen ist es möglich, eine gegebene Position auf mehr als eine Weise zu erreichen. Diese werden Umstellungen genannt. Im Schach, zum Beispiel, der Folge von Bewegungen 1. d4 Nf6 2. c4 g6 (sieh algebraische Schachnotation), hat 4 mögliche Umstellungen, da jeder Spieler ihre Bewegungsordnung tauschen kann. Im Allgemeinen, danach n Bewegungen, ist eine obere Grenze auf den möglichen Umstellungen (n!) ². Obwohl viele von diesen ungesetzliche Bewegungsfolgen sind, ist es noch wahrscheinlich, dass das Programm damit enden wird, dieselbe Position mehrere Male zu analysieren.

Um dieses Problem zu vermeiden, werden Umstellungstische verwendet. Solch ein Tisch ist eine Hash-Tabelle von jeder der Positionen analysiert bis jetzt bis zu einer bestimmten Tiefe. Auf eine neue Position stoßend, überprüft das Programm den Tisch, um zu sehen, ob die Position bereits analysiert worden ist; das kann schnell in der erwarteten unveränderlichen Zeit getan werden. Wenn so, der Tisch enthält den Wert, der vorher dieser Position zugeteilt wurde; dieser Wert wird direkt verwendet. Wenn nicht, der Wert wird geschätzt, und in die neue Position wird in die Hash-Tabelle eingegangen. Das ist im Wesentlichen memoization angewandt auf die Suchfunktion.

Die Zahl von Positionen, die durch einen Computer häufig außerordentlich gesucht sind, überschreitet die Speichereinschränkungen des Systems, auf dem sie läuft; so können nicht alle Positionen versorgt werden. Wenn sich der Tisch füllt, werden weniger verwendete Positionen entfernt, um Platz für neue zu machen; das lässt die Umstellung eine Art geheimes Lager auf den Tisch legen.

Die Berechnung, die durch einen Umstellungstisch lookup gespart ist, ist nicht nur die Einschätzung einer einzelnen Position - wenn das der Fall wäre, würde es der Anstrengung kaum wert sein, da Einschätzungsfunktionen entworfen werden, um irgendwie sehr schnell zu sein. Statt dessen wird die Einschätzung eines kompletten Subbaums vermieden. So sind Umstellungstabelleneinträge für Knoten an einer seichteren Tiefe im Spielbaum wertvoller (da die Größe des an solch einem Knoten eingewurzelten Subbaums größer ist) und deshalb mehr Wichtigkeit gegeben werden, wenn sich der Tisch füllt und einige Einträge verworfen werden müssen.

Die Hash-Tabelle, die den Umstellungstisch durchführt, kann anderen Nutzen haben als Entdeckung von Umstellungen. In der Beschneidung des Alpha-Betas ist die Suche (tatsächlich am schnellsten, optimal), wenn das Kind eines Knotens entsprechend der besten Bewegung immer erst betrachtet wird. Natürlich gibt es keine Weise, die beste Bewegung zu wissen, aber wenn das wiederholende Vertiefen verwendet wird, ist die Bewegung, die, wie man fand, in einer seichteren Suche am besten war, eine gute Annäherung. Deshalb wird diese Bewegung zuerst versucht. Für das beste Kind eines Knotens zu versorgen, wird der Zugang entsprechend diesem Knoten im Umstellungstisch verwendet.

Der Gebrauch eines Umstellungstisches kann zu falschen Ergebnissen führen, wenn das Graph-Geschichtswechselwirkungsproblem nicht fleißig vermieden wird. Dieses Problem entsteht in bestimmten Spielen, weil die Geschichte einer Position wichtig sein kann. Zum Beispiel im Schach kann ein Spieler nicht rochieren, wenn sich der König oder die Saatkrähe, die damit zu rochieren ist, während des Kurses des Spiels bewegt haben. Eine allgemeine Lösung dieses Problems ist, die rochierenden Rechte als ein Teil des Schlüssels von Zobrist hashing hinzuzufügen. Ein anderes Beispiel ist Attraktion durch die Wiederholung: In Anbetracht einer Position kann es nicht möglich sein zu bestimmen, ob es bereits vorgekommen ist. Eine Lösung des allgemeinen Problems ist, Geschichtsinformation in jedem Knoten des Umstellungstisches zu versorgen, aber das ist ineffizient und in der Praxis selten getan.

Zusammenhängende Techniken

• Ähnliche Techniken können an Einschätzungen des geheimen Lagers von bestimmten Eigenschaften einer Position gewöhnt sein. Zum Beispiel kann eine Pfand-Hash-Tabelle verwendet werden, um eine Einschätzung der Pfand-Strukturen in einer Position zu versorgen. Da die Zahl von untersuchten Pfand-Positionen allgemein viel kleiner ist als die Gesamtzahl von gesuchten Positionen, hat die Pfand-Hash-Tabelle eine sehr hohe Erfolg-Rate, einem Programm erlaubend, mehr Zeit auf hoch entwickelten Pfand-Einschätzungen zu verbringen, weil sie oft wiederverwendet werden.
• Ein Widerlegungstisch kann verwendet werden, um Folgen von Bewegungen vom Wurzelknoten bis Blatt-Knoten zu versorgen. Das schließt die Hauptschwankung und Antworten auf andere Linien ein zeigend, dass sie untergeordnet sind. Widerlegungstische wurden manchmal statt Umstellungstische in den früheren Jahren des Computerschachs verwendet, als Gedächtnis mehr beschränkt wurde. Einige moderne Schachprogramme verwenden Widerlegungstische zusätzlich zu Umstellungstischen für die Bewegungseinrichtung.

Siehe auch

• Algorithmus von Minimax
• Alpha-Beta, das beschneidet
• Zobrist hashing

Zeichen und Verweisungen

Links

• Umstellungstische Sigmachess.com
• Technisch Der Hauptumstellungstisch (Information über die Datenstruktur und Durchführung)
• Die Anatomie von Schachprogrammen T.A. Marsland, Universität von Alberta