[인공지능] Adversarial Search 1 - 1

Outline

1. Games
   • 게임은 여러 다양한 종류가 있다. 주요 분류 기준은 다음과 같다:
   • 결정론적 또는 확률론적인가? 한 명, 두 명, 또는 그 이상의 플레이어가 있는가? 제로섬 게임인가? 완벽한 정보(상태를 볼 수 있는) 게임인가?
   • 게임에서는 각 상태에서 움직임을 추천하는 전략(정책)을 계산하기 위한 알고리즘이 필요하다.
2. Adversarial search and trees
   • 적대적 검색은 두 명의 에이전트가 제로섬 게임을 하는 것을 의미한다. 하나는 값을 최대화하고 다른 하나는 값을 최소화한다.
   • 적대적 검색 트리와 minimax 값은 최적의 상대에 대한 최상의 달성 가능한 유틸리티를 찾기 위해 사용된다.
3. Minimax values
   • Minimax는 결정론적 제로섬 게임에서 사용된다. 예를 들면, 틱택토, 체스, 체커스 등이 있다.
   • 한 플레이어는 결과를 최대화하고 다른 플레이어는 결과를 최소화한다.
   • Minimax 검색은 상태 공간 검색 트리입니다.
   • 플레이어는 번갈아 가며 턴을 진행한다. 각 노드의 minimax 값은 합리적(최적)인 상대에 대한 최상의 달성 가능한 유틸리티를 재귀적으로 계산하여 얻는다.
4. Pruning
   • Alpha-Beta Pruning은 minimax 검색의 효율성을 향상시키는 기술이다.
   • 이 기술은 루트에서 계산된 minimax 값에 영향을 주지 않으면서 검색 트리의 일부를 잘라낸다.
   • 좋은 자식 정렬은 pruning의 효과를 향상시킨다.
5. Resource limits and evaluation functions
   • 실제 게임에서는 모든 리프 노드까지 검색할 수 없다. 깊이 제한 검색을 사용하여 트리의 제한된 깊이까지만 검색한다.
   • 터미널 유틸리티를 비터미널 위치의 평가 함수로 대체합니다. 평가 함수는 깊이 제한 검색에서 비터미널을 점수화하는 데 사용된다. 이상적인 함수는 위치의 실제 minimax 값을 반환한다. 실제로는 일반적으로 특징의 가중치가 부여된 선형 합으로 사용된다.

Game Playing State-of-the-Art ( 게임 플레이의 최신 기술 동향 )

현재는 Go의 레벨이 더 높아져 chess와 거의 동등하다.

1. Checkers (체커)
   • 1950년: 첫 번째 컴퓨터 플레이어가 등장했다.
   • 1994년: 첫 번째 컴퓨터 챔피언인 Chinook이 8개의 말로 끝나는 게임을 완전히 사용하여 40년 동안 인간 챔피언 Marion Tinsley의 통치를 끝냈다.
   • 2007년: 체커 게임이 완전히 해결되었다.
2. Chess (체스)
   • 1997년: Deep Blue가 6게임 경기에서 인간 챔피언 Gary Kasparov를 이겼다. Deep Blue는 초당 2억 개의 포지션을 검토했으며, 매우 정교한 평가와 40 ply까지 일부 검색 라인을 확장하기 위한 비공개 방법을 사용했다. 현재의 프로그램들은 역사적으로는 덜 중요할지라도 훨씬 더 나아졌다.
3. Go (바둑):
   • 인간 챔피언들이 이제 기계에 의해 도전을 받고 있다. 바둑에서는 b > 300이다! 고전 프로그램들은 패턴 지식 베이스를 사용하지만, 최근의 큰 발전은 몬테 카를로 (무작위) 확장 방법을 사용한다.
   • 2016년: Alpha GO가 인간 챔피언을 이겼다. Alpha GO는 Monte Carlo Tree Search와 학습된 평가 함수를 사용한다.(팩맨)

---

Adversarial Games

 

적대적 검색(Adversarial Search): 두 에이전트가 제로섬 게임을 플레이하며, 하나는 값을 최대화하고 다른 하나는 값을 최소화한다.

Types of Games

• 게임은 종류가 정말 다양하다.
• 게임의 분류 기준 (Axes):
  • 결정론적(Deterministic) 또는 확률론적(Stochastic)인가?
  • 플레이어는 한 명, 두 명, 또는 그 이상인가?
  • 제로섬(Zero sum) 게임인가?
  • 완벽한 정보(Perfect information) 게임인가? (상태를 볼 수 있는가?)
• 각 상태에서 움직임을 추천하는 전략strategy(정책policy)을 계산하기 위한 알고리즘이 필요하다.

Deterministic Games

• 결정론적 게임의 다양한 형식화 방법:
  • 상태(States): S (시작 상태는 s_0)
  • 플레이어(Players): P={1...N} (보통 번갈아 가며 턴을 진행)
  • 행동(Actions): A (플레이어 / 상태에 따라 달라질 수 있음)
  • 전이 함수(Transition Function): SxA → S (어떤 상태와 행동의 조합에서 다음 상태로 어떻게 전이되는지를 나타냄)
  • 종료 테스트(Terminal Test): S → {t,f} (게임이 종료되었는지 아닌지를 판별)
  • 종료 유틸리티(Terminal Utilities): SxP → R (게임이 종료될 때 각 플레이어에게 주어지는 유틸리티 값)
• 플레이어에 대한 solution은 정책(policy) : S → A ( 각 상태에서 어떤 행동을 추천하는지를 나타냄)

Zero-Sum Games

• 제로섬 게임(Zero-Sum Games)
  • 에이전트들은 반대되는 유틸리티(결과(outcome)에 대한 값)를 가진다.
  • 이를 통해 하나는 값을 최대화하고 다른 하나는 값을 최소화하는 단일 값에 대해 생각할 수 있다.
  • 이러한 게임은 적대적(adversarial)이며, 순수한 경쟁(pure competition)의 형태를 가진다.
• 일반 게임(General Games)
  • 에이전트들은 독립적인 유틸리티(결과(outcome)에 대한 값)를 가진다.
  • 협력(cooperation), 무관심(indifference), 경쟁(competition) 등 다양한 관계가 모두 가능하다.
  • 제로섬이 아닌 게임에 대한 더 많은 내용은 나중에 다룰 예정이다.