- Monte-Carlo Graph Search(MCGS) 는 여러 수순이 같은 상태로 전이되는 게임에서, MCTS를 트리 대신 방향 그래프에 적용해 중복 탐색을 공유하려는 접근임
- 기존 MCTS의 방문 횟수 N과 평균 가치 Q를 그대로 DAG에 옮기면, 공유 자식의 방문 수가 부모의 정책·가치 추정과 어긋나 알고리듬이 불건전해질 수 있음
- MCTS를 정규화된 정책 최적화로 보면, PUCT가 만든 액션별 방문 분포는 사후 정책이고 Q는 그 정책의 기대 효용으로 해석됨
- 올바른 MCGS는 자식 노드 방문 수와 별도로 엣지 방문 수 N(n,a) 를 추적하고, Q를
U(n)과 자식 Q의 가중합으로 재계산해 그래프에서도 정책과 가치의 의미를 유지함
- 실제 구현에는 stale Q, 증분 업데이트, 전이된 자식에서 playout을 계속할지, 해시 충돌과 게임 내 사이클 처리 같은 선택지가 남아 있으며 KataGo는 현재 멱등적 업데이트를 사용함
트리 탐색이 놓치는 전이 상태
- 게임 트리 탐색에서는 서로 다른 수순이 같은 상태로 전이(transposition) 되는 일이 있음
- 체스에서
1. d4 d5 2. Nf3와 1. Nf3 d5 2. d4는 같은 포지션에 도달함
- 전이가 가능한 게임은 탐색 깊이가 깊어질수록 중복 상태가 지수적으로 늘 수 있어, 같은 상태의 계산을 공유하는 편이 바람직함
- 일반적인 MCTS 구현은 게임을 분기 트리로 취급해 같은 포지션의 여러 인스턴스를 다시 탐색함
- 반복 포지션에 대한 신경망 평가 캐싱 같은 저수준 최적화는 비용을 줄일 수 있음
- 하지만 한 인스턴스에서 중요한 전술을 발견해 평가가 고쳐져도 다른 인스턴스로 전파되지 않는 문제가 남음
- 상태 공간을 방향 비순환 그래프(DAG) 로 모델링하면, 여러 경로가 같은 상태에 도달할 때 그 상태를 하나의 노드로 표현할 수 있음
- 실제 사이클이 있는 게임의 처리는 대부분 제외하고, DAG에서 MCTS가 어떻게 작동해야 하는지에 초점을 맞춤
표준 MCTS: 실행 통계를 쌓는 트리
- 표준 MCTS는 탐색한 게임 일부를 메모리의 노드 트리로 저장함
- 각 노드는 보통 다음 값을 추적함
N: 지금까지 이 노드를 지나거나 이 노드에서 끝난 playout 수Q: 해당 playout들이 샘플한 효용 값의 실행 평균
- 한 번의 playout은 다음 순서로 진행됨
- 루트에서 시작해 탐험 공식에 따라 다음 액션을 선택하며 내려감
- 아직 탐색하지 않은 상태에 도달하면 새 노드를 추가함
- 새 상태의 효용
U를 얻음. 예시는 신경망의 value head 질의임
- 트리를 거슬러 올라가며 각 노드의
N을 증가시키고 Q 평균을 갱신함
- AlphaZero 스타일 MCTS에서는 액션 선택에 PUCT 공식을 사용함
N(a): 액션 a가 시도된 횟수이며, 트리에서는 그 액션이 가리키는 자식 노드의 N과 같음Q(a): 액션 a의 평균 효용이며, 자식 노드의 Q와 같음PlayerToMove: 현재 플레이어가 최대화하는지 최소화하는지를 반영함P(a): 신경망 정책 예측 같은 사전 확률c_PUCT: 조정 가능한 상수
- “PUCT”는 예측 사전분포를 쓰는 Predictor UCT/UCB 계열에서 왔으며, AlphaZero 변형은 원래 형태와 함수 꼴이 다름
- 현대 MCTS는 신경망 평가를 쓰면 결정론적일 수 있지만, 이름의 “Monte-Carlo”는 과거 무작위 rollout을 끝까지 수행해 효용을 추정하던 방식에서 왔음
- 턴의 계산 예산이 끝날 때까지 playout을 반복한 뒤, 루트에서
Q가 아니라 방문 수 N이 가장 큰 자식을 최종 액션으로 선택함
- 높은
Q와 낮은 N을 가진 자식은 얕은 탐색에서 노이즈로 높게 나온 실수일 수 있음
- 루트의 방문 분포
N(a) / ΣN(b)는 AlphaZero 학습 루프에서 정책 학습 목표로 쓰일 수 있음
DAG에 순진하게 적용하면 생기는 문제
- 트리 MCTS 코드를 거의 그대로 두고, 새 게임 상태가 이미
nodes_by_hash에 있으면 기존 노드를 가리키게 만들 수 있음
- 이 방식은 자식 노드 방문 수가 부모에서 선택한 액션 방문 수와 같다는 트리의 가정을 유지하지 못함
- 예시 상황
- 노드 A가 노드 C로 가는 액션을 선호하고, A의
Q가 대부분 C를 탐색한 약 30회 playout에 의해 결정돼 있음
- C는 다른 전이 경로에서도 약 40회 방문됨
- 이후 C가 다른 전이 경로에서 더 많이 방문되며 깊은 곳의 전술이 발견되어 C의 효용 추정이
0.39 → 0.51로 상승함
- C를 갱신한 playout이 A를 지나지 않았기 때문에, A의
Q는 C의 새 평가를 반영하지 못함
- 이후 A가 다시 playout을 받더라도 PUCT는 방문 수가 많은 C 대신 방문 수가 적은 다른 액션을 탐험할 수 있음
- C가 “이미 충분히 탐색된” 것처럼 보이기 때문임
- 그 결과 A의
Q가 오히려 낮아질 수 있음
- 순진한 그래프 확장은 전이 경로가 상위 선호 수를 많이 방문할수록 부모가 다른 수를 더 탐색하게 만들어, playout 평균에 인위적 편향을 만들 수 있음
- 무한 탐색에서도 최적 수로 수렴하는지 명확하지 않을 정도로 불건전한 알고리듬이 됨
모든 부모를 갱신해도 해결되지 않음
- 한 노드가 어떤 playout으로 갱신될 때, 그 playout이 실제 지나온 부모뿐 아니라 모든 부모와 조상에 반영하는 방식도 생각할 수 있음
- 이 방식은 앞선 A-C 사례에서는 A의 효용을 함께 갱신할 수 있음
- 하지만 다른 예시에서는 부모 D가 스스로는 선호하지 않는 전이 자식 F의 많은 방문 때문에 오염됨
- D의 최선 자식 E는
Q = 0.56이고, D의 Q = 0.55는 이에 부합함
- D는 F를 한 번만 탐색했지만, F는 다른 경로에서 이미 9회 방문되어 총 10회 방문 상태임
- 이후 F가 다른 경로에서 100회 더 방문되고 낮은 효용을 유지하면, 모든 부모 갱신 방식은 D의
Q를 0.35까지 끌어내릴 수 있음
- D 입장에서는 F에 그렇게 많은 playout을 배정하고 싶지 않았으므로, 모든 부모 갱신도 정책 의미를 깨뜨리는 방식임
MCTS를 정책 최적화로 보기
π가 최대화하는 값:
Σ π(a) Q(a) - λ_N D_KL(P || π)
- 구성 요소의 의미
Σ π(a) Q(a): 정책 π를 따를 때의 추정 기대 효용D_KL(P || π): 사전 정책 P와 사후 정책 π의 차이를 재는 역방향 KL 발산λ_N: KL 항의 강도를 정하는 계수이며 방문 수가 늘수록 감소함
- 방문 분포는 신경망의 사전 정책
P를 출발점으로 삼아, 더 많은 방문으로 액션 효용 근거가 쌓일수록 개선되는 사후 정책으로 볼 수 있음
- 따라서 MCTS는 트리의 각 노드에서 작은 온라인 정책 학습을 동시에 수행하는 알고리듬으로 해석됨
- 이 관점은 방문 분포가 강한 에이전트의 정책처럼 보이고, AlphaZero에서 정책 학습 목표로 쓰이는 이유를 설명함
- 최적화 문제의 정확한 해를 계산해 정책으로 쓰는 방법도 가능하지만, 실제로는 방문이 적고 우연히
Q가 높아 보이는 수에 큰 가중치를 줄 수 있음
- 방문 분포를 사후 정책으로 쓰면, 어떤 수가 높은 가중치를 얻으려면 실제로 많이 탐색되어야 하므로 더 견고함
Q의 재해석: playout 평균에서 정책 기대값으로
- 표준 정의에서 노드
n의 Q(n)은 n을 방문한 playout들의 효용 평균임
Q(n) = (1 / N(n)) Σ U(p)
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
- 여기서
U(n)은 노드 n 자체의 원시 신경망 효용 추정이고, N(c) Q(c)는 자식별 방문 수로 가중한 자식 가치임
- 따라서
Q는 자식 Q들의 방문 분포 가중 평균으로 해석할 수 있음
- 방문 분포가 MCTS가 최적화하는 사후 정책이라면,
Q(n)은 그 사후 정책을 따를 때의 정규화된 기대 효용임
- 이 해석에서는 각 노드가 자식들이 보고하는
Q를 최대화하도록 정책을 계속 최적화하고, 자신의 Q를 그 정책으로 달성 가능한 기대 효용의 최신 추정치로 갱신함
- 자식 노드의
Q가 게임이론적 최적값으로 수렴하면, 부모의 정책과 Q도 재귀적으로 최적값에 수렴함
올바른 MCGS: 엣지 방문과 자식 방문 분리
- 그래프에서 생기는 문제는 부모의 자식 방문이 오직 그 부모를 통해서만 발생한다고 가정하기 때문에 발생함
- 전이 경로가 있으면 자식 노드 방문 수가 PUCT가 해당 부모에서 배정하려던 방문 수와 임의로 달라질 수 있음
- 해결책은 PUCT가 특정 노드에서 선택한 액션의 누적 횟수를 별도로 추적하는 것임
- 각 노드
n은 다음 값을 추적함
N(n): 이 노드가 방문된 총 횟수N(n,a): 노드 n에서 PUCT가 액션 a를 선택한 횟수, 즉 엣지 방문 수Q(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
- 여기서
Q(n,a)는 액션 a를 두어 도달한 자식 노드 c의 Q(c)와 같음
- PUCT 계산에서도 자식 방문 수가 아니라 엣지 방문 수를 사용함
argmax_a PlayerToMove(n) * Q(n,a)
+ c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
- 기본 알고리듬은 playout 경로의 액션을 선택하고, 전이된 상태가 이미 있으면 기존 노드를 연결하며, 되돌아오며 엣지 방문 수를 증가시킨 뒤
N과 Q를 자식 값의 함수로 재계산함
- 이 방식은 Czech, Korus, Kersting의 Monte-Carlo Graph Search for AlphaZero와 고수준에서 유사하지만, 실행 통계가 아니라 정책 최적화 관점에서 도출됨
구현 선택지: stale Q와 갱신 방식
- 제시된 의사코드는 playout이 실제 지나간 경로의 노드만 갱신함
- 이 때문에 지나가지 않은 경로의 노드
Q는 stale Q가 될 수 있음
- 그래도 이론적으로는 건전함
- PUCT 같은 표준 탐험 공식은 한계에서 모든 액션을 무한히 시도함
- 노드가 다시 방문되면 그 시점의 자식
Q와 엣지 방문 수를 사용해 올바른 Q를 직접 계산함
- DAG에서는 한계적으로 게임이론적 최적값에 수렴할 수 있음
- stale Q는 탐색 효율을 낮출 수 있음
- 즉시 부모 포인터를 유지해 부모 Q도 갱신할 수 있음
- 모든 조상을 위상 정렬 순서로 갱신해 stale 상태를 없앨 수 있음
- playout 경로만 갱신하면서 별도 병렬 스레드가 stale 노드를 찾아 갱신하게 할 수 있음
- 의사코드는 멱등적 업데이트를 사용함
- 이전에 어떤 중간 갱신이 있었든, 노드를 한 번 방문하면 자식들의 현재 값에 대한
N과 Q가 맞게 됨
- 증분 업데이트도 가능하지만, 그래프에서는 동등하거나 한계적으로 동등하게 만들기가 더 까다로움
- Czech 등은 실행 통계 관점에서 접근했기 때문에 더 증분적인 공식을 사용함
- 엣지 방문 수뿐 아니라 엣지의 Q도 저장함
- stale Q가 최신 값으로 점진적으로 따라잡는 메커니즘과 오차 허용 하이퍼파라미터를 둠
- 제시된 의사코드는 새 오차 허용 파라미터나 엣지 Q 저장 없이도 MCGS를 작동시킬 수 있음을 보임
- KataGo는 현재 멱등적 공식을 사용함
전이된 자식에서 playout을 계속할지
- 트리 MCTS에서는 엣지 방문 증가와 자식 방문 증가가 같은 사건임
- 그래프에서는 전이 때문에 자식 노드가 해당 엣지보다 이미 더 많이 방문되어 있을 수 있음
- 이때 자식 노드가 이미 충분히 방문됐다고 보고 playout을 중단하고, 엣지 방문만 증가시킨 뒤 부모와 조상을 갱신할 수 있음
- 중단을 선호하는 이유
- 엣지 방문이 낮고 자식 방문이 높다면, 해당 자식에 추가 방문을 주는 한계 정보량이 작을 수 있음
- 계속을 선호하는 이유
- 자식 방문이 엣지 방문보다 큰 노드는 여러 부모가 전이해 오는 노드일 가능성이 높고, 더 많은 부모에 영향을 주므로 정확한 평가가 중요할 수 있음
- 이 선택은 실험 영역으로 남아 있음
- 자식 방문 수가 엣지 방문 수보다 충분히 클 때만 중단하는 임계값 방식도 가능함
- KataGo는 기본적으로 playout을 중단하지만, 계속하거나 확률적으로 일부만 중단하는 설정 옵션을 제공함
- 의사코드는 playout을 중단하지 않으며, 필요하면
child.N <= edge_visits 조건으로 한 줄 체크를 추가할 수 있음
해시, 종료 노드, 실제 게임 사이클
- 게임 종료 노드는 의사코드에서 방문 횟수와 관계없이
N = 1, U = Q = 게임 결과 효용으로 다시 계산됨
- 부모의 해당 엣지 방문 수는 정상적으로 증가하므로 이 방식도 가능함
- 게임 결과가 확률적이고 기대 효용을 직접 계산할 수 없다면, 종료 노드 방문마다
N을 증가시키고 샘플된 결과를 평균내는 방식이 중요할 수 있음
- 게임 종료 효용을 더 넓게 처리해 증명 가능한 값을 그래프 위로 더 빨리 전파하는 것도 가능함
- 일반 MCTS/MCGS는 확실한 효용 값을 인식하는 장치가 없기 때문에, 종료 상태가 중요할 때 alpha-beta 같은 고전 탐색만큼 싸게 최적값에 수렴하지 않음
- 전이를 찾기 위해 게임 상태의 고유 해시를 가정함
- 복잡한 게임 상태에 대해 진짜 충돌 없는 해시를 만드는 것은 까다롭고 비용이 클 수 있음
- 128비트나 192비트의 충분히 큰 Zobrist hash는 적대적으로 만든 상태가 아니라면 실무에서 충돌을 사실상 막기에 보통 충분함
- 해시 충돌로 사이클이 생겼을 때 무한 재귀를 피하려면 사이클 감지를 추가할 수 있음
- 바둑의 superko, 체스의 3회 반복처럼 실제 게임 규칙에서 생기는 사이클 처리는 자세히 다루지 않음
- 2024-03-10 부록은 반복과 사이클 처리에 대한 더 거친 생각을 담은 Google Docs 링크를 제공하며, 게임별 휴리스틱 실험이 필요할 수 있음
- KataGo의 바둑 처리에서는 특정 수 이후 원래 포지션으로 돌아가려면 적어도
S + E - 1수가 필요하다는 바둑 특화 정리를 활용해, 사이클 관련 상황에서 노드 공유를 안정적으로 제한함