몬테카를로 트리 탐색

몬테카를로 트리 탐색은 MCTS로 줄여 쓰며, 모든 변형을 같은 깊이까지 살피려 하지 않는다. 트리를 점차 확장하고 누적된 결과를 이용해 다음 계산을 어디에 투입할지 정한다. 많이 방문한 수가 자동으로 좋은 수인 것은 아니지만, 그 추정에는 보통 더 많은 탐색 근거가 쌓여 있다.

한 번의 MCTS 순환

1. 선택: 시작 포지션에서 출발해 기존 가지를 따라가며, 이미 강해 보이는 수와 아직 불확실한 수 사이의 균형을 맞춘다.
2. 확장: 트리가 아직 전개하지 않은 포지션이나 수를 추가한다.
3. 평가: 새 포지션에서의 결과를 추정한다. 고전적 방법은 모의 게임을 끝까지 진행할 수 있고, 현대 시스템은 패턴을 인식하도록 학습된 모델인 신경망으로 포지션을 평가할 수도 있다.
4. 역전파: 방문한 경로를 따라 결과를 되돌려 보내며 방문 횟수와 추정값을 갱신한다.

이 순환을 반복하면 활용과 탐색 사이의 균형이 만들어진다. 활용은 이미 근거가 좋은 곳에 더 많은 노력을 쓰는 것이고, 탐색은 놀라운 대안을 너무 일찍 버리지 않도록 불확실한 선택을 시험하는 것이다. 둘의 정확한 균형 규칙은 구현에 따라 다르다.

미니맥스와 달리 MCTS는 흔히 균일한 깊이만이 아니라 탐색 중 모은 근거에 따라 한 가지를 얼마나 조사할지 결정한다. 신경망 기반의 일부 체스 프로그램에서는 네트워크가 가능성 높은 수를 제안하는 정책과 결과를 추정하는 가치를 제공한다. 가치는 평가 함수와 관련된 역할을 하지만 전체 탐색 과정은 다르다.