[머신러닝 - 이론] MCTS (Monte Carlo Tree Search) (몬테카를로 트리 탐색)

1. 몬테카를로 방법이란?

 

 

몬테카를로 방법은 난수를 생성하여 시뮬레이션하는 방법입니다.

이러한 방법을 이용해서 트리를 탐색하는 MCTS(Monte Carlo Tree Search)알고리즘이 개발되었습니다.

 

몬테카를로 방법에서는 자신의 상태에서 다음 상태를 랜덤으로 정합니다. 즉 자식 노드 중에 랜덤 하게 선택을 하고, 

선택된 노드에서 플레이아웃을 생성해서 시뮬레이션을 합니다. 이때 승패가 정해질 때까지 랜덤하게 수를 선택해 나갑니다.

 

이후 승패가 결정되면 점수를 부여하고, 각 노드에서 승리 횟수/방문 회수를 갱신합니다.

마지막으로 승률이 가장 높은 수를 최종적으로 선택합니다.

 

즉, 

1. 자식 노드 중에 랜덤하게 선택
2. 선택된 노드에서 시뮬레이션, 승패가 정해질 때까지 랜덤 하게 선택
3. 승패가 정해지면 점수를 부여
4. 승리 횟수/방문 회수 갱신
5. 승률이 가장 높은 수를 최종 선택

이 됩니다.

 

무작위로 수를 선택하지만, 승률이 높으면 좋은 수일 가능성이 높다는 믿음이 바탕에 있고, 실제 실험을 통해 입증되었습니다.

 

 

미니맥스와 비교해서 미니맥스는 정교한 휴리스틱 함수를 통해 최적에 가까운 수를 찾지만,

MCTS는 랜덤하게 수를 두고, 승률이 높은 수를 최적에 가까운 수로 간주합니다.

다른 알고리즘은 BFS, DFS를 통해서 계산하지만, MCTS는 게임 종료 상태까지 가보기 때문에 점수 계산이 쉽습니다.

또한 허용된 자원만큼 시뮬레이션을 돌릴 수 있는 융통성, GPU 병렬 처리를 통해 시뮬레이션 수를 획기적으로 늘릴 수 있습니다.

즉 샘플링이 많으면 승률에 대한 정확도가 올라갑니다.

 

 

여기까지가 몬테카를로 트리 탐색의 기본 원리입니다만, 제대로 성능을 발휘하기 위해서는 몇 가지를 추가로 고려해야 합니다.

 

 

바로 선택, 확장, 시뮬레이션, 역전파입니다.

 

 

 

---

2. MCTS의 동작 특성

 

 

MCTS는 본인의 차례가 될 때마다 수많은 시뮬레이션을 만들고 최적의 수를 선택하기 때문에 많은 시간을 사용합니다.

이때 가장 대표적인 방법이 GPU를 사용해서 병렬적으로 처리하는 방법이 있습니다.

 

또한 MCTS는 가끔 실수를 할 수 있는데, 이는 시뮬레이션을 통한 추정한 승률을 기반으로 하기 때문입니다.

극복 방안으로는

• 시뮬레이션 개수를 늘려서 추정치를 정확하게 -> 계산 시간 늘어남
• 게임 규칙을 코딩하여 위험한 수를 미연에 방지
• 복사본끼리 겨루는 자율 플레이(self play)를 통해 학습

 

---

3. 자율 플레이 (self-play)

 

 

복사본 프로그램끼리 겨루는 방식입니다.

마치 GAN과 비슷한 방식입니다. 이때 자율 플레이와 강화 학습이 결합하면 강력한 게임 인공지능이 완성됩니다.

이는 알파고의 주요 전략입니다.

 

알파고는 딥러닝과 MCTS을 결합하여 만들었습니다.

알파고는 승리하기 위해서 최적 정책을 사용하고, 최적 정책은 정책 신경망을 따로 제작해서 알아냅니다.

 

이때 정책 신경망은 총 세 개가 있습니다.

 

첫 번째로는 SL(supervised learning) 정책 신경망이 있습니다.

이는 기존의 프로 기사들이 축적해놓은 정보를 집합으로 활용하는 것입니다.

하지만 이는 어떤 상태에서 다음 수를 예측하는 방식으로 학습되었기 때문에 성능에 한계가 있습니다.

 

두 번째로는 RL(강화 학습) 정책 신경망이 있습니다.

self-play를 통해 SL 정책 신경망을 개선합니다.

 

마지막으로 가치 신경망입니다.

 

알파고는 이러한 신경망과 MCTS를 사용해서 인간을 넘어섰습니다.

 

 

알파고 제로는 자율 학습만 사용하여 알파고를 100% 승률로 이겼습니다..

 

 

감사합니다.

 

 

지적 환영합니다.