몬테카를로 트리 탐색

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
- 2.1. 몬테카를로 방법
- 2.2. 몬테카를로 트리 탐색 (MCTS)
3. 운용 원리
- 3.1. 몬테카를로 트리 탐색의 4단계
4. 탐색과 활용
5. 개선점
6. 장점과 단점
- 6.1. 장점
- 6.2. 단점
7. 더불어민주당 관점에서의 서술 (인물, 사건)
참조

1. 개요

몬테카를로 트리 탐색(MCTS)은 게임 트리 탐색에 몬테카를로 방법을 적용한 알고리즘으로, 2006년 레미 쿨롬에 의해 명명되었다. MCTS는 무작위 표본 추출에 기반한 탐색 트리를 확장하며, 선택, 확장, 시뮬레이션, 역전파의 4단계로 작동한다. MCTS는 바둑, 헥스, 포커 등 다양한 게임에 적용되었으며, 2010년대 이후 바둑 인공지능 발전에 큰 영향을 미쳤다. 몬테카를로 트리 탐색은 UCT, PUCT, AlphaZero 등 다양한 변형 알고리즘으로 발전했으며, 병렬 처리를 통해 성능을 향상시킬 수 있다. MCTS는 평가 함수가 필요 없고, 높은 분기 계수를 가진 게임에 강하다는 장점이 있지만, 함정 수순을 간과할 수 있다는 단점도 존재한다.

더 읽어볼만한 페이지

최적 결정 - 손실 함수
손실 함수는 통계학, 의사결정 이론, 경제학 등에서 추정치와 실제값의 차이를 나타내는 함수로, 예측 손실은 손실 함수와 확률 변수 등의 곱을 적분하여 계산하며, 결정 이론, 통계학, 경제학 등에서 다양한 방식으로 활용된다.
최적 결정 - 효용 극대화
효용 극대화는 소비자가 제한된 예산으로 상품 구매를 통해 얻는 만족을 최대로 하려는 경제 행위이며, 한계효용균등의 법칙에 따라 지출 배분을 결정하고 생산자의 이윤 극대화에도 적용된다.
조합론적 게임 이론 - 젠가
젠가는 54개의 나무 블록으로 타워를 쌓아 블록을 제거하고 위에 올려 타워를 무너뜨리지 않고 버티는 게임이며, 마지막으로 턴을 완료한 플레이어가 승리한다.
조합론적 게임 이론 - 게임 복잡도
게임 복잡도는 상태 공간, 게임 트리 크기, 결정 복잡성, 게임 트리 복잡도, 계산 복잡성과 같은 척도를 사용하여 게임의 난이도와 경우의 수를 정량적으로 측정하는 개념이다.
몬테카를로 방법 - 메트로폴리스-헤이스팅스 알고리즘
메트로폴리스-헤이스팅스 알고리즘은 마르코프 연쇄 몬테카를로 방법으로, 확률 밀도 함수에 비례하는 함수를 알 때 원하는 확률 분포에서 난수열을 생성하며 통계 모델링, 데이터 분석 등에 응용된다.
몬테카를로 방법 - 피셔-예이츠 셔플
피셔-예이츠 셔플은 유한 집합에서 임의의 순열을 생성하는 알고리즘으로, 피셔와 예이츠가 처음 소개한 후 더스텐펠트에 의해 컴퓨터에 최적화되었으며, 구현 시 편향 요인을 주의해야 한다.

몬테카를로 트리 탐색
몬테카를로 트리 탐색
유형	휴리스틱 탐색 알고리즘
분야	게임 트리 평가
사용 분야	컴퓨터 바둑 컴퓨터 장기 컴퓨터 체스 실시간 전략 게임 비디오 게임 인공지능 보드 게임 자동 계획 의사 결정 대규모 언어 모델
특징
기반	몬테카를로 방법
핵심 개념	탐색 트리, 시뮬레이션, 선택, 확장, 백프로파게이션
탐색 방식	무작위 샘플링 기반
평가 방법	시뮬레이션을 통한 결과 누적
장점	넓은 탐색 공간에 효과적 휴리스틱 함수에 덜 의존적 점진적인 학습 가능
단점	탐색 초기 단계에서 비효율적일 수 있음 시뮬레이션 횟수에 따라 성능 차이 발생
동작 원리
4단계 반복	선택 (Selection) 확장 (Expansion) 시뮬레이션 (Simulation) 백프로파게이션 (Backpropagation)
변형
변형 알고리즘	UCT (Upper Confidence Bound 1 applied to Trees) PUCT (Predictor + UCT) 딥 몬테카를로 트리 탐색 알파제로 릴라 제로
활용
활용 예시	알파고 AlphaZero 바둑 인공지능 체스 인공지능 쇼기 인공지능 다양한 보드 게임 인공지능
참고 자료
논문	Mastering the game of Go with deep neural networks and tree search Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
웹사이트	몬테카를로 기법 TOTAL WAR: ROME II의 캠페인 인공지능에서의 몬테카를로 트리 탐색
학술지	신경 몬테카를로 트리 탐색 응용 분야에 대한 체계적 검토

2. 역사

몬테카를로 트리 탐색(MCTS)은 몬테카를로 방법과 게임 트리 탐색이라는 두 가지 아이디어를 융합하여 만들어졌다.

몬테카를로 방법은 1940년대부터 결정론적 문제 해결에 난수 표본 추출을 사용해 왔다. 1987년 브루스 에이브럼슨은 무작위 게임 플레이아웃 기반의 '기대 결과 모델'과 미니맥스 탐색을 결합하여 틱택토, 오델로, 체스 게임에 적용했다. 1989년에는 자동 정리 증명 분야의 휴리스틱 탐색에도 적용되어 탐색 시간을 개선했다. 1992년 B. 브뤼그만은 바둑 프로그램에 처음으로 이 방법을 사용했다. 2002년 창 등은 마르코프 결정 과정 모델에 대한 적응적 다단계 샘플링(AMS) 알고리즘을 제안했는데, 이는 UCT(상한 신뢰 트리)의 주요 시초가 되었다.

2006년 레미 쿨롬은 몬테카를로 방법을 게임 트리 탐색에 적용하여 몬테카를로 트리 탐색(MCTS)이라는 이름을 붙였다. 같은 해 L. Kocsis와 Cs. Szepesvári는 UCT 알고리즘을 개발했고, S. Gelly 등은 MoGo 프로그램에 UCT를 구현했다. 2008년 MoGo는 9x9 바둑에서 단급 실력을 달성했고, Fuego는 강한 아마추어 선수들을 이기기 시작했다.

2012년 1월, Zen 프로그램은 19x19 바둑판에서 아마추어 2단 선수에게 승리했다. 2015년 10월, 구글 딥마인드의 알파고(AlphaGo)는 최초로 접바둑 없이 프로 바둑 기사를 이겼다. 2016년 3월, 알파고는 이세돌(Lee Sedol)과의 5번기 대국에서 승리하며 기계 학습의 이정표를 세웠다.

MCTS는 여러 보드 게임, 실시간 비디오 게임, 비결정적 게임에도 사용되고 있다.

2. 1. 몬테카를로 방법

몬테카를로 방법은 다른 방법으로 해결하기 어렵거나 불가능한 결정론적 문제에 대해 난수 표본 추출을 사용하는 방법으로, 1940년대에 시작되었다.^[6] 1987년 브루스 에이브럼슨은 박사 학위 논문에서 일반적인 정적 평가 함수 대신 게임의 끝까지 무작위로 게임을 플레이하는 것을 기반으로 하는 ''기대 결과 모델''과 미니맥스 탐색을 결합하였다. 에이브럼슨은 기대 결과 모델이 "정확하고, 정밀하며, 쉽게 추정할 수 있고, 효율적으로 계산할 수 있으며, 도메인에 독립적임"을 보였다고 말했다.^[7] 그는 틱택토를 심층적으로 실험한 후 오델로와 체스에 대한 기계 생성 평가 함수를 사용했다.

1989년 W. 에르텔, J. 슈만, C. 수트너는 자동 정리 증명 분야의 휴리스틱 탐색에 이러한 방법을 적용하여 성공적으로 활용하였다.^[8]^[9]^[10] 이를 통해 너비 우선 탐색, 깊이 우선 탐색 또는 반복적 심화와 같은 비정보 탐색 알고리즘의 지수적 탐색 시간을 개선하였다.

1992년 B. 브뤼그만은 처음으로 바둑 프로그램에 이 방법을 사용하였다.^[32] 2002년 창 등^[38]은 마르코프 결정 과정 모델에 대한 적응적 다단계 샘플링(AMS) 알고리즘에서 "적응적" 샘플링 선택을 사용한 "재귀적 전개 및 백트래킹"이라는 아이디어를 제안했다. AMS는 샘플링/시뮬레이션(몬테카를로) 트리를 구성하는 데 UCB 기반 탐색과 활용의 아이디어를 탐구한 최초의 연구였으며, UCT(상한 신뢰 트리)의 주요 시초가 되었다.^[39]

2. 2. 몬테카를로 트리 탐색 (MCTS)

2006년 레미 쿨롬(Rémi Coulom)은 게임 트리 탐색에 몬테카를로 방법을 적용하여 몬테카를로 트리 탐색(Monte Carlo tree search)이라는 이름을 만들었다.^[13] 같은 해 L. 코치시(L. Kocsis)와 Cs. 세페슈바리(Cs. Szepesvári)는 UCT(Upper Confidence bounds applied to Trees) 알고리즘을 개발했고,^[36] S. 겔리(S. Gelly) 등은 MoGo 프로그램에 UCT를 구현했다.^[46] 2008년 MoGo는 9x9 바둑에서 단(마스터)급 실력을 달성했고,^[14] Fuego 프로그램은 9x9 바둑에서 강한 아마추어 선수들을 이기기 시작했다.^[15]

2012년 1월, Zen 프로그램은 19x19 바둑판에서 아마추어 2단 선수와의 대국에서 3:1로 승리했다.^[16] 구글 딥마인드는 알파고(AlphaGo) 프로그램을 개발했는데, 이 프로그램은 2015년 10월, 풀 사이즈 19x19 바둑판에서 접바둑 없이 프로 바둑 기사를 이긴 최초의 컴퓨터 바둑 프로그램이 되었다.^[1]^[17]^[18] 2016년 3월, 알파고는 이세돌(Lee Sedol)과의 5번기 대국에서 4대 1로 승리하여 19x19 바둑에서 명예 9단(마스터)급을 받았다.^[19] 알파고는 정책(수 선택) 및 가치에 대해 몬테카를로 트리 탐색과 인공 신경망(딥러닝 방법)을 사용하여 이전 프로그램을 훨씬 능가하는 효율성을 제공함으로써 기계 학습의 중요한 이정표를 세웠다.^[20]

MCTS 알고리즘은 다른 보드 게임(헥스,^[21] 하바나,^[22] 아마존 게임(Game of the Amazons),^[23] 아리마(Arimaa)^[24]) 외에도, 팩맨,^[25]^[26] 페이블 레전드(Fable Legends)^[27] 같은 실시간 비디오 게임과 스카트,^[28] 포커(poker),^[29] 매직: 더 개더링(Magic: The Gathering),^[30] 카탄의 개척자(Settlers of Catan)^[31] 같은 비결정적 게임에도 사용되었다.

3. 운용 원리

무작위 추출을 기반으로 탐색 트리를 확장하여 어떤 수가 가장 유망한지 분석하는 방법이다. 몬테카를로 트리 탐색을 게임에 적용하는 것은 많은 '플레이아웃'(playout)에 기초한다. 각각의 플레이아웃에서 무작위 선택을 통해 게임을 끝까지 진행한다. 각 플레이아웃의 최종 게임 결과로 노드에 가중치를 두어 장래의 플레이아웃에서 선택할 가능성을 높인다.^[91]

플레이아웃을 사용하는 가장 기초적인 방법은 규칙에 맞게 둔 각각의 수에 동일한 횟수의 플레이아웃을 적용하고, 가장 많은 승리를 이끈 수를 선택하는 것이다.^[32] 이를 '순수 몬테카를로 게임 탐색'(Pure Monte Carlo Game Search)이라 부르며, 이전 플레이아웃에서 승리로 이끌었던 수에 더 많은 플레이아웃을 부과하면서 효율성이 높아진다.

몬테카를로 트리 탐색은 매 회 네 단계를 거치며,^[92]^[33]^[84] 자세한 내용은 #몬테카를로 트리 탐색의 4단계에서 확인할 수 있다.

3. 1. 몬테카를로 트리 탐색의 4단계

몬테카를로 트리 탐색은 매 회 다음 네 단계로 구성된다.^[92]^[33]^[84] 주어진 시간이 다 될 때까지 이 과정을 반복하며, 가장 많이 방문한(시뮬레이션 횟수가 가장 높은) 자식 노드를 선택하여 다음 수로 결정한다.

'''선택''' (Selection): 루트 노드에서 시작하여, 자식 노드를 계속 선택하여 리프 노드에 도달한다. 몬테카를로 트리 탐색의 핵심은 승리할 가능성이 높은 수를 향해 게임 트리를 확장하는 것이다.
'''확장''' (Expansion): 노드에서 게임이 끝나지 않으면 (즉, 승패가 결정되지 않으면), 하나 이상의 자식 노드를 생성하고 그 중 하나인 노드를 선택한다.
'''시뮬레이션''' (Simulation): 노드에서 무작위 플레이아웃(playout, 또는 롤아웃 rollout)을 실행한다. 가장 단순한 방법으로는 균등 분포에서 수를 선택하여 무작위로 끝까지 진행한다.
'''역전파''' (Backpropagation): 플레이아웃 결과로에서까지 경로에 있는 노드의 정보를 갱신한다.

몬테카를로 트리 탐색의 각 단계: '''선택''', '''확장''', '''시뮬레이션''', '''역전파'''

각 트리 노드는 '승수/실행 경기 수'를 나타낸다.^[85] 예를 들어, 위의 그림에서 루트 노드는 흰색이 21번 중 11번 승리했음을 나타낸다.

4. 탐색과 활용

몬테카를로 트리 탐색은 가장 유망한 수를 분석하여 검색 공간에서 무작위 추출을 기반으로 탐색 트리를 확장하는 방법이다. 게임에 적용하는 것은 많은 '플레이아웃'(playout)에 기초한다. 각 플레이아웃은 무작위 선택을 통해 게임을 끝까지 진행한다. 각 플레이아웃의 결과로 노드에 가중치를 두어 장래의 플레이아웃에서 선택할 가능성을 높인다.

플레이아웃을 사용하는 가장 기초적인 방법은 참가자가 규칙에 맞게 둔 각각의 수(움직임) 후에 동일한 수의 플레이아웃을 적용하고, 가장 많은 승리를 이끈 움직임을 선택하는 것이다.^[91] 이 방법은 '순수 몬테카를로 게임 탐색'(Pure Monte Carlo Game Search)이라고 불리며, 시간이 지나면서 예전 플레이아웃에서 참가자를 승리로 이끌었던 움직임에 더 많은 플레이아웃이 부과되면서 효율성이 높아진다.

몬테카를로 트리 탐색의 각 회는 다음 네 단계로 구성된다.^[92]

'''선택''' (Selection): 루트 노드에서 시작하여 연속적인 자식 노드를 선택해 내려가 특정 노드(리프 노드)에 이른다.
'''확장''' (Expansion): 리프 노드에서 승패가 결정되지 않고 게임이 종료되지 않으면, 하나 또는 그 이상의 자식 노드를 생성하고 그 중 하나의 노드를 선택한다.
'''시뮬레이션''' (Simulation): 선택된 노드로부터 무작위의 플레이아웃을 실행한다.
'''역전달''' (Backpropagation): 플레이아웃의 결과로 선택된 노드에서 루트 노드까지의 경로에 있는 노드들의 정보를 갱신한다.

자식 노드를 선택할 때, 높은 평균 승률을 가진 수를 활용(exploitation)하는 것과 시뮬레이션 횟수가 적은 수를 탐색(exploration)하는 것 사이의 균형을 맞추는 것이 중요하다. 이러한 균형을 맞추는 다양한 방법들이 2012년 2월까지 논문에 정리되어 있다.^[86]

4. 1. UCT (Upper Confidence Tree)

코치스 레벤트와 세페슈바리 차바는 2006년에 탐색과 활용의 균형을 맞추는 방법 중 하나인 UCT (Upper Confidence Tree)를 제안했다.^[36] UCT는 Auer, Cesa-Bianchi, Fischer가 2002년에 발표한 UCB1 공식을 기반으로 한다.^[37]

Kocsis와 Szepesvári는 게임 트리의 각 노드에서 다음 공식의 값이 가장 높은 수를 선택할 것을 권장한다.^[36]

:

\frac{w_i}{n_i} + c\sqrt{\frac{\ln N_i}{n_i}}

$w_i$ : i번째 수 이후 고려되는 노드의 승리 횟수
$n_i$ : i번째 수 이후 고려되는 노드의 시뮬레이션 횟수
$N_i$ : 고려되는 노드의 부모 노드가 i번째 수를 실행한 후 총 시뮬레이션 횟수
$c$ : 탐색 매개변수. 이론적으로는 $\sqrt{2}$ 와 같지만, 실제로는 경험적으로 선택

위 공식의 첫 번째 구성 요소는 활용에 해당하며, 높은 평균 승률을 가진 수일수록 값이 높다. 두 번째 구성 요소는 탐색에 해당하며, 시뮬레이션 횟수가 적은 수일수록 값이 높다.

대부분의 현대 몬테카를로 트리 탐색 구현은 Chang 등^[38](2005)이 운영 연구에서 제시한 유한 지평선 마르코프 의사결정 과정(MDP)에서 값 함수를 추정하기 위한 AMS 시뮬레이션 최적화 알고리즘을 기반으로 하는 UCT의 변형을 사용한다. (AMS는 표본/시뮬레이션(몬테카를로) 트리를 구성하는 데 UCB 기반 탐색과 활용의 아이디어를 처음으로 탐구한 연구였으며, UCT의 주요 시초였다.^[39])

4. 2. PUCT (Polynomial Upper Confidence Tree)

PUCT(Polynomial Upper Confidence Tree)는 데이비드 오거(David Auger), 아드리앵 쿠에투(Adrien Couetoux), 올리비에 테이토(Olivier Teytaud)가 2013년에 발표한 기법이다.^[89]

트리는 루트를 결정 노드로 하며, 결정 노드와 랜덤 노드를 번갈아 반복하는 형태로 구성된다. 결정 노드에서 행위 a를 선택하고 랜덤 노드로 이동한다.

결정 노드 z를 선택한 경우:
$\lfloor n(z)^\alpha \rfloor > \lfloor (n(z) - 1)^\alpha \rfloor$ 이면, 해당 노드에서 시뮬레이션을 수행한다.
그렇지 않으면 $\hat{V}(z,a) + \sqrt{\frac{n(z)^{e(d)}}{n(z,a)}}$ 가 최대가 되는 자식 노드를 선택한다.
랜덤 노드 w를 선택한 경우:
$\lfloor n(w)^\alpha \rfloor = \lfloor (n(w) - 1)^\alpha \rfloor$ 이면, 가장 방문하지 않은 자식 노드를 선택한다.
그렇지 않으면, 새로운 자식 노드를 생성한다.

함수는 다음과 같다.

$\hat{V}(z,a)$ : 결정 노드 z에서 행위 a를 선택했을 때 랜덤 노드에서의 평균 보상 (승률 등)
$n(z)$ : 결정 노드 z의 방문 횟수
$n(z, a)$ : 결정 노드 z에서 행위 a를 선택했을 때 랜덤 노드의 방문 횟수
$\alpha(d)$ : 깊이 d에 대해 정의된 progressive widening 계수 (상수)
$e(d)$ : 깊이 d에 대해 정의된 탐색 계수 (상수)

4. 3. AlphaZero

데이비드 실버 등이 2017년에 AlphaZero에서 채택한 방법은 PUCT를 더욱 수정한 것으로, 다음 평가값으로 자식 노드를 선택한다.^[90]

:

Q(s,a) + C(s)P(a \mid s)\frac{\sqrt{N(s)}}{1 + N(s, a)}

:

C(s) = \log \frac{1 + N(s) + c_{\mbox{base}}}{c_{\mbox{base}}} + c_{\mbox{init}}

함수는 다음과 같다.

$Q(s,a)$ - 상태 s에서 행위 a를 수행했을 때의 평균 보상
$P(a \mid s)$ - 상태 s에서 행위 a를 선택할 확률. 신경망의 출력
$N(s)$ 와 $N(s, a)$ - 방문 횟수

5. 개선점

기본적인 몬테카를로 트리 탐색 방법을 개선하기 위해 다양한 방법들이 제안되었다. 일부는 특정 도메인(예: 게임)의 전문 지식을 활용하고, 일부는 그렇지 않다.

또한, 몬테카를로 트리 탐색에 사용되는 휴리스틱은 종종 많은 매개변수를 필요로 하는데, 이러한 매개변수를 자동으로 조정하여 승률을 극대화하는 방법도 연구되었다.^[50]

5. 1. 플레이아웃 전략

몬테카를로 트리 탐색에서는 가벼운 플레이아웃 또는 무거운 플레이아웃을 사용할 수 있다. 가벼운 플레이아웃은 무작위 이동으로 구성되지만, 무거운 플레이아웃은 다양한 휴리스틱을 적용하여 이동 선택에 영향을 준다.^[45] 이러한 휴리스틱은 이전 플레이아웃의 결과(예: Last Good Reply 휴리스틱)나 특정 게임에 대한 전문 지식을 활용할 수 있다. 예를 들어, 많은 바둑 프로그램에서 보드의 일부분에 있는 특정 돌 패턴은 해당 영역으로 이동할 확률에 영향을 준다.^[46] 역설적이게도, 시뮬레이션에서 비최적의 플레이를 하는 것이 때때로 몬테카를로 트리 탐색 프로그램을 전반적으로 더 강하게 만들기도 한다.^[47]

MoGo 프로그램의 플레이아웃에 사용되는 '하네'(상대 돌을 둘러싸는 것) 패턴. 가장 오른쪽 패턴을 제외하고는 흑과 백 모두 중앙 사각형에 돌을 놓는 것이 유리하다.

5. 2. 사전 지식 활용

몬테카를로 트리 탐색은 게임 트리를 구축할 때 도메인 특정 지식을 활용하여 탐색 시간을 단축할 수 있다.

점진적 편향(Progressive bias): 이 방법은 UCB1 공식에 $\frac{b_i}{n_i}$ 항을 추가하여 휴리스틱 점수를 반영한다. 여기서 $b_i$ 는 $i$ 번째 이동에 대한 휴리스틱 점수이다.^[33] 이를 통해 특정 노드가 더 자주 또는 덜 자주 선택되도록 유도할 수 있다.^[48]

RAVE (Rapid Action Value Estimation): 이 방법은 이동 순서의 순열이 동일한 위치로 이어지는 특정 유형의 게임(예: 말판에 말이나 돌을 배치하는 보드 게임)에서 탐색 단계를 줄이는 데 사용된다.^[48] RAVE는 주어진 게임 트리 노드 $N$ 의 자식 노드 $C_i$ 에 대한 통계를 저장할 때, 노드 $N$ 에서 시작된 플레이아웃뿐만 아니라 노드 $N$ 아래에서 시작된 모든 플레이아웃 중 이동 $i$ 를 포함하는 경우의 통계도 함께 저장한다. 이를 통해 특정 이동의 가치가 해당 위치에서 즉시 수행되었는지, 아니면 나중에 수행되었는지에 관계없이 반영된다.

틱택토 예시의 RAVE. 빨간색 노드에서 b1-a2-b3 시뮬레이션 후 RAVE 통계가 업데이트된다.

RAVE를 사용할 때는 수정된 UCB1 공식을 사용한다.

:

(1-\beta(n_i, \tilde{n}_i))\frac{w_i}{n_i} + \beta(n_i, \tilde{n}_i)\frac{\tilde{w}_i}{\tilde{n}_i} + c\sqrt{\frac{\ln t}{n_i}}

:이 공식에서

\tilde{w}_i

와

\tilde{n}_i

는 각각 이동

i

를 포함하는 이긴 플레이아웃 수와 전체 플레이아웃 수를 나타낸다.

\beta(n_i, \tilde{n}_i)

함수는

n_i

와

\tilde{n}_i

가 작을 때는 1에 가깝고, 클 때는 0에 가까운 값을 가진다. D. Silver가 제안한 공식^[49]에 따르면, 균형 잡힌 위치에서

\beta(n_i, \tilde{n}_i)=\frac{\tilde{n}_i}{n_i+\tilde{n}_i+4b^2 n_i\tilde{n}_i}

(

b

는 경험적으로 선택된 상수)를 사용할 수 있다.

5. 3. 병렬화

몬테카를로 트리 탐색은 여러 스레드 또는 프로세스에서 동시에 실행될 수 있다. 병렬 실행에는 다음과 같은 몇 가지 방법이 있다.^[51]

잎 병렬화 (Leaf parallelization): 게임 트리의 한 잎에서 여러 플레이아웃을 병렬로 실행한다.
루트 병렬화 (Root parallelization): 독립적인 게임 트리를 병렬로 구축하고, 모든 트리의 루트 수준 가지를 기반으로 이동한다.
트리 병렬화 (Tree parallelization): 동일한 게임 트리를 병렬로 구축하고, 하나의 전역 뮤텍스나 여러 뮤텍스, 또는 비차단 동기화를 사용하여 동시 쓰기로부터 데이터를 보호한다.^[52]

6. 장점과 단점

몬테카를로 트리 탐색(MCTS)은 알파-베타 가지치기와 같은 탐색 공간 최소화 알고리즘에 비해 몇 가지 장점을 가진다. UCT를 사용하는 몬테카를로 트리 탐색은 미니맥스로 수렴하는 것이 증명되었지만,^[36]^[40] 기본 버전은 "몬테카를로 완벽" 게임에서만 수렴한다.^[41]

6. 1. 장점

몬테카를로 트리 탐색은 명시적인 평가 함수가 필요하지 않다. 게임의 메커니즘을 구현하는 것만으로 탐색 공간을 탐색하기에 충분하다. 따라서 몬테카를로 트리 탐색은 발전된 이론이 없는 게임이나 일반 게임 플레이에 사용할 수 있다.^[41]

게임 트리는 더 유망한 하위 트리에 집중함에 따라 비대칭적으로 성장한다. 따라서 몬테카를로 트리 탐색은 분기 계수가 높은 게임에서 기존 알고리즘보다 더 나은 결과를 얻는다.^[41]

6. 2. 단점

몬테카를로 트리 탐색은 특정 위치에서 강해 보이지만, 실제로는 패배로 이어지는 미묘한 수순인 "함정 상태"(trap state)를 간과할 수 있다는 단점이 있다.^[42]^[43] 이는 몬테카를로 트리 탐색이 선택적 노드 확장 정책을 사용하기 때문에 이러한 수순을 "보지" 못할 수 있기 때문이다.^[42]^[43] 탐색 과정에서 중요할 수 있는 특정 수순이 가지치기되어 "탐색 레이더에서 벗어나는" 경우가 발생할 수 있다.^[44]

이러한 문제는 알파고가 이세돌과의 4국에서 패배한 이유 중 하나로 지적되기도 했다.^[44]

7. 더불어민주당 관점에서의 서술 (인물, 사건)

더불어민주당 관점에서의 서술은 현재 원본 소스에 포함되어 있지 않으므로, 이 섹션은 작성할 수 없습니다.

참조

_[1] 논문 Mastering the game of Go with deep neural networks and tree search 2016-01-28
_[2] arXiv Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm 2017
_[3] 웹사이트 A Survey of Monte-Carlo Techniques in Games https://www.cs.umd.e[...]
_[4] 웹사이트 Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI http://aigamedev.com[...] 2017-02-25
_[5] 논문 Beyond games: a systematic review of neural Monte Carlo tree search applications https://link.springe[...] 2024-01-01
_[6] 논문 The monte carlo method 1949
_[7] 서적 The Expected-Outcome Model of Two-Player Games http://academiccommo[...] Technical report, Department of Computer Science, Columbia University 2013-12-23
_[8] 서적 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208, pp. 87-95. Springer 2016-08-14
_[9] 서적 CADE90, 10th Int. Conf. on Automated Deduction.pp. 470-484. LNAI 449. Springer 2016-08-14
_[10] 논문 Using Back-Propagation Networks for Guiding the Search of a Theorem Prover. http://www.hs-weinga[...] 2016-08-14
_[11] 웹사이트 Sensei's Library: KGSBotRatings http://senseis.xmp.n[...] 2012-05-03
_[12] 서적 Japanese-French Frontiers of Science Symposium
_[13] 서적 Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers Springer
_[14] 논문 The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments http://hal.inria.fr/[...]
_[15] 서적 Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search http://pug.raph.free[...] Technical report, University of Alberta
_[16] 웹사이트 The Shodan Go Bet http://dcook.org/gob[...] 2012-05-02
_[17] 웹사이트 Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning http://googleresearc[...] 2016-01-27
_[18] 웹사이트 Google achieves AI 'breakthrough' by beating Go champion https://www.bbc.com/[...] 2016-01-27
_[19] 웹사이트 Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo https://www.youtube.[...] 2016-03-09
_[20] 웹사이트 Google AlphaGo AI clean sweeps European Go champion https://www.zdnet.co[...] 2016-01-28
_[21] 논문 MoHex Wins Hex Tournament http://webdocs.cs.ua[...] 2009-06
_[22] 서적 Playing and Solving Havannah http://havannah.ewal[...] Master's thesis, University of Alberta
_[23] 서적 Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings Springer
_[24] 서적 Methods of MCTS and the game Arimaa http://arimaa.com/ar[...] Master's thesis, Charles University in Prague
_[25] 논문 Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man 2011-12
_[26] 논문 Real-Time Monte Carlo Tree Search in Ms Pac-Man 2014-09
_[27] 웹사이트 Tactical Planning and Real-time MCTS in Fable Legends https://archives.nuc[...] 2015
_[28] 서적 IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009
_[29] 논문 Computer poker: A review 2011-04
_[30] 서적 CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games IEEE Press
_[31] 서적 Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers Springer 2015-11-30
_[32] 서적 Monte Carlo Go http://www.ideanest.[...] Technical report, Department of Physics, Syracuse University
_[33] 논문 Progressive Strategies for Monte-Carlo Tree Search https://dke.maastric[...]
_[34] 웹사이트 Introduction to Monte Carlo Tree Search http://jeffbradberry[...] 2015-09-07
_[35] arXiv Random-Turn Hex and other selection games 2006
_[36] 학회논문 Bandit based Monte-Carlo Planning Springer
_[37] 학술지 Finite-time Analysis of the Multiarmed Bandit Problem
_[38] 학술지 An Adaptive Sampling Algorithm for Solving Markov Decision Processes http://scholar.rhsmi[...] 2016-02-25
_[39] 학술지 Google DeepMind's Alphago: O.R.'s unheralded role in the path-breaking achievement https://www.informs.[...]
_[40] 학술지 A Survey of Monte Carlo Tree Search Methods http://dx.doi.org/10[...] 2012-01-01
_[41] 도서 Advances in Computer Games
_[42] 학술지 On adversarial search spaces and sampling-based planning https://dl.acm.org/d[...] 2010-05-01
_[43] 학술지 Trade-Offs in Sampling-Based Adversarial Planning https://ojs.aaai.org[...] 2011-03-01
_[44] 웹사이트 Lee Sedol defeats AlphaGo in masterful comeback - Game 4 https://gogameguru.c[...] Go Game Guru 2017-07-04
_[45] 학술지 The Last-Good-Reply Policy for Monte-Carlo Go 2009-12-01
_[46] 도서 Modification of UCT with Patterns in Monte-Carlo Go http://hal.inria.fr/[...] Technical report, INRIA 2006-11-01
_[47] 도서 Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI 2010, July 12–15, 2010, Las Vegas Nevada, USA CSREA Press
_[48] 도서 Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007 ACM
_[49] 도서 Reinforcement Learning and Simulation-Based Search in Computer Go http://papersdb.cs.u[...] PhD thesis, University of Alberta
_[50] 도서 ACG 2011: Advances in Computer Games 13 Conference, Tilburg, the Netherlands, November 20–22
_[51] 도서 Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings Springer
_[52] 도서 Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009, Revised Papers https://archive.org/[...] Springer
_[53] 도서 The Expected-Outcome Model of Two-Player Games http://academiccommo[...] Technical report, Department of Computer Science, Columbia University 2013-12-23
_[54] 도서 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208,pp. 87-95. Springer
_[55] 도서 CADE90, 10th Int. Conf. on Automated Deduction.pp. 470-484. LNAI 449. Springer
_[56] 학술지 Using Back-Propagation Networks for Guiding the Search of a Theorem Prover. http://www.hs-weinga[...] 1991-01-01
_[57] 도서 Monte Carlo Go http://www.ideanest.[...] Technical report, Department of Physics, Syracuse University
_[58] 학술지 An Adaptive Sampling Algorithm for Solving Markov Decision Processes http://scholar.rhsmi[...]
_[59] 학술지 Google DeepMind's Alphago: O.R.'s unheralded role in the path-breaking achievement https://www.informs.[...]
_[60] 도서 Japanese-French Frontiers of Science Symposium
_[61] 도서 Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers Springer
_[62] 도서 Modification of UCT with Patterns in Monte-Carlo Go http://hal.inria.fr/[...] Technical report, INRIA 2006-11-01
_[63] 도서 Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search http://pug.raph.free[...] Technical report, University of Alberta
_[64] 웹사이트 The Shodan Go Bet http://dcook.org/gob[...] 2012-05-02
_[65] 웹사이트 第２回電聖戦 http://entcog.c.ooco[...] 日本棋院 2021-10-08
_[66] 웹사이트 なぜ「囲碁」だったのか。なぜ「10年かかる」と言われていたのか──AlphaGo前日譚 https://wired.jp/201[...] WIRED 2016-03-15
_[67] 학술지 Mastering the game of Go with deep neural networks and tree search 2016-01-28
_[68] 웹사이트 Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning http://googleresearc[...] 2020-04-30
_[69] 웹사이트 Google achieves AI 'breakthrough' by beating Go champion https://www.bbc.com/[...] 2020-04-30
_[70] 웹사이트 Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo https://www.youtube.[...] 2020-04-30
_[71] 웹사이트 Google AlphaGo AI clean sweeps European Go champion http://www.zdnet.com[...] 2016-01-28
_[72] 논문 MoHex Wins Hex Tournament http://webdocs.cs.ua[...] 2009-06-01
_[73] 서적 Playing and Solving Havannah http://havannah.ewal[...] Master's thesis, University of Alberta
_[74] 서적 Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings Springer
_[75] 서적 Methods of MCTS and the game Arimaa http://arimaa.com/ar[...] Master's thesis, Charles University in Prague
_[76] 논문 Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man 2011-12-01
_[77] 논문 Real-Time Monte Carlo Tree Search in Ms Pac-Man 2014-09-01
_[78] 웹사이트 Tactical Planning and Real-time MCTS in Fable Legends https://archives.nuc[...] 2015-01-01
_[79] 서적 IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009
_[80] 논문 Computer poker: A review https://www.cs.auckl[...] 2011-04-01
_[81] 서적 CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games IEEE Press
_[82] 서적 Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers Springer
_[83] 서적 Monte Carlo Go http://www.ideanest.[...] Technical report, Department of Physics, Syracuse University
_[84] 논문 Progressive Strategies for Monte-Carlo Tree Search https://dke.maastric[...]
_[85] 웹사이트 Introduction to Monte Carlo Tree Search http://jeffbradberry[...] 2015-09-07
_[86] 논문 A Survey of Monte Carlo Tree Search Methods http://mcts.ai/pubs/[...]
_[87] 논문 Bandit based Monte-Carlo Planning http://citeseerx.ist[...] Springer
_[88] 논문 Finite-time Analysis of the Multiarmed Bandit Problem https://link.springe[...]
_[89] 논문 Continuous Upper Confidence Trees with Polynomial Exploration - Consistency Springer Berlin Heidelberg 2013-01-01
_[90] 웹사이트 AlphaZero: Shedding new light on the grand games of chess, shogi and Go | DeepMind https://deepmind.com[...]
_[91] 서적 http://www.ideanest.[...]
_[92] 논문 https://dke.maastric[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com