탐색 - 몬테카를로 트리 탐색(Monte Carlo tree search, MCTS)

오늘부터 인공지능에 대해 공부를 해보겠습니다.

들어보셨을 수도 있고 한 탐색 기법인,

몬테카를로 트리 탐색 기법에 대해 알아보겠습니다.

 

우선 탐색기법부터 정의를 살펴보겠습니다.

탐색이란? - 컴퓨터가 문제를 해결하기 위하여 스스로 해답에 이르는

경로를 찾아가는 과정이다.

라고 합니다.

 

알파고가 딥러닝만 가지고 바둑을 제패한건 아니고

이 인공지능 알고리즘 중, 탐색 알고리즘이 적용되었다고 합니다.

 

사실 상, 모든 경우의 수를 탐색하기에는 하드웨어 상, 굉장히 높은

복잡도를 요구하게 됩니다.

 

그래서 샘플링을 해서 가장 가능성 있는 몇개의 수만을 추려낸 후에

이들 수에 대해서만 탐색을 합니다. 즉, 샘플링을 하는거죠

 

다음 그림을 보고 얘기를 한번 드려보겠습니다.

 

몬테카를로 트리 서치(MCTS)기법이라고 합니다.

이 알고리즘은 총 4단계로 이루어집니다.

 

https://ko.wikipedia.org/wiki/%EB%AA%AC%ED%85%8C%EC%B9%B4%EB%A5%BC%EB%A1%9C_%ED%8A%B8%EB%A6%AC_%ED%83%90%EC%83%89

 

1단계 선택(Selection)

루트 R에서 시작하여 연속적인 지식 노드를 선택해 내려가

마디 L에 이른다. 몬테카를로 트리 탐색의 본질인, 게임 트리를

가장 승산 있는 수로 확장시킬 자식 노드를 선택하는 방법은

아래 난을 참고한다.

 

2단계 확장(Expansion)

노드 L에서 승패를 내지 못하고 게임이 종료되면, 하나 또는

그 이상의 자식 노드를 생성하고 그 중 하나의 노드 C를 선택한다.

 

3단계 시뮬레이션(Simulation)

노드 C로부터 무작위의 플레이아웃을 실행한다.

 

4단계 역전달(Backpropagation)

플레이아웃의 결과로 C에서 R까지의 경로에 있는 노드들의 

정보를 갱신한다.

 

무슨 말인지 이해하셨나요??

저는 선택까지만 알겠는데 그 뒤는 도통 모르겠습니다.

 

그래서 다시 정리해봤습니다.

 

쉬운버전

여기서 자꾸 노드라는 얘기가 나오는데, 노드는 저 위 그림 보시면 원 그자체를 얘기합니다.

통신 또는 영상처리 쪽에서 많이 쓰이는 용어구요(다른 쪽도 아마 쓰일건데

잘모르겠네요)

 

노드에 대한 간단한 개념설명을 드려볼게요.

소스노드(또는 원천노드) -> 데스티네이션 노드(또는 목적노드)라고 표현을 많이합니다. 

 

소스노드는 저희가 지금 들고 있는 휴대폰

데스티네이션노드는 제가 전화를 한 상대방의 휴대폰이라고 생각하시면 됩니다.

즉 노드는, 매개체? 인데 확률을 가진 매개체 라고 이해를 하시면 됩니다.

이거는 인공지능 공부하면서 계속 다뤄보겠습니다.

최대한 쉽게쉽게 저도 이해하면서 써보도록 하겠습니다.

지금 잘 이해가 안되셔도 좋습니다. 계속 하다보면 이해가 될거니깐요^^

 

다시 4단계 설명을 좀 더 쉽게 설명해보겠습니다.

 

1. 선택(Selection)에서는 뿌리 노드에서 시작하여 현재까지 펼쳐진 트리를 선택한다.

- 여기서 뿌리노드는 최상단에 있는 11/21이라는 숫자가 들어간 노드를 뜻합니다

 

2. 확장(expansion)에서는 만약 그렇게 선택한 트리에서 게임의 종료가 되지 않은 경우에는

하나 이상의 자식노드를 생성하여 하나를 선택한다.

- 뿌리노드가 밑에 3개의 노드를 만들었죠? 7/10, 3/8, 0/3 이 3개의 노드가

뿌리노드의 자식노드입니다. 밑에도 마찬가지겠죠. 한 노드를 기준으로 자기 위에 노드는

부모노드, 자기 밑에 있는 노드는 자식노드라고 합니다.

 

3. 시뮬레이션(Simulation)에서는 확장에서 선택된 자식노드에서 게임의 시뮬레이션을

돌려 게임 종료가 될 때까지 시행한다.

 

4. 역전파(Backpropagation)에서 선택된 자식노드에 시뮬레이션 결과를 반영한다.

시뮬레이션 결과에 기초하여 기록된 값은 방문한 횟수와 시뮬레이션 결과로 나온

점수를 포함해야 한다.

 

-> 오목을 예로 들게요. 시뮬레이션을 하면 이제 게임이 종료될 때 까지 상황들을 

축적을 하는겁니다. 내가 어디에 어떤 수를 두면, 상대방이 또 수를 두고 이렇게 나가다가

게임이 끝나잖아요? 이게 시뮬레이션이고, 이 상황을 역전파해서 뿌리노드에게

값을 전달해줍니다. 그럼 뿌리노드는 하나의 상황을 더 알게된거죠?

 

이런 식으로 MCTS에서는 몇개의 상황을 추출해서 가지고 있는 정보로

상대편이 어떤 수를 두면, 나는 이런수를 두었을 때 가장 승률이 높다라고 판단을 해서

그 수를 두게 됩니다.

 

어렵죠? 쉽나요?

 

그림을 그려서 표현하면 조금 더 쉬울수도 있겠네요.

글로 쓰기가 상당히 쉽지는 않은데요. 

나중에 영상으로 제가 설명을 드리는 시간을 꼭 가져보도록 하겠습니다.

 

긴 글 읽어주셔서 감사합니다.

공부 화이팅입니다~!