[인공지능] Monte Carlo Tree Search 요약

플레이어의 이익이나 손실은 정확히 상대방들의 이익이나 손실과 균형을 이룬다.

 

전통적인 전략 - MinMax

• 각 상태에서 상대방의 최대 보상을 최소화하려고 시도 (나시 균형)
• 철저한 탐색

 

밴딧 기반 메소드

• K개의 행동/움직임 중 선택
• 최상의 움직임을 계속해서 선택하여 누적 보상을 극대화해야 함 • 밴딧 기반 메소드는 가장 불확실한 가지를 **탐색(Exploration)**하고 가장 유망한 가지를 **개발(Exploitation)**하는 효율적인 트레이드오프로 알려져 있어서 트리 탐색에 사용된다. • 상한 신뢰 구간 (UCB) 밴딧 알고리즘은 트리 탐색에 적용되며 UCT (트리에 적용된 상한 신뢰 구간)라고 한다.

MCTS overview

부분 탐색 트리를 반복적으로 구축

반복

• 가장 긴급한 노드
  • 트리 정책
  • 탐색/개발
• 시뮬레이션
  • 자식 노드 추가
  • 기본 정책
• 가중치 업데이트

 

MCTS의 발전

Kocsis와 Szepesvari, 2006

밴딧 기반 메소드를 형식적으로 설명

보상을 근사화하기 위해 시뮬레이션을 수행

MCTS가 MinMax 솔루션으로 수렴함을 입증

 

상한 신뢰 구간 (UCB)

• 상한 신뢰 구간의 optical arm을 찾음
• UCT는 각 탐사된 노드에 UCB 알고리즘을 사용

상한 신뢰 트리 (UCT)는 몬테 카를로 탐색을 위한 밴딧 알고리즘의 응용이다. (USB1)

 

알고리즘

Selection(선택)

• 루트 노드부터 좋은 자식 노드를 선택한다.
  • 루트 노드에서 시작한다.
    • 트리 정책을 기반으로 자식 노드를 선택한다.
  • 재귀적으로 적용 - 트리를 따라 내려간다.
    • 확장 가능한 노드에 도달하면 중단한다.
    • 확장 가능한 노드: 종단이 아니고 탐사되지 않은 자식을 가지고 있는 노드

Explosion(확장)

• L이 종단 노드가 아니라면 하나 이상의 자식 노드를 생성하고 하나를 선택한다. (C)

Simulation(Rollout)

• C에서 결과가 얻어질 때까지 C에서 시뮬레이션을 실행한다.
• 선택된 경로의 시뮬레이션을 실행한다.
• 시뮬레이션 종료 지점의 위치를 얻는다.
• 본 정책은 시뮬레이션을 실행하는 방식을 결정한다.
• 게임 결과는 가치를 결정한다.

Backpropagation(역전파)

• 저장된 경로를 역방향으로 이동한다.
• 노드의 가치
  • 그 경로를 따라 내려가는 이점을 대표한다.
• 값은 게임 결과에 따라 업데이트된다.
  • 시뮬레이션된 게임이 어떻게 끝나는지에 따라 값이 업데이트된다.

Monte Carlo Alogorithm

 

MCTS의 정책들

• 트리 정책
  • 리프 노드 선택/생성
  • 선택 및 확장
  • 밴딧 문제!
• 기본 정책
  • 게임을 끝낼 때까지 게임을 진행
  • 시뮬레이션
• 최상의 자식 선택
  • 최댓값(Max) (가장 높은 가중치)
  • 견고한(Robust) (가장 많은 방문)
  • 최댓값-견고한(Max-Robust) (두 가지, 없으면 반복)

자식 노드 선택: Multi-Arm 밴딧 문제

각 자식 선택을 위한 UCB1

 

UCT

UCT 공식

 

 

• n: 현재 (부모) 노드가 방문된 횟수
• nj: 자식 j가 방문된 횟수
• Cp: 양수인 상수 (> 0)
• Xj: 이 위치를 선택한 경우의 평균 보상 [0,1]

 

MCTS의 장점과 단점

Aheuristic

• 도메인 특정 지식이 필요하지 않음
• 휴리스틱이 존재하는 경우 다른 알고리즘들이 더 잘 동작할 수 있음
  • 체스의 경우 MinMax
  • 체스는 트리 크기를 줄일 수 있는 강력한 휴리스틱을 가지고 있기 때문에 MinMax가 더 나음

Anytime

• 언제든지 MCTS 실행을 중지할 수 있음
• 최상의 행동 반환

Asymmetric

• 더 유망한 노드를 우선으로 하는 특징을 가짐

UCB for a tree

UCB 공식

• Vi: 이 노드 아래의 모든 노드의 평균 보상/가치
• N: 부모 노드가 방문된 횟수
• Ni: 자식 노드 i가 방문된 횟수

Multiplayer MCTS

• MinMax 탐색의 중심 원칙:
• 탐색하는 플레이어는 자신의 보상을 최대화하는 움직임을 찾으려 하며, 상대방은 이를 최소화하려고 한다.
• 두 플레이어의 경우: 각 플레이어는 자신의 보상을 최대화하려고 합니다.
  • 그러나 두 플레이어 이상의 경우에는 반드시 사실이 아니다.
    • 플레이어 1의 손실과 플레이어 2의 이익이 반드시 플레이어 3에게 이익이 되는 것은 아닙니다.
• 2명 이상의 플레이어는 zero-sum 게임을 보장하지 않습니다. • 모든 플레이어 간의 보상/손실을 완벽하게 모델링하는 방법은 없다. • 간단한 제안 - max^n

아이디어

• 노드는 보상 벡터를 저장한다.
• 그런 다음 UCB는 현재 플레이어에 따라 적절한 벡터 구성 요소를 사용하여 값을 최대화하려고 한다.
• 벡터의 구성 요소는 현재 플레이어에 따라 사용된다.
• 그러나 이러한 구성 요소가 정확하게 어떻게 결합되는 것일까?
• Cazenave는 다중 플레이어 바둑에 UCT의 여러 변형을 적용한다.
• 플레이어들이 공통적인 적을 가질 수 있기 때문에 "연합(coalition)"의 가능성을 고려한다.
• max^n을 사용하지만 연합 멤버에게 적대적일 수 있는 움직임을 고려한다.
• scoring을 변경하여 연합 돌을 플레이어 자신의 것처럼 포함시킨다.