4단계를 그림으로

4단계를 트리 그림으로 차례차례 따라가보자. 트리 노드는 게임 상태 + 통계 (visits/wins).

🌳 트리의 초기 상태

처음에는 루트(현재 보드)만 있고, 자식은 없음. 모든 노드의 visits=0, wins=0.

루트의 자식들 중 UCB1 최대인 자식 선택. 그 자식의 자식들 중 또 UCB1 최대 자식 선택. 리프 노드(자식이 없거나 미확장)에 도달할 때까지 반복.

예시

루트의 자식 A (visits 30, wins 18) vs B (visits 20, wins 10). UCB1 계산해서 더 큰 자식으로 내려감. 그 자식의 자식들 중에서 또 UCB1 비교.

처음 iteration에서는 루트가 곧 리프이므로 즉시 ②로 감.

리프 노드의 가능한 수 중 아직 자식이 없는 수 하나를 골라 자식으로 추가. 보통 무작위로 (또는 정해진 순서로). 새 자식 노드의 visits=0, wins=0으로 초기화.

예시

리프 노드의 가능한 수가 9개. 이미 7개 자식이 있으면 남은 2개 중 1개를 무작위로 골라 자식으로 추가. 게임이 끝났으면 ② 생략.

새로 추가된 자식 노드에서 rollout 한 번. 양쪽이 무작위로 끝까지 두고 결과 반환 (X 승 = 1, draw = 0.5, O 승 = 0 등 게임에 맞게).

방금 받은 보상을 새 자식부터 루트까지의 모든 경로 노드의 visits, wins 갱신. 위로 거슬러 올라가며.

💡 핵심 — 보상의 방향

Backup할 때 주의: 각 노드의 차례(MAX/MIN)에 따라 보상이 다른 의미. X에게 +1이 좋은 거지만, O 노드 입장에서는 -1로 봐야. 보통 "현재 차례 입장에서의 승률"로 통일.

그래서 boost 누적할 때 노드의 turn에 따라 보상을 뒤집어 누적. minimax의 MAX/MIN 분리와 같은 원리.

이 4단계가 끝나면 다시 ①부터 반복. N번 후 종료.

🌳 N번 후 트리의 모습

유망한 수(높은 UCB1)는 select에서 자주 뽑혀서 그 아래로 자식이 많이 생기고 더 깊이 들어감. 별로인 수는 위쪽에 머무름. 결과적으로 트리가 "유망한 가지 쪽으로 비대칭으로 자라남".

이게 minimax와 결정적 차이. minimax는 모든 가지를 같은 깊이로 봄. MCTS는 좋은 가지에만 깊이 들어감 — 한정된 시간을 똑똑하게 사용.

다음 페이지에서 노드 클래스부터 코드로.