카테고리 없음

[인공지능] Adversarial Search 2 - 2

7_JUN_7 2023. 10. 24. 23:08

Modeling Assumptions

 

The Dangers of Optimism and Pessimism( 낙관주의와 비관주의의 위험성)

Dangerous Optimism(낙관주의)

  • 세계가 적대적일 때 우연히 발생한다고 가정하기

Dangerous Pessimism(비관주의)

  • 그렇게 가능성이 높지 않을 때 최악의 경우를 가정하기

 

지금까지 2가지 Game search를 살펴보았는데 두 알고리즘은 양날의 검이라 할 수 있다. 만약 Opponent가 optimal 한 MIN player라 생각했는데 상대방이 랜덤하게 움직인다면 게임에서 질 수 있다. 이런 경우를 Dangerous Pessimism이라 한다. 그림처럼 Opponent는 순한 토끼인데 무서운 Ghost라 생각한 것 처럼 말이다.

물론 반대의 경우도 있다. Opponent가 확률적으로 랜덤하게 움직이는 쉬운 상대인 줄 알았는데 알고보니 optimal 한 MIN player라면 분명 패배할 것이다. 이런 경우를 Dangerous Optimism 이라 한다.

 

Assumptions vs. Reality

팩맨은 문제를 피하는 평가 함수를 사용하여 깊이 4 검색( depth 4 search )을 사용했습니다. 유령은 팩맨을 찾는 평가 함수(eval function)로 깊이 2 검색( depth 2 search )을 사용했습니다.

적대적고스트는 최적 상대. 랜덤 고스트는

미니맥스 팩맨은 상대를 매우 강하게 보는것 ( 비관주의: Optimism)

엑스펙티맥스 팩맨은 상대를 과소평가하는것 (낙관 주의:Pessimism)

 

Other Game Types

 

Mixed Layer Types( 혼합 레이어 유형)

 

예: 백개먼 (Backgammon)

 

기대값-최소값-최대값 (Expectiminimax)

  • 환경은 각 최소/최대 에이전트 후에 움직이는 추가적인 "무작위 에이전트" 플레이어입니다.
  • 각 노드는 자식들의 적절한 조합을 계산합니다.

Mixed Layer Type은 쉽게 말해 opponent는 MIN Player지만 그 사이에 주사위와 같은 확률이 동작하는 경우이다. 예를 들면 backgammon이 있는데 무슨 게임인지는 잘 모르겠고, 모두의 마블정도로 생각하면 좋겠다. 이런 경우 MIN, MAX player 전후로 change 노드를 둠으로써 주사위의 확률을 반영할 수 있다.

Multi-Agent Utilities  ( 다중 에이전트 유틸리티)

  • 게임이 제로섬이 아니거나, 여러 플레이어가 있을 경우 어떻게 될까요?

최소-최대 (minimax)의 일반화:

  • 터미널은 유틸리티 튜플을 가집니다.
  • 노드 값도 유틸리티 튜플입니다.
  • 각 플레이어는 자신의 구성요소를 최대화합니다.
  • 이로 인해 협력과 경쟁이 동적으로 발생할 수 있습니다...

말 그대로 MIN player가 여려명 있는 경우이며, Minimax Search의 Utility를 복수로 생각하고 풀이하면 된다. 위 예제는 player가 3명인 경우이다

Monte Carlo Tree Search( 몬테 카를로 트리 검색)

 

 

  • 알파-베타 검색을 기반으로 한 방법들은 고정된 수평선을 가정합니다.
    • 바둑에서는 b > 300으로 꽤 희망이 없습니다.
  • MCTS는 두 가지 중요한 아이디어를 결합합니다:
    • 롤아웃을 통한 평가 - 상태 s에서 여러 게임을 종료까지 플레이 (간단하고 빠른 롤아웃 정책을 사용)하고 승리와 패배를 계산합니다.
    • 선택적(selective) 검색 - 깊이에 관계없이 루트에서의 결정을 개선하는 데 도움이 될 트리의 일부를 탐색합니다.

Rollouts

  • 각 롤아웃에 대하여: 
    • 종료 상태가 될 때까지 반복:
      • 고정된, 빠른 롤아웃 정책에 따라 움직임을 실행
    •  결과를 기록
  •  승리의 비율은 포지션의 참 값과 관련이 있습니다!
  • "더 나은" 롤아웃 정책을 가지는 것이 도움이 됩니다.

MCTS Version 0

 

루트의 각 자식에서 N번의 롤아웃을 수행하고 승리의 비율을 기록

이 척도(metric)에 따라 최상의 결과를 제공하는 움직임을 선택

MCTS Version 0.9

•롤아웃을 더 유망한 노드에 할당

이러한 균일하지 않은 분포는 이 버전의 MCTS가 "적응형"이라는 특성을 나타냅니다. 주어진 맥락에서 "더 유망한 노드에 롤아웃 할당"은 알고리즘이 초기 결과를 바탕으로 더 유망해 보이는 노드(결정)에 더 많은 시뮬레이션(롤아웃)을 투자한다는 것을 의미합니다. 예를 들어, 초기에 높은 승률의 징후를 보이는 노드는 더 많은 롤아웃을 통해 더 많이 탐색되는 반면, 덜 유망한 노드는 더 적은 롤아웃을 받을 수 있습니다.

MCTS Version 1.0

롤아웃을 더 유망한 노드에 할당

롤아웃을 더 불확실한 노드에 할당

 

이 버전은 유망해 보이는 노드뿐만 아니라 불확실한 노드에도 롤아웃을 할당합니다.

 

더 불확실한 노드에 롤아웃 할당 :"6/10" 노드는 시뮬레이션 횟수가 10회밖에 되지 않아 세 노드 중 가장 불확실성이 높습니다.이 버전의 알고리즘은 10번의 롤아웃만을 기반으로 한 결정은 불확실할 수 있으며 추가 탐색이 필요할 수 있음을 인식하는 것 같습니다.유망한 노드와 불확실한 노드 모두에 롤아웃을 할당함으로써 MCTS 버전 1.0은 착취(이미 좋은 것으로 알려진 움직임 선택)와 탐색(충분히 탐색되지 않은 움직임 조사) 사이의 균형을 목표로 합니다.이를 통해 알고리즘이 사용 가능한 데이터를 기반으로 최선의 결정을 내리는 동시에 덜 탐색된 노드를 무시하여 잠재적인 기회를 놓치지 않도록 합니다.이 전략은 종종 복잡한 환경에서 보다 강력하고 정보에 입각한 의사 결정으로 이어질 수 있습니다.

UCB Heuristics

UCB1 공식은 "유망한(promising)"과 "불확실한"(uncertain)을 결합합니다:

 

  • N(n) = 노드 n에서의 롤아웃 횟수
  • U(n) = n에 대한 롤아웃의 총 유틸리티 (예: 승리 수)
  • 밴딧 문제(bandit problem)에 대해 증명된 대로 나쁘지 않은 휴리스틱
    • (우리가 여기에서 직면하는 문제와는 다릅니다!)

MCTS Version 2.0 : UCT

시간이 다 될 때까지 반복:

  • 현재의 검색 트리가 주어졌을 때, leaf(완전히 확장되지 않은) 노드 n까지의 경로를 선택하기 위해 UCB를 재귀적으로 적용
  • n에 새로운 자식 c를 추가하고 c에서 롤아웃을 실행
  • 루트까지 c에서의 승리 횟수를 업데이트

가장 높은 N을 가진 자식으로 이어지는 동작을 선택

 

UCT Example

 

SUMMARY

게임은 최적성이 불가능할 때 결정을 필요로 합니다.

  • 제한된 깊이의 검색 및 근사 평가 함수

게임은 계산의 효율적인 사용을 강요합니다.

  • 알파-베타 가지치기, MCTS

게임 플레이는 중요한 연구 아이디어를 제공하였습니다.

  • 강화 학습 (체커)
  • 반복적 깊이 증가 (체스)
  • 합리적 메타추론 (오델로)
  • 몬테 카를로 트리 검색 (체스, 바둑)

비디오 게임은 훨씬 더 큰 도전을 제시합니다 – 해야 할 것이 많습니다!

  • b = 10^500, |S| = 10^4000, m = 10,000, 부분적으로 관찰 가능, 종종 2명 이상의 플레이어가 있음