Zobrist hashing

Zobrist-hashning (även kallad Zobrist-nycklar eller Zobrist-signaturer ) är en hashfunktionskonstruktion som används i datorprogram som spelar abstrakta brädspel , som schack och Go , för att implementera transponeringstabeller , en speciell typ av hashtabell som indexeras av en styrelseposition och används för att undvika att analysera samma position mer än en gång. Zobrist-hashing är uppkallad efter sin uppfinnare, Albert Lindsey Zobrist . Det har också använts som en metod för att känna igen substitutionslegeringskonfigurationer i simuleringar av kristallina material. Zobrist-hashning är den första kända instansen av den allmänt användbara underliggande tekniken som kallas tabuleringshashning .

Beräkning av hashvärdet

Zobrist-hashningen börjar med att slumpmässigt generera bitsträngar för varje möjligt element i ett brädspel, dvs. för varje kombination av en pjäs och en position (i schackspelet är det 12 pjäser × 64 brädpositioner, eller 18 × 64 om kungar och torn som may still castle, och bönder som kan fånga en passant , behandlas separat för båda färgerna). Nu kan alla kortkonfigurationer delas upp i oberoende stycke-/positionskomponenter, som mappas till de slumpmässiga bitsträngar som genererats tidigare. Den slutliga Zobrist-hashen beräknas genom att kombinera dessa bitsträngar med hjälp av bitvis XOR . Exempel pseudokod för spelet schack: ^{[ citat behövs ]}

 konstantindex white_pawn := 1 white_rook := 2 # etc. black_king := 12  funktion  init_zobrist(): # fyll i en tabell med slumptal/bitsträngar tabell := en 2-d array med storleken 64×12  för  i från 1 till 64 : # slinga över brädan, representerad som en linjär array  för  j från 1 till 12: # slinga över pjästabellen[i][j] := random_bitstring() table.black_to_move = random_bitstring()  funktion  hash(board): h := 0 if is_black_turn(board): h := h XOR table.black_to_move  for  i från 1 till 64: # slinga över brädans positioner  om  brädet[i] ≠ tomt: j := pjäsen vid brädet[i], som listade i konstantindexen, ovanför h := h XOR-tabell[i][j]  returnerar  h

Användning av hashvärdet

Om bitsträngarna är tillräckligt långa kommer olika styrelsepositioner nästan säkert att hash till olika värden; längre bitsträngar kräver dock proportionellt mer datorresurser att manipulera. Den vanligaste bitsträngen (nyckel) längden är 64 bitar. Många spelmotorer lagrar endast hash-värdena i transponeringstabellen, utelämnar själva positionsinformationen helt för att minska minnesanvändningen, och antar att hashkollisioner inte kommer att inträffa, eller inte i stor utsträckning kommer att påverka tabellens resultat om de gör det.

Zobrist-hashning är den första kända instansen av tabuleringshashning . Resultatet är en 3-vis oberoende hashfamilj . I synnerhet är det starkt universellt .

Som ett exempel, i schack kan var och en av de 64 rutorna när som helst vara tomma eller innehålla en av de 6 spelpjäserna, som antingen är svarta eller vita. Det kan också vara antingen svarts tur att spela eller vits tur att spela. Man behöver alltså generera 6 x 2 x 64 + 1 = 769 slumpmässiga bitsträngar. Givet en position får man sin Zobrist-hash genom att ta reda på vilka bitar som finns på vilka rutor och kombinera de relevanta bitsträngarna. Om positionen är svart för att flytta, ingår också bitsträngen för att flytta svart i Zobrist-hash.

Uppdaterar hashvärdet

Istället för att beräkna hashen för hela kortet varje gång, som pseudokoden ovan gör, kan hashvärdet för ett bräda uppdateras stegvis genom att helt enkelt XORera ut bitsträngen/bitsträngarna för positioner som har ändrats och XORing i bitsträngarna för nya befattningar. Till exempel, om en bonde på en schackbrädesruta ersätts av ett torn från en annan ruta, skulle den resulterande positionen produceras genom att XORing av den befintliga hashen med bitsträngarna för:

 'bonda vid denna ruta' (XORing  ut  bonden vid denna ruta) 'Rook på denna ruta' (XORing  i  tornet vid denna ruta) 'Rook vid source square' (XORing  ut  tornet vid source square)

Detta gör Zobrist-hashningen mycket effektiv för att korsa ett spelträd .

I computer Go används denna teknik även för superko- detektion.

Bredare användning

Mer generellt kan Zobrist-hashning tillämpas över ändliga uppsättningar av element (i schackexemplet är dessa element $(piece,position)$ tupler ), så länge som en slumpmässig bitsträng kan tilldelas varje möjligt element. Detta kan antingen göras med en slumpgenerator för mindre elementutrymmen, eller med en hashfunktion för större. Denna metod har använts för att känna igen substitutionslegeringskonfigurationer under Monte Carlo-simuleringar för att förhindra slöseri med beräkningsansträngning på tillstånd som redan har beräknats.

Se även

Alfa-beta beskärning

^ ^a ^b ^c ^d Bruce Moreland. Zobrist-nycklar: ett sätt att möjliggöra positionsjämförelse.
^ Albert Lindsey Zobrist, en ny hashingmetod med applikation för att leka, Tech. Rep. 88, datavetenskapsavdelningen, University of Wisconsin, Madison, Wisconsin, (1969).
^ ^a ^b Mason, DR; Hudson, TS; Sutton, AP (2005). "Snabbt återkallande av tillståndshistoria i kinetiska Monte Carlo-simuleringar med hjälp av Zobrist-nyckeln". Datorfysik kommunikation . 165 : 37. Bibcode : 2005CoPhC.165...37M . doi : 10.1016/j.cpc.2004.09.007 .

[moreland-1] Bruce Moreland. Zobrist-nycklar: ett sätt att möjliggöra positionsjämförelse.

[2] Albert Lindsey Zobrist, en ny hashingmetod med applikation för att leka, Tech. Rep. 88, datavetenskapsavdelningen, University of Wisconsin, Madison, Wisconsin, (1969).

[MonteCarlo-3] Mason, DR; Hudson, TS; Sutton, AP (2005). "Snabbt återkallande av tillståndshistoria i kinetiska Monte Carlo-simuleringar med hjälp av Zobrist-nyckeln". Datorfysik kommunikation . 165 : 37. Bibcode : 2005CoPhC.165...37M . doi : 10.1016/j.cpc.2004.09.007 .