전치표

Transposition table

전이 테이블은 컴퓨터 게임 플레이 프로그램에 의해 생성된 게임 트리에서 이전에 본 위치 및 관련 평가의 캐시다.다른 이동 순서를 통해 위치가 반복되면 해당 위치 아래의 게임 트리를 다시 검색하지 않도록 테이블에서 위치 값을 검색한다.전이 테이블은 (게임의 전체 상태를 항상 모든 플레이어가 알 수 있는) 완벽한 정보 게임에서 주로 유용하다.전이 테이블의 사용은 본질적으로 트리 검색에 적용되는 메모화로서 동적 프로그래밍의 한 형태다.

전이 테이블은 일반적으로 현재 보드 위치를 해시 인덱스로 인코딩하는 해시 테이블로 구현된다.게임 트리에서 발생할 수 있는 가능한 위치의 수는 검색 깊이의 지수 함수로, 수천에서 수백만 또는 훨씬 더 클 수 있다.따라서 전환 테이블은 사용 가능한 시스템 메모리의 대부분을 소비할 수 있으며 대개 게임 실행 프로그램의 메모리 설치 공간의 대부분이다.

기능

게임 플레이 프로그램은 게임의 다음 몇 번의 움직임에서 발생할 수 있는 수백만 개의 위치를 분석함으로써 작동한다.전형적으로, 이 프로그램들은 깊이 우선 검색을 닮은 전략을 채택하고 있는데, 이것은 그들이 지금까지 분석된 모든 위치를 추적하지 못한다는 것을 의미한다.많은 게임에서, 한 가지 이상의 방법으로 주어진 위치에 도달하는 것이 가능하다.이것을 전이라고 한다.[1]예를 들어 체스에서 이동 순서는 어느 한 선수가 이동 순서를 바꿀 수 있기 때문에 1. d4 Nf6 2. c4 g6 (대수 체스 표기법 참조)는 4개의 전이가 가능하다.일반적으로 n이 이동한 후 가능한 전이 상한은 (n!)2이다.이들 중 상당수는 불법 이동 시퀀스지만 결국 같은 위치를 여러 차례 분석하는 것으로 끝날 가능성이 높다.

이 문제를 피하기 위해, 전환 테이블을 사용한다.그러한 표는 지금까지 분석된 각각의 위치를 일정한 깊이까지 해시 표로 나타낸 것이다.새로운 직책에 직면했을 때, 프로그램은 그 직책이 이미 분석되었는지 확인하기 위해 표를 체크한다. 이것은 상각된 일정한 시간에 신속하게 할 수 있다.만일 그렇다면, 표에는 이전에 이 위치에 할당한 값이 포함되어 있다. 이 값은 직접 사용된다.그렇지 않으면 값을 계산하고 해시 테이블에 새 위치를 입력한다.

컴퓨터에 의해 검색된 위치의 수는 종종 그것이 실행되는 시스템의 메모리 제한을 크게 초과한다. 따라서 모든 위치가 저장될 수 있는 것은 아니다.테이블이 가득 차면 사용량이 적은 위치가 제거되어 새로운 위치를 위한 공간을 만든다. 이는 배치 테이블을 일종의 캐쉬로 만든다.

전위 테이블 조회를 통해 절약되는 연산은 단순히 단일 위치의 평가만이 아니다.대신에 전체 하위 트리에 대한 평가는 피한다.따라서 게임 트리의 얕은 깊이에 있는 노드에 대한 대체 테이블 항목은 더 가치 있고(이러한 노드에 뿌리를 둔 하위 트리의 크기가 더 크기 때문에) 따라서 테이블이 채워지고 일부 항목은 폐기해야 할 때 더 중요성이 부여된다.

전이표를 구현하는 해시 테이블은 전이를 찾는 것 외에 다른 용도를 가질 수 있다.알파-베타 가지치기에서는 최상의 이동에 해당하는 노드의 자식을 항상 먼저 고려할 때 검색이 가장 빠름(사실, 최적)이다.물론 사전에 최선의 움직임을 알 수 있는 방법은 없지만, 반복적인 심층화를 사용할 때 얕은 곳 검색에서 최고로 판명된 움직임은 좋은 근사치가 된다.그러므로 이 조치가 먼저 시도된다.노드의 가장 좋은 하위 항목을 저장하기 위해, 전환 테이블의 해당 노드에 해당하는 항목이 사용된다.

그래프와 역사 상호작용 문제를 연구적으로 피하지 않을 경우, 전환 표를 사용하면 잘못된 결과를 초래할 수 있다.이 문제는 특정 경기에서 발생한다. 왜냐하면 포지션의 역사가 중요할 수 있기 때문이다.예를 들어, 체스에서, 체스에서는, 주물러질 왕이나 루크가 게임 도중에 움직인다면, 플레이어는 성을 쌓지 않을 수 있다.이 문제에 대한 일반적인 해결책은 조브리스트 해싱 키의 일부로 캐슬링 권한을 추가하는 것이다.또 다른 예는 반복에 의한 추첨이다: 위치에 따라, 이미 발생했는지 여부를 판단할 수 없을 수도 있다.일반적인 문제에 대한 해결책은 전환표의 각 노드에 이력 정보를 저장하는 것이지만, 이것은 비효율적이고 실제로 거의 수행되지 않는다.

교체 전략

전이 테이블은 사용 가능한 시스템 메모리에 의해 최대 크기가 제한되는 캐시로, 언제든지 오버플로우할 수 있다.실제로 오버플로우가 예상되며, 언제든지 캐시 가능한 포지션의 수는 게임 트리의 노드 수보다 작은 일부(규모가 작은 순서도 포함)에 지나지 않을 수 있다.대부분의 노드는 전치 노드가 아니므로, 즉 재발할 위치가 아니므로, 잠재적인 전치 노드를 유지하고 다른 노드를 대체하는 효과적인 교체 전략은 트리 크기를 현저히 감소시킬 수 있다.대체는 대개 나무 깊이와 노화를 기반으로 한다. 나무에서 더 높은 노드(뿌리에 더 가까운 노드)가 선호된다. 그 아래 하위 트리가 더 크고 더 큰 절감 효과를 낳기 때문이다. 그리고 더 최근의 노드는 더 오래된 노드가 더 이상 현재 위치와 비슷하지 않기 때문에 노드 전환 가능성이 더 낮기 때문이다.

다른 전략은 주요 변동에 있는 노드, 트리의 깊이에 관계 없이 하위 트리가 큰 노드, 컷오프를 발생시킨 노드 등을 유지하는 것이다.

크기 및 성능

전이가 될 노드의 분율은 작지만, 게임 트리는 기하급수적인 구조여서, 그러한 노드의 극히 적은 수를 캐시하는 것은 상당한 차이를 만들 수 있다.체스에서는 복잡한 중간 게임 포지션에서 0~50%의 검색 시간 단축, 최종 게임에서 최대 5배까지 검색 시간이 단축된 것으로 보고됐다.[2]

관련 기법

  • 포지션의 특정 특징에 대한 평가를 캐싱하기 위해 유사한 기법을 사용할 수 있다.예를 들어, 폰 해시 테이블을 사용하여 폰 구조에 대한 평가를 위치에 저장할 수 있다.일반적으로 조사된 폰 포지션 수가 검색된 총 포지션 수보다 훨씬 적기 때문에, 폰 해시 테이블은 적중률이 매우 높아 프로그램이 여러 번 재사용되기 때문에 정교한 폰 평가에 더 많은 시간을 할애할 수 있다.
  • refutation table은 루트 노드에서 리프 노드로의 이동 순서를 저장하는 데 사용될 수 있다.여기에는 주요 변동과 열등하다는 것을 보여주는 다른 라인에 대한 반응이 포함된다.기억력이 더 제한되었던 컴퓨터 체스의 초기에는 테이블의 위치를 바꾸는 대신 리퓨테이션 테이블이 사용되기도 했다.일부 현대 체스 프로그램에서는 이동 순서를 위한 전환 테이블 외에 리퓨테이션 테이블을 사용한다.
  • 보드의 각 공간에 있는 각 유형의 조각의 가능한 움직임의 정적 비트맵은 프로그램 초기화에 캐시될 수 있으므로, 조각의 법적 움직임(또는 이동 생성을 위한 모든 법적 움직임)을 연속적으로 열거할 필요 없이 단일 메모리 로드로 검색할 수 있다.이것들은 일반적으로 비트보드 구현에 사용된다.

참고 항목

참고 및 참조

  1. ^ Transplosition Tables, Gamedev.net, Francois-Dominic Laramee.
  2. ^ 1977년 앳킨, L. 앤 슬레이트, D., "Chess 4.5, 노스웨스턴 대학교 체스 프로그램", Chess in Man and Machine, Peter W.프레이, 에드뉴욕 주 뉴욕 스프링거-베를라크

외부 링크