컴퓨터 체스 용어 목록

아래는 컴퓨터 체스에 사용되는 용어 목록이다.

일반적인 체스 용어는 체스 용어 목록을 참조하라.
체스 문제에 사용되는 용어는 체스 문제 용어 목록을 참조하라.

알고리즘: algorithm. 작업을 수행하기 위해 정확하게 정의된 단계별 절차. 알고리즘을 참조하라.
알파: alpha. 미니맥스 탐색 알고리즘에서, 지금까지 평가된 변화에 따라 움직이는 쪽이 달성할 수 있는 최소값.
알파-베타 가지치기: alpha–beta pruning. 미니맥스 알고리즘에서 탐색되는 노드의 수를 줄이는 알고리즘. 이 개선은 체스와 같은 큰 게임 트리를 탐색하는 것을 실용적으로 만드는 데 필수적이다. 알파-베타 가지치기를 참조하라.
배열: array. 숫자 색인으로 항목을 빠르게 검색할 수 있는 컴퓨터 메모리에 저장된 목록.
인공지능
AI: artificial intelligence. 컴퓨터에서 인간 수준의 사고를 재현하거나 모방하는 것을 다루는 컴퓨터 과학 분야. 게임 플레이는 AI 연구의 초기 영역이었다. 인공지능을 참조하라.
기대 윈도우: aspiration window. 알파-베타 가지치기의 개선으로, 일반적으로 경험을 바탕으로 좁은 윈도우만 고려하여 탐색 속도를 더욱 높인다. 제로 윈도우 탐색, 널 윈도우 탐색, 네가스카우트 탐색은 알파와 베타가 같은 값으로 설정되는 극한의 경우에 대한 이름이다. 기대 윈도우를 참조하라.
베타: beta. 미니맥스 탐색 알고리즘에서, 지금까지 평가된 변화를 기반으로 움직이는 쪽이 달성할 수 있는 최대값.
비트: bit. 이진 숫자, 0 또는 1. 컴퓨터가 저장하거나 조작할 수 있는 가장 작은 정보 조각.
비트보드: bit board. 64비트 배열로, 각 비트는 체스판의 한 칸을 나타낸다. 여러 비트보드가 사용되며, 각 보드는 특정 기물이 차지하는 모든 칸 또는 공격받는 모든 칸과 같은 특정 특성을 기록한다.
분기 요소: branching factor. 탐색 트리의 각 수준에서 고려해야 할 가능성의 수.
무차별 대입: brute force. 우아한 알고리즘보다는 빠른 컴퓨터 하드웨어에 의존하는 문제 해결 접근 방식.
후보 수: candidate move. 초기 포지션 관찰 단계에서 추가 분석 가치가 있는 것으로 선택된 수. 최적의 수가 먼저 고려되도록 후보 수 목록이 제대로 정렬되면 알파-베타 알고리즘이 더 효율적일 수 있다. 후보 수를 참조하라.
잡기 탐색: capture search. 각 측이 만들 수 있는 잡기만 고려하여 터미널 노드에서 계속되는 탐색 알고리즘의 확장.
가지치기: cutoff. 탐색 트리의 한 분기를 탐색할 필요 없이 제거하는 것. 이것은 알파-베타 알고리즘의 가지치기 동작이다.
평가 함수: evaluation function. 포지션의 유리함을 평가하는 데 사용되는 알고리즘. 대부분의 체스 포지션은 정확한 값(승리, 패배 또는 무승부)을 할당할 수 없으므로, 이는 말 균형, 공간 우위, 기물 이동성, 폰 구조, 킹 안전 등과 같은 요소를 기반으로 한 휴리스틱 수치이다. 대부분의 평가 함수는 주어진 위치에서 백이 가진 우위를 나타내는 폰 및 폰의 부분으로 된 숫자 값을 반환한다. 0은 위치가 균형 잡혀 있음을 나타내고, 음수 값은 흑이 앞서 있다고 판단됨을 나타낸다. 평가 함수을 참조하라.
전폭 탐색: full width search. 게임 트리의 모든 분기를 탐색하는 탐색. 체스의 높은 분기 요소로 인해, 보드에 기물이 거의 남아 있지 않아 가능한 위치가 크게 줄어든 경우를 제외하고는 전폭 탐색은 일반적으로 실용적이지 않다.
게임 트리: game tree. 주어진 위치에서 모든 합법적인 수로부터 발생할 수 있는 모든 가능한 위치.
휴리스틱: heuristic. 문제의 정확한 해결 방법이 알려지지 않았거나 비실용적일 때 사용되는, 최적 또는 정확하다고 보장되지 않는 문제 해결 방법. 휴리스틱은 컴퓨터 체스에서 위치를 평가하고 탐색 알고리즘을 안내하는 데 사용될 수 있다.
지평선 효과: horizon effect. 대부분의 포지션에서 탐색 알고리즘이 게임의 결론까지 탐색하는 것이 비실용적이라는 결과. 컴퓨터는 최대 탐색 깊이보다 한 수 더 멀리까지 결과를 볼 수 없기 때문에 나쁜 수를 둘 수 있다. 지평선 효과는 컴퓨터 체스 초기에 주요 문제였지만, 현대 체스 엔진은 복잡한 포지션에서도 여러 수 깊이까지 탐색할 수 있으므로 오늘날에는 덜 문제가 된다. 지평선 효과를 참조하라.
반복적 심화 탐색: iterative deepening. 처음에는 N 플라이 깊이까지 탐색한 다음, 해당 탐색 결과를 사용하여 후보 수의 순서를 변경하여 N + 1 플라이 깊이까지 탐색을 수행하는 탐색 알고리즘. 반복적 깊이심화 탐색을 참조하라.
킬러 휴리스틱: killer heuristic. 동일한 깊이에서 게임 트리의 다른 분기에서 탐색 가지치기를 유발한 수(킬러 수)가 현재 위치에서도 가지치기를 유발할 수 있다는 가정. 이것은 알파-베타 가지치기를 더 효과적으로 만들 수 있다. 킬러 휴리스틱을 참조하라.
미니맥스 알고리즘: minimax algorithm. 게임 트리를 탐색하는 데 사용되는 기본 알고리즘. 게임 트리의 각 수준에서 움직이는 플레이어는 상대방의 가능한 응답 중 어떤 것이든 결과적으로 얻을 수 있는 최소 이점을 최대화하는 가능성을 선택한다. 미니맥스 알고리즘을 참조하라.
수 생성기: move generator. 특정 위치에서 고려할 수의 목록을 생성하는 모듈. 이것은 일반적으로 체스 엔진 소프트웨어의 일부이지만, 일부 체스 컴퓨터는 하드웨어에서 수 생성을 수행했다.
오프닝 북: opening book. 게임 시작부터 체스 오프닝에서 두어야 할 수의 데이터베이스. 이 수는 컴퓨터 저장소에서 직접 선택할 수 있으므로 탐색이 필요하지 않다.
플라이: ply. 백 또는 흑의 한 수, 즉 반수. 한 풀 무브는 두 플라이이다. 플라이를 참조하라.
주 바리에이션: principal variation. 최적 또는 정확한 진행 라인. 각 플레이어가 최적의 수를 선택한다고 가정할 때 현재 플레이어에게 가장 유리한 변화.
가지제거: pruning. 게임 트리의 가지를 탐색하지 않고 제거하는 것.
준허용수: pseudo-legal. 체크에 노출되는 것을 제외한 모든 기준에 따라 합법적인 수에 대한 용어. 벨과 같은 하드웨어 수 생성기는 준합법적인 수를 생성한다. 이 수들은 움직이는 쪽이 체크에 놓이지 않도록 테스트되어야 한다.^[1]
침묵 탐색: quiescence search. 탐색 알고리즘의 확장으로, 일반적으로 탐색의 가장 깊은 부분(터미널 노드)을 넘어 분기를 계속 탐색하여 잡을 수 있는 기물이 없고 어느 킹도 체크 상태가 아닌 침묵 위치에 도달할 때까지 계속된다. 이 기술은 지평선 효과의 위험을 최소화하는 데 사용될 수 있다.
반격수: refutation. 이전에 고려 중이던 수가 나쁠 것임을 보여주는 수.
탐색 깊이: search depth. 게임 트리가 탐색되는 플라이 수.
선택적 탐색: selective search. 게임 트리의 각 수준에서 일부 가능성만 확인하는 탐색. 전폭 탐색과 대조된다.
섀넌 수: Shannon number. 체스의 게임 트리 복잡성에 대한 추정된 하한. 1950년에 클로드 섀넌은 체스 시작 위치에서 약 10¹²⁰개의 변화가 있다고 추정했다.
터미널 노드
터미널 위치: terminal node/terminal position. 게임 트리의 특정 분기에서 탐색의 가장 깊은 부분. 평가 함수는 터미널 노드에 적용되어 해당 분기에 값을 할당한다.
전환 테이블: transposition table. 탐색의 이전 부분에서 발견된 위치 및 그 평가에 대한 기록. 전환 테이블은 위치의 값을 다른 수의 순서로 다시 도달했을 때 다시 계산할 필요 없이 조회할 수 있도록 하여 계산을 절약한다. 전환 테이블을 참조하라.
유형-A 전략: type-A strategy. 무차별 대입, 탐색 트리의 각 수준에서 가능한 모든 합법적인 수를 고려하는 전폭 탐색. 1949년 클로드 섀넌이 만든 용어. 유형-B 전략과 대조된다.
유형-B 전략: type-B strategy. 선택적 탐색, 특정 라인을 다른 라인보다 더 깊이 고려하는 것. 1949년 클로드 섀넌이 만든 용어. 유형-A 전략과 대조된다.
변형: variation. 특정 수열로, 현재 위치에 도달하기 위해 두어진 수보다는 게임의 미래 가능성을 설명하는 데 자주 사용된다. 변형을 참조하라.
윈도우: window. 알파-베타 탐색 알고리즘에서 알파와 베타의 차이. 탐색이 진행될수록 윈도우는 작아진다. 기대 탐색에서는 윈도우가 좁은 값으로 설정된다. 가장 극단적인 경우인 제로 윈도우 탐색은 널 윈도우 탐색 또는 스카우트 탐색이라고도 불린다.

각주

↑ Frey 1983 p. 203.

참고 문헌

Levy, David; Newborn, Monty (1991), 《How Computers Play Chess》, Computer Science, ISBN 0-7167-8239-1
Welsh, David (1984), 《Computer Chess》, Wm. C. Brown, ISBN 0-697-09900-8
Condon, Joseph H.; Thompson, Ken (1983). 〈Chapter 9: Belle〉. Frey, Peter W. (편집). 《Chess Skill in Man and Machine》. New York: Springer-Verlag. 201–210쪽. ISBN 978-0-387-90815-1.

[1] Frey 1983 p. 203.

[1]