[인공지능] Adversarial Search 1 - 4

Evaluation Functions

Evaluation Functions

평가 함수는 게임의 특정 상태를 얼마나 좋거나 나쁜지를 평가하는 데 사용되며, 실제 게임에서는 완벽한 minimax 값을 계산하는 것이 불가능할 때 이러한 평가 함수를 사용하여 깊이 제한 검색을 수행한다.

• 평가 함수 (Evaluation Functions)는 깊이 제한 검색에서 비터미널 노드를 점수화(score)하는 데 사용된다.
  • 이상적인 함수(ideal function) : 해당 위치(position)의 실제 minimax 값을 반환하는 함수이다.
  • 실제 함수 (in practice): 일반적으로 , 특징(features)들의 가중치가 적용된(weighted) 선형 합(linear sum)으로 표현된다 : 
    • Eval(s)=w_1​f_1​(s)+w_2​f_2​(s)+...+w_n​f_n​(s)
    • 여기서 w_i​는 각 특징 f_i​(s)의 가중치이며, s는 게임의 특정 상태를 나타낸다.
  • 예시:
    • f_1​(s) = (흰색 퀸의 수 - 검은색 퀸의 수)

Evaluation for Pacman

Video of Demo Smart Ghosts (Coordination)

데모 영상에서 팩맨은 똑똑한 고스트에 포위당해 죽는다. 이를 통해 다음을 설명하고자 한다.

Depth Matters

• 평가 함수(evaluation function)는 항상 완벽하지 않다(imperfect)
  • 평가 함수는 게임의 특정 상태나 위치를 평가하는 데 사용되는 함수이다. 이러한 평가는 다양한 요소나 특징에 기반하여 계산되며, 실제 게임의 결과와 항상 일치하지는 않는다.
• 트리 내에서 평가 함수가 더 깊게 위치할수록(buried deeper), 평가 함수의 품질(quality)의 중요성(matter)이 줄어든다.
  • 탐색 트리의 깊은 부분에서의 평가는 상위 레벨의 결정에 큰 영향을 미치지 않을 수 있다. 따라서 트리의 깊은 부분에서는 평가 함수의 정확성이나 품질이 상대적으로 덜 중요해질 수 있다.
• 특징(feature)의 복잡성과 계산(computation)의 복잡성 사이의 균형(tradeoff)에 대한 중요한 예시
  • 게임의 상태를 평가하는 데 사용되는 특징들의 복잡성과 이러한 평가를 계산하는 데 필요한 계산의 복잡성 사이에는 균형이 필요하다. 특징이 너무 복잡하면 계산의 복잡성이 증가하게 되며, 이는 실시간 게임 플레이에서 빠른 결정을 내리는 데 방해가 될 수 있다.

Video of Demo Thrashing (d=2)

데모 영상에서는 팩맨이 어떤 이유에서인지 왔다갔다 하면서 도트를 먹지 않는다. 이러한 이유에 대해서 다음에서 설명하고자 한다.

Why Pacman Starves

• Pacman이 굶는 이유 (Why Pacman Starves)
  • 재계획하는 에이전트의 위험성( A danger of replanning agents )
    • Pacman은 지금 도트를 먹음으로써 점수가 올라갈 것을 알고 있다(서쪽으로 이동한 후 동쪽으로 이동).
    • 나중에 도트를 먹음으로써 점수가 마찬가지로 올라갈 것을 알고 있다(동쪽으로 이동한 후 서쪽으로 이동).
    • 도트를 먹은 후에는 (플레이어의 시야(horizon) 내에서, 여기서는 두 번) 점수를 올릴 기회가 없다.
    • 따라서, Pacman 입장에서는 도트를 먹는 것을 기다리는 것이 도트를 바로 먹는 것만큼 좋아 보인다: Pacman은 다음 재계획 단계에서 동쪽으로 이동한 후 다시 서쪽으로 이동할 수 있다!

이 설명은 Pacman 게임에서 재계획하는 에이전트의 한계를 보여준다. 특히, 에이전트가 단기적인 보상만을 고려하게 되면, 장기적인 목표나 전략을 놓칠 수 있다.

Video of Demo Limited Depth (2) /(10)

이 데모 영상들에서는  limited dept가 2일때와 10일 때의 차이에 대해서 데모를 실행한 영상인것같아 보인다.

모든 경우의 수를 알고 있는 limited depth 10에서의 팩맨이 dot을 먹어 목표를 달성하는데에 성공했다.

Synergies between Evaluation Function and Alpha-Beta?

• Alpha-Beta와 평가 함수 사이의 시너지
  • Alpha-Beta: 가지치기(pruning)의 양(amoung)은 확장 순서(expansion ordering)에 따라 달라진다.
    • 평가 함수는 가장 유망한(promising) 노드를 먼저 확장하는 지침을 제공할 수 있다. 이렇게 하면 루트까지의 경로에 이미 좋은 대안이 있을 가능성이 더 커진다.
      • (A* 휴리스틱의 역할이나 CSPs 필터링과 약간 유사하다.)
  • Alpha-Beta: (min-max의 역할(role)이 바뀌었을 때도(swapped) 유사하다.)
    • min-node에서의 값은 계속해서 감소할 것이다.
    • min-node의 값이 루트까지의 경로에서 max에 대한 better 옵션보다 낮아지면 가지치기(prune)를 할 수 있다.
    • 따라서: 평가 함수가 min-node에서의 값에 대한 상한을 제공하고, 상한이 이미 루트까지의 경로에서 max에 대한 better 옵션보다 낮다면 가지치기(prune)를 할 수 있다.

Summary

대립적 검색 (Adversarial search)

• 두 에이전트가 제로섬 게임을 플레이한다. 한 에이전트는 값을 최대화하는 반면, 다른 에이전트는 값을 최소화한다.
• 대립적 검색 트리(adversarial search tree)와 minimax 값들을 사용하면 최적의 상대(optimal opponent)에 대한 최상의 유틸리티를 찾을 수 있다.

알파-베타 가지치기 (Alpha-beta pruning)

• 이는 대립적 검색의 효율성을 향상시키는 기술이다.
• 알파-베타 가지치기를 사용하면, 결과에 영향을 미치지 않는 노드의 검색을 건너뛸 수 있다. 이로 인해 검색 시간이 크게 줄어든다.

평가 함수 (Evaluation functions)

• 평가 함수는 자원 제한 문제를 완화하기 위해 ( to mitigate resource limits issues) 깊이 제한 검색에서 비터미널 노드의 유틸리티를 근사화(approximate)하는 데 사용된다.
• 실제 게임에서는 모든 가능한 상태나 결과를 탐색하는 것이 불가능하기 때문에, 평가 함수를 사용하여 현재 상태의 가치나 유틸리티를 추정한다.