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

Zero-sum Games and AI

 

• A player's utility gain or loss is exactly balanced by the combined gain or loss of opponents
• This is a powerful concept important to AI development for measuring the cost/benefit of a particular move

어느 한 플레이어에게 이득인 것은 반대편 상대에게는 손해인 제로 섬 게임이어야합니다. 이는 게임의 비용과 이득을 계산하는데에 필수적입니다.

 

Games and AI

 

• Traditional strategy - Minimax:
  • Attempt to minimize opponent's maximum reward at each state
  • Exhaustive Search

전통적인 Min-Max Search는 상대방의 이윤을 줄이고, 본인의 이윤을 늘리는 방향으로 시도하는 방법입니다. 하지만 이는 비용이 매우 큽니다.

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

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

 

Drawbacks

 

• The number of moves to be analyzed quickly increases in depth
• The computation power limits how deep the algorithm can go
• It is difficult to solve a complex game in a finite amount of time
  • Games like checkers and chess can arguably be solved using the minmax algorithms state (branching factor ≒ 30)
  • Things can get a little tricky when there are a large number of potential actions to be taken at each state (branching factor ≒ 300)

깊이가 깊어질수록 분석하는 움직임의 수가 빠르게 늘어나고, 알고리즘이 갈 수 있는 깊이에 한계가 있습니다. 또한 한정된 시간에 복잡한 문제를 푸는 것이 매우 힘듭니다.

 

Alternative Idea

 

• Bandit-based Methods
  • Choosing between K actions/moves
  • Need to maximize the cumulative reward by continuously picking the best move
• Bandit-based methods have been used for tree search, because of their efficient trade-off between
  • Exploration of the most uncertain branches and
  • Exploitation of the most promising ones
  • Finally leading to very promising results in dealing with huge trees
• Upper confidence bound (UCB) bandit algoritms applied to tree search

특정하지 않은 가지를 탐색하는 것과 특정한 가지를 개발하는 것의 적당한 밸런스를 유지하기 위한 UCB를 Tree에 적용할 수 있습니다.

 

Monte Carlo Tree Search

 

• Application of the Bandit-based methods
• Two fundamental concepts:
  • The true value of any action can be approximated by running several random simulation
  • These values can be efficiently used to adjust the policy (strategy) towards a best-first strategy
• Builds a partial game tree before each move. Then selection is made
  • Moves are explored and values are updated/estimated

위에서 설명한 UCB를 적용한 방법으로, 몇 번의 랜덤 시뮬레이션을 통해 행동의 값을 추정할 수 있고, 이런 값들을 통해 다음 수를 선택합니다. 게임의 초반에는 부분 트리를 미리 만들어놓으면 효율 부분에서 유리합니다.

 

General Applications of MCTS

 

• Numerical Algoritms
• AI Games
  • Particularly games with imperfect imformation
  • Very successful in Go
• Many other applications
  • Real world planning
  • Optimization
  • Control systems

Algoritm Overview

 

• Selection
  • Selecting good child nodes, starting the root node
• Expansion
  • If L is a not a terminal node, then create one or more child nodes and select on e
• Simulation (rollout)
  • Run a simulated playout from C until a result is achieved
• Backpropagation
  • Update the current move sequence with the simulation result

MCTS

 

Policies

 

• Policies are crucial for how MCTS operates
• Tree policy
  • Used to determine how children are selected
• Default policy
  • Used to determine how simulations are run
  • Result of simulation used to update values

정책은 MCTS의 동작에 매우 중요합니다. Tree정책은 어떤 자식 노드를 선택할지를 담당합니다. Default정책은 어떻게 시뮬레이션하고 어떻게 결과를 업데이트할 것인지를 담당합니다.

 

Selection

 

• Start at root node
• Based on tree policy select child
• Apply recursively - desend through tree
  • Stop when expandable node is reached
  • Expandable: node that is not-terminal and has unexplored children

루트 노드에서 시작합니다. 그리고 확장가능한 노드, 즉 종단노드가 아니고 아직 탐색하지 않은 자식 노드가 있는 노드를 찾을 때까지 재귀적으로 반복합니다.

 

Expansion

 

• Add one or more child nodes to tree
  • Depends on what actions are available for the current position
  • Method in which this is done depends on Tree Policy

하나 혹은 여러 개의 자식 노드들을 트리에 추가하는 것입니다. 이는 현재 어떤 상태인지에 달라지며, Tree정책에 따라 달라집니다.

 

Simulation

 

• Runs simulation of path that was selected
• Get position a end of simulation
• Default Policy determines how simulation is running
• Board outcome determines value

선택한 경로의 시뮬레이션을 실행하는 것입니다. Default정책에 의해 결정되며, value가 결정됩니다.

 

Backpropagation

 

• Moves backward through saved path
• Value of node
  • Representative of benefit of going down that path from start to the end
• Values are updated dependent on board outcomes

저장된 경로를 되돌아가며 값들을 수정하는 단계입니다.

 

Policies

 

• Tree policy
  • Select/create leaf node
  • Selection and expansion
  • Bandit problem
• Default policy
  • Play the game till end
  • Simulation
• Selection the best child
  • Max (highest weight) → simulation의 결과값을 신뢰하는 경우, 게임의 후반
  • Robust (most visits) → simulation의 결과를 신뢰할 수 없는 경우, 게임의 초반
  • Max-Robust (both, iterate if none exists)

 

UCT Algorithm

 

UCT

• Selecting child node: Multi-Arm Bandit Problem

왼쪽 항은 Exploitation을 의미합니다. value값의 평균으로 시뮬레이션 결과 value값이 계속 좋다면 그 노드에 대한 자식 노드들만 파고들게 됩니다.

오른쪽 항은 Exploration을 의미합니다. 부모노드 대비 해당 노드의 탐색 횟수가 많을 수록 UCT값이 줄어듭니다. 이는 부모 대비 많이 탐색하지 않은 노드들에 대해 가중치를 부여한다는 의미입니다. 따라서 부모노드는 한 번이라도 탐색이 되었지만 자식 노드는 한 번이라도 탐색되지 않았다면 오른쪽 항의 값이 inf가 나오기 때문에 반드시 탐색됩니다.

 

상수 c를 통해 Exploitation과 Exploration의 조화를 맞출 수 있습니다.

 

Advantages/disadvantages of MCTS

 

• Aheuristic
  • No need for domain-specific knowledge
  • Other algoritms may work better if heuristic exists
    • Minimax for chess
    • Better because chess has strong heuristic that can decrease size of tree
• Anytime
  • Can stop running MCTS at any time
  • Return best action
• Asymetric
  • Favor more promising nodes

MCTS