Zobrist Schlüssel

Wozu wird er benutzt?

Hier, im Zusammenhang mit diesen Spielen, wird der Zobrist Key verwendet, um Inhalte ganzer Spielfelder eindeutig auf eine Zahl abzubilden. Gleichzeitig wird er, im Zusammenhang mit Hashtables, benutzt um einen Index zu erzeugen, mit dem Schreib- und Lesezugriffe in eben diese Tabelle gesteuert werden.

Wie wird er konstruiert?

Um ihn erzeugen zu können bedarf es einiger Vorbereitung. Man muß zuerst ein paar Listen mit ganzen Zufallszahlen bauen. Man braucht für jede Spielpartei, jeden Figurtyp und jedes Feld auf das diese Figur gesetzt werden kann, eine Zufallszahl. Der Zufallszahlenbereich sollte im echten Spiel sehr, sehr, sehr, deutlich größer als die Summe aller Listenlängen sein. Vermutlich muß er größer als die Anzahl der gültigen Spielpositionen sein. Man kann sich ja mal überlegen, was passiert, wenn in dem unterem Beispiel nur Zufallszahlen im Bereich von 1 - 5 verwendet würden. Klarer Fall: keine Zahl darf mehr als einmal vorkommen. Damit ist erreicht, das jede dieser Zufallszahlen eine Spielfigur eines Spielers auf einer bestimmten Position repräsentiert. Der Schlüssel für das leere Spielfeld wird mit dem Wert 0 initialisiert. Anschießend erfolgt sowohl für das Setzen, als auch für das Entfernen der Figuren eine Brettkey = Brettkey XOR Zufallszahl von(Figurtyp, Spieler, Position) Operation. Das ganze funktioniert so nur bei Spielen, die mehrere gleiche Figuren einer Partei auf einem Feld, verbieten.

Schauen wir uns das einmal zu Fuß an.

Der Einfachheit wegen : 1 Figurtyp, 1 Partei, 5 Spielfelder. Spielfelder 1- 5 von links nach rechts.

    XOR: entweder das eine oder das andere Bit  =>  True (1)
         keines oder beide                      => False (0)

    Die Zufallszahlen : Pos 1   5,       0000 0101
                        Pos 2   232,     1110 1000
                        Pos 3   19,      0001 0011
                        Pos 4   64,      0100 0000
                        Pos 5   217      1101 1001

    Das Brett: .....    Key = 0          0000 0000
    Einsetzten auf Position 3
                                  Key:   0000 0000
                              XOR Figur: 0001 0011
                              --------------------
                                  Key:   0001 0011 kein Wunder
    Das Brett: ..F..   Key = 19
    Erneutes Einsetzten auf Position 5
                                  Key:   0001 0011
                              XOR Figur: 1101 1001
                              --------------------
                                  Key:   1100 1010
    Das Brett: ..F.F   Key = 202
    Erneutes Einsetzten auf Position 2
                                  Key:   1100 1010
                              XOR Figur: 1110 1000
                              --------------------
                                  Key:   0010 0010
    Das Brett: .FF.F   Key = 34
    Verschieben von 5 nach 1
    Schritt 1: entfernen von Pos 5
                                  Key:   0010 0010
                              XOR Figur: 1101 1001
                              --------------------
                                  Key:   1111 1011
    Schritt 2: setzten auf Pos 1
                                  Key:   1111 1011
                              XOR Figur: 0000 0101
                              --------------------
                                  Key:   1111 1110
    Das Brett: FFF..   Key = 254
    Verschieben von 3 nach 4
    Schritt 1: entfernen von Pos 3
                                  Key:   1111 1110
                              XOR Figur: 0001 0011
                              --------------------
                                  Key:   1110 1101
    Schritt 2: setzten auf Pos 4
                                  Key:   1110 1101
                              XOR Figur: 0100 0000
                              --------------------
                                  Key:   1010 1101
    Das Brett: FF.F.   Key = 173
    Entfernen von 1
                                  Key:   1010 1101
                              XOR Figur: 0000 0101
                              --------------------
                                  Key:   1010 1000
    Das Brett: .F.F.   Key = 168
    Verschieben von 2 nach 3
    Schritt 1: entfernen von Pos 2
                                  Key:   1010 1000
                              XOR Figur: 1110 1000
                              --------------------
                                  Key:   0100 0000
    Schritt 2: setzten auf Pos 3
                                  Key:   0100 0000
                              XOR Figur: 0001 0011
                              --------------------
                                  Key:   0101 0011
    Das Brett: ..FF.   Key = 83
    Entfernen von 4
                                  Key:   0101 0011
                              XOR Figur: 0100 0000
                              --------------------
                                  Key:   0001 0011
    Das Brett: ..F..   Key = 19
    sieht gut aus: der Key behauptet es gäbe 1 Figur auf Position 3
    Entfernen von 3
                                  Key:   0101 0011
                              XOR Figur: 0101 0011
                              --------------------
                                  Key:   0000 0000
    Das Brett: .....   Key = 0  sehr schön: das Brett ist wieder leer.
                    

Magie mit XOR.