Monte-Carlo 알고리즘
난수를 사용하여 함수의 값을 확률적으로 계산하는 알고리즘을 부르는 용어. 계산하려는 값이 닫힌 값으로 표현되지 않거나 복잡한 경우, 이를 근사적으로 계산하기 위해 사용된다. Monte-Carlo 알고리즘을 적용해 원의 넓이를 구하는 경우, 원과 원에 내접하는 정사각형을 그리고 정사각형 안에 많은 수의 점을 찍어 점이 원의 내부에 찍힌 확률을 계산하면 원의 넓이를 근사적으로 구할 수 있다. Monte-Carlo 알고리즘은 임의 시행의 횟수를 증가시킬 수록 정확도가 증가한다.
Monte-Carlo Tree Search(MCTS)란?
MCTS는 최선의 선택(optimal decision)을 찾는 방법이다. MCTS는 의사 결정을 위한 체험적 탐색 알고리즘으로 수식을 만들어 해를 찾기가 쉽지 않을 때 주로 사용되는데, 예를 들어 게임에서 최선의 수를 찾기 위한 방법으로 활용할 수 있다. MCTS를 게임에 적용한다면, 게임에서 두는 각각의 수가 노드이고 게임의 전체 과정은 각 수의 연속인 트리로 표현된다. 각 노드에는 승률이 기록되어 있으며, 게임에서 최선의 수를 찾는 과정은 가장 승률이 높은 노드를 찾아가는 것으로 근사될 수 있다. MCTS는 각 노드 별 승률을 계산하고 승률이 높은 노드를 찾아가는 과정이라 할 수 있다.
트리 탐색의 문제점은 자식 노드가 많아지면 탐색에 시간이 굉장히 많이 걸린다는 점이다. 자유도가 높은 게임의 경우 자식 노드(다음에 둘 수 있는 수)가 굉장히 많아져 모든 결과를 살펴보고 노드 별 승률을 계산하는 것이 거의 불가능하다. MCTS는 전체 가능성을 모두 탐색하지 않고 다수의 random simulation을 통해 게임 결과를 구하여 이를 노드의 승률에 적용하는 알고리즘으로, 자유도가 높은 게임에서도 높은 효율성을 보여준다. MCTS 알고리즘은 Selection, Expansion, Simulation, Back propagation 네 가지 단계로 이루어진다.
- Selection (선택): 루트 R에서 시작하여 연속되는 자식 노드를 따라 내려가 노드L을 선택한다.
- Expansion (확장): 노드L에서 게임이 종료되지 않은 경우, 새로운 자식 노드C를 생성하거나 기존의 자식 노드 중 하나를 노드C로 선정한다.
- Simulation (시뮬레이션): 노드C를 대상으로 random playout을 수행한다
- Back propagation (역전파): playout의 결과를 노드 C에서 루트 R까지 업데이트한다.
MCTS를 적용하기 위해서는 다음과 같은 3가지 조건을 만족해야 한다고 한다.
- 게임의 최대/최소 점수값이 있음
- 게임의 규칙이 정해져 있으며, 게임이 완전 정보 게임이어야 함
- 게임의 길이가 제한되어 비교적 빨리 게임이 끝나야 함
댓글 없음:
댓글 쓰기