보드 표현(컴퓨터 체스)

이 기사는 에 관한 시리즈의 일부분이다.
체스 프로그래밍
이사회 표현 0x88 비트보드
평가 기능 심층 신경망 효율적으로 업데이트할 수 있는 신경 네트워크 수공예 평가 기능 조각-제곱 테이블 강화학습 확률적 경사 강하강 감독 학습 텍셀 튜닝 무감독 학습
그래프 및 트리 검색 알고리즘 미니맥스 알파베타 가지치기 주 변동 검색 정지 검색 몬테카를로 나무 수색
체스 컴퓨터 벨 체스머신 칩테스트 크레용 블리츠 딥 블루 딥씽크 하이테크 히드라 메피스토 사이텍
체스 엔진 알파제로 체스 타이거 교활한 쿠쿠체스 딥 프리츠 페어리 맥스 팻 프리츠 프리츠 과일 GNU 체스 히아릭스 후디니 이카루스 주니어 나이트캡 코모도 릴라 체스 제로 맥헤스 프로 무제로 나움 럽카 슈레더 쩡 시 스마씽크 스톡피시 투로샹 자파
v t

컴퓨터 체스에서 보드 표현은 체스판 위의 위치와 관련 게임 상태를 나타내는 체스 프로그램의 데이터 구조다.^[1]보드 표현은 이동 생성, 평가 기능, 만들기 및 언메이킹 동작(즉, 검색)을 포함한 체스 프로그램의 모든 측면에 기본적이며, 플레이 중 게임의 상태를 유지한다.몇몇 다른 이사회 대표들이 존재한다.체스 프로그램은 효율을 위해 서로 다른 시간에 둘 이상의 보드 표현을 사용한다.실행 효율성과 메모리 설치 공간은 보드 표현을 선택하는 데 있어 1차적인 요인이다. 이차적인 고려사항은 애플리케이션을 코드화하고 테스트하며 디버그하는 데 필요한 노력이다.

초기 프로그램에서는 두 어레이를 모두 기반으로 한 조각 목록과 사각형 목록을 사용했다.대부분의 현대적인 구현에서는 64비트 워드 또는 이중 워드의 비트를 보드의 사각형에 매핑하는 비트보드라고 불리는 더 정교하지만 더 효율적인 비트 어레이 접근방식을 사용한다.

보드 상태

체스 포지션, 즉 "상태"에 대한 전체 설명은 다음 요소를 포함해야 한다.

• 보드의 각 피스의 위치
• 누가 움직일 차례인가.
• 50 이동 그리기 규칙의 상태.선수 한 명당 50개씩 움직여서 100개의 하프무브, 즉 플라이가 되기 때문에 명칭이 다소 헷갈릴 때도 있다.예를 들어 이전의 80여 명의 하프무브들이 포획이나 졸개 이동 없이 통과했다면 50여 명의 반무브 후에 다시 50여 명의 룰이 발동하게 된다.
• 어느 한 선수가 영구적으로 성에 실격되는지, 킹사이드와 퀸사이드 둘 다.
• 통과 포획이 가능한 경우.

일반적으로 이사회의 표현은 3배 반복 추첨 규칙의 상태를 포함하지 않는다.이 규칙을 결정하려면 마지막 되돌릴 수 없는 조치(캡처, 전당 이동 또는 캐슬링)의 완전한 게임 이력을 유지해야 하므로 일반적으로 별도의 데이터 구조에서 추적된다.이 정보가 없다면, 모델은 승리 우위에도 불구하고 그 위치를 반복할 수 있고, 그로 인해 과도한 무승부가 초래될 수 있다.^[2]

보드 상태는 또한 사각형을 공격하는 조각, 조각을 포함하는 정사각형, 그 조각에 의해 공격되거나 보호되는 공간, 어떤 조각이 고정되는지, 그리고 기타 편리하거나 일시적인 상태와 같은 2차 파생 정보를 포함할 수 있다.

보드 상태는 게임 트리의 각 노드와 연관되어 있으며, 이동에 의해 도달된 위치를 나타내며, 그 이동이 보드를 통해 실행되었는지 또는 프로그램 검색의 일부로 생성되었는지 여부를 가리킨다.개념적으로 노드에 로컬이지만 전체적으로 정의될 수 있으며 트리가 통과할 때 노드 간에 점진적으로 업데이트될 수 있다.

종류들

배열 기반

조각 목록

극히 제한된 양의 메모리로 작업하는 초창기 체스 프로그램들 중 일부는 가장 크거나 작은 것 같은 편리한 검색 가능한 순서로 조각들의 일련 목록(array)을 유지했다. 각 조각과 관련된 것은 각 조각들의 법적 움직임을 나타내는 사각형과 같은 다른 정보뿐만 아니라 보드 위의 위치였다.리스트가 몇 개 있었는데, 하나는 흰 조각으로, 다른 하나는 검은 조각으로 설정되었다.명단은 보통 조각과 졸개로 나누어져 있었다.이것은 대부분의 사각형들이 비어있기 때문에 압축된 표현이었지만, 조각들의 서로 또는 서로에 대한 관계에 대한 정보를 얻는 것은 지루하기 때문에 비효율적이었다.조각 목록은 별도의 보드 표현 구조와 함께 오늘날 많은 프로그램에서 여전히 사용되고 있으며, 보드를 검색하지 않고도 조각에 직렬로 접근할 수 있다.

사각 리스트

보드를 나타내는 가장 간단한 방법 중 하나는 8x8 2차원 배열(또는 동등하게 64요소 1차원 배열)을 만드는 것이다.각 배열 요소는 주어진 정사각형을 어떤 조각이 차지하고 있는지, 또는 정사각형이 비어 있는지 여부를 식별한다.일반적인 인코딩은 0을 비어 있고, 백색처럼 양성이며, 흑색처럼 음성으로 간주하는 것이다. 예: 백색 전당 +1, 흑색 전당 -1, 백색 기사 +2, 백색 주교 +3 등.이 계획을 우편함 주소 지정이라고 한다.

이 접근방식의 문제는 이동 생성 중에 발생한다.각 움직임을 점검해 보드에 올라있는지 확인해야 하기 때문에 과정이 상당히 느려진다.한 가지 해결책은 12x12 어레이를 대신 사용하는 것인데, 외측 가장자리는 예를 들어 값 99로 채워진다.이동 생성 중에 목적지 사각형의 피스를 확인하는 작업에서도 목적지 사각형이 보드에서 떨어져 있는지 여부를 알 수 있다.^[1][3]

10x12 어레이로 더 나은 메모리 사용을 달성할 수 있으며, 이 어레이는 최좌측 및 최우측 에지 파일(기판 밖으로 표시됨)을 겹쳐서 12x12와 동일한 기능을 제공한다.^[1][3]일부 체스 엔진은 16x16 배열을 사용하여 순위 및 파일 번호 변환 속도를 개선하고 공격 등에 대한 몇 가지 특별한 코딩 기술을 허용한다.

0x88 방법

0x88 방법은 체스판의 8x8 치수가 2의 짝수 힘(즉, 8 제곱)이라는 점을 활용한다.이 보드는 64 크기의 배열이 아니라 0에서 127까지 번호가 매겨진 16x8 = 128 크기의 1차원 배열을 사용한다.기본적으로 서로 옆에 있는 두 개의 판인데, 왼쪽 판은 실제 판이고 오른쪽 판은 불법 영역을 포함하고 있다.배열 내의 법정 보드 좌표의 순위 및 파일에 대한 이진 레이아웃은 (r's는 순위를 나타내기 위해 사용되는 3비트 입니다.f는 파일에 대한 것이다.예를 들어 0x71(이진수 )은 제곱 b8(대수 표기법)을 나타낸다.메인보드에서 이동을 생성할 때 단순히 16진수 0x88(이진수)으로 사각형 번호를 AND로 배열하기 전에 목적지 사각형이 메인보드에 있는지 확인할 수 있다.0이 아닌 결과는 정사각형이 메인보드에서 떨어져 있음을 나타낸다.또한 두 제곱의 좌표의 차이는 두 제곱이 동일한 행, 열 또는 대각선(체크를 결정하는 데 사용되는 공통 질의)을 따라 있는지 여부를 고유하게 결정한다.^[1][4]

비트보드

배열 기반 구조보다 효율적이지만 정교한 보드 표현이 비트보드다.비트보드란 비트의 64비트 시퀀스(0 또는 1)로, 보드 위에 있는 각 공간의 일부 상태(거짓 또는 참)의 부재나 존재(거짓 또는 참)를 나타낸다.보드 위치는 일련의 비트보드를 사용하여 나타낼 수 있다.예를 들어, 각 측면에 대해 각 피스 유형에 대한 일련의 비트보드는 보드 위치를 나타낼 수 있다.

이 표현에 대한 장점은 이사회의 상태에 대한 정보를 조정하고 도출하기 위해 반복하는 대신 64비트 실체에 비트 병렬 연산을 사용할 수 있다는 것이다.이것은 특히 64비트 프로세서가 주류가 되면서 하드웨어를 최대한 사용할 수 있게 한다.

비트보드의 실질적인 장점은 보드의 각 공간에 있는 각 유형의 피스페이스에 의해 공격된 공간에 대한 맵을 미리 압축하여 테이블에 저장할 수 있도록 하여, 프리가 점유한 공간을 제외하고 피스톨이 위치한 사각형의 공격 맵에 대한 단일 메모리 픽업으로 피스의 가능한 움직임을 검색할 수 있다는 것이다.최종 조각(한 비트씩 작동)은 조각의 합법적인 움직임을 산출한다.그러나 미닫이 조각(루크, 주교, 여왕)의 움직임은 보드의 다른 조각들의 구성에 따라 달라지기 때문에 확실하지 않다.그래서 그들의 움직임을 나타내기 위해 특별하고 복잡한 데이터 구조가 고안되었다.

회전 비트보드

회전 비트보드(Rotated Bitboard)는 비트보드의 회전된 복사본을 사용하여 파일이나 대각선으로 순위를 나타내는 비트와 유사한 인접 비트에 공간(비트)을 배치하는 슬라이딩 피스의 이동 생성 기법이다.이 비트는 추출하여 표에 인덱스로 사용하여 이 조각들이 공격한 공간의 지도를 얻을 수 있다.비트보드는 파일 인덱싱을 위해 90° 회전하고 대각선 인덱싱을 위해 45° 또는 -45° 회전한다.체스보드를 회전하는 것은 개념적으로 어려운 일이며 비트보드를 회전시키는 것은 계산상 비지니스적이지만, 변환은 피스의 움직임을 연속적으로 열거하거나, 보드 구성을 고려하기 위해 피스의 공격 맵의 비트보드를 이동 및 마스킹하는 긴 시퀀스를 피한다.

직접 조회

슬라이딩 피스의 마스크된 순위, 파일, 대각선 등을 해시함수를 통해 마스킹 부분의 점유 비트를 기반으로 사전 계산된 공격 벡터 테이블을 직접 인덱싱할 수 있다.메모리에 저장해야 하는 테이블의 잠재적 크기를 최소화하기 위해 트릭과 함께 완벽한 해시함수를 사용하는 그러한 계략 중 하나를 "매직 비트보드"라고 한다.

전치표

전이 테이블은 컴퓨터 게임 플레이 프로그램에 의해 생성된 게임 트리에서 이전에 본 위치 및 관련 평가의 캐시다.테이블의 빠른 검색을 위해 조브리스트 해싱과 같은 해시 함수를 사용하여 일치하는 보드를 신속하게 찾을 수 있다.^[5]

기타 방법

CCR(Compact Chessboard Presentation, CCR)과 같은 다른 방법들이 제안되었지만,^{[citation needed]} 어느 것도 받아들여지지 않았다.

CCR은 사각형당 4비트를 사용하여 정사각형의 점유율을 나타내고,^{[Notes 1]} 전체 순위를 32비트로 나타낼 수 있으며, 보드는 8개의 레지스터(남은 위치 정보를 위해 1개 추가)로 표시할 수 있다.사각형의 점유 코드는 레지스터에서 전화를 걸어 프로그램 카운터에 추가하여 점프 테이블을 인덱싱할 수 있으며, 이 사각형의 피스 유형에 대한 이동을 생성하기 위해 코드(있는 경우)에 직접 분기할 수 있다.프로그램은 기존 이동 생성 방식보다 길지만 보드 가장자리 점검이 필요 없고, 보드 이탈이 불가능해 이동 생성 속도가 빨라진다.

CCR의 단점은 1) 32비트 워드 크기에 대한 의존성, 2) API에 대한 최소 9개의 무료 레지스터의 가용성, 3) 레지스터에 접근하기 위한 CICS 아키텍처의 어셈블리 프로그래밍 필요성, 4) 어셈블리 애플리케이션의 비포트성이다.

메모들

참조