C : 체스의 쉽고 빠른 해시 테이블?

누군가 C의 해시 테이블을 잘 구현하는지 알고 있는지 궁금합니다. 제가하려는 것은 체스 보드 해시입니다. 구현을 빠르게하고 한 번에 테이블을 지울 수있는 기능을 원합니다. 어떤 도움이 appreicated 것입니다!C : 체스의 쉽고 빠른 해시 테이블?

출처

2014-11-18 John

안녕하세요 존, 환영. [ '묻는 방법'] (http://stackoverflow.com/help/how-to-ask) 페이지에서 좋은 질문을하는 법을보다 잘 이해할 수있게하십시오. (그러면 얻을 수있는 기회를 늘릴 수 있습니다. 좋은 답변) stackoverflow. 현재 귀하의 질문은 너무 광범위하며 연구 노력이나 예를 보여주지 않습니다. – streppel

아마도 나는 뭔가를 놓치고 있지만, 체스 판을 해쉬 할 필요는 없습니다. 'file *'과'rank'는 C 스타일의 인덱스가 0에서 7까지 인'8 * file + rank'의 인덱스를 사용하십시오. 여러분의 인덱스 나 키가 작은 것으로 매핑 될 수없는 데이터라면 해시가 유용합니다 정수 쉽게. 물론 파일을 통한 인덱싱을 고려하고 64 개의 키로 최소의 완벽한 해시를 얻을 수 있습니다. –

감사합니다. 나는 이것에 대해 생각하지 않았습니다. – John

체스에서는 대체로 "전치 테이블"이라고합니다. 이것은 해시 테이블보다 더 특수화 된 데이터 구조입니다.

조 변경 테이블은 캐시와 비슷합니다. 충돌 처리가 훨씬 간단하기 때문에 클래식 해시 테이블보다 빠릅니다. 결국 오래된 항목은 축출됩니다. 대조적으로, 클래식 해시 테이블은 요청하지 않으면 항목을 삭제해서는 안됩니다.

전치 테이블을 재사용 할 수 있다는 것을 인식하지 못했습니다. 내가 본 모든 체스 엔진은 자신의 구현을 가져옵니다.

이

조바꿈 테이블 자체
해시 기능의 핵심에 위치를 매핑 hash (자세한 내용은 Zobrist hashing 살펴보고)

조옮김 테이블 : 그것은 두 가지 측면으로 구성 자체가 매우 쉽습니다. 깊은 검색에서 항목이 더 적은 검색에서 항목에 의해 퇴거되도록

Entry* table = malloc(n * sizeof(Entry)); 
// ... 

// clear transposition table 
memset(table, 0, n * sizeof(Entry)); 

Position position; // the chess position 
// ... 

Key key = hash(position); 

// probe 
Entry entry = table[hash(position) % n]; 
if(entry.key == key) 
{ 
    // found something --> entry can be used 
    ... 
} 

// store 
table[hash(position) % n] = updated_entry;

보다 진보 된 전위 테이블이 자주, 여러 개의 슬롯을 사용하지 : 시작, 당신은 단순히 하나 개의 큰 배열을 사용할 수 있습니다. 다중 스레드 엔진에서 데이터 경합을 방지하면 실제 구현이 더욱 까다로워집니다. 여기

당신이 직접 작성하는 데 도움이됩니다 몇 가지 더 링크입니다 : 사이트에

출처

2015-01-27 14:56:14

C : 체스의 쉽고 빠른 해시 테이블?

답변

관련 문제