Learn And Earn

이번 포스팅에서는 MCTS에 대해서 본격적으로 알아보겠습니다. MCTS는 기본적으로 state이 주어질 때 그에 맞게 action을 선택하는 알고리즘입니다. 하지만 기본적으로 이 알고리즘은 learning algorithm이 아닌, search algorithm입니다. 하지만 "learning 하는 것 같이" 지식을 축적해가면 보다 더 있음직한 미래의 경우의 수만 살펴보게 됩니다. 이와 같이 어떻게 추려나가 효율적인 선택을 하는지 본론에서 보겠습니다. 개요 - MCTS의 한 loop를 구성하는 4개의 연산들 MCTS 알고리즘의 한 호출은 기본적으로 제한된 resource가 모두 소모될때까지 아래의 연산들을 차례로 연산해가며 partial tree를 계속해서 구성해 나갑니다. Selection Expans..

이번 포스팅에서는 Monte Carlo Tree Search 알고리즘에 대해서 알아보겠습니다. 이 알고리즘은 2016년, 알파고가 이세돌 선수에게 승리를 쟁취하는데에 기여한 알고리즘 중 하나입니다. 이 MCTS 알고리즘을 이용해서 이 player, 즉 알파고가 결정을 내려나갔다는 건데요, 기본적으로 바둑이라는 게임은 인공지능이 정복하기 어려운 게임 중 하나로 평가되는 게임이었습니다. 그럼에도 불구하고 승리를 가능케 한 MCTS 알고리즘은 어떠한 강점이 있기에 그런 어려운 문제를 풀어냈을까요? 먼저 스포일러를 하자면, "있음직한 게임의 경우의 수를 시뮬레이션을 통해 미리 헤아려보고, 그들을 토대로 하여 가장 합리적으로 보이는 수를 선택하는 것입니다. 어떤 문제를 해결해주는 알고리즘인가요? Monte Car..