Zobrist haszuje - Zobrist hashing

Haszowanie Zobrista (określane również jako klucze Zobrist lub podpisy Zobrist ) to konstrukcja funkcji skrótu używana w programach komputerowych, które grają w abstrakcyjne gry planszowe , takie jak szachy i Go , do implementacji tabel transpozycji , specjalnego rodzaju tabeli skrótów, która jest indeksowana przez pozycji tablicy i służy do unikania analizowania tej samej pozycji więcej niż raz. Nazwa haszowania Zobrist pochodzi od nazwiska jego wynalazcy, Alberta Lindseya Zobrista . Został również zastosowany jako metoda rozpoznawania substytucyjnych konfiguracji stopów w symulacjach materiałów krystalicznych.

Obliczanie wartości skrótu

Haszowanie Zobrista zaczyna się od losowego generowania ciągów bitów dla każdego możliwego elementu gry planszowej, tj. Dla każdej kombinacji figury i pozycji (w grze w szachy jest to 12 sztuk × 64 pozycje na szachownicy lub 16 x 64, jeśli król może nieruchomy zamek i pionek, który może zbić w przelocie, są traktowane oddzielnie dla obu kolorów). Teraz dowolna konfiguracja płytki może zostać podzielona na niezależne elementy / pozycje, które są odwzorowywane na losowe ciągi bitów wygenerowane wcześniej. Ostateczna wartość skrótu Zobrist jest obliczana przez połączenie tych ciągów bitów za pomocą bitowego XOR . Przykładowy pseudokod do gry w szachy:

constant indices
    white_pawn := 1
    white_rook := 2
    # etc.
    black_king := 12

function init_zobrist():
    # fill a table of random numbers/bitstrings
    table := a 2-d array of size 64×12
    for i from 1 to 64:  # loop over the board, represented as a linear array
        for j from 1 to 12:      # loop over the pieces
            table[i][j] := random_bitstring()

function hash(board):
    h := 0
    for i from 1 to 64:      # loop over the board positions
        if board[i] ≠ empty:
            j := the piece at board[i], as listed in the constant indices, above
            h := h XOR table[i][j]
    return h

Użycie wartości skrótu

Jeśli ciągi bitów są wystarczająco długie, różne pozycje na planszy prawie na pewno będą miały różne wartości; jednak dłuższe łańcuchy bitowe wymagają proporcjonalnie większej ilości zasobów komputera do manipulacji. Najczęściej używana długość łańcucha bitów (klucza) to 64 bity. Wiele silników gier przechowuje tylko wartości skrótu w tabeli transpozycji, całkowicie pomijając informacje o pozycji, aby zmniejszyć zużycie pamięci i zakładając, że kolizje skrótów nie wystąpią lub nie wpłyną znacząco na wyniki tabeli, jeśli tak się stanie.

Haszowanie Zobrista jest pierwszym znanym przypadkiem haszowania tabel . W rezultacie otrzymujemy niezależną rodzinę hash na trzech poziomach . W szczególności jest silnie uniwersalny .

Na przykład w szachach każde z 64 pól może być w dowolnym momencie puste lub zawierać jeden z 6 pionów, które są czarne lub białe. Oznacza to, że każdy kwadrat może w dowolnym momencie znajdować się w jednym z 1 + 6 x 2 = 13 możliwych stanów. Zatem trzeba wygenerować co najwyżej 13 x 64 = 832 losowych ciągów bitów. Biorąc pod uwagę pozycję, uzyskuje się jej hash Zobrist, sprawdzając, które kawałki znajdują się na których kwadratach, i łącząc ze sobą odpowiednie ciągi bitów.

Aktualizowanie wartości skrótu

Zamiast obliczać hash dla całej tablicy za każdym razem, jak robi to powyższy pseudokod, wartość skrótu tablicy można zaktualizować po prostu przez XORowanie ciągów bitów dla pozycji, które uległy zmianie i XORowanie w ciągach bitów dla nowego pozycje. Na przykład, jeśli pionek na kwadracie szachownicy zostanie zastąpiony wieżą z innego kwadratu, wynikowa pozycja zostanie utworzona przez XORowanie istniejącego skrótu z ciągami bitów dla:

'pawn at this square'      (XORing out the pawn at this square)
'rook at this square'      (XORing in the rook at this square)
'rook at source square'    (XORing out the rook at the source square)
'nothing at source square' (XORing in nothing at the source square).

To sprawia, że ​​haszowanie Zobrista jest bardzo wydajne podczas poruszania się po drzewie gry .

W komputerze Go ta technika jest również używana do wykrywania superko .

Szersze zastosowanie

Ta sama metoda została użyta do rozpoznania konfiguracji stopów substytucyjnych podczas symulacji Monte Carlo , aby zapobiec marnowaniu wysiłku obliczeniowego na stany, które zostały już obliczone.

Zobacz też

• Przycinanie alfa-beta

Bibliografia