조브리스트 해싱

조브리스트 해싱(Zobrist keys 또는 Zobrist signatures라고도 함)은 체스나 바둑과 같은 추상 보드게임을 하는 컴퓨터 프로그램에서 사용하는 해시함수 구조로, 보드 포지션에 의해 색인화되어 같은 포지션의 분석을 한 번 이상 회피하기 위해 사용되는 특수한 종류의 해시 테이블이다.조브리스트 해싱은 발명가 알버트 린지 조브리스트의 이름을 따서 명명되었다.^[2]결정물질 시뮬레이션에서 대체합금 구성을 인정하는 방법으로도 적용됐다.^[3]조브리스트 해싱은 일반적으로 유용한 기본 기술인 표 해싱의 첫 번째 알려진 예다.

해시값 계산

조브리스트 해싱은 보드 게임의 가능한 각 요소, 즉 한 조각과 한 포지션의 각 조합에 대해 무작위로 비트스트링을 생성하는 것으로 시작한다(장기 게임에서, 12조각 × 64 보드 포지션 또는 아직도 성을 쌓을 수 있는 왕과 엔패런트를 포획할 수 있는 졸이 두 가지 색상에 대해 별도로 취급되는 경우 16 x 64).이제 모든 보드 구성은 독립된 조각/위치 구성 요소로 분할될 수 있으며, 이 구성 요소는 이전에 생성된 임의 비트스트링에 매핑된다.최종 조브리스트 해시는 비트 와이즈 XOR를 사용하여 이러한 비트스트링을 결합하여 계산한다.체스 게임의 유사 코드 예:^{[citation needed]}

상수지수 white_messages :=1 white_message :=2 # black_king := 12 함수 init_zobrist() : # 1부터 64까지 i를 위한 크기 64×12의 2-d 배열: 보드 위로 #loop, 1부터 12까지 j를 위한 선형 배열로 표현된다.표백[i][j] := random_bitstringstring 테이블black_to_move = random_bitstring()함수 해시(board): h := 0 if is_black_turn(board): h := h XOR table1에서 64까지 i에 대해 black_to_move: # 보드[i]가 비어 있는 경우 보드 위치 위로 루프: j := 보드[i]의 조각, 상수 지수에 나열된 대로 보드[i]에 있는 조각, h := h XOR 테이블[j][j] 리턴 h

해시 값 사용

만약 비트스트링이 충분히 길다면, 다른 보드 위치는 거의 확실히 다른 값과 일치할 것이다; 그러나 비트스트링은 조작하는데 비례적으로 더 많은 컴퓨터 자원을 필요로 한다.가장 일반적으로 사용되는 비트 문자열(키) 길이는 64비트다.^[1]많은 게임 엔진은 메모리 사용을 줄이기 위해 위치 정보 자체를 완전히 생략하고, 해시 충돌이 일어나지 않거나, 발생하더라도 테이블 결과에 큰 영향을 미치지 않는다고 가정하면서, 전환 표에 해시 값만 저장한다.

조브리스트 해싱은 표 해싱의 첫 번째 알려진 예다.그 결과는 3가지 지혜의 독립 해시 패밀리가 된다.특히, 그것은 강하게 보편적이다.

예를 들어 체스에서 64개의 사각형은 언제든지 비어 있거나 6개의 게임 조각 중 하나를 포함할 수 있는데, 이는 검은색 또는 흰색이다.또한, 그것은 검은색이 연주할 차례가 될 수도 있고 흰색이 연주할 차례가 될 수도 있다.따라서 6 x 2 x 64 + 1 = 769 랜덤 비트스트링을 생성해야 한다.지위가 주어지면 어떤 조각이 어떤 정사각형 위에 있는지 알아내고, 관련 비트스트링을 함께 결합하여 조브리스트 해시를 얻는다.이동할 위치가 검은색일 경우, 흑 대 이동 비트 문자열도 조브리스트 해시에 포함된다.^[1]

해시 값 업데이트

위의 유사 코드가 그렇듯이 매번 전체 보드의 해시를 계산하기보다는, 보드의 해시 값은 단순히 변경된 위치의 비트 문자열을 XOR로 출력하고, 새로운 위치의 비트 스트링의 XORing으로 증분적으로 업데이트할 수 있다.^[1]예를 들어 체스보드 사각형의 폰이 다른 사각형의 루크로 대체되는 경우, 기존 해시를 다음에 대한 비트스트링으로 XOR하여 결과 위치가 생성된다.

'이 사각형에서 새끼를 낳는다'(이 사각형에서 졸을 빼는 XORING) '이 사각형에서 rook at source square'(이 사각형에서 rook at source square에서 rook를 뺀 XORING) '아무것도 원본 사각형에서 rook at source square'(XORING) 

이것은 조브리스트가 게임 트리를 가로지르는 것을 매우 효율적으로 만든다.

컴퓨터 바둑에서는 이 기술이 슈퍼코 검출에도 쓰인다.

사용량 확대

좀 더 일반적으로, 조브리스트 해싱은 각 가능한 요소에 무작위 비트 문자열을 할당할 수 있는 한, 유한한 요소 집합에 적용될 수 있다(체스 예에서$,{\displaystyle }$ ${\displaystyle \mathrm{이러한}}$ ${\displaystyle \mathrm{요소들}}$은 ${\displaystyle (p}$ i e ${\displaystyle e}$, ${\displaystyle p}$ ${\displaystyle o}$ i ${\displaystyle o}$ i${\displaystyle o}$ ) ${\$디스플레이 $스타일(피스,$ 위치$)$ tupply$$)이다.이것은 작은 요소 공간에 대한 난수 생성기 또는 더 큰 공간에 대한 해시 함수를 사용하여 수행할 수 있다.이 방법은 이미 계산된 상태에 연산 노력이 낭비되는 것을 방지하기 위해 몬테카를로 시뮬레이션 동안 대체 합금 구성을 인식하는 데 사용되었다.^[3]

참고 항목

• 알파베타 가지치기

참조