Minimax

Hashtabellen

Hashtabellen dienen der Erkennugn von Zugumstellungen im Suchprozess und der Vermeidung von redundanter Rechenarbeit. In Computer, Schach und Spiele (CSS) erschien ein Artikel, der die Funktionsweise der Hashtabelle ausführlich erläutert. Dort wurde bewusst auf Codebeispiele verzichtet und statt dessen an diese Stelle verwiesen. Die folgenden Erkärungen beschränken sich also auf Code-Beispiele und setzen den Artikel ein Stück weit voraus. Falls trotzdem noch Fragen offen sind, können diese im Diskussionsforum besprochen werden.

Der Code:

THash = record // Der Typ eines Hashtabelleneintrags
  Kennung: Integer; // Die Hashkennung
  Tiefe: Shortint; // aus welcher Rechentife stammt der Wert?
  Wert: Smallint; // Die Bewertung
  Typ: Byte; // EXACT, LOW oder HIGH. Man darf nicht jeden Typ blind verwenden
  BesterZug: THashZug; // Der beste Zug in der entsprechenden Position
end;

THashZug ist dabei eine abgespeckte Variante von TZugTyp ohne Informationen über das ep-Feld, die geschlagene oder umgewandelte Figur, Rochadestatus und den Wert. Die Typendeklaration lautet:

THashZug = record
von, nach: Byte; // von und nach Feld
end;

Beim Programmstart wird ein Array mit Zufallszahlen gefüllt. Die Dimension A1-H8 entspricht dabei allen 64 Feldern des Schachbretts, -6..6 steht für die weißen und schwarzen Figurentypen. Die Schleife läuft dabei auch über einige Randfelder des 10x12 Schachbretts, somit werden einige Array Elemente angelegt, die später nie verwendet werden. Die Alternative wäre Umrechnen, das scheint aber umständlicher zu sein.

Randomize; // Zufallsgenerator initialisieren
Hashsize := (1048576) - 1; // 2^20 - 1 // Größe der Hashtabelle (müß 2^x - 1 sein)
SetLength(HashTable, HashSize + 1);

for i := A1 to H8 do // Zufallszahlen für das Hashing erzeugen
begin
  for j := -6 to 6 do //Figurentypen
  begin
    Zufall[i][j].index := Random(2147483646) + 1;
    Zufall[i][j].kennung := Random(2147483646) + 1;
  end;
end;

Deklariert sind die Typen und Variablen folgendermaßen:

TZufall = record
index, kennung: integer;
end;

Zufall: array[A1..H8, -6..6] of TZufall; // Zufallsarray für Hashing
HashSize: integer;
Hashtable: array of THash; // Dynamisches Array!
HashIndex, HashKennung: integer;

Beim Ausführen und Zurücknehmen von Zügen müssen nun die Figuren nicht nur auf dem Brett, sondern auch in den beiden Variablen HashIndex und HashKennung gesetzt werden. Dies geschieht durch eine XOR-Verknüpfung mit dem entsprechenden Element aus dem Zufallsarray. Der Zug e2-e4 würde für den Index folgendermaßen aussehen:

HashIndex := HashIndex XOR Zufall[E2, WB].Index // Weißen Bauern von E2 entfernen
HashIndex := HashIndex XOR Zufall[E4, WB].Index // Weißen Bauern auf E$ setzen

Wobei E2, E4 und WB Konstanten für die Feldnummern und den weißen Bauern sind (E2 = 35; E4 = 55; WB = 1). Selbiges muss noch auf HashKennung angewendet werden. Neben dem normalen ziehen der Figuren darf man natürlich nicht vergessen, geschlagene Figuren zu entfernen, bei der Umwandlung die neue Figur zu setzen und bei der Rochade den Turm zu ziehen. Auch das Zugrecht muß beim Farbwechsel in Index und Kennung vermerkt werden, hierzu kann man eine der oben erwähnten zu viel erzeugten Zufallszahlen nehmen (Beispielsweise das Randfeld: Zufall[H1+1, 0].Index).

Vor Spielbeginn werden HashIndex und HashKennug auf Null gesetzt und die Grundstellung erzeugt:

HashIndex := 0; // HashIndex und Kennung zurücksetzen
HashKennung := 0;

for i := A1 to H8 do begin // Grundstellung erzeugen
  if (Brett[i] <> Leer) and (Brett[i] <> Rand) then begin
    HashIndex := HashIndex xor Zufall[i][Brett[i]].index;
    HashKennung := HashKennung xor Zufall[i][Brett[i]].kennung;
  end;
end;

Nun ist alles vorbereitet um die eigentliche Idee zu verwirklichen:

Jedes Mal, wenn zu einer Position der beste Wert berechnet wurde, dann wird er in die Hashtabelle geschrieben in der Erwartung, dass diese Position vielleicht per Zugumstellung nochmals erreicht wird. Dann kann der Wert aus der Hashtabelle gelesen werden und die erneute Wertberechnung wurde erspart.
Bevor in einer Position begonnen wird alle Züge zu generieren und rekursiv zu bewerten schaut das Programm in die Hashtabelle in der Hoffnung, die aktuelle Stellung im Laufe des bisherigen Suchprozesses bereits berechnet und bewertet zu haben.

Welche Information muss in die THashtabelle geschieben werden?

HashKennung: Um sicher zu gehen, dass die Stellung aus der Hashtabelle auch zur aktuellen Stellung passt muss die aktuelle HashKennung gleich der HashKennung aus der Hashtabelle sein.
Tiefe: Wenn in der aktuellen Stellung noch 4 Züge tief zu rechnen ist, dann darf natürlich kein Wert aus der Hashtabelle gelesen werden, der nur aus einer Suchtiefe 2 Stammt. Die verbleibende Suchtiefe (Distanz) muss also kleiner oder gleich der Tiefe aus der Hashtabelle sein.
Wert: Die entsprechende Bewertung zu der aktuellen Position.
Typ: EXACT, LOW oder HIGH, je nachdem ob die Bewertung genau oder eine obere/untere Schranke ist.
BesterZug: Der beste Zug zur der Position im Rahmen der Vorausberechnung auf Tiefe Distanz.

Am Anfang der Funktion AlphaBeta wirft man also einen Blick in die Hashtabelle und bricht mit entsprechender Bewertung ab, falls man fündig wurde:

pos := HashIndex and HashSize; // Position in der HashTabelle (AND Schneller als MOD)
if (Hashtable[pos].Kennung = HashKennung) then begin
  Hashtreffer[tiefe] := Hashtable[pos].BesterZug; // Merken zur besseren Zugsortierung
  if Hashtable[pos].tiefe >= Distanz then begin
    case Hashtable[pos].typ of
      EXACT:
      begin
        AlphaBeta := Hashtable[pos].wert;
        exit;
      end;
      HIGH:
      begin
        if Hashtable[pos].wert >= Beta then begin
          AlphaBeta := Hashtable[pos].wert;
          exit;
        end;
      end;
      LOW:
      begin
        if Hashtable[pos].wert < Alpha then begin
          AlphaBeta := Hashtable[pos].wert;
          exit;
        end;
      end;
    end;
  end;
end;

Wann immer zu einer Position der beste Wert errechnet wurde, werden die Informationen in der Tabelle aufbewahrt:

if (Distanz >= HashTable[pos].Tiefe then begin
  HashTable[pos].Kennung := HashKennung;
  HashTable[pos].Tiefe := Distanz; // Aus welcher Rechentiefe stammt der Wert?
  HashTable[pos].Wert := BesterWert; // Der beste gefundene Wert der Position
  HashTable[pos].BesterZug.von := Zugstapel[BestesI].von; // Der entsprechende Zug
  HashTable[pos].BesterZug.nach := Zugstapel[BestesI].nach;
  HashTable[pos].Typ := tmp_HashTyp; // HashTyp wird beim Lesen verwendet
end;

Nun muss man nur noch dafür sorgen, dass der Typ richtig gesetzt ist. Standardmäßig hat man einen Wert vom Typ LOW in der Tasche. Im Falle eines Beta-Cutoff setzt man tmp_HashTyp auf HIGH und wenn man einen verbesserten Alpha Wert findet ist der Wert vom Typ EXACT

In DelphiMAX wird die Hashtabelle vor jedem Zug gelöscht. Zwar wirft man damit das gewonnene Wissen quasi nach jedem Zug weg, aber man erspart sich damit auch eine Menge Ärger. Tut man das nicht, so muss man sehr darauf achten, dass sich keine Karteileichen ansammeln, die dann ewig in der Tabelle verweilen und zu einer veralteten Brettstellung gehören. Der Platz in der Tabelle schwindet dann dahin und das Programm wird mit jedem Zug langsamer, da Hashtreffer immer seltener werden. Das Kollisionsrisilo erhöht sich und schlechte Züge werden immer wahrscheinlicher. Ich spreche aus Erfahrung.

[Zurück] [Home]