체스 매직 비트보드의 해시 테이블 패킹 문제의 NP 완전성

본 논문은 체스에서 매직 비트보드를 최적화할 때 발생하는 해시 테이블 패킹 문제가 강 NP 완전 문제임을 증명합니다. 저자는 3-분할 문제를 해시 테이블 패킹 문제로 축소하여 최소 크기의 패킹을 찾는 것이 계산적으로 어려움을 보여줍니다. 이는 실제로 최적 해를 찾는 대신 휴리스틱 알고리즘을 사용해야 함을 의미합니다. 매직 비트보드가 효율적인 수 생성에 필수적이므로 체스 엔진의 성능 최적화에 큰 영향을 미칩니다.