비트보드

Bitboard

비트보드는 보드 게임을 하는 컴퓨터 시스템에서 일반적으로 사용되는 특수한 비트 배열 데이터 구조입니다. 여기서 각 비트는 게임 보드 공간 또는 조각에 해당합니다.이를 통해 병렬 비트 연산을 통해 게임 상태를 설정 또는 쿼리하거나 게임 내 이동 또는 플레이를 결정할 수 있습니다.

같은 비트보드 내의 비트는 게임의 규칙에 의해 서로 관련지어지며, 종종 함께 사용될 때 게임 위치를 형성합니다.다른 비트보드는 일반적으로 위치에 대한 쿼리를 변환하거나 응답하기 위한 마스크로 사용됩니다.비트보드는 데이터 구조의 비트에 공간 상태를 매핑함으로써 게임 보드의 개별 공간 상태 또는 조각의 존재로 진척이 나타나는 게임에 적용할 수 있다.비트보드는 기존의 우편함 표현을 대체하는 보다 효율적인 보드 표현입니다.보드의 각 부분 또는 공간은 어레이 요소입니다.

비트보드는 보드상의 다양한 관련 상태의 관련 비트가 CPU 아키텍처의 단일 워드 또는 이중 워드에 적합할 때 특히 효과적이며, AND 및 OR과 같은 단일 비트 연산자를 사용하여 게임 상태를 구축하거나 쿼리할 수 있습니다.

비트보드를 사용하는 컴퓨터 게임에는 체스, 체커, 오셀로, 워드 게임 등이 있습니다.이 계획은 1950년대에 체커 프로그램에 처음 적용되었고 1970년대 중반부터 컴퓨터 자동기에서 게임 보드 표현을 위한 사실상의 표준이 되었다.

묘사

상세 정보:비트 필드

비트보드(bitboard)는 여러 개의 관련 부울 변수를 동일한 기계어로 묶는 형식이며, 일반적으로 보드 게임의 위치 또는 게임 상태를 나타냅니다.각 비트는 공간을 나타냅니다.비트가 양의 경우 해당 공간의 속성이 참입니다.비트보드를 사용하면 컴퓨터는 한 번의 비트 조작으로 게임 상태에 대한 몇 가지 질문에 대답할 수 있습니다.예를 들어 체스 프로그램에서 흰색 플레이어가 보드 중앙에 폰이 있는지 알고 싶다면(중앙 네 칸) 비트 AND 연산을 사용하여 플레이어 폰의 비트보드를 보드 중앙의 비트보드와 비교할 수 있습니다.센터 폰이 없는 경우 결과는 모두 0비트(즉, 0과 동일)가 됩니다.복수의 비트보드는 보드상의 공간의 다른 속성을 나타내며, 특수 또는 임시 비트보드(임시 변수 등)는 로컬 속성을 나타내거나 중간 대조 결과를 유지할 수 있습니다.

비트보드의 효율은 구현의 다른 두 가지 특성에 의해 강화됩니다.첫째, 비트보드는 조각 이동 시 조각 위치를 위해 비트보드의 소스 및 대상 위치에서 비트를 플립하는 등 증분 업데이트가 빠릅니다.둘째, 체스보드 상의 위치별로 각 피스 타입에 의해 공격된 모든 공간과 같은 정적 특성을 나타내는 비트맵을 미리 조합하여 테이블에 저장할 수 있으므로 "공간 e4 위의 나이트의 법적 움직임은 무엇인가?" 등의 질문에 답할 수 있는 단일 메모리 페치로 응답할 수 있다.

비트필드 구현에서는 AND, OR, NOT 등의 풀워드(32비트 또는 64비트)의 논리연산이 최신 CPU 아키텍처에 존재하기 때문에 효율적입니다.비트보드는 이전의 8비트 및 16비트 미니컴퓨터와 마이크로프로세서 아키텍처에서는 효과적이지 않을 수 있습니다.

구현 문제

대량의 테이블 내용의 압축과 부호화가 필요하고, 문자 변환이나 부호화 에러가 발생할 가능성이 높기 때문에, 비트보드 프로그램은 소프트웨어 개발자가 쓰거나 디버깅하는 데 지루하다.일반적으로 표를 작성하려면 애플리케이션의 일부가 아닌 보조 생성 방법이 필요합니다.

프로세서 사용률

장점

비트보드 표현은 거의 모든 CPU에서 사용할 수 있는 병렬 비트 연산을 사용합니다.이 작업은 한 사이클로 완료되며 파이프라인 처리 및 캐시 처리 등이 완료됩니다.거의 모든 CPU에는 AND, OR, NOR 및 XOR이 있습니다.또한 최신 CPU에는 실행을 위해 명령을 대기하는 명령 파이프라인이 있습니다.복수의 실행 유닛을 가지는 프로세서는, 파이프라인내에서 복수의 명령을 사용할 수 있는 경우, 사이클 마다 복수의 명령을 실행할 수 있다.분기가 있는 일반 명령 시퀀스로 인해 분기가 잘못 예측된 경우 파이프라인이 비워질 수 있습니다.많은 비트보드 동작에서는 필요한 조건이 적기 때문에 파이프라이닝이 증가하여 많은 CPU에서 여러 실행 유닛을 효율적으로 사용합니다.

CPU는 비트폭으로 설계되어 있으며, 이 폭에서 1 사이클로 비트 동작을 실행할 수 있습니다.따라서 64비트 이상의 CPU에서는 64비트 연산이 하나의 명령으로 발생할 수 있습니다.더 크거나 더 작은 폭의 명령이 지원될 수 있습니다.많은 32비트 CPU에는 64비트 명령이 있으며 32비트 명령에 비해 여러 사이클이 소요되거나 장애가 발생할 수 있습니다.

비트보드가 명령어 세트의 폭보다 클 경우 비트보드에서 전체 폭 연산을 수행하려면 여러 명령이 필요합니다.따라서 64비트 비트보드를 사용하는 프로그램은 32비트 프로세서보다 64비트 프로세서에서 더 빨리 실행됩니다.

단점

비트보드 표현은 소스 코드와 객체 코드 모두 훨씬 더 긴 코드를 가집니다.긴 비트 트위들링 시퀀스는 기술적으로는 쓰기 및 디버깅이 어렵습니다.비트보드 자체는 희박하며 64비트 중 1비트만 포함하는 경우도 있습니다.따라서 비트보드 구현은 메모리를 많이 사용합니다.이 두 가지 문제로 인해 캐시 누락이 증가하거나 캐시 스레싱이 발생할 수 있습니다.

프로세서에 '퍼스트 원'(또는 '카운트 선행 제로')와 '카운트 원'(또는 '카운트 제로')에 대한 하드웨어 명령이 없는 경우, 이러한 조작은 어셈블리 언어 루프로 코드화하기가 매우 비효율적이기 때문에 구현이 상당히 어려워집니다.

캐시 및 메모리 사용

장점

비트보드는 조각 목록 보드 데이터 구조보다 더 많은 메모리를 필요로 하지만, 많은 루프 앤 비교 작업이 단일(또는 소수의) 비트 작업으로 감소하기 때문에 실행 효율이 더 높습니다.예를 들어 우편함에서 조각 공격 공간이 합법적인 조각 이동을 통해 생성 및 루프되는지 여부를 판단하고 최종 공간과 공간을 비교해야 합니다.비트보드를 사용하면 조각의 합법적인 이동이 비트맵에 저장되고 해당 맵은 공간용 비트맵과 앤딩됩니다.0이 아닌 결과는 그 조각이 공간을 공격한다는 것을 의미합니다.

단점

일부 게임에서는 비트보드 엔진을 쓰려면 데이터 테이블을 포함한 상당한 양의 소스 코드가 필요하며, 이는 콤팩트 메일함/번호 입력 구현보다 더 길어집니다.레지스터 또는 프로세서명령 캐시의 수가 제한된 모바일 디바이스(휴대전화 등)의 경우, 이것이 문제의 원인이 될 가능성이 있습니다.풀사이즈 컴퓨터의 경우 레벨 1과 레벨 2의 캐시 사이에 캐시 누락이 발생할 수 있습니다.이는 잠재적인 문제일 뿐 큰 단점은 아닙니다.대부분의 머신에는 이 문제가 발생하지 않도록 충분한 명령 캐시가 있기 때문입니다.

증분 갱신

어떤 종류의 비트보드는 체스의 공격 맵과 같은 정교한 상호 상관 프로세스를 통해 다른 비트보드에서 파생됩니다.각 게임 상태 변경(이동 등)에서 이러한 모든 맵을 재구성하는 것은 비용이 많이 들기 때문에 파생 비트맵이 점진적으로 업데이트되며, 이 프로세스는 복잡하고 정확한 코드를 필요로 합니다.보드 위의 모든 비트맵이 아니라 변경된 공간과 관련된 비트맵만 변경하기 때문에 이 작업은 훨씬 더 빠르게 수행됩니다.증분 업데이트가 없으면 업데이트가 본질적으로 로컬이고 증분인 오래된 편지함 표현보다 비트맵 표현이 더 효율적이지 않을 수 있습니다.

사전 계산된 비트맵 및 테이블 검색

보드 구성에 의존하지 않는 일부 비트맵은 보드 이동 또는 상태 변경 후 조합이 아닌 테이블 룩업을 통해 사전 계산 및 검색할 수 있습니다. 예를 들어 체스 보드의 64개 공간에 각각 있는 기사 또는 킹에 의해 공격된 공간 등입니다.

체스 비트보드

체스판에서의 피스 구성을 알기 쉽고 간단하게 나타내는 것은 검색하기 쉬운 순서(예: 가장 작은 것부터 가장 큰 것까지)의 피스 리스트(배열)로서 각 피스를 보드상의 위치에 매핑하는 것입니다.마찬가지로, 각 조각에 의해 공격된 공간을 조합하려면 조각에 대해 해당 공간에 대한 직렬 열거가 필요합니다.이 방식을 우편함 주소 지정이라고 합니다.흰색과 검은색 조각에 대해 별도의 목록이 유지되며, 종종 흰색과 검은색 전당포에 대해 유지됩니다.지도는 이동할 때마다 업데이트되므로 조각 목록을 통해 선형 검색(또는 조각이 캡처된 경우 두 개)해야 합니다.우편함의 장점은 단순한 코드이며, 단점은 선형 검색이 느리다는 것입니다.조각을 위치에 매핑하는 더 빠르고 정교한 데이터 구조를 비트보드라고 합니다.

표준.

대수 표기법

비트보드 표현에서 64비트 워드(또는 32비트 아키텍처에서는 더블 워드)의 각 비트는 체스보드의 정사각형과 관련지어집니다.어떤 비트와 정사각형의 매핑도 사용할 수 있지만, 넓은 관례에 따라 비트는 왼쪽에서 오른쪽으로, 그리고 아래쪽에서 위로 정사각형과 관련지어지기 때문에 비트 0은 정사각형의 a1, 비트 7은 정사각형의 h1, 비트 56은 정사각형의 a8, 비트 63은 정사각형의 h8.

보드의 많은 다른 구성은 보통 킹, 모든 화이트 폰, 모든 블랙 폰의 위치 및 다른 조각 유형 또는 모든 흰색 조각의 조합에 대한 비트 보드로 나타납니다.두 가지 공격 비트보드도 공통적입니다. 정사각형을 공격하는 모든 조각에 대한 비트보드 1개와 조각을 포함하는 각 정사각형의 조각에 의해 공격되는 모든 사각형에 대한 역 비트보드 1개입니다.비트보드는 첫 번째 순위를 나타내는 것과 같은 상수일 수도 있습니다.첫 번째 순위는 위치 0 ~7에 1비트를 가집니다.다른 로컬 또는 과도기 비트보드는 필요에 따라 또는 [1]편리할 경우 "대립 피스에 의해 공격된 킹에 인접한 모든 공간"과 같은 데이터를 수집할 수 있습니다.

비트보드 사용의 예로는 조각이 프리세인지 여부를 판단하는 것이 있습니다.즉, "공간을 지키는 모든 우호적인 조각"과 "공간을 공격하는 모든 조각"을 위한 비트보드는 조각들을 매칭하여 공간상의 타깃 조각이 프리세인지 여부를 쉽게 판단할 수 있도록 합니다.

표준 비트보드의 결점 중 하나는 슬라이드 피스(rook, bishop, queen)의 공격 벡터를 조합하는 것입니다.이는 다른 점유 공간에 따라 공격 공간의 수가 제한되기 때문입니다.이를 위해서는 한 조각당 여러 개의 긴 마스크, 시프트 및 보완 시퀀스가 필요합니다.

보조 비트보드 표현

슬라이딩 피스의 공격 벡터를 위한 비트보드 생성의 코드 사이즈 및 계산 복잡성을 인식하여 이들을 대조하기 위한 대체 비트보드 데이터 구조를 고안했다.기사, 킹, 폰 및 기타 보드 구성의 비트보드 표현은 슬라이딩 피스에 보조 비트보드를 사용해도 영향을 받지 않습니다.

회전식 비트보드

회전 비트보드는 슬라이딩 피스 공격 벡터의 표화, 룩의 파일 공격 벡터의 표화 및 비숍의 대각 및 반대각 공격 벡터의 표화를 가능하게 하는 보완 비트보드 데이터 구조입니다(룩의 순위 공격은 표준 비트보드에서 인덱싱할 수 있습니다).이러한 비트보드에서는 단일 테이블 룩업이 긴 비트 단위 연산 시퀀스를 대체합니다.

이러한 비트보드는 보드 점유 구성을 90도, 45도 및/또는 315도 회전시킵니다.표준 비트보드는 체스 보드의 등급당 1바이트를 가집니다.이 비트보드를 사용하면 점유된 사각형과 순위 내 점유된 위치에 따라 색인화된 테이블을 사용하여 순위 전체에서 루크 공격을 쉽게 결정할 수 있습니다(루크 공격은 처음 점유된 사각형에서 중지되기 때문입니다).비트보드를 90도 회전시키면 루크 공격을 파일 위아래로 동일하게 검사할 수 있습니다.45도 및 315도(-45도) 회전하는 비트보드를 추가하면 대각선을 쉽게 검사할 수 있는 비트보드가 생성됩니다.퀸은 루크와 비숍의 공격을 조합하여 조사할 수 있습니다.실제로 비트보드를 회전시키는 것은 수십 가지 [2][3]명령이 필요한 고상한 변환입니다.

다이렉트

루크의 랭크 및 파일 공격 벡터와 비숍의 대각선 및 대각선 공격 벡터는 점유율에 따라 별도로 마스킹하여 미리 계산된 공격 벡터의 해시 테이블로 사용할 수 있으며, 루크의 경우 각각 8비트, 비숍의 경우 각각 2-8비트로 사용할 수 있습니다.조각의 전체 공격 벡터는 해시 테이블에서 인덱싱된 두 개의 단방향 벡터의 결합으로 얻어집니다.해시 테이블의 엔트리 수는 8*2^8 또는 2K바이트 정도로 적지만 해시함수 계산과1개당2개의 조회가 필요합니다.[4][5]

매직 비트보드

매직 비트보드는 공격 벡터의 직접 해시 룩업의 시공간 트레이드오프를 추정하는 것입니다.이들은 완전한 공격 벡터의 변환을 해시 테이블의 인덱스로 사용합니다.매직은 잘못된 명칭으로, 단순히 메모리에 저장해야 하는 해시 테이블의 잠재적인 크기를 줄이기 위한 속임수와 함께 완벽한 해시 함수를 생성하고 사용하는 것을 의미합니다. 즉, 8*2^64 또는 144 [nb 1]엑사바이트입니다.첫 번째 관찰은 외부 정사각형 또는 1위와 8위가 'a' 및 'h' 파일과 함께 공격 벡터의 점유와는 무관하다는 것입니다. 점유율에 관계없이 해당 정사각형을 공격하거나 공격하지 않기 때문에 6x6 또는 36 평방(비트)만 남겨둘 수 있습니다.s)를 참조해 주세요.완벽한 해시함수를 필요로 하는 다른 스킴과 마찬가지로 해시함수를 생성하기 위해서는 부분적으로 알고리즘적이고 부분적으로 시행착오를 포함한 완전한 열거처리가 필요하다.그러나 여전히 다루기 어려운 문제가 남아 있습니다. 즉, 이러한 테이블은 매우 활성적인 테이블이며, 최신 칩 아키텍처의 낮은 수준의 캐시 크기에 비해 그 크기(대부분의 경우 100만 항목 미만)가 크기 때문에 캐시 플래딩이 발생합니다.따라서 많은 애플리케이션의 매직 비트보드는 보다 가벼운 해시 방식이나 회전식 비트보드에 [6][7]비해 성능이 전혀 향상되지 않습니다.

역사

보드 게임을 나타내는 비트보드 방법은 아서 사무엘에 의해 1950년대 중반에 발명된 것으로 보이며 그의 [8]체커 프로그램에 사용되었다.좀 더 복잡한 체스 게임의 경우, 1960년대 [9]후반 소련의 카이사 팀과 1970년대 초반 미국 노스웨스턴 대학 프로그램 "체스"의 저자들에 의해 독립적으로 이 방법이 재발견된 것으로 보인다.Amdahl과 Cray 머신과 같은 1970년대 슈퍼 컴퓨터의 64비트 워드 길이는 체스 보드의 64제곱을 단어의 비트에 편리하게 매핑하는 비트보드 표현 개발을 촉진했다.

슬라이딩 피스의 움직임을 대조하기 위한 회전식 비트보드는 1990년대 중반 크레이 블리츠와 크래프트 체스 엔진의 저자인 로버트 하얏트 교수에 의해 발명되어 다크 씽크 프로그래밍 팀과 공유되었다.그것들은 나중에 Crafty와 Dark Think에서 구현되었지만, 1997년에야 처음으로 출판되었다.

10년 후 마스크된 순위, 파일 및 대각선을 사용하여 마스크된 비트의 점유 상태에 따라 공격 벡터 테이블을 인덱싱하는 직접 검색 방법이 도입되었습니다.해시 충돌을 제거하기 위해 완벽한 해시 함수를 사용하는 이러한 스킴 중 하나는 "매직 비트보드"라고 불렸다.그럼에도 불구하고 이러한 테이블의 큰 크기와 높은 액세스 속도는 메모리 점유율 및 캐시 경합 문제를 일으켰으며 회전식 비트보드 접근법보다 더 효율적이지는 않았습니다.오늘날 게임 프로그램은 여전히 분할된 상태로 있으며, 가장 좋은 방법은 애플리케이션에 의존하는 것입니다.

기타 게임

체스 외에도 많은 다른 게임들이 비트보드의 혜택을 받는다.

  • Connect Four에서는 방향당 2개의 시프트 + AND 조작만으로 4개의 디스크를 연속적으로 매우 효율적으로 테스트할 수 있습니다.
  • Conway의 Game of Life에서는 어레이를 대체할 수 있습니다.
  • Othello/Reversi(Reversi 기사 참조).

「 」를 참조해 주세요.

메모들

  1. ^ 이 방법을 구현하기 위해 완벽한 해시 함수를 사용할 필요는 없으며 표준 해시 방법에 비해 극히 적은 이점만 제공합니다.

레퍼런스

  1. ^ Atkin, Larry R.; Slate, David J. (1983) [1977]. "Chess 4.5: the Northwestern University Chess Program". In Frey, Peter W. (ed.). Chess Skill in Man and Machine (2 ed.). Springer Verlag. pp. 82–118. CiteSeerX 10.1.1.111.926. ISBN 0-387-90790-4.
  2. ^ Heinz, Ernst A. (September 1997). "How Dark Thought Plays Chess". ICCA Journal. 20 (3): 166–176.
  3. ^ Hyatt, Robert (1999). "Rotated Bitboards: New Twist on an Old Idea". Archived from the original on 2005-04-28.
  4. ^ Tannous, Sam (2007-07-23) [2006]. "Avoiding Rotated Bitboards with Direct Lookup". ICGA Journal (2 ed.). Durham, North Carolina, USA. 30 (2): 85–91. arXiv:0704.3773v2. CiteSeerX 10.1.1.561.3461. doi:10.3233/ICG-2007-30204.
  5. ^ Knuth, Donald (1973). "Section 6.4. Algorithm D (Open addressing with double hashing)". The Art of Computer Programming. Vol. 3.
  6. ^ Sherwin, Michael; Isenberg, Gerd (2006-12-04). "Magic Bitboards Explained!". Winboard Forum. Call it Kindergarten Bitboards
  7. ^ 를 클릭합니다Hansen, Lasse (2006-06-14). "Fast(er) bitboard move generator". Winboard Forum..
  8. ^ "Some Studies in Machine Learning Using the Game of Checkers". IBM Journal of Research and Development. 1959.
  9. ^ "Programming a computer to play chess". Russian Mathematical Surveys. 1970.

추가 정보

외부 링크

계산기

체커

체스

기사들

코드 예시

  • [1] Frenzee 엔진의 개발자는 몇 가지 소스 예를 게시했습니다.
  • [2] 비트보드 사용을 보여주는 155라인 Java Connect-4 프로그램.

실장

오픈 소스
  • 베어울프 유닉스, 리눅스, 윈도우즈.회전식 비트보드
  • 교활하다 교활하다 기사를 보라.스트레이트 C로 기재되어 있습니다.이전 버전의 회전식 비트보드가 이제 매직 비트보드를 사용합니다.
  • GNU 체스 GNU 체스 기사 참조.
  • Stockfish UCI 체스 엔진 2010년 엘로 2위
  • 회색 물질 C++, 회전 비트보드
  • 2300의 KnightCap GPL, ELO
  • 페피토 C비트보드, 카를로스 델 카초의 작품.Windows 및 Linux 바이너리 및 소스 사용 가능.
  • Simontacci 회전 비트보드.
폐쇄 소스

오셀로

  • C 및 어셈블리의 Othello 비트보드를 포함한 소스코드와 함께 Othello(Reversi) 엔진에 대해 자세히 설명합니다.
  • Edax (컴퓨팅)Edax 기사를 참조해 주세요.비트보드를 기반으로 소스 코드를 사용하는 Othello(Reversi) 엔진.

워드 게임