[인공지능] Quarto Team Project - MCTS Parallelization

https://boardgamegeek.com/boardgame/681/quarto

Quarto

 

Quarto

 

(자세한 룰은 위 게시물을 참고)

 

Team project

 

인공지능 수업에서 Quarto를 이용해서 팀들끼리 리그전을 합니다.

성적이 좋은 팀이 좋은 점수를 받는 식의 프로젝트입니다.

 

이 게임에는 시간 제한 5분이 존재하고,

5분을 넘는다면 기권패가 됩니다.

 

그렇기 때문에,

시간과 정확도 사이의 적절한 균형을 찾는 것이 key입니다.

 

해공간의 크기는 16*16*15*15* ... * 1이기 때문에,

상당히 크다고 볼 수 있습니다.

 

Monte Carlo Tree Search

 

이 게임은 2 Players game이고, 내쉬 평형을 이루는 zero-sum게임이기 때문에 MCTS가 적당하다 판단했습니다.

2024.11.04 - [분류 전체보기] - [인공지능] Game Tree Search (2) - Monte Carlo Search

[인공지능] Game Tree Search (2) - Monte Carlo Search

 

일반적인 UCB로는 다른 팀들과 구별할 수 없다고 판단했기 때문에,

다른 팀들과 차이점을 주기 위한 다양한 의견들이 나왔습니다.

• UCB에서 적절한 C값 찾기
• 최종 node를 선택하는 기준의 변경 → 비교적 초반에는 simulation의 정확도를 신뢰할 수 없기 때문에 most visited된 node를 선택하고, 후반이되면 simulation의 정확도를 신뢰할 수 있기 때문에 most highest value를 갖는 node를 선택하는 식의 기준을 게임의 진행에 따라 변경하는 전략
• 병렬화

 

Paper

 

https://dke.maastrichtuniversity.nl/m.winands/documents/multithreadedMCTS2.pdf

위 논문은 MCTS의 병렬화의 방식 3가지를 설명하는 paper로 이를 공부하기로 결정했습니다.

 

Abstract.

 

MCTS는 최상 우선 탐색의 새로운 버전으로,

특히 바둑에서 놀라운 성과를 보여줬습니다.

 

하지만, MCTS의 병렬화는 MCTS의 성능을 끌어올릴 수 있는 좋은 방법으로,

이 paper는 병렬화의 3가지 방법을 설명하고있습니다.

 

이때 해당 paper가 제시하는 tree parallelization의 좋은 성능을 위해서는 2가지가 필요하다 주장합니다.

• local mutext
• virtual loss

 

따라서 제시하는 3가지 방법의 병렬화를 13x13과 9x9의 바둑에서의 성능을 비교합니다.

 

Introduction.

 

지난 10년동안 2 players game을 지배해온 방법론은 alpha-beta 방식이었습니다.

2024.11.04 - [[학교 수업]/[학교 수업] 인공지능] - [인공지능] Game Tree Search (1) - MiniMax Algoritm

[인공지능] Game Tree Search (1) - MiniMax Algoritm

 

하지만, 2006년에 등장한 MCTS는 바둑의 영역에서 500등 안에 랭크에 등록되는 등의 놀라운 성과를 보였습니다.

그렇기 때문에 더 좋은 성과를 보일 수 있는 병렬화 방법이 대두되었는데,

Cazanave와 Jouandueu의 연구를 통해 leaf parallelization과 root parallelization 이 발명되었습니다.

 

이 paper에서는 3가지의 병렬화 방법 (leaf, root, tree) 을 제시합니다.

이 3가지 방법을 2가지의 평가 지표로 비교합니다.

• Game-Per-Second (GPS) speedup measure → 이는 속도의 향상을 나타냅니다.
• strength-speedup measure → 이는 플레이 강도의 향상을 나타냅니다.

연구 환경은 16-cores를 사용하는 환경으로,

16 Threads까지는 true parallelization 이 가능한 환경입니다.

 

Monte-Carlo Tree Search

 

MCTS는 평가 함수가 존재하지 않는 최상 우선 탐색 방법입니다.

이는 랜덤한 상태 공간의 탐색을 기반으로 합니다. 이전 결과에 영향을 받아 게임 트리가 점점 성장하는 알고리즘입니다.

 

MCTS는 4가지의 전략 페이즈가 있습니다.

• Selection phase
• Expansion phase
• Simulation strategy
• Backpropagation strategy

위 4가지의 페이즈는 앞서 올렸던 MCTS관련 포스트를 참고할 수 있습니다.

 

모든 주어진 시간이 끝나면, MCTS는 가장 많이 탐색되었던 node를 다음 움직임으로 선택합니다.

이는 언제나 MCTS의 탐색을 종료시킬 수 있음을 보여줍니다.

하지만, 탐색 시간이 길면 길수록, 프로그램의 플레이는 더욱 강력해짐을 같이 고려해야합니다.

 

Parallelization of MCTS

 

이 paper에서는 symmetric multiprocessor (SMP) computer를 사용했습니다.

이는 한 프로세스에서는 하나의 쓰레드만을 가지는 특징이 있습니다.

SMP는 낮은 지연으로 공유된 메모리에 접근할 수 있다는 장점이 있습니다.

 

이런 병렬 프로세스 환경에서는 mutex가 필수적입니다.

데이터가 충돌을 일으킬 수 있기 때문입니다.

 

하지만 MCTS의 phase에서 simulation phase만 공유된 정보를 사용하지 않습니다.

즉, simulation phase는 독립적으로 실행할 수 있다는 의미입니다.

 

이러한 MCTS의 특징을 이용해서 MCTS의 병렬화를 수행할 수 있습니다.

 

Leaf parallelization

 

leaf 병렬화는 구현하기 쉬운 병렬화 방법중 하나입니다.

 

오직 하나의 thread에서만 tree를 관리하며,

leaf 노드에 도달할 때까지 하나의 thread만을 이용합니다.

 

leaf 노드에 도달했을 때,

독립적인 simulation이 실행됩니다.

 

leaf 병렬화는 mutex를 필요로하지 않기 때문에 구현이 쉽다는 특징을 갖습니다.

하지만, 여기에는 2가지 문제점이 존재합니다.

 

첫 번째로는 simulation game에 소요되는 시간을 예측할 수 없다는 것입니다.

즉, n번의 simulation을 하는 시간보다, n개의 thread를 이용하는 시간이 더 짧을 수도 있습니다.

 

왜냐하면, program은 가장 긴 simulation game을 기다리기 때문에,

소요시간은 얼마나 긴 simulation game을 수행하는지에 달려있습니다.

하지만, simulation game의 길이는 random하게 정해지기 때문에, 소요시간을 예측할 수 없습니다.

즉, 병렬화를 해도 시간이 줄어든다는 보장이 없습니다.

 

두 번째로는 정보가 공유되지 않는다는 점입니다.

만약 16개의 thread가 동시에 simulation된다고 했을 때,

먼저 도착한 8개의 thread의 결과는 부정적이라면,

나중에 도착할 8개의 thread의 결과도 부정적이라고 예측할 수 있습니다.

 

하지만, 나중에 도착할 8개의 thread가 부정적이라고 예측되는데,

program은 이 8개의 thread를 기다려야합니다.

 

즉, 쓸데없는 simulation game이 수행될 수 있다는 것입니다.

 

따라서 이 전략은 병렬화 방법중

그리 좋지 않은 방식이라 예측할 수 있습니다.

 

Root parallelization

 

Cazenave는 이를 single-run 병렬화라 표현했지만,

이 paper에서는 root 병렬화라 부릅니다.

 

처음에 여러 개의 MCTS 트리를 만들면서 시작합니다.

이 트리들은 서로 정보를 공유하지 않고, 독립적으로 탐색을 실행합니다.

 

사용가능한 시간이 모두 지나면,

이 트리들의 결과를 합쳐서 다음 선택지를 고릅니다.

 

이는 leaf 병렬화와 마찬가지로 구현이 쉽다는 장점이 있습니다.

 

Tree parallelization

 

이 paper는 새로운 병렬화 방법인 tree 병렬화를 소개합니다.

이는 하나의 공유된 tree를 갖는다는 점에서 root 병렬화와 차이점을 둡니다.

 

하지만 공유된 tree를 갖기 때문에 mutex가 필수적입니다.

 

따라서 성능과 정확도를 위해 다음 2가지의 기술을 제시합니다.

• mutex
• virtual loss

 

Mutex Location

 

mutex를 어디에 설정하느냐에 따라 tree 병렬화의 성격이 달라질 수 있습니다.

 

먼저 tree 전체를 mutex로 설정하는 방법입니다.

이는 오직 하나의 thread만이 tree에 접근할 수 있습니다.

 

하지만, 이는 leaf 병렬화와 마찬가지로 가장 긴 simulation game의 소요시간에 의해

프로그램 전체의 소요시간이 결정되기 때문에 시간 단축의 측면에서는 유리하지 않습니다.

 

그렇가면 노드 하나만을 mutex로 설정하는 방법입니다.

이는 simulation이 시작되는 node에 오직 하나의 thread만이 접근할 수 있습니다.

 

이는 grobal mutex를 사용하는 것보다는 병렬성이 좋기 때문에,

시간 단축의 측면에서 유리할 수 있습니다.

 

Virtual Loss

 

만약 같은 루트 노드에서 병렬적으로 탐색을 시작한다면, 같은 노드에서 simulation이 될 가능성이 큽니다.

같은 UCB를 갖고 계산하기 때문입니다.

 

만약 이렇게 된다면 leaf 병렬화와 비슷하게 수행될 수 있다는 문제점이 있습니다.

따라서 이를 방지하기 위해 가상 손실의 개념을 만들었습니다.

 

이는 thread가 해당 노드를 탐색중에 있다면,

가상 손실값을 UCB에 더해주어서 exploration을 하도록 유도합니다.

 

이 가상 손실은 그 노드가 역전파를 수행할 때 사라집니다.

 

Experiments.

 

leaf 병렬화는 나머지 두 병렬화 방법에 비해 좋지 않은 성능을 보여줍니다.

 

root 병렬화는 꽤 우수한 성능을 보여주고,

one-thread대비 속도도 빠른 모습을 보여줍니다.

 

tree parallelization with global mutex는 성능도 우수하지 않을 뿐더러

속도의 측면에서도 떨어지는 성능을 보입니다.

 

tree parallelization with local mutex는 with global mutex보다는 성능과 속도의 측면에서 우수하지만,

root에 비해서는 떨어지는 성능을 보였습니다.

 

하지만, 해공간의 크기가 줄어든 9x9 바둑에서는 tree 병렬화가 root 병렬화보다 우수한 성능을 보였습니다.

root 병렬화는 해공간의 크기가 매우 크고, 시간 제한이 엄격한 상황에서 우수한 성능을 보였지만,

해공간의 크기가 상대적으로 작고, 시간 제한이 느슨한 상황에서는 tree 병렬화가 우수한 성능을 보였습니다.

 

Quarto는 9x9 바둑보다 해공간이 작기 때문에,

MCTS가 계산할 시간이 많다고 가정할 수 있고,

 

여유로운 상황에서 더 나은 성능을 보여준 tree 병렬화를 선택하기로 결정했습니다.