미루고 미루다가 개념 한 번 정리해보는 것이 좋겠다고 생각이 들었다.
바로 몬테카를로 트리 탐색~!
배경 및 장점
몬테카를로 트리 탐색 배경 :
게임 트리에 mini-max 알고리즘을 적용할 때, 단말 노드의 형세를 판단하여 제대로 수치화하는 것은 쉽지 않다. 이러한 형세 판단 함수를 직접 만들지 않고, 무작위적인 시뮬레이션에 의해 형세의 유리한 정도를 결정하여 게임 트리를 구성하는 알고리즘이 생겼다.장점
형세 판단을 위한 휴리스틱이 필요 없을 뿐만 아니라 여러 게임 문제에서 성능이 뛰어나다는 것이 확인되었다. 단말 노드의 형세 평가를 하는 기본 아이디어는 단말 노드의 상태에서 무작위로 게임을 많이 해보는 것이다. 단말 노드의 형세가 좋다면 무작위로 게임을 하더라도 이기는 횟수가 많을 것이고, 그렇지 않다면 지는 횟수가 많을 것이다. 그래서 무작위로 게임을 하는 시뮬레이션을 많이 수행한 다음에 승률을 계산하여 단말 노드의 형세 판단값으로 사용하자는 것이다.
이뤄지는 과정
과정
선택 - 확장 - 시뮬레이션 - 역전파mini-max 알고리즘과는 다르게 일정 깊이까지 탐색을 하지 않고, 도움이 될 것 같은 부분을 점직적으로 확장해가며 게임 트리를 만들어간다.
(1) 선택 단계
게임 트리를 사용하는 루트 노드로부터 아래로 이동하기 위해 자식 노드를 순차적으로 선택하는 것을 말한다.
선택 기준
자식 노드를 선택할 때는 현재까지의 승률이 큰 것과 지금까지 방문횟수가 작은 것을 선호하도록 선택 우선순위를 정한다. UCB라는 식을 사용하여, 그 값이 가장 큰 수에 해당하는 노드를 따라 아래로 내려간다. 만약 UCB값이 가장 큰 수에 해당하는 노드가 아직 만들어져 있지 않으면 확장 단계로 진행한다.
(2) 확장 단계
선택 과정을 통해 마지막에 도달한 노드에 새로운 노드를 추가할 수 있다. 확장 단계로 진입하게 한 수가 특정 조건을 만족하면, 해당 수에 해당하는 노드를 추가한다.
(3) 시뮬레이션 단계
노드의 형세 평가를 위해 승패가 결정될 때까지 무작위로 게임을 해보는 단계이다. 이러한 시뮬레이션은 시간이 많이 걸리기 때문에, 게임 규칙에 맞는 수를 무작위로 선택해서 하거나 약간 똑똑하지만 빠르게 계산되는 방법으로 게임을 한다.
시뮬레이션을 시작한 노드에는 가능한 첫 수의 시도 횟수 및 승률을 기록을 해두어서 나중에 선택 단계와 확장 단계에서 이 정보를 이용할 수 있도록 한다.
(4) 역전파 단계
시뮬레이션 게임의 승패 정보를 현재 노드에서 루트 노드까지의 경로 상에 있는 노드들의 '이긴 횟수/전체 횟수' 정보에 반영한다.
시뮬레이션 단계에서 지면, 역전파 단계에서는 단말 토드부터 루트 노드까지 정보 상의 모든 노드의 이긴 횟수는 그대로 두고 전체 횟수 값만 1씩 증가시킨다.
마지막 정리
이와 같이 노드에서 무작위로 게임을 많이 해서 형세 평가 값을 확률적으로 결정하는 방식을 "몬테카를로 방법"이라 한다.
몬테카를로 트리 탐색 기법은 다믕 수를 결정하기 위한 방법으로, 루트 노드의 자식 노드들에 대한 평가값을 결정하여 그 중 평가값이 가장 좋은 노드의 수를 선택한다.
게임의 형세 판단을 위해 휴리스틱을 만들어 사용하는 대신, 몬테카를로 트리 탐색은 가능한 많은 수의 몬테카를로 시뮬레이션을 한다. 따라서 휴리스틱을 만들 필요가 없으며, 컴퓨터 자원만 충분하면 좋은 성능을 기대할 수 있는 장점이 있다. 한편, 몬테카를로 트리 탐색은 일정 조건을 만족하는 부분만 트리로 구성하고, 나머지 부분은 몬테카를로 시뮬레이션으로 대신한다.
-> 즉, 가능성이 높은 수들에 대해서만 노드를 생성하기 때문에, 게임 트리의 폭을 줄이면서 깊이를 늘리지 않아 탐색 공간이 줄어들고 메모리 요구량도 줄어드는 효과도 있다.
