Mastering_the_game_of_Go_with_deep_neura.pdf

https://kim95175.tistory.com/11

Abstract

• 참고

search space 줄이기

바둑과 같이 경우의 수가 아주 많은 게임의 경우, 모든 경우에 대해 탐색하는 것은 불가능하다.

1. Reduce the depth of the search

   • position evaluation을 통해 depth를 줄일 수 있다.
   • state $s$에서 search tree의 길이를 줄이고, state $s$ 아래의 subtree를 approximate value function $v(s)\approx v^*(s)$로 대체한다.
     • 이 value function은 state $s$에서 연결된 subtree의 결과값을 예측한다.

2. Reduce the breadth of the search

   • sampling actions from a policy $p(a|s)$를 통해 breadth를 줄일 수 있다.
     • 이 policy는 state $s$에서 가능한 action $a$에 대한 확률분포이다.
   • ex. MC rollouts는 모든 경우의 수를 계산하지 않고, policy를 통해 sampling한 actions의 평균을 통해 효과적인 position evaluation을 한다.

MCTS

MC rollout을 이용해 tree의 각 state에 대한 가치를 계산한다.

• 더 많은 시뮬레이션을 시행함으로써 search tree는 확장되고, 그 값은 정확해진다.
• action을 선택하는 policy는 시간이 지남에 따라 더 높은 value의 action을 선택하도록 향상되고, optimal play에 가까워진다. value evaluation도 optimal value function에 가까워진다.