[인공지능] Ch14 Adversarial Search

 

Adcersarial Search

적대적 탐색이란, 두 개 이상의 agent가 서로 적대적인 관계를 가졌을 때의 탐색 방법을 의미한다.

여러 agent가 서로의 이득을 취하기 위해 움직이는 상황을 '게임'이라고 하며 해당 강의에서는 여러 게임들을 소개한다.

 

Deterministric Games

Deterministric 게임을 formalize 하는 방법은 다양한데 그 중 아래와 같은 방법이 있다.

하나씩 설명해보자면,

 

States (𝑆)는 게임의 모든 가능한 상태를 나타낸다.

게임은 특정 상태 𝑠0에서 시작한다. 이후의 상태는 플레이어의 행동과 상태 전이 함수에 의해 결정된다.

 

Players (𝑃)는 플레이어 집합을 나타낸다.

일반적으로 플레이어는 턴을 번갈아가며 진행하며, 보통 𝑃 = {1, 2} 또는 여러 명일 수 있다.

 

Actions (𝐴)는 각 상태에서 플레이어가 취할 수 있는 모든 가능한 행동의 집합이다.

 

Transition Function (𝑆 × 𝐴 → 𝑆')는 현재 상태와 플레이어의 행동을 입력받아 다음 상태를 출력한 것이다.

 

Terminal Test (𝑆 → {𝑡, 𝑓})는 특정 상태가 종료 상태인지 확인하는 함수이다. 

종료 상태라면 게임이 끝난 것이며, 더 이상 움직이지 않는다.

 

Terminal Utilities (𝑆 × 𝑃 → ℝ)는 게임이 종료된 상태에서 각 플레이어에게 부여되는 점수를 나타낸다 .

 

Zero-Sum Game

Zero-Sum 게임은 말그대로 게임 전체의 총합이 0으로 유지돼야 한다는 것이다.

즉, 한 플레이어의 이득은 다른 플레이어의 손실과 정확히 같다.

 

Minimax Search

이제 본격적으로 탐색에 대해 알아보자.

Minimax Search는, 가능한 모든 게임 상태를 탐색하여 가장 최선의 움직임을 결정하고자 한다.

이 게임에는 두 플레이어가 있다.

 

- MAX: 자신의 점수를 최대화하려는 플레이어

- MIN: 상대방의 점수를 최소화하려는 플레이어

 

게임의 모든 가능한 상태를 아래처럼 트리 구조로 표현한다.

위의 트리는 팩맨 게임을 나타낸 것이다. 

팩맨 게임에서 MAX는 팩맨, MIN은 유령이라고 보는 것이다.

팩맨이 위의 상황에서 우측으로 간다면 유령은 -10으로 갈 것이고, 좌측으로 간다면 유령은 -8로 갈 것이다.

그래서 좌측으로 가는 게 그나마 나은 상황이므로 좌측으로 가는 것이다.

 

구현 방법은 아래와 같다.

 

 

다른 예제로 다시 봐보자.

여기서 역삼각형은 MIN을, 삼각형은 MAX를 의미한다.

내가 필기한 것으로도 알 수 있듯이, 가장 왼쪽 MIN은 3, 12, 8 중 가장 작은 값인 3을 선택했다.

그리고 중간 MIN, 오른쪽 MIN 각각 작은 값인 2를 선택했다.

 

그러나 이렇게 모두 탐색을 한다면 시간이 많이 들 것이다.

자세히 살펴보면, 가운데 MIN에서 4와 6은 탐색하지 않아도 될 것이다.

왜냐하면 어차피 MAX는 3보다 큰 값을 선택할 것이기 때문이다.

 

즉, 탐색을 멈추고 다른 경로를 탐색하는 것이다.

이를 나타낸 것이 바로 뒤에서 설명할 Alpha-Beta Pruning(알파 베타 가지치기)이다.

 

 Alpha-Beta Pruning

구현 방식은 위 그림과 같다.

 

- Alpha(α)는 MAX가 선택할 수 있는 최고의 값을 의미한다.

- Beta (β)는 MIN이 선택을 수 있는 최저의 값을 의미한다.

 

어떤 노드에서 α ≥ β인 경우, 해당 노드의 나머지 자식들은 더 이상 탐색할 필요가 없는 것이다.

이미 최적의 경로가 결정되었기 때문이다.

 

- α = −∞, β = +∞로 초기값을 설정한다.

- 각 노드를 탐색하면서 α와 β를 갱신하는 것이다.

 

 

지금까지 나온 내용을 바탕으로 문제를 풀어보았다.

이해가 되길 바란다.

 

회색으로 두번 그은 것은 탐색하지 않는 길을 의미한다.

g의 경우, α > β이기 때문에 탐색하지 않는다.

l의 경우 , α = β이기 때문에 탐색하지 않는다. 당연히 하위에 있는 m과 n도 탐색하지 않는다.