이것은 병렬 체스 검색을위한 shared hashtable algorithm에 대한 개념적인 질문입니다.병렬 체스 검색을위한 공유 해시 테이블
저는 4 개의 스레드를 생성하는 알파 베타 검색을 구현했습니다. 각 스레드는 검색을 수행하고 최상의 이동/평가를 반환합니다. 그러나 스레드가 다른 결과를 반환하는 검색 불안정을 관찰하고 있습니다. 링크에 설명 된 잠금없는 해시 테이블을 사용하고 있으므로 일부 항목은 덮어 쓰여지거나 손상 될 수 있습니다. 단, 손상된 데이터는 실제로 사용되지 않습니다.
왜 검색 결과가 다른 결과를 반환 할 수 있습니까? 이것은 병렬 검색의 예상 결과입니까, 아니면 문제입니까? 예상되는 경우, 선택할 이동 방법을 어떻게 알 수 있습니까?
병렬 검색은 비 결정적인이 될 것으로 예상됩니다. 전이 테이블 (일명 해시 테이블)을 통해 지식을 공유하면이 효과를 얻게됩니다.
병렬 검색을 실행하면 올바른 결과가 무엇인지 쉽게 판단 할 수 없습니다. 그래서, 당신은 무엇을 할 수 있습니까? 4 개의 스레드가있는 경우 다수결을 시도 할 수 있지만 그 작업을 수행하는 엔진은 알지 못합니다.
검색 안정성은 중첩 테이블을 사용하기 시작하면 순차 검색 알고리즘에있을지라도 문제가됩니다.
전치 테이블을 사용하여 순차 검색 알고리즘을 실행하고 나중에 같은 검색을 반복하면 (전치 테이블을 재설정하지 않고) 동일한 결과를 얻을 수있는 것은 아닙니다. 병렬 검색에 대해서도 마찬가지이며, 병렬 검색은 결정적이지 않습니다.
검색의 안정성과 결정은 같은 것이 아니다 : 순차 검색에
왜 전치 테이블이 검색 불안정성을 초래하는지 설명하려면 this question을 살펴보십시오.