미니맥스

미니맥스는 게임을 가능성의 트리로 표현한다. 각 가지는 하나의 수이고, 각 단계에서는 두는 쪽이 번갈아 바뀐다. 포지션을 분석하고 수를 선택하는 프로그램인 체스 엔진은 자신의 선택을 살핀 뒤 상대의 가장 강한 응수를 고려한다. 중심 가정은 신중하다. 상대가 실수할 것이라고 기대하지 않는다.

엔진이 두는 단계에서는 알고리즘이 가장 유리한 결과를 남긴다. 상대가 두는 단계에서는 상대가 최선으로 저항한다고 가정하므로 엔진에 가장 불리한 결과를 남긴다. 그런 다음 미래 포지션의 값을 현재 포지션까지 거꾸로 전달한다. 이로써 각 시작 수가 최선의 수비를 상대로 보장할 수 있는 결과를 비교할 수 있다.

실전 탐색은 게임 전체를 거의 살필 수 없다. 깊이 한계에 도달하면 어느 쪽이 더 좋은지를 추정하는 공식인 평가 함수를 사용한다. 따라서 깊이가 제한된 미니맥스 선택은 절대적인 증명이 아니다. 탐색한 거리와 추정의 정확도에 따라 달라진다. 중요한 결과가 중단점 바로 너머에 놓이는 지평선 효과의 영향도 받을 수 있다.

엔진은 유망한 선택을 먼저 살펴 관련 없는 가지를 더 일찍 버릴 수 있게 하는 수 순서화 같은 기법으로 이 틀을 효율화한다. 몬테카를로 트리 탐색을 포함한 다른 시스템은 계산 노력을 다르게 배분하지만, 가장 신뢰할 만한 수를 찾는다는 같은 실전 목표를 추구한다.