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

(github.com/lightvector)

몬테카를로 그래프 탐색의 기본 원리

몬테카를로 트리 탐색(MCTS)은 트리 대신 방향 그래프에 적용되는 "몬테카를로 그래프 탐색"("MCGS")으로, 때때로 구현하기 까다로운 것으로 여겨짐.
기존 학술 참고문헌은 트리에 대한 MCTS의 "표준" 설명을 따르기 때문에 그래프로 일반화하는 것을 개념적으로 이해하기 어려움.
이 문서는 더 직관적이라고 여겨지는, 본질적으로 동등하지만 더 깔끔한 설명을 제시하고, 그래프 탐색이 왜 이런 방식으로 작동해야 하는지 기본 원리에서 유도함.

게임 트리 탐색이나 다른 트리 탐색 응용에서는 같은 상태로 이어지는 여러 가능한 움직임이나 행동의 시퀀스를 찾을 수 있음.
예를 들어, 체스에서 1. d4 d5 2. Nf3은 1. Nf3 d5 2. d4와 같은 위치로 이어짐.
게임에서 이러한 상황이 가능할 때, 탐색 깊이와 함께 가능한 경우의 수가 기하급수적으로 증가하여 깊은 탐색을 필요 이상으로 비용이 많이 들게 만듦.
이상적으로는 이러한 탐색의 분기들이 계산을 공유하도록 하고 싶음.
그러나 표준 MCTS 구현은 게임을 분기 트리로 취급하고 트리 내의 중복된 위치를 비효율적으로 재탐색함.

MCTS는 트리의 노드를 통과하는 플레이아웃의 실행 통계를 추적하는 알고리즘으로 종종 설명됨.
각 노드는 게임의 단일 상태를 나타내며, 방문 횟수(N)와 플레이아웃에 의해 샘플링된 유틸리티 값의 실행 평균(Q)을 추적함.
MCTS의 단일 반복 또는 플레이아웃은 트리를 따라 내려가면서 탐색할 다음 행동을 샘플링하고, 새로운 상태에 도달하면 트리를 확장하며, 새로운 상태의 유틸리티 U를 추정하고, 트리를 다시 올라가면서 각 노드에서 N을 증가시키고 샘플링된 새로운 유틸리티 U로 평균 Q를 업데이트하는 과정으로 구성됨.

위 알고리즘을 트리 대신 방향 비순환 그래프에 그대로 적용하면, 알고리즘이 부정확해질 수 있음.
이는 MCTS가 멀티암드 밴딧 기반 방법의 확장으로서 플레이아웃의 실행 통계 측면에서 일반적으로 설명되기 때문임.
Czech, Korus, Kersting은 이러한 문제를 해결하고 사운드 알고리즘에 도달했지만, 온라인 정책 학습 관점에서 MCTS를 접근하는 대안적인 방법이 있음.
이 대안적인 설명에서는 그래프로의 일반화가 상대적으로 자연스럽게 나타남.

그래프로 MCTS를 확장할 때 발생하는 모든 문제는 부모 노드로부터의 자식 노드 방문만을 가정하는 데서 비롯됨.
이론은 PUCT가 선택한 누적 행동 횟수가 최적화된 정책 π를 근사하는 사후 정책을 제공한다는 것을 보장하므로, 이를 추적해야 함.
노드가 보고하는 Q 값이 사후 정책의 예상 가치라는 해석을 사용하면, 개별 플레이아웃을 어떻게 계산할지에 대해 다루지 않고도 재귀적 Q 공식을 적용할 수 있음.

이 문서에서 제시된 알고리즘은 Czech, Korus, Kersting의 알고리즘과 매우 유사하지만, 몇 가지 구현 선택과 몇 가지 사소한 차이가 있음.
Q 값의 "오래됨"을 줄이기 위한 전략이나 점진적 대신 동일한 업데이트를 사용하는 것과 같은 구현의 단순성을 위해 선택할 수 있는 여러 가지 방법이 있음.

이 기사는 몬테카를로 그래프 탐색(MCGS)의 복잡성과 그것을 이해하기 위한 새로운 접근법을 제시함으로써 인공지능과 게임 이론 분야에 관심 있는 사람들에게 흥미를 끌 수 있음.
MCTS와 같은 알고리즘은 체스나 바둑과 같은 복잡한 전략 게임에서 중요한 역할을 하며, 이러한 게임의 인공지능 개발에 기여함.
그러나 이 기사에서 다루는 내용은 초급 소프트웨어 엔지니어에게는 다소 어려울 수 있으며, 이론적인 배경 지식이 필요함.
MCGS를 구현할 때 고려해야 할 사항으로는 알고리즘의 효율성과 정확성을 어떻게 균형잡을 것인가가 있으며, 이는 실제 게임 환경에서의 성능에 큰 영향을 미칠 수 있음.
비슷한 기능을 제공하는 다른 프로젝트나 제품으로는 DeepMind의 AlphaZero가 있으며, 이는 체스, 바둑, 쇼기에서 인간 최고수를 능가하는 수준에 도달했음.

그래프 탐색은 인공지능의 추론 발전에 필요한 것으로, 단순한 LLMS는 실패할 것임. 링크에는 게임 테이블용 Zobrist 해싱을 포함한 많은 좋은 참고자료가 있음. 언어 기반 상태 설명을 위한 좋은 해싱을 찾아야 그래프 탐색이 계산적으로 폭발하지 않음. 트리 검색에 대한 좋은 읽을거리로는 'Thinking Fast and Slow'와 'Teaching Large Language Models to Reason with Reinforcement Learning'이 있으며, 이들은 MCTS 접근법을 다른 현재의 RL 전략들과 비교함.
HN URL에서 바로 KataGo의 천재 개발자를 인식함. 그의 Reddit의 cbaduk 게시물들은 일관되게 훌륭함.
"Monte-Carlo Tree Search"라는 이름에 대해, 언급된 알고리즘에는 "Monte-Carlo"가 없으며 완전히 결정론적이라는 점을 독자들이 알아차려야 함. MCTS가 일반적으로 결정론적으로 구현된다는 것은 이상함. 샘플링에 무작위성이 있다고 가정했음.
언급된 논문은 MCTS를 연구할 때 내 레이더에서 완전히 벗어났음. 다음 기회에 이 수정을 시도하는 것이 매우 재미있을 것임.

배경 지식:

LLMS: 이 컨텍스트에서 LLMS는 특정한 기술을 지칭하는 것이 아니라, 일반적인 기계 학습 시스템을 의미할 수 있음.
Zobrist 해싱: 게임 상태를 효율적으로 해싱하기 위한 기술로, 특히 보드 게임에서 많이 사용됨.
MCTS (Monte-Carlo Tree Search): 무작위 샘플링을 통해 최적의 결정을 내리는 알고리즘으로, 보통 게임과 같은 결정 과정에서 사용됨.
Reinforcement Learning (RL): 시행착오를 통해 학습하는 기계 학습의 한 분야로, 보상 시스템을 통해 최적의 행동 전략을 학습함.