몬테카를로 트리 탐색(MCTS)의 개념과 구성 단계 [인공지능]

 

몬테카를로 트리 탐색은 의사결정을 위한 알고리즘 중에서 가장 유명한 것 중 하나입니다.

특히 포커나 바둑과 같은 보드 게임의 인공지능을 개발하는데 많이 이용되어 왔는데요.

그 유명한 알파고가 바로 MTCS를 이용해 코딩한 AI입니다.

바로 이 몬테카를로 트리 탐색의 개념적 이해와 구성 단계에 대해 알아보겠습니다.

 

반응형

---

 몬테카를로 트리 탐색은 경험적 탐색 알고리즘의 하나로서 무작위 탐색을 통해 최적의 답을 찾아가는 알고리즘이라 할 수 있다. 

쉽게 풀리지 않는 방정식의 해를 구하기 위해 하나하나 숫자를 대입해 본다거나, 원의 넓이를 구하기 위해 무작위로 수많은 점을 찍고 몇 개가 원의 면적 안에 존재하는지 세어 보는 등의 방법을 예시로 들 수 있다. 

즉, 어떤 특정한 공식 혹은 방정식을 모르거나 혹은 존재하지 않는 상황에서 최선의 결과를 산출해 내기 위해 사용하는 알고리즘이라 할 수 있으며 확률적으로 문제의 해결에 가까워지는 답을 찾아가는 알고리즘이라 할 수 있다.

 몬테카를로 트리 탐색 알고리즘을 구성하는 네 단계는 선택, 확장, 시뮬레이션, 역전파가 있다. 

선택은 선택할 수 있는 여러 개의 트리 중 하나를 선택하는 과정이다. 

만약 선택된 트리에서 답을 찾거나 게임을 종료시키지 못했다면 확장을 통해 자식 노드를 생성하여 선택한다. 시뮬레이션 단계에서는 생성된 자식 노드를 통해 게임의 결과를 도출할 때까지 진행한다. 

역전파 단계에서는 선택된 자식 노드에 시뮬레이션 결과를 반영하여 통계를 업데이트하게 된다. 

 

 이처럼 몬테카를로 트리 탐색 알고리즘을 적용하는 일에 있어서 자식 노드 중의 하나를 탐색의 목적에 맞게 효율적으로 선택하기 위한 전략이 있다면 탐색에 소요되는 시간과 자원을 줄일 수 있을 것이다. 

그러한 전략의 일환으로 크게 두 가지 개념이 있다. 하나는 탐사이다. 

탐사는 어떤 특정한 기준을 통해 미래 가능성을 측정하여 향후 우수한 결과를 가져올 것으로 예상되는 노드를 선택하는 것이다. 

다른 하나는 활용인데, 활용은 현재까지 탐색된 결과들 중에서 가장 뛰어난 노드를 선택하는 것이다.

 몬테카를로 트리 탐색 알고리즘의 애초 개념대로 게임이 종료될 때까지 무작위로 선택하고 탐색하는 방법을 쓰게 된다면 탐색 깊이가 깊어지고 정확한 해를 찾을 가능성이 매우 크지만 탐색에 필요한 시간과 자원이 많이 소요되게 된다. 이것을 해결하기 위한 선택 전략으로는 UCT 알고리즘이 있다. 이 알고리즘은 UCB1이라고 부르는 잘 알려진 신뢰도 상한에 대한 계산식이 최대가 되는 트리를 선택한 후 몬테카를로 트리 탐색을 실행하는 것이다.

 시뮬레이션 단계와 역전파 단계에 대해서도 더 효율적인 탐색과 정확한 해를 구하기 위한 전략들이 있다. 특정 기준에 따라 스스로 수를 선택하여 시뮬레이션하는 전략, 가치의 누적값과 방문 횟수를 각각의 노드에 저장하여 이의 평균을 사용하는 역전파 전략 등 다양한 방식으로 몬테카를로 트리 탐색 알고리즘을 목적에 맞게 효율적으로 운영할 수 있다.

 

2023.07.06 - [분류 전체보기] - 증권시장선, 베타계수와 균형수익률, 채권의 볼록성 [증권투자론]

증권시장선, 베타계수와 균형수익률, 채권의 볼록성 [증권투자론]

2023.07.19 - [분류 전체보기] - 수요공급곡선의 의미와 내용, 생활속의 경제

수요공급곡선의 의미와 내용, 생활속의 경제