기초 원리에서 출발한 몬테카를로 그래프 탐색

 (github.com/lightvector)
3P by GN⁺ | ★ favorite | 댓글 1개
  • 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수가 필요하다는 바둑 특화 정리를 활용해, 사이클 관련 상황에서 노드 공유를 안정적으로 제한함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 이런 그래프 탐색이 AI 추론을 발전시키는 데 필요하다고 봄. 단순 LLM만으로는 실패할 가능성이 큼
    링크에는 게임 테이블용 Zobrist 해싱 https://en.wikipedia.org/wiki/Zobrist_hashing을 포함해 좋은 참고자료가 많음
    그래프 탐색의 계산량이 폭발하지 않도록, 언어 기반 상태 설명에 맞는 좋은 해싱을 찾아야 함
    트리 탐색 관련해서는 Thinking Fast and Slow: https://arxiv.org/abs/1705.08439와, MCTS 접근을 현재의 다른 강화학습 전략과 비교한 Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642도 읽어볼 만함

    • 이건 너무 저수준으로 보임
      한 단계 나아가려면 상태 표현과 탐색 알고리즘을 함께 학습하는 방식이 될 수 있음. 탐색 알고리즘이 비용을 얻을 수 있는 신경망의 상태 표현 위를 탐색하는 식임
      https://sites.google.com/view/genie-2024/
      DeepMind의 Genie는 이산 상태를 모델링하는 좋은 예시임. 신경망이 충돌 판정과 행동을 포함한 매우 복잡한 표현을 학습함. 그 상태를 픽셀로 디코딩하는 대신, 아마 그 상태 위에서 직접 탐색할 수 있을 것임
      물론 이 구조는 실제로는 꽤 다를 수 있음
    • 지나치게 단순화했지만 탐구해볼 만한 접근은 이렇다고 봄
      논리적 논증 모음을 놓고 각 논증에 해시를 부여하는 방법을 찾고, 그 논증 해시들을 제1원리에 따라 중첩한 Merkle 트리로 표현함
      어떤 논증이 성공적으로 반박되면 그 논증의 해시가 바뀌고, 하위 논증들의 해시도 무효가 됨
    • 둘을 어떻게든 결합하는 게 불가능할까 싶음. 뇌가 모든 일에 단 하나의 기법만 쓴다고 보기는 어렵고, 여러 도구와 그 위에서 어떤 도구를 언제 쓸지 고르는 선택기가 있을 가능성이 높아 보임

  • HN URL에서 저자를 보고 바로 KataGo를 만든 천재라고 알아봄: https://github.com/lightvector/KataGo
    https://www.reddit.com/r/cbaduk/에 올리는 글들도 꾸준히 훌륭함

    • URL이 말 그대로 KataGo 저장소 안에 있음

  • 체스 경험이 아주 많지는 않지만, 탐색 트리 안에서 같은 포지션이 중요할 만큼 자주 중복된다는 주장에는 회의적임. Leela Zero로 실제 측정값을 보고 싶음
    삼중 반복과 50수 규칙까지 상태에 포함하면 반복 가능성은 훨씬 낮아질 텐데, 그 부분은 고려하지 않은 상태에서도 그렇다고 봄

    • 바둑에서는 패가 매우 흔함. 판 위치를 그대로 반복하는 것은 둘 수 없지만, 트리 탐색이 패 위치를 제대로 평가하지 못하면 AI가 나쁜 수를 두는 상황을 쉽게 만들 수 있음

  • “Monte-Carlo Tree Search”라는 이름과 달리 위 알고리즘에는 몬테카를로가 전혀 없고 완전히 결정적이라는 대목이 이상함. 보통 구현되는 MCTS가 결정적이라니, 표본추출에 무작위성이 있는 줄 알았음

    • 원래 MCTS에는 무작위성이 있었음. 글에서도 언급하는 것 같은데, 마지막에 위치를 평가하기 위해 플레이아웃을 수행하는 형태였음
      현재의 비슷한 프로젝트들에서는 이것이 더 품질 좋은 신경망 평가로 대체됨. 무작위 수를 둬서 누가 이기는지 보는 방식은 별로 좋지 않지만, 당시 알려진 최선의 전략이었음
      결국 몬테카를로 부분은 지금도 MCTS라고 불리는 것의 본질적 요소가 아니었고 오히려 차선이었음. 그래서 이름이 조금 불행해짐
    • 엄밀히는 같은 “monte carlo” 이름 아래 있는 다른 알고리즘임
      흥미로운 점은 대부분의 몬테카를로 방법이 진짜 난수 생성기가 아니라 의사난수 생성기에 의존하므로, 같은 시드와 입력이 주어지면 항상 같은 결과가 나오는 결정적 방식이라는 것임
      이 알고리즘은 일반적인 의사난수 생성기와 별도 휴리스틱을 쓰는 대신 신경망에 질의함. 신경망은 거대한 탐색 공간 위의 휴리스틱이라, 학습에 따라 특정 결과 쪽으로 강하게 치우친 매우 나쁜 의사난수 생성기처럼 작동하고, 결과적으로 휴리스틱이 적용된 의사난수 생성기처럼 보이게 됨
      중요한 점은 이것이 MCTS의 특수화라서, 기술적으로 모든 사용 사례에 맞지는 않는다는 것임
    • 무작위성이 있다면 수렴은 되는지, 그리고 어느 정도의 자원-시간이 필요한지 궁금함. CPU, RAM, GPU, TPU, QPU 기준으로도 달라질 수 있음

  • MCTS를 조사할 때 글에서 언급한 논문이 완전히 레이더 밖에 있었음. 다음 기회에 이 수정 방식을 직접 돌려보면 꽤 재미있을 것 같음

  • 간단한 소개가 있으면 좋겠음

    • 게임 플레이 AI를 만들 때, 넓게 비유하면 모든 AI가 그렇지만, 가장 유망한 기법 중 하나가 트리 탐색임. 후속 수들을 바탕으로 현재 수의 순위를 매기는 방식임
      같은 상태에 여러 경로로 도달할 수 있는 게임에서는, 서로 다른 가지에 같은 상태 노드를 반복 기록하느라 메모리를 많이 낭비할 수 있음
      이 글은 그래프 탐색이라는 접근을 잘 살펴봄. 본질적으로는 게임 상태를 해싱하는 추가 계산을 해서 이미 방문한 노드인지 확인하고, 그 대가로 메모리를 아끼는 방식임
      이미 본 노드를 다시 기록하지 않아도 되므로, 순환이 없는 트리가 방향 비순환 그래프로 바뀜
      이 때문에 올바른 결과를 얻으려면 트리 탐색을 조금 손봐야 함. 특히 최적화 단위를 정점, 즉 상태가 아니라 간선, 즉 행동이나 수에 더 맞춰야 함
      주제를 잘 이해한 사람이 쓴, 문학적 프로그래밍 스타일의 잘 쓰인 기술 에세이임
답변달기