몬테카를로 트리 검색

컴퓨터 과학에서, 몬테카를로 트리 서치(MCTS)는 보드 게임을 하는 소프트웨어에 채용된 어떤 종류의 의사결정 프로세스를 위한 휴리스틱 검색 알고리즘이다.이러한 맥락에서 MCTS는 게임 트리를 해결하기 위해 사용됩니다.

MCTS는 2016년에^[1] 뉴럴 네트워크와 결합되어 Chess, Shogi,^[2] Checkers, Backgamon, Contract Bridge, Computer Go, Scrabble, Clobber^[3] 등 여러 보드 게임과 턴제 전략 비디오 게임(예: Total War: Rome II의 고급 AI^[4] 구현)에 사용되고 있습니다.MCTS는 테슬라의 오토파일럿 소프트웨어 ^[5]등 자가운전 자동차에도 사용되고 있습니다.

역사

몬테카를로법

몬테카를로 방법은 다른 접근방식을 사용하여 해결이 어렵거나 불가능한 결정론적 문제에 대해 무작위 표본을 사용하는 것으로 1940년대까지 ^[6]거슬러 올라간다.1987년 박사학위 논문에서 브루스 에이브람슨은 미니맥스 검색을 일반적인 정적 평가 함수 대신 랜덤 게임 플레이아웃에 기초한 기대 결과와 결합했다.에이브람슨은 기대되는 모델은 "정밀하고 정확하며 쉽게 추정할 수 있고 효율적으로 계산할 수 있으며 도메인에 ^[7]의존하지 않는 것으로 나타났다"고 말했다.그는 tic-tac-toe로 심도 있는 실험을 했고, 그 후 오셀로와 체스를 위한 기계 생성 평가 함수를 사용했다.

그런 다음 이러한 방법을 탐색하여 W. Eertel, J. Schumann 및 C.에 의해 증명된 자동 정리 분야에서 발견적 검색에 성공적으로 적용하였다.1989년 ^[8]^[9]^[10]Suttner를 통해 폭 우선 검색, 깊이 우선 검색 또는 반복 심화와 같은 정보 없는 검색 알고리즘의 지수적 검색 시간을 개선했다.

1992년, B. Brügmann은 바둑 ^[11]프로그램에 처음으로 그것을 채용했다.2002년 ^[12]Chang 등은 마르코프 의사결정 프로세스 모델에 대한 적응형 다단계 샘플링(AMS) 알고리즘에서 "적응적" 샘플링 선택과 함께 "재귀적 롤아웃 및 역추적" 아이디어를 제안했다.AMS는 샘플링/시뮬레이션된(몬테 카를로) 트리 구축에서 UCB 기반 탐색 및 착취의 아이디어를 탐색한 첫 번째 연구였으며 UCT(Upper Confidence Tree)^[13]의 주요 씨앗이었다.

몬테카를로 트리 검색(MCTS)

2007년 이후 KGS 서버 최고의 바둑 프로그램 평가.2006년 이후, 모든 최고의 프로그램은 몬테카를로 트리 ^[14]검색을 사용합니다.

2006년,^[15] Remi Coulom은 이러한 전임자로부터 영감을 얻어 몬테 카를로 방법의 게임 트리 검색에 대한 적용을 설명하고 몬테 카를로 트리 ^[16]검색이라는 이름을 만들어 냈으며, L. Kocsis와 Cs. Szepesvarri는 UCT(^[17]나무에 적용되는 상한 신뢰 한계) 알고리즘과 S.Gelly 등은 프로그램 MoGo에서 ^[18]UCT를 구현했다.2008년 9×9 ^[19]바둑에서 MoGo는 단을 달성하였고, Fuego 프로그램은 9×9 ^[20]바둑에서 강력한 아마추어 선수들을 상대로 승리를 거두기 시작했다.

2012년 1월, Zen 프로그램은 아마추어 2단 ^[21]선수와의 19×19 바둑판 바둑에서 3:1로 승리했습니다.구글 딥마인드는 2015년 10월 19x19 크기의 대형 보드에서 장애 없이 프로 바둑 ^[1]^[22]^[23]선수를 이긴 최초의 컴퓨터 바둑 프로그램이 되었다.2016년 3월 알파고는 이세돌을 5대 ^[24]1로 꺾은 공로로 19×19 바둑에서 명예 9단(명장)을 받았다.AlphaGo는 정책(이동 선택)과 가치를 위해 인공 신경망(딥러닝 방법)과 함께 몬테카를로 트리 검색을 사용하여 이전 프로그램을 ^[25]훨씬 능가하는 효율성을 제공하므로 이전 바둑 프로그램에 비해 상당한 개선과 기계 학습의 이정표를 나타낸다.

MCTS 알고리즘은 다른 보드 게임(예: ^[26]Hex, Havannah,^[27] Game of the Amazons,^[28] Arimaa^[29]), 실시간 비디오 게임(예: Ms. Pac-Man^[30]^[31] 및 Fable^[32] Legends), 비결정론적 게임(예: skat,^[33] 포커,^[34] Magic: 집결지,^[35] 또는 카탄의^[36] 정착민).

작동 원리

MCTS의 초점은 가장 유망한 움직임의 분석에 있으며, 서치 공간의 랜덤 샘플링에 기초하여 서치 트리를 확장한다.게임에서 몬테카를로 트리 검색의 적용은 롤아웃이라고도 불리는 많은 플레이아웃을 기반으로 합니다.각 플레이아웃에서는 랜덤으로 무브 선택을 하여 끝까지 게임을 진행한다.각 플레이아웃의 최종 게임 결과는 게임 트리의 노드에 무게를 부여하기 위해 사용되며, 향후 플레이아웃에서 더 나은 노드가 선택될 가능성이 높아집니다.

플레이아웃을 사용하는 가장 기본적인 방법은 현 선수의 합법적 이동 후에 같은 수의 플레이아웃을 적용한 후 가장 많은 ^[11]승리를 이끌었던 동작을 선택하는 것이다.Pure Monte Carlo Game Search(순수 몬테카를로 게임 검색)라고 불리는 이 방법의 효율은 종종 이전의 플레이아웃에 따라 현재 플레이어의 승리를 초래한 움직임에 더 많은 플레이아웃이 할당됨에 따라 시간이 지남에 따라 높아집니다.몬테카를로 트리 검색의 각 라운드는 다음 ^[37]4단계로 구성됩니다.

선택: $루트$ R에서 시작하여 리프 $노드$ L에 도달할 때까지 연속된 하위 노드를 선택합니다.루트는 현재 게임 상태이며, 리프는 시뮬레이션(플레이아웃)이 아직 시작되지 않은 잠재적인 자식을 가진 노드입니다.아래 섹션에서는 게임 트리가 가장 유망한 움직임으로 확장되도록 하는 하위 노드의 선택을 바이어스하는 방법에 대해 자세히 설명합니다. 이것이 몬테카를로 트리 검색의 본질입니다.
확장:L이 어느 한 플레이어에 대해 결정적으로 게임을 종료하지 $않는$ 한(예를 들어 승패/추첨), 하나 이상의 하위 노드를 생성하고 그 중 하나에서 $노드$ C를 선택합니다.자노드는 L에 $의해$ 정의된 게임 포지션에서 유효한 움직임입니다.
시뮬레이션: $노드$ C에서 랜덤 플레이아웃을 1회 완료합니다.이 단계는 플레이아웃 또는 롤아웃이라고도 합니다.플레이아웃은 게임이 결정될 때까지 균일한 랜덤 동작을 선택하는 것(예를 들어 체스에서는 게임이 이기거나, 지거나, 무승부)으로 간단할 수 있습니다.
역전파:플레이아웃 결과를 사용하여 $C에서R$ 로의 패스상의 노드의 정보를 갱신합니다.

몬테카를로 나무 탐색 단계입니다.

이 그래프는 하나의 결정에 관련된 단계를 보여 주며, 각 노드는 해당 ^[38]노드가 나타내는 플레이어의 게임 트리의 해당 시점부터 총 플레이아웃에 대한 승리 비율을 보여 줍니다.선택 다이어그램에서 검정색이 이동하려고 합니다.루트 노드는 지금까지 이 포지션에서 화이트 플레이아웃 21개 중 11개가 승리했음을 나타냅니다.이는 아래에 있는 3개의 검은색 노드를 따라 표시된 10/21 검은색 총 승수를 보완합니다. 각 노드는 검은색 이동 가능성을 나타냅니다.이 그래프는 다음에 설명하는 UCT 알고리즘을 따르지 않습니다.

흰색으로 시뮬레이션이 손실되면 선택 항목을 따라 모든 노드가 시뮬레이션 카운트(분모)를 증가시키지만, 그 중 검은색 노드만 승리(분자)를 인정받았다.대신 흰색 노드가 승리할 경우 선택 영역의 모든 노드가 시뮬레이션 수를 계속 증가시키지만, 그중에서도 흰색 노드만 승리자로 인정됩니다.추첨이 가능한 게임에서는 추첨을 통해 흑백 모두 분자가 0.5씩 증가하고 분모가 1씩 증가합니다.이것은 선택 중에 각 플레이어의 선택이 해당 플레이어의 가장 유망한 움직임으로 확장되도록 하며, 이는 각 플레이어의 움직임의 가치를 극대화하는 목표를 반영합니다.

이동에 할당된 시간이 남아 있는 한 검색을 반복합니다.그런 다음 가장 많은 시뮬레이션을 수행한 이동(즉, 가장 높은 분모)이 최종 답으로 선택된다.

순수 몬테카를로 게임 검색

이 기본 절차는 위치가 반드시 한정된 수의 움직임과 한정된 길이를 갖는 모든 게임에 적용될 수 있습니다.각 포지션에 대해 k개의 랜덤 게임이 끝까지 진행되어 점수가 기록되는 모든 실행 가능한 동작을 결정한다.최고 점수로 이어지는 동작이 선택됩니다.페어코인 플립으로 동점이 깨진다.순수 몬테카를로 게임 검색은 EinStein würfelt nicht! 게임과 같이 랜덤 요소가 있는 여러 게임에서 강력한 플레이를 제공합니다.랜덤 턴 순서의 보드 필링 게임, 예를 들어 랜덤 턴 ^[39]순서의 헥스 게임에서 최적의 플레이(k가 무한대에 이르는 경향이 있음)로 수렴됩니다.DeepMind의 AlphaZero는 시뮬레이션 단계를 뉴럴 ^[2]네트워크에 기반한 평가로 대체한다.

탐색 및 이용

하위 노드를 선택할 때 가장 큰 어려움은 높은 평균 승률을 가진 이동 후 심층 변형을 이용하는 것과 시뮬레이션이 거의 없는 이동 탐색 사이의 균형을 유지하는 것이다.Levente Kocsis와 Csaba Szepesvarri에 ^[17]의해 UCT(Upper Confidence Bound 1)라고 불리는 게임에서의 착취와 탐험의 균형을 위한 첫 번째 공식은 도입되었습니다.UCT는 Auer, Cesa-Bianchi 및^[40] Fischer에 의해 도출된 UCB1 공식과 Chang, Fu, Hu 및 ^[12]Marcus에 의해 다단계 의사결정 모델(특히 마르코프 의사결정 프로세스)에 최초로 적용된 입증 가능한 수렴형 다단계 샘플링(Adaptive Multi-stage Sampling) 알고리즘을 기반으로 한다.Kocsis와 Szepesvarri는 게임 트리의 각 노드에서 ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$ + ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$ ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$ ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$ ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$ n ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$ i \ $displaystyle$ { $w _$ { $i$ } { $n$ _ { $i$ } + c { \ $sqrt$ \ $ln$ _ { $i$ } $c$ n _ { $n$ _ { i ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$ } } c c c for ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$ c c c c c c k k k k c k k k k c c k for c c c c \ frcrcrcrtransplay st다음 공식에서:

$w$ 는_i i번째 이동 후 고려된 노드의 승리 수를 나타냅니다.
$n$ 은_i i번째 이동 후 고려된 노드의 시뮬레이션 수를 나타냅니다.
N은 고려된 상위 노드에 의해 실행된 i번째 이동 후 시뮬레이션의 총 수를 $나타냅니다 i$ .
$c$ 는 탐색 파라미터로 이론적으로 $δ2$ 와 동일하며, 실제로는 일반적으로 경험적으로 선택된다.

위의 공식의 첫 번째 구성 요소는 부정 이용에 해당하며 평균 승률이 높은 이동에 대해 높은 편입니다.두 번째 요소는 탐색에 해당하며 시뮬레이션이 거의 없는 이동에 적합합니다.

몬테카를로 트리 검색의 대부분의 현대적 구현은 Chang ^[12]et al.에 의해 도입된 유한 수평 마르코프 의사결정 프로세스(MDP)의 가치 함수를 추정하기 위해 AMS 시뮬레이션 최적화 알고리즘에 뿌리를 두고 있는 UCT의 일부 변형에 기초한다.(2005) 운영연구에서 (AMS는 샘플링/시뮬레이션(Monte Carlo) 트리 구축에서 UCB 기반 탐색 및 이용 아이디어를 탐색한 첫 번째 연구였으며 UCT의 주요 씨앗이었다.)^[13]

장점과 단점

몬테카를로 트리 검색의 움직임 평가가 미니맥스로 ^[41]수렴된다는 것이 입증되었지만 몬테카를로 트리 검색의 기본 버전은 소위 "몬테카를로 퍼펙트" ^[42]게임에서만 수렴됩니다.그러나 몬테카를로 트리 검색은 검색 공간을 최소화하는 알파 베타 가지치기 및 유사한 알고리즘에 비해 상당한 이점을 제공한다.

특히 순수한 몬테카를로 트리 검색은 명시적 평가 함수를 필요로 하지 않는다.단순히 게임의 메커니즘을 구현하는 것만으로 서치 공간을 탐색할 수 있습니다(즉, 주어진 위치 및 게임 종료 조건에서 허용되는 이동 생성).이와 같이 몬테카를로 트리 탐색은 발전된 이론이 없는 게임이나 일반적인 게임 플레이에서 사용될 수 있다.

몬테카를로 트리 검색의 게임 트리는 방법이 더 유망한 하위 트리에 집중함에 따라 비대칭적으로 성장한다.따라서^[dubious – discuss] 분기 계수가 높은 게임에서 고전 알고리즘보다 더 나은 결과를 얻을 수 있습니다.

단점은 어떤 포지션에서는 겉으로는 강해보이지만 실제로는 미묘한 플레이라인으로 실점으로 이어지는 움직임이 있다는 것이다.이러한 「트랩 상태」는, 특히 익스퍼트 플레이어와 플레이 할 때에, 정확하게 취급할 필요가 있습니다.다만, MCTS는 선택적 노드 ^[43]^[44]확장 정책을 실시하고 있기 때문에, 이러한 라인을 「인식」하지 않는 경우가 있습니다.이것이 알파고가 이세돌과의 네 번째 경기에서 패배한 이유 중 하나였을 것으로 생각된다.본질적으로 검색은 관련성이 낮은 시퀀스를 제거하려고 시도합니다.경우에 따라서는 플레이가 매우 구체적인 플레이의 행으로 이어질 수 있는데, 이는 중요하지만 트리가 가지치기될 때 간과되기 때문에 이 결과는 "검색 레이더에서 벗어납니다".^[45]

개선점

검색 시간을 단축하기 위해 기본적인 몬테카를로 트리 검색 방법의 다양한 수정이 제안되었다.도메인 고유의 전문 지식을 채용하고 있는 사람도 있고, 채용하고 있지 않은 사람도 있습니다.

몬테카를로 트리 검색에서는 가벼운 플레이아웃과 무거운 플레이아웃 중 하나를 사용할 수 있습니다.가벼운 플레이아웃은 랜덤한 움직임으로 구성되며, 무거운 플레이아웃은 다양한 휴리스틱스를 적용하여 ^[46]움직임 선택에 영향을 미칩니다.이러한 휴리스틱스는 이전 플레이아웃의 결과(예: Last Good Reply 휴리스틱^[47]) 또는 주어진 게임에 대한 전문가 지식을 사용할 수 있습니다.예를 들어, 많은 바둑 프로그램에서는 보드의 일부에 있는 특정 돌 무늬가 해당 ^[18]영역으로 이동할 가능성에 영향을 미칩니다.역설적으로 시뮬레이션에서 차선책으로 재생하면 몬테카를로 트리 검색 프로그램이 전체적으로 ^[48]재생되는 경우가 있다.

MoGo 프로그램에서 플레이아웃에 사용되는 Hane(상대 돌을 둘러싼) 패턴입니다.검은색만 ^[18]선호하는 오른쪽 무늬를 제외하고 가운데 사각형에 돌을 넣는 것이 흑백 모두에게 유리하다.

게임 트리를 구축할 때 도메인 고유의 지식을 사용하여 일부 변종의 이용을 지원할 수 있습니다.이러한 방법 중 하나는 각 자노드를 생성할 때 0이 아닌 우선 순위를 부여하고, 선택 ^[49]단계에서 노드를 선택하는 빈도를 각각 높인 평균 당첨률을 인위적으로 올리거나 낮춘다.프로그레시브 바이어스라고 불리는 관련 방법은 UCB1 공식 ${\frac {b_{i}}{n_{i}}}$ ${\frac {b_{i}}{n_{i}}}$ n ${\frac {b_{i}}{n_{i}}}$ { $display$ { $frac$ { b $_$ { $i$ } { $n$ _ { $i$ } } , ,, 。 $여기$ 서_i b는 i번째 ^[37]움직임의 휴리스틱 점수이다.

기본적인 몬테카를로 트리 검색은 많은 라운드가 끝난 후에야 가장 유망한 움직임을 찾을 수 있는 충분한 정보를 수집한다.그때까지 그 움직임은 본질적으로 무작위이다.이 탐색 단계는 RAVE(Rapid Action Value Estimation)^[49]를 사용하는 특정 등급의 게임에서 크게 줄어들 수 있습니다.이러한 게임에서는 일련의 움직임의 배열이 같은 위치로 이어집니다.일반적으로 보드 위에 조각이나 돌을 놓는 보드 게임입니다.이러한 게임에서 각 동작의 가치는 종종 다른 동작에 의해 약간만 영향을 받는다.

RAVE에서는 소정의 유기목 $노드$ N에 대해 그 $자노드 i$ C는 $노드$ N에서 개시된 플레이아웃의 승리 통계뿐만 $아니라$ 노드 N에서 개시된 모든 플레이아웃의 승리 통계도 $move$ i( $노드$ N과 플레이아웃 사이에서 이동했을 때)가 포함되어 있으면 기억한다.이와 같이 트리 노드의 내용은 특정 위치에서 즉시 실행되는 이동뿐만 아니라 나중에 실행되는 동일한 이동에 의해서도 영향을 받습니다.

tic-tac-toe의 예에 대한 RAVE.빨간색 노드에서는 b1-a2-b3 시뮬레이션 후에 RAV 통계 정보가 업데이트됩니다.

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}}}}$ 공식( $(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}}}}$ - $(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}}}}$ ( $(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}}}}$ , $(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}}}}$ n ~ $(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}}}}$ $(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}}}}$ 와 $(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}}}}$ $(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}}}}$ + $(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}}}}$ $(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}}}}$ $(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}}}}$ i , $(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}}}}$ ~ $(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}}}}$ ) $(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}}}}$ ~ $(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}}}}$ n + $(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}}}}$ ln $(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}}}}$ i ( $1$ - \ $displaystyle$ ( n _ { i , { \ $tilde$ { n } { n } { i $_ frac$ } ){ $frac$ } w )의 $(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}}}}$ 를 선택합니다. $_{i}{\frac {\tilde {w}}_{i}}{\tilde {n}_{i}}}+c4rt {frac$ { $ln t}{n_{$ i}}}}의 $(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}}}}$ 값이 가장 높습니다.이 공식에서 w ${\tilde {w}}_{i}$ ~ $(style$ { $tilde$ ${w}_$ ${$ $i$ }) ${\tilde {n}}_{i}$ n $($ $displaystyle$ ${$ $n}_{i})$ 은 $\tilde{n}_i$ $\beta(n_i, \tilde{n}_i)$ $move$ i를 포함한 won 플레이아웃의 $\beta (n_{i},{\tilde {n}}_{i})$ 와 move $\beta (n_{i},{\tilde {n}}_{i})$ 를 포함한 모든 $플레이아웃$ 의 수를 나타냅니다 $.$ d는 상대적으로 작고 $상대적$ 으로_i 큰 n과 $($ 스타일 ${n}_{i$ 의 경우 각각 1에 가깝고 0에 가깝다.D가 제안한 $\beta (n_{i},{\tilde {n}}_{i})$ β ( $\beta (n_{i},{\tilde {n}}_{i})$ , $\beta (n_{i},{\tilde {n}}_{i})$ ~ $\beta (n_{i},{\tilde {n}}_{i})$ ) { $displaystyle \beta$ ( n $_$ { i , { \ $tilde$ { $n} _$ { $i$ } } $\beta (n_{i},{\tilde {n}}_{i})$ } }의 $\beta (n_{i},{\tilde {n}}_{i})$ 식 중 하나.Silver,[50]이 b는 경험적으로 선택한 constan이 균형 있게 위치에서)n~나의 나는 + n~나는 + 4b2ni의 스녀일 나는{\displaystyle\beta(n_{나는},{\tilde{n}}_{나는})={\frac{{\tilde{n}}_{나는}}{n_{나는}+{\tilde{n}}_{나는}+4b^{2}n_{나는}{\tilde{n}}_{나는}}}},β(nin까지는 나는) 걸릴 수 있다고 말한다.t.

몬테카를로 트리 검색에 사용되는 휴리스틱스는 많은 매개변수를 필요로 한다.파라미터를 조정하여 승률을 ^[51]최대화하는 자동화된 방법이 있습니다.

몬테카를로 트리 검색은 많은 스레드 또는 프로세스에 의해 동시에 실행될 수 있습니다.병렬 ^[52]실행에는 기본적으로 다른 방법이 몇 가지 있습니다.

리프 병렬화, 즉 게임 트리의 한 리프에서 여러 플레이아웃을 병렬로 실행합니다.
루트 병렬화, 즉 독립된 게임 트리를 병렬로 구축하고 이러한 모든 트리의 루트 레벨 분기를 기반으로 이동을 수행합니다.
트리 병렬화, 즉 동일한 게임 트리의 병렬 구축으로 하나의 글로벌 뮤텍스, 더 많은 뮤텍스 또는 비블로킹 ^[53]동기화를 사용하여 데이터를 동시 쓰기로부터 보호합니다.

「」를 참조해 주세요.

몬테카를로 트리 검색, 강화 학습 및 딥 러닝을 이용한 바둑 프로그램인 알파고.
몬테카를로 트리 검색, 강화 학습 및 딥 러닝을 사용하여 업데이트된 바둑 프로그램인 AlphaGo Zero.
AlphaZero는 몬테카를로 트리 검색, 강화 학습 및 딥 러닝을 사용하는 AlphaGo Zero의 일반화된 버전입니다.
릴라 체스 제로(Leela Chess Zero)는 현재 선도적인 체스 프로그램 중 하나인 AlphaZero의 체스 방법을 자유 소프트웨어로 구현한 것입니다.

레퍼런스

^ ^a ^b Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28 January 2016). "Mastering the game of Go with deep neural networks and tree search". Nature. 529 (7587): 484–489. Bibcode:2016Natur.529..484S. doi:10.1038/nature16961. ISSN 0028-0836. PMID 26819042. S2CID 515925.
^ ^a ^b Silver, David (2017). "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm". arXiv:1712.01815v1 [cs.AI].
^ https://www.cs.umd.edu/sites/default/files/scholarly_papers/Rajkumar_1.pdf^{[베어 URL PDF]}
^ "Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI". AI Game Dev. Archived from the original on 13 March 2017. Retrieved 25 February 2017.
^ Tesla의 AI Day 비디오 https://youtube.com/watch?v=j0z4FweCy4M
^ Nicholas, Metropolis; Stanislaw, Ulam (1949). "The monte carlo method". Journal of the American Statistical Association. 44 (247): 335–341. doi:10.1080/01621459.1949.10483310. PMID 18139350.
^ Abramson, Bruce (1987). The Expected-Outcome Model of Two-Player Games (PDF). Technical report, Department of Computer Science, Columbia University. Retrieved 23 December 2013.
^ Wolfgang Ertel; Johann Schumann; Christian Suttner (1989). "Learning Heuristics for a Theorem Prover using Back Propagation.". In J. Retti; K. Leidlmair (eds.). 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208,pp. 87-95. Springer.
^ Christian Suttner; Wolfgang Ertel (1990). "Automatic Acquisition of Search Guiding Heuristics.". CADE90, 10th Int. Conf. on Automated Deduction.pp. 470-484. LNAI 449. Springer.
^ Christian Suttner; Wolfgang Ertel (1991). "Using Back-Propagation Networks for Guiding the Search of a Theorem Prover". Journal of Neural Networks Research & Applications. 2 (1): 3–16.
^ ^a ^b Brügmann, Bernd (1993). Monte Carlo Go (PDF). Technical report, Department of Physics, Syracuse University.
^ ^a ^b ^c Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marcus, Steven I. (2005). "An Adaptive Sampling Algorithm for Solving Markov Decision Processes" (PDF). Operations Research. 53: 126–139. doi:10.1287/opre.1040.0145. hdl:1903/6264.
^ ^a ^b Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). "Google DeepMind's Alphago: O.R.'s unheralded role in the path-breaking achievement". OR/MS Today. 45 (5): 24–29.
^ "Sensei's Library: KGSBotRatings". Retrieved 2012-05-03.
^ Rémi Coulom (2008). "The Monte-Carlo Revolution in Go" (PDF). Japanese-French Frontiers of Science Symposium.
^ Rémi Coulom (2007). "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search". Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers. H. Jaap van den Herik, Paolo Ciancarini, H. H. L. M. Donkers (eds.). Springer. pp. 72–83. CiteSeerX 10.1.1.81.6817. ISBN 978-3-540-75537-1.
^ ^a ^b Kocsis, Levente; Szepesvári, Csaba (2006). "Bandit based Monte-Carlo Planning". In Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4212. Springer. pp. 282–293. CiteSeerX 10.1.1.102.1296. doi:10.1007/11871842_29. ISBN 3-540-45375-X.
^ ^a ^b ^c Sylvain Gelly; Yizao Wang; Rémi Munos; Olivier Teytaud (November 2006). Modification of UCT with Patterns in Monte-Carlo Go (PDF). Technical report, INRIA.
^ Chang-Shing Lee; Mei-Hui Wang; Guillaume Chaslot; Jean-Baptiste Hoock; Arpad Rimmel; Olivier Teytaud; Shang-Rong Tsai; Shun-Chin Hsu; Tzung-Pei Hong (2009). "The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments" (PDF). IEEE Transactions on Computational Intelligence and AI in Games. 1 (1): 73–89. CiteSeerX 10.1.1.470.6018. doi:10.1109/tciaig.2009.2018703. S2CID 15266518.
^ Markus Enzenberger; Martin Mūller (2008). Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search (PDF). Technical report, University of Alberta.
^ "The Shodan Go Bet". Retrieved 2012-05-02.
^ "Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning". Google Research Blog. 27 January 2016.
^ "Google achieves AI 'breakthrough' by beating Go champion". BBC News. 27 January 2016.
^ "Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo". Youtube. 9 March 2016.
^ "Google AlphaGo AI clean sweeps European Go champion". ZDNet. 28 January 2016.
^ Broderick Arneson; Ryan Hayward; Philip Henderson (June 2009). "MoHex Wins Hex Tournament" (PDF). ICGA Journal. 32 (2): 114–116. doi:10.3233/ICG-2009-32218.
^ Timo Ewalds (2011). Playing and Solving Havannah (PDF). Master's thesis, University of Alberta.
^ Richard J. Lorentz (2008). "Amazons Discover Monte-Carlo". Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. pp. 13–24. ISBN 978-3-540-87607-6.
^ Tomáš Kozelek (2009). Methods of MCTS and the game Arimaa (PDF). Master's thesis, Charles University in Prague.
^ Xiaocong Gan; Yun Bao; Zhangang Han (December 2011). "Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man". ICGA Journal. 34 (4): 209–222. doi:10.3233/ICG-2011-34404.
^ Tom Pepels; Mark H. M. Winands; Marc Lanctot (September 2014). "Real-Time Monte Carlo Tree Search in Ms Pac-Man". IEEE Transactions on Computational Intelligence and AI in Games. 6 (3): 245–257. doi:10.1109/tciaig.2013.2291577.
^ Mountain, Gwaredd (2015). "Tactical Planning and Real-time MCTS in Fable Legends". Retrieved 2019-06-08. .. we implemented a simulation based approach, which involved modelling the game play and using MCTS to search the potential plan space. Overall this worked well, ...
^ Michael Buro; Jeffrey Richard Long; Timothy Furtak; Nathan R. Sturtevant (2009). "Improving State Evaluation, Inference, and Search in Trick-Based Card Games". IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009. Craig Boutilier (ed.). pp. 1407–1413. CiteSeerX 10.1.1.150.3077.
^ Jonathan Rubin; Ian Watson (April 2011). "Computer poker: A review". Artificial Intelligence. 175 (5–6): 958–987. doi:10.1016/j.artint.2010.12.005.
^ C.D. Ward; P.I. Cowling (2009). "Monte Carlo Search Applied to Card Selection in Magic: The Gathering" (PDF). CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press. Archived from the original (PDF) on 2016-05-28.
^ István Szita; Guillaume Chaslot; Pieter Spronck (2010). "Monte-Carlo Tree Search in Settlers of Catan" (PDF). In Jaap Van Den Herik; Pieter Spronck (eds.). Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. Springer. pp. 21–32. ISBN 978-3-642-12992-6.
^ ^a ^b G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; B. Bouzy (2008). "Progressive Strategies for Monte-Carlo Tree Search" (PDF). New Mathematics and Natural Computation. 4 (3): 343–359. doi:10.1142/s1793005708001094.
^ Bradberry, Jeff (2015-09-07). "Introduction to Monte Carlo Tree Search".
^ Peres, Yuval; Schramm, Oded; Sheffield, Scott; Wilson, David B. (2006). "Random-Turn Hex and other selection games". arXiv:math/0508580.
^ Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). "Finite-time Analysis of the Multiarmed Bandit Problem". Machine Learning. 47 (2/3): 235–256. doi:10.1023/a:1013689704352. S2CID 207609497.
^ Bouzy, Bruno. "Old-fashioned Computer Go vs Monte-Carlo Go" (PDF). IEEE Symposium on Computational Intelligence and Games, April 1–5, 2007, Hilton Hawaiian Village, Honolulu, Hawaii.
^ Althöfer, Ingo (2012). "On Board-Filling Games with Random-Turn Order and Monte Carlo Perfectness". Advances in Computer Games. Lecture Notes in Computer Science. Vol. 7168. pp. 258–269. doi:10.1007/978-3-642-31866-5_22. ISBN 978-3-642-31865-8.
^ Ramanujan, Raghuram; Sabharwal, Ashish; Selman, Bart (May 2010). "On adversarial search spaces and sampling-based planning". ICAPS '10: Proceedings of the Twentieth International Conference on International Conference on Automated Planning and Scheduling. Icaps'10: 242–245.
^ Ramanujan, Raghuram; Selman, Bart (March 2011). "Trade-Offs in Sampling-Based Adversarial Planning". ICAPS '11: Proceedings of the International Conference on Automated Planning and Scheduling. 21 (1): 202–209.
^ "Lee Sedol defeats AlphaGo in masterful comeback - Game 4". Go Game Guru. Archived from the original on 2016-11-16. Retrieved 2017-07-04.
^ § Wiechowski, Maddjiuk, J., "일반 게임에서의 플레이 전략의 자기 적응" (2010), 게임에서의 컴퓨터 인텔리전스 및 AI에 관한 IEEE 트랜잭션, vol: 6(4), pp.367-381, doi:10.1109/TCIAG.2013.CIAG.
^ Drake, Peter (December 2009). "The Last-Good-Reply Policy for Monte-Carlo Go". ICGA Journal. 32 (4): 221–227. doi:10.3233/ICG-2009-32404.
^ Seth Pellegrino; Peter Drake (2010). "Investigating the Effects of Playout Strength in Monte-Carlo Go". Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI 2010, July 12–15, 2010, Las Vegas Nevada, USA. Hamid R. Arabnia, David de la Fuente, Elena B. Kozerenko, José Angel Olivas, Rui Chang, Peter M. LaMonica, Raymond A. Liuzzi, Ashu M. G. Solo (eds.). CSREA Press. pp. 1015–1018. ISBN 978-1-60132-148-0.
^ ^a ^b Gelly, Sylvain; Silver, David (2007). "Combining Online and Offline Knowledge in UCT" (PDF). Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007. Zoubin Ghahramani (ed.). ACM. pp. 273–280. ISBN 978-1-59593-793-3. Archived from the original (PDF) on 2017-08-28.
^ David Silver (2009). Reinforcement Learning and Simulation-Based Search in Computer Go (PDF). PhD thesis, University of Alberta.
^ Rémi Coulom. "CLOP: Confident Local Optimization for Noisy Black-Box Parameter Tuning". ACG 2011: Advances in Computer Games 13 Conference, Tilburg, the Netherlands, November 20–22.
^ Guillaume M.J-B. Chaslot, Mark H.M. Winands, Jaap van den Herik (2008). "Parallel Monte-Carlo Tree Search" (PDF). Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. pp. 60–71. ISBN 978-3-540-87607-6.{{cite book}}: CS1 maint: 여러 이름: 작성자 목록(링크)
^ Markus Enzenberger; Martin Müller (2010). "A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm". In Jaap Van Den Herik; Pieter Spronck (eds.). Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009, Revised Papers. Springer. pp. 14–20. CiteSeerX 10.1.1.161.1984. ISBN 978-3-642-12992-6.

참고 문헌

Cameron Browne; Edward Powley; Daniel Whitehouse; Simon Lucas; Peter I. Cowling; Philipp Rohlfshagen; Stephen Tavener; Diego Perez; Spyridon Samothrakis; Simon Colton (March 2012). "A Survey of Monte Carlo Tree Search Methods". IEEE Transactions on Computational Intelligence and AI in Games. 4 (1): 1–43. CiteSeerX 10.1.1.297.3086. doi:10.1109/tciaig.2012.2186810. S2CID 9316331.
Maciej Świechowski; Konrad Godlewski; Bartosz Sawicki; Jacek Mańdziuk (July 2022). "Monte Carlo Tree Search: a review of recent modifications and applications". Springer Nature Artificial Intelligence Review: (66 pages). doi:10.1007/s10462-022-10228-y.

외부 링크

몬테카를로 트리 서치 초보자 가이드

[alphago-1] Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28 January 2016). "Mastering the game of Go with deep neural networks and tree search". Nature. 529 (7587): 484–489. Bibcode:2016Natur.529..484S. doi:10.1038/nature16961. ISSN 0028-0836. PMID 26819042. S2CID 515925.

[:0-2] Silver, David (2017). "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm". arXiv:1712.01815v1 [cs.AI].

[3] ttps://www.cs.umd.edu/sites/default/files/scholarly_papers/Rajkumar_1.pdf^{[베어 URL PDF]}

[4] "Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI". AI Game Dev. Archived from the original on 13 March 2017. Retrieved 25 February 2017.

[5] Tesla의 AI Day 비디오 https://youtube.com/watch?v=j0z4FweCy4M

[6] Nicholas, Metropolis; Stanislaw, Ulam (1949). "The monte carlo method". Journal of the American Statistical Association. 44 (247): 335–341. doi:10.1080/01621459.1949.10483310. PMID 18139350.

[Abramson-7] Abramson, Bruce (1987). The Expected-Outcome Model of Two-Player Games (PDF). Technical report, Department of Computer Science, Columbia University. Retrieved 23 December 2013.

[8] Wolfgang Ertel; Johann Schumann; Christian Suttner (1989). "Learning Heuristics for a Theorem Prover using Back Propagation.". In J. Retti; K. Leidlmair (eds.). 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208,pp. 87-95. Springer.

[9] Christian Suttner; Wolfgang Ertel (1990). "Automatic Acquisition of Search Guiding Heuristics.". CADE90, 10th Int. Conf. on Automated Deduction.pp. 470-484. LNAI 449. Springer.

[10] Christian Suttner; Wolfgang Ertel (1991). "Using Back-Propagation Networks for Guiding the Search of a Theorem Prover". Journal of Neural Networks Research & Applications. 2 (1): 3–16.

[Bruegmann-11] Brügmann, Bernd (1993). Monte Carlo Go (PDF). Technical report, Department of Physics, Syracuse University.

[Chang2005-12] Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marcus, Steven I. (2005). "An Adaptive Sampling Algorithm for Solving Markov Decision Processes" (PDF). Operations Research. 53: 126–139. doi:10.1287/opre.1040.0145. hdl:1903/6264.

[changORMStoday-13] Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). "Google DeepMind's Alphago: O.R.'s unheralded role in the path-breaking achievement". OR/MS Today. 45 (5): 24–29.

[14] "Sensei's Library: KGSBotRatings". Retrieved 2012-05-03.

[15] Rémi Coulom (2008). "The Monte-Carlo Revolution in Go" (PDF). Japanese-French Frontiers of Science Symposium.

[16] Rémi Coulom (2007). "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search". Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers. H. Jaap van den Herik, Paolo Ciancarini, H. H. L. M. Donkers (eds.). Springer. pp. 72–83. CiteSeerX 10.1.1.81.6817. ISBN 978-3-540-75537-1.

[Kocsis-Szepesvari-17] Kocsis, Levente; Szepesvári, Csaba (2006). "Bandit based Monte-Carlo Planning". In Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4212. Springer. pp. 282–293. CiteSeerX 10.1.1.102.1296. doi:10.1007/11871842_29. ISBN 3-540-45375-X.

[Gelly-et-al-18] Sylvain Gelly; Yizao Wang; Rémi Munos; Olivier Teytaud (November 2006). Modification of UCT with Patterns in Monte-Carlo Go (PDF). Technical report, INRIA.

[19] Chang-Shing Lee; Mei-Hui Wang; Guillaume Chaslot; Jean-Baptiste Hoock; Arpad Rimmel; Olivier Teytaud; Shang-Rong Tsai; Shun-Chin Hsu; Tzung-Pei Hong (2009). "The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments" (PDF). IEEE Transactions on Computational Intelligence and AI in Games. 1 (1): 73–89. CiteSeerX 10.1.1.470.6018. doi:10.1109/tciaig.2009.2018703. S2CID 15266518.

[20] Markus Enzenberger; Martin Mūller (2008). Fuego – An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search (PDF). Technical report, University of Alberta.

[21] "The Shodan Go Bet". Retrieved 2012-05-02.

[22] "Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning". Google Research Blog. 27 January 2016.

[23] "Google achieves AI 'breakthrough' by beating Go champion". BBC News. 27 January 2016.

[24] "Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo". Youtube. 9 March 2016.

[25] "Google AlphaGo AI clean sweeps European Go champion". ZDNet. 28 January 2016.

[26] Broderick Arneson; Ryan Hayward; Philip Henderson (June 2009). "MoHex Wins Hex Tournament" (PDF). ICGA Journal. 32 (2): 114–116. doi:10.3233/ICG-2009-32218.

[27] Timo Ewalds (2011). Playing and Solving Havannah (PDF). Master's thesis, University of Alberta.

[28] Richard J. Lorentz (2008). "Amazons Discover Monte-Carlo". Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. pp. 13–24. ISBN 978-3-540-87607-6.

[29] Tomáš Kozelek (2009). Methods of MCTS and the game Arimaa (PDF). Master's thesis, Charles University in Prague.

[30] Xiaocong Gan; Yun Bao; Zhangang Han (December 2011). "Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man". ICGA Journal. 34 (4): 209–222. doi:10.3233/ICG-2011-34404.

[31] Tom Pepels; Mark H. M. Winands; Marc Lanctot (September 2014). "Real-Time Monte Carlo Tree Search in Ms Pac-Man". IEEE Transactions on Computational Intelligence and AI in Games. 6 (3): 245–257. doi:10.1109/tciaig.2013.2291577.

[32] Mountain, Gwaredd (2015). "Tactical Planning and Real-time MCTS in Fable Legends". Retrieved 2019-06-08. .. we implemented a simulation based approach, which involved modelling the game play and using MCTS to search the potential plan space. Overall this worked well, ...

[33] Michael Buro; Jeffrey Richard Long; Timothy Furtak; Nathan R. Sturtevant (2009). "Improving State Evaluation, Inference, and Search in Trick-Based Card Games". IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009. Craig Boutilier (ed.). pp. 1407–1413. CiteSeerX 10.1.1.150.3077.

[cpr-34] Jonathan Rubin; Ian Watson (April 2011). "Computer poker: A review". Artificial Intelligence. 175 (5–6): 958–987. doi:10.1016/j.artint.2010.12.005.

[35] C.D. Ward; P.I. Cowling (2009). "Monte Carlo Search Applied to Card Selection in Magic: The Gathering" (PDF). CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press. Archived from the original (PDF) on 2016-05-28.

[36] István Szita; Guillaume Chaslot; Pieter Spronck (2010). "Monte-Carlo Tree Search in Settlers of Catan" (PDF). In Jaap Van Den Herik; Pieter Spronck (eds.). Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. Springer. pp. 21–32. ISBN 978-3-642-12992-6.

[chaslot2008-37] G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; B. Bouzy (2008). "Progressive Strategies for Monte-Carlo Tree Search" (PDF). New Mathematics and Natural Computation. 4 (3): 343–359. doi:10.1142/s1793005708001094.

[38] Bradberry, Jeff (2015-09-07). "Introduction to Monte Carlo Tree Search".

[39] Peres, Yuval; Schramm, Oded; Sheffield, Scott; Wilson, David B. (2006). "Random-Turn Hex and other selection games". arXiv:math/0508580.

[40] Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). "Finite-time Analysis of the Multiarmed Bandit Problem". Machine Learning. 47 (2/3): 235–256. doi:10.1023/a:1013689704352. S2CID 207609497.

[41] Bouzy, Bruno. "Old-fashioned Computer Go vs Monte-Carlo Go" (PDF). IEEE Symposium on Computational Intelligence and Games, April 1–5, 2007, Hilton Hawaiian Village, Honolulu, Hawaii.

[42] Althöfer, Ingo (2012). "On Board-Filling Games with Random-Turn Order and Monte Carlo Perfectness". Advances in Computer Games. Lecture Notes in Computer Science. Vol. 7168. pp. 258–269. doi:10.1007/978-3-642-31866-5_22. ISBN 978-3-642-31865-8.

[43] Ramanujan, Raghuram; Sabharwal, Ashish; Selman, Bart (May 2010). "On adversarial search spaces and sampling-based planning". ICAPS '10: Proceedings of the Twentieth International Conference on International Conference on Automated Planning and Scheduling. Icaps'10: 242–245.

[44] Ramanujan, Raghuram; Selman, Bart (March 2011). "Trade-Offs in Sampling-Based Adversarial Planning". ICAPS '11: Proceedings of the International Conference on Automated Planning and Scheduling. 21 (1): 202–209.

[45] "Lee Sedol defeats AlphaGo in masterful comeback - Game 4". Go Game Guru. Archived from the original on 2016-11-16. Retrieved 2017-07-04.

[46] § Wiechowski, Maddjiuk, J., "일반 게임에서의 플레이 전략의 자기 적응" (2010), 게임에서의 컴퓨터 인텔리전스 및 AI에 관한 IEEE 트랜잭션, vol: 6(4), pp.367-381, doi:10.1109/TCIAG.2013.CIAG.

[47] Drake, Peter (December 2009). "The Last-Good-Reply Policy for Monte-Carlo Go". ICGA Journal. 32 (4): 221–227. doi:10.3233/ICG-2009-32404.

[48] Seth Pellegrino; Peter Drake (2010). "Investigating the Effects of Playout Strength in Monte-Carlo Go". Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI 2010, July 12–15, 2010, Las Vegas Nevada, USA. Hamid R. Arabnia, David de la Fuente, Elena B. Kozerenko, José Angel Olivas, Rui Chang, Peter M. LaMonica, Raymond A. Liuzzi, Ashu M. G. Solo (eds.). CSREA Press. pp. 1015–1018. ISBN 978-1-60132-148-0.

[Gelly-Silver-49] Gelly, Sylvain; Silver, David (2007). "Combining Online and Offline Knowledge in UCT" (PDF). Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007. Zoubin Ghahramani (ed.). ACM. pp. 273–280. ISBN 978-1-59593-793-3. Archived from the original (PDF) on 2017-08-28.

[50] David Silver (2009). Reinforcement Learning and Simulation-Based Search in Computer Go (PDF). PhD thesis, University of Alberta.

[51] Rémi Coulom. "CLOP: Confident Local Optimization for Noisy Black-Box Parameter Tuning". ACG 2011: Advances in Computer Games 13 Conference, Tilburg, the Netherlands, November 20–22.

[52] Guillaume M.J-B. Chaslot, Mark H.M. Winands, Jaap van den Herik (2008). "Parallel Monte-Carlo Tree Search" (PDF). Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. pp. 60–71. ISBN 978-3-540-87607-6.{{cite book}}: CS1 maint: 여러 이름: 작성자 목록(링크)

[53] Markus Enzenberger; Martin Müller (2010). "A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm". In Jaap Van Den Herik; Pieter Spronck (eds.). Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009, Revised Papers. Springer. pp. 14–20. CiteSeerX 10.1.1.161.1984. ISBN 978-3-642-12992-6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[51]

[52]

[53]

Search

몬테카를로 트리 검색

네임스페이스

더

목차

역사

몬테카를로법

몬테카를로 트리 검색(MCTS)

작동 원리

순수 몬테카를로 게임 검색

탐색 및 이용

장점과 단점

개선점

「」를 참조해 주세요.

레퍼런스

참고 문헌

외부 링크

몬테카를로 트리 검색

학급	검색 알고리즘

Search

몬테카를로 트리 검색

역사

몬테카를로법

몬테카를로 트리 검색(MCTS)

작동 원리

순수 몬테카를로 게임 검색

탐색 및 이용

장점과 단점

개선점

「 」를 참조해 주세요.

레퍼런스

참고 문헌

외부 링크

「」를 참조해 주세요.