11장 강화학습과 게임지능

11.6 몬테카를로 트리 탐색 알고리즘

  • 게임에 몬테카를로 방법을 적용하려고함
  • UCB(Upper confidence bound)
    • 탐사와 탐험을 효과적으로 조절하는 사용되는 공식
    • 몬테카를로 방법의 핵심 연산으로 사용함
  • 몬테카를로 트리 탐색 알고리즘(Monte Carlo tree research, MCTS)
    • 위의 아이디어가 총 정리된 알고리즘

11.6.1 MCTS 기본원리

  1. selection
    • 모든 경우의 수 중 1개를 선택하는 행위
    • UCT 제어방법을 통해 랜덤하게 선택
  2. simulation
    • 1번에서 선택된 상태에서 출발해 랜덤하게 수를 선택하여 승/패까지 진행
    • 완전한 랜덤
    • playout : 승패가 정해질 때까지 게임을 진행하는 일
    • w/v : 점수 / 방문한 횟수 업데이트 (승1패0무0.5)
    • 이를 반복
  3. 선택전략(MCTS)
    • 위의 과정을 통해 얻은 정보를 통해 최적의 수를 선택
    • 어떻게 선택할 것인지에 대한 선택전략이 중요!
    • 예시 : w/v 비율이 높은 경우의 수, 방문 횟수가 가장 큰 경우의 수 …
  4. MCTS의 특징
    • simulation 단계에서 랜덤하게 수를 선택 -> huristic 함수가 필요없음
    • playout이 매우 빨라 많은 sampling 수행

    • sampling 수가 많을 수록 최적의 수 찾을 수 있음

        제대로된 성능을 발휘하기 위해 추가 방안이 필요

11.6.2 네 단계 처리 절차

  • 선택, 확장, 시뮬레이션, 역전파
  1. 선택
    • 이미 탐색된 트리에서 최적의 경로를 선택하는 과정
    • root에서 시작하여 완전 확장된 노드 n에 UCT를 적용하며 트리를 내려감
    • 완전 확장이 되지 않는 노드를 만나면 노드를 t로 설정하고 확장단계로 넘어감
    • 탐사와 탐험의 균형이 중요
      • UTC(upper confidence tree)
      • UTC 공식을 통해 탐사와 탐험의 균형을 유지함
    • 완전 확장된 노드 (fully expanded node)
      • 모든 자식 노드가 한 번 이상 방문된 노드를 의미
      • 표시방법 : “w/v”
      • 완전 확장된 노드의 자식 노드는 모두 “w/v”를 가지고 있음
      • UCT 공식을 이용해 자식 노드 중 하나를 선택
    • UTC 공식
    • \[UCT(n, n_i) = \frac{w(n_i)}{v(n_i)} + \gamma \sqrt{\frac{\log(v(n))}{v(n_i)}}\]
      • $n$ : 완전 확장된 노드
      • $n_i$ : $n$의 자식 노드
      • $v(n)$ : n 노드를 방문한 횟수
      • ${v(n_i)}$ : 자식 노드를 방문한 횟수
      • ${w(n_i)}$ : 자식 노드가 승리한 횟수
      • $\gamma$ : 첫 번째, 두 번째 항의 중요도를 조절하는 가중치 계수 (보통 $\sqrt{2}$, 상황에 따라 설정) - 값이 크면 2번째 항인 탐험을 강조, 값이 작으면 1항인 탐사를 강조
      1. \[\frac{w(n_i)}{v(n_i)}\]
        • w/v, 승률을 의미
        • 승률이 높은 자식 노드일 수록 큰 값 (w/v)
        • 즉, 승률이 높을 수록 값이 커지기 때문에 승률이 높은 자식 노드의 선택확률이 높아짐 “탐사 항”을 의미
      2. \[\gamma \sqrt{\frac{\log(v(n))}{v(n_i)}}\]
        • n 노드를 방문한 횟수 / 자식 노드를 방문한 횟수
        • 적게 방문된 자식노드일 수록 큰 값
        • 즉, 적게 방문 될수록 값이 커지기 때문에 적게 방문된 노드의 선택확률이 높아짐 “탐험 항”을 의미
        • 여기서 값이 커지는 것은 최선의 행동임을 의미
  2. 확장
    • 선택 단계에서 도달한 노드에서 추가적인 자식 노드를 생성
    • 선택 단계에서 결정한 단말 노드 t의 자식 중에서 random하게 하나를 선택
    • 선택된 자식을 위해 노드 c를 생성하여 t와 연결 시켜줌
    • 즉, 선택단계에서 정보를 모르는 노드까지 간 후, 트리를 이어나가기 위해 새로운 자식노드를 생성해줌
  3. 시뮬레이션
    • 새로 확장된 노드에서 게임을 무작위로 끝까지 진행하여 결과를 예측
    • 노드 c에서 시작해 종료 상태(승, 패)까지 진행하여 플레이 아웃을 하나 만듦
    • 게임을 진행할 때 완전 랜덤일 수도 있고 신경망을 이용할 수 도 있음 (바둑의 경우 신경망 사용)
  4. 역전파
    • 시뮬레이션 결과를 사용하여 트리의 상위 노드들의 통계를 업데이트
    • 노드 c에서 시작하여 트리를 역으로 타고 올라가면서 root 노드까지 이어지는 모든 노드의 v를 1만큼 증가시킴
    • w값은 노드 선택자(사람, 인공지능)의 승패에 따라 다른 값으로 업데이트 해야함. 승리한 쪽의 노드만 1 증가시키고 무승부면 0.5씩 증가