바둑 관련 기사와 몬테카를로 트리 탐색(MCTS)

https://www.ilemonde.com/news/articleView.html?idxno=22166

지금은 맞고 그때는 틀리다? ― 이세돌식 서사의 불온함(1) - 르몽드 디플로마티크

 

"바둑 분석가 데이비드 오메로드는 79~87수 일대의 오류가 몬테카를로 트리 탐색(MCTS) 기반 프로그램에서 전형적으로 나타나는 실수 패턴이라고 분석했다."

 

 

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

 

경우의 수가 무한에 가까울 때, 어떻게 최적의 수를 찾을 것인가?

 

바둑처럼 한 수 한 수 둘 때마다 경우의 수가 기하급수로 늘어나는 경우 Bruteforce 불가능

 

MCTS : 완벽한 전체 탐색을 포기하고 확률에 기반하여 최적에 가까운 답을 내리자 (새로운 탐색 패러다임)

휴리스틱

불확실성을 확률적으로 관리

 

선택 > 확장 > 시뮬레이션 > 역전파

현재 상태에서 특정 경로를 예측 > 경로 끝에 새로운 탐색지점 만들어봄 > 시뮬레이션으로 잠재가치 평가 > 평가결과를 방문한 노드에 반영 => 경로의 가치를 평가하여 정확도를 높여가기

시뮬레이션: 확장 단계에서부터 게임 종료까지를 빠르게 진행시켜보기 (playout, roleout) 그래서 잠재가치를 평가

역전파 : 시뮬레이션 결과를 상위노드에 전파하여 정보를 업데이트. 이 길로 가보니까 이렇더라. 통계 갱신.

 

- 정책Policy : 트리 검색의 '폭'을 제한

- 가치Value : 트리 검색의 '깊이'를 제한

 

Tree Policy : child node를 선택하는 전략

이용-탐사 딜레마 exploitation-exploration dilemma : 당장 승률이 좋은 노드만 계속 선택해서 이용exploitation하지 않고 위험을 무릎쓰고 탐사해볼 필요가 있다.

알파고의 경우 이용과 탐사의 균형을 맞추기 위해 UCT를 사용했다고 함

 

유리한 경우

1. 바둑처럼 탐색공간이 너무 커서 모든 경우의 수를 다 따져보는 게 거의 불가능

2. 게임의 끝까지 빠르게 시뮬레이션 해볼 수 있는 모델이 필요

3. 100% 정답이 아니라 good enough 솔루션 찾는 것이 목표

4. 시뮬레이션을 돌릴 수 있는 컴퓨팅 자원의 확보

"초반에 오류가 나기는커녕 바둑 인공지능은 초반에 강력하다. 그 이유는, 착점의 가짓수가 많더라도 정책망이 강한 사전분포(prior)를 제공하고 가치망이 일반화된 평점을 주기 때문이다. 또 이 둘이 고급트리탐색 ‘몬테카를로 트리서치(MCTS)’와 결합되어 연산으로 구현된 직관을 실전에서 재현하기 때문이다. 말하자면, 이세돌은 직관을 발휘하는 존재와 바둑을 둔 것이다. (김수광, 2026, 3부)"

 

AlphaGo의 경우 MCTS에 신경망 2개를 붙임

1. Policy Network : 사람이 둘 법한 수를 확률로 학습, 어떤 노드를 확장할 때 모든 수를 균등하게 탐색하지 않고 정책망을 통해 좋은 수를 더 많이 탐색. 정책망이 준 확률(prior)

2. Value Network : value network로 바로 점수 계산 가능. 이쪽이 rollout 보다 안정적(속도/정확)

 

정책망이 강한 사전분포

가치망이 일반화된 평점을 줌

> 해당 바둑 인공지능의 특징

 

몬테카를로 트리 서치(Monte Carlo Tree Search, 이하 MCTS)는 MDP(Markov Decision Process)를 해결하는 방법의 한 종류

출처 : https://gusals1620.tistory.com/3