조브리스트 해싱 계산기

판 위의 (칸, 말) 조합마다 난수를 하나씩 미리 뽑아 두고, 놓여 있는 것들의 난수를 모두 XOR한 값을 그 판의 해시로 쓰는 방법입니다. 1970년 앨버트 조브리스트가 바둑 프로그램을 위해 내놓았고, 지금 체스·바둑 엔진의 전치표가 모두 이것 위에 서 있습니다.

한 수에 XOR 두 번으로 해시가 갱신되기 때문입니다. 말을 a에서 b로 옮기면 새 해시 = 옛 해시 XOR key(a, 말) XOR key(b, 말)입니다. 판을 처음부터 다시 훑을 필요가 없어 탐색 트리에서 초당 수백만 번씩 판이 바뀌어도 감당이 됩니다.

똑같이 XOR 두 번입니다. XOR은 자기 자신이 역연산이라 같은 값을 두 번 넣으면 없던 일이 됩니다. 두었다 물렀다를 되풀이하는 게임 트리 탐색에 이보다 잘 맞는 성질이 없습니다.

이미 계산해 본 판을 해시로 찾아 쓰는 표입니다. XOR은 순서에 상관없으므로 「수순은 달랐지만 같은 판」이 같은 해시를 갖고, 그래서 같은 판을 두 번 계산하지 않게 됩니다. 「전치(transposition)」란 서로 다른 수순이 같은 판에 이르는 것을 말합니다.

서로 다른 두 판을 같은 것으로 착각합니다. 64비트라면 판 백만 개를 담아도 확률이 2.7×10⁻⁸이지만, 십억 개면 2.7%까지 오릅니다. 엔진이 32비트가 아니라 64비트를 쓰는 이유이고, 그래도 아주 드물게 잘못된 판을 재사용하는 일이 생기는 이유이기도 합니다.

씨앗 하나에서 결정적으로 뽑습니다. 이 도구는 splitmix64를 씁니다. 씨앗이 같으면 언제나 같은 표가 나오므로, 같은 해시를 재현할 수 있고 프로그램을 껐다 켜도 같은 전치표를 쓸 수 있습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력한 판과 씨앗은 이 기기에만 남습니다.