Detail View

행동의 불확실성이 존재하는 연속 행동 공간은 의사 결정 알고리즘을 활용하
여 최적의 전략을 수립하기 어려운 도메인이다. 기존의 대다수의 MCTS 방법
론들은 이러한 도메인에서 낮은 탐색 성능을 보였다. 본 논문은 이러한 도메인
의 한 종류인 컬링에서 최적의 전략을 수립하는 탐색 알고리즘을 제안하는 것
을 목표로 한다. 이를 위해 컬링 경기의 특징이 반영된 평가 함수를 사용하여
스톤 투구의 불확실성 크기와 롤 아웃 시뮬레이션 퀄리티를 추정하는 방법을
적용한 UCT 기반의 탐색 알고리즘을 제안하였다. 실험을 위해 제안하는 각각
의 두 가지 방법론의 적용 여부에 따라 기본 UCT 알고리즘을 포함한 4가지
알고리즘을 준비하였다. 이들 간 대전 결과를 통하여 제안하는 방법론의 성능
을 평가하였다. 제안하는 방법론을 적용하지 않은 UCT가 가장 낮은 승률을 가
졌고 행동의 불확실성과 시뮬레이션 퀄리티 모두를 측정한 UCT_AR이 4가지
탐색 알고리즘 중 가장 높은 승률을 보여주었다. 또한 (우리는) 불확실성이 있
는 연속 공간의 도메인을 고려하여 기존에 제안된 알고리즘인 DPW, KR-UCT
와의 성능 비교를 통해 제안된 알고리즘이 가장 높은 성능을 보임을 확인했다.
이 결과는 본 연구가 불확실성이 있는 연속 행동 공간에서 사용할 수 있는 유
망한 방법론임을 증명한다.

Continuous action spaces in which uncertainty exists are the domain that
is difficult to establish optimal strategy by using MCTS algorithm. Most of
the existing MCTS variants showed low performance in these domains. This
paper aims at proposing a MCTS algorithm to establish an optimal strategy
for curling. For this purpose, UCT-based search algorithm is proposed using
estimation function reflecting key features of curling game and estimating
the size of uncertainty of stone throwing and the quality of rollout simulation.
4 algorithms including the basic UCT are prepared according to whether each
of the two proposed methods are applied for the experiment. We evaluate
the performance of the proposed methods by performing games between 4
algorithms. Basic UCT without any method applied had the lowest winning
rate, and UCT_AR, which estimated both the uncertainty of actions and the
simulation quality, showed the highest winning rate among the 4 search
algorithms. In addition, we have confirmed that the proposed algorithm shows
the best performance by comparing the performance with the DPW and KRUCT
algorithms considering the uncertainty of the domain of the continuous
space. This result proves that the proposed algorithm performs well in the
challenging problem of continuous action space with uncertainty.

1 Introduction 1
2 Related works 5
 2.1 Probabilistic search 5
 2.2 Monte Carlo tree search 6
 2.3 Kernel Regression UCT 7
 2.4 Double Progressive Widening 8
 2.5 Rollout policies with domain knowledge 9
3 Method 10
 3.1 Evaluation functions for curling 10
 3.2 Action Reliability Assessment (ARA) 11
 3.3 Rollout Quality Assessment (RQA) 13
 3.4 Search algorithm for continuous action spaces with uncertainty 15
4 Experiments 16
 4.1 Experimental setting 16
 4.1 Experiments of each proposed method 16
 4.1 Experiments with other algorithms 17
5 Conclusion 19