[인공지능] Adversarial Search 1 - 3

Resource Limits

Game Tree Pruning

게임 트리 가지치기(Game Tree Pruning):

• 게임 트리의 모든 노드를 탐색하는 것은 매우 비효율적일 수 있다. 따라서, 필요하지 않은 노드의 탐색을 중단하고 트리의 일부분만 탐색하는 방법을 사용하여 검색 효율성을 향상시킬 수 있다. 이러한 프로세스를 가지치기(pruning)라고 한다.

Minimax Example

Minimax Pruning 

두번째 분기에서는 2 이하의 노드만 존재해야하기 때문에? 4와 6의 값을 가지는 node를 가지치기(pruning)하여 검색 효율성을 향상시킨다.

Alpha-Beta Pruning

이 기법은 Minimax 검색의 효율성을 향상시키기 위해 사용된다. 알파-베타 가지치기는 불필요한 노드의 탐색을 중단하여 검색 시간을 줄인다.

• 일반 구성 General Configuration (MIN 버전):
  • 어떤 노드 n에서 MIN-VALUE를 계산하고 있다고 가정하자.
  • n의 자식 노드들을 순회하면서(looping over) 계산을 진행한다.
  • n의 자식 노드들의 최소값 추정치(estimate)는 점점 감소한다.(dropping)
  • n의 값에 누가 관심을 가질까? 바로 MAX 에이전트이다.
  • a를 루트에서 현재 경로(current path)를 따라 어떤 선택 지점(choice point)에서든 MAX가 얻을 수 있는 최상의 값이라 하자.
  • 만약 n이 a보다 나쁘다면(become worse), MAX는 n을 피할 것이다.(avoid) 따라서 n의 다른 자식들을 고려할 필요가 없다.(이미 n은 플레이되지 않아도 정도로 나쁘기bad 때문이다).
• MAX 버전:
  • MAX 버전은 MIN 버전과 대칭적(symmetric)이다. MAX 에이전트가 최대 값을 찾는 동안, 만약 특정 노드의 값이 이미 알려진 최소 값보다 더 나쁘다면, 그 노드의 다른 자식들을 고려할 필요가 없다.

Alpha-Beta Implementation

• 변수 설명:
  • α: 루트까지의 경로에서 MAX 에이전트의 최상의 옵션이다.
  • β: 루트까지의 경로에서 MIN 에이전트의 최상의 옵션이다.

def max-value(state, α, β):

  initialize v = -∞

  for each successor of state:

    v = max(v, value(successor, α, β))

    if v ≥ β return v

    α = max(α, v)

  return v

• max-value 함수:
  • 이 함수는 주어진 상태에서 가능한 모든 후속 상태를 고려하여 최대 유틸리티 값 v 을 계산하여 반환한다.
  • 초기값 v는 -∞로 설정된다.
  • 각 후속 상태에 대해 value 함수를 호출하여 해당 상태의 값을 얻는다. 그리고 그 값을 현재의 v 값과 비교하여 더 큰 값을 v에 저장한다.
  • 만약 v가 β보다 크거나 같다면, v 값을 반환한다. 이는 MIN 에이전트가 이미 더 좋은 옵션을 가지고 있기 때문에, 이 경로를 더 이상 탐색할 필요가 없음을 의미한다.
  • α는 α와 v 중 더 큰 값으로 업데이트된다.

def min-value(state , α, β):

  initialize v = +∞

  for each successor of state:

    v = min(v, value(successor, α, β))

    if v ≤ α return v

    β = min(β, v)

  return v

• min-value 함수:
  • 이 함수는 주어진 상태에서 가능한 모든 후속 상태를 고려하여 최소 유틸리티 값 v 을 계산하여 반환한다.
  • 초기값 v는 +∞로 설정된다.
  • 각 후속 상태에 대해 value 함수를 호출하여 해당 상태의 값을 얻는다. 그리고 그 값을 현재의 v 값과 비교하여 더 작은 값을 v에 저장한다.
  • 만약 v가 α보다 작거나 같다면, v 값을 반환한다. 이는 MAX 에이전트가 이미 더 좋은 옵션을 가지고 있기 때문에, 이 경로를 더 이상 탐색할 필요가 없음을 의미한다.
  • β는 β와 v 중 더 작은 값으로 업데이트된다.

Alpha-Beta Pruning Properties

알파-베타 pruning의 특성

• 이 pruning은 루트에 대해 계산된 minimax 값에 영향을 주지 않는다!
  • 알파-베타 가지치기를 사용하더라도, 루트 노드에 대한 최종 minimax 값은 변경되지 않는다. 가지치기는 단순히 검색 과정을 최적화하는 데 도움을 주는 것이다.
• 중간 노드(immediate nodes)의 값은 잘못될 수 있다
  • 중요 : 루트의 자식 노드들은 잘못된 값을 가질 수 있다.
  • 따라서, 가장 단순한(naïve) 버전의 알파-베타 가지치기는 행동 선택(action selection)을 수행하는 데 사용될 수 없다.
• 좋은 자식 정렬(Good child ordering)은 가지치기의 효과성(effectiveness)을 향상시킨다
  • 자식 노드들을 올바른 순서로 정렬하면, 가지치기의 효과가 더욱 증가한다.
• "완벽한 정렬"(perfect ordering)을 사용하면:
  • 시간 복잡도는 O(b^(m/2))로 감소한다.(drop)
  • 이는 탐색 가능한 깊이(solvable depth)를 두 배로 늘린다!(double)
  • 그러나 예를 들어 체스와 같은 게임에서의 전체 탐색(Full search)은 여전히 불가능하다.(hopeless)
• 이것은 메타 추론(metareasoning)의 간단한 예시이다
  • 메타 추론은 어떤 것을 계산할지에 대해 계산하는(computing what to compute) 과정을 의미한다. 즉, 어떤 부분을 계산할지 결정하는 데 도움을 주는 추론 과정이다.

Alpha-Beta Quiz

Alpha-Beta Quiz 2

Resource Limits

• 문제점: 현실적인(realistic) 게임에서는 트리의 모든 노드를 탐색할 수 없다. ( leave까지 탐색할 수 없다.)
• 해결책: 깊이 제한 검색 (Depth-limited search)
  • 전체 트리를 탐색하는 대신, 트리 내에서 제한된 깊이까지만 탐색한다.
  • 비터미널 위치(nonterminal position)에 대한 평가 함수(evaluation)를 사용하여  터미널 노드의 유틸리티 값을 대체한다.
• 예시:
  • 100초의 시간이 주어지고, 초당 10K 노드를 탐색할 수 있다고 가정하자.
  • 따라서 한 번의 움직임에 대해 1M 노드를 확인할 수 있다.
  • 알파-베타 가지치기를 사용하면 대략 8의 깊이(depth)까지 도달할 수 있다. 이는 괜찮은(decent) 체스 프로그램의 수준입니다.
• 최적의 플레이 보장(Guarantee of optimal play)이 사라진다
  • 깊이 제한 검색을 사용하면, 더 이상 최적의 플레이를 보장받을 수 없다.
• 더 많은 ply(수준)는 큰 차이를 만든다
  • 탐색 깊이를 늘리면 게임의 성능에 큰 영향을 미친다.
• 언제든지 사용할 수 있는 알고리즘(anytime algorithm)을 위해 반복적인 깊이 증가 (Iterative deepening)를 사용한다.
  • 반복적 깊이 증가는 주어진 시간 내에서 가능한 최대 깊이까지 탐색을 확장하는 방법이다?