조브리스트 해싱

조브리스트 해싱은 포지션을 구성할 수 있는 특징에 의사난수를 할당한다. 보통 기물 종류, 색, 칸의 모든 조합에 숫자 하나씩을 두고, 둘 차례인 쪽, 킹과 룩이 특별한 수를 둘 수 있는지 기록하는 캐슬링 권리, 특별한 폰 잡기를 위한 관련 en passant 상태에도 숫자를 둔다. 의사난수란 값이 무작위처럼 보이지만 재현 가능하게 생성된다는 뜻이다.

포지션 키는 활성 값들을 XOR로 결합해 만든다. XOR는 exclusive OR의 약자로 토글처럼 작동하는 이진 연산이다. 같은 값을 두 번 적용하면 효과가 되돌아간다. 기물이 움직일 때 프로그램은 키를 처음부터 다시 만들지 않고 이전 칸의 값을 제거하고 새 칸의 값을 추가할 수 있다. 잡기, 승격, 둘 차례 변경도 같은 방식으로 갱신할 수 있다.

이 지문을 이용하면 포지션을 분석하는 프로그램인 체스 엔진이 같은 포지션이 전에 나타났는지 빠르게 알아볼 수 있다. 서로 다른 수순이 같은 상태에 도달하면 저장된 분석을 재사용하고, 반복을 감지하며, 이전 결과를 빠르게 보관하는 캐시를 정리할 수 있다. 올바른 비교에는 기물 배치뿐 아니라 합법적인 가능성을 바꾸는 둘 차례와 특별 권리도 포함해야 한다.

조브리스트 키는 고유성이 보장되지 않는다. 서로 다른 두 포지션이 같은 숫자를 만들 수 있으며 이를 충돌이라고 한다. 큰 키를 쓰면 가능성이 낮아지지만 저장과 검증 설계는 여전히 그 가능성을 고려해야 한다. Perft 같은 테스트에서는 수를 두고 무른 뒤 증분 키가 원래 값으로 돌아오지 않을 때 갱신 오류를 드러낼 수도 있다.