인공지능개론 | Adverserial Search and Game Playing

⚠ Before reading the post ⚠

본 포스팅은 컴퓨터 공학 계열 전공자 대학교 4학년에서 대학원생 기준으로 작성하였습니다.
기본적인 자료구조나 알고리즘 내용은 생략하였습니다.

Adverserial Search and Game Playing | 대립 검색과 게임

이전과 다르게, 한정된 환경에서 1개의 Agent가 목표를 향해 수행했 것과 반면, 이번 시간에 알아볼 검색 방법은 2개의 Agent가 대립하여 한정된 자원을 차지하는 것이 목표인 방법이다.
상대의 상태를 예측함으로써 자신의 action을 결정하고 번갈아가며(turn-taking) 완전이 관측이 가능한 상태(perfect information)에서 zero-sum game(win or lose)를 수행하게 된다.

검색과 게임 방법이 어떻게 다른지 보자

여기서 질문, 게임이라고 했으니 카드 게임과 같은 원카드는 게임 전략에 해당이 될까?
답은 아니요. 여기서 정의하는 게임 환경은 온전히 상대방의 패가 관측이 가능해야 하므로 해당이 되지 않는다. 덧붙여서 온라인 RPG와 같이 턴제 게임이 아닌 이상, 이번 시간에 다룰 전략에 적용되지 않는다.

Before diving in.. (Game Setup)

검색과 유사하게 게임 또한 상태공간은 하나의 상태 공간 그래프인 게임트리로 엮어서 나오게 된다. 다만 차이점은 상대방과 번갈아가며 게임이 진행되기 때문에 후행자는 상대방의 패가 나오게 된다.
아래는 게임 setup에 관해 간략하게 정래본 것이다.

• 2 players: 내가 최대(max)의 몫, 상대방이 최소(min)의 몫을 가지는 것이 목표
  • b: branching factor
  • d: number of legal moves performed by both players = 총 게임 턴 수
• Initial State: 초기 상태
• Succesor function: 현 상태에서 움직일 수 있는 여러 가지 경우의 수
• Terminal Test(State): 종료 판정
• Utility funcion: 게임 종료 시 최종 수치

이제 다양한 게임 상태 공간 속에서 오로지 "나"만 이득을 취할 수 있는 경우를 찾는 전략에 대해 알아보자.

MinMax Strategy

최적의 전략을 찾는 것이 목표이므로 두 플레이어 모두 최적으로 플레이하며 상대방(MIN)은 최선의 플레이를 한다는 가정하에 수를 두게 된다.

1. 먼저 3,12,8이라는 패가 있다고 가정하자.
2. 이 때 Min 계층에서는 각 자식에서 최소인 수를 올려다 놓는다.
3. Max 계층에서는 Min 계층에서 최대인 수를 올려놓는 방색

이미지에 쓰여져있는 것처럼 상대방 역시 최선의 플레이를 하므로 상대방을 방해하는 즉, 최악의 경우를 최대화하게 된다.

이 때 만약에, Min 이 최적의 플레이를 안하게 된다면? 그럼에도 Max인 나는 더 좋은 결과를 얻을 수 있게 될 것이다. 이미지에서 $A_{12}, A_{13}$ 을 고른다고 하면 Max는 더 좋은 결과를 얻을 수 있다.

탐색시에는 완결적인 DFS를 활용하기 때문에 아래와 같이 복잡도가 나오게 된다. (m as max depth, b as legal moves)

• Time and Space Complexity
  • Time complexity: $O(b^m)$
  • Space complexity: $O(bm)$

이처럼 exponential 하다는 점에서 시간이 굉장히 많이 소요된다는 단점을 지니고 있다.

Multiplayer Alliance?

모 아니면 도인 zero sum game이 아닌 경우 다인용 게임이라면? 게임을 하다보면 PUBG처럼 동맹을 맺는 경우가 있는데, 이 때 최약체 플레이어끼리 동맹을 맺어 고인물을 꺾는 플레이를 보이는 경우가 있다. 이 때 최약체 플레이어의 효용(utility) 가치를 합하여 전략이 짜여진다.

Alpha-beta pruning

위 전략은 exponential 하다는 점과 불필요한 공간까지 탐색해야하는 단점을 지니고 있어 이번에 살펴볼 전략에서는 아예 필요없는 경우는 가지치기 해버리는 전략에 대해 알아볼 것이다. 여기서 alpha=max, beta=min으로 이해하면 된다.

말단 노드들이 채워지면서 가능한 범위에서 소거해 나아가면서 진행한다. Max root 노드에서는 아예 3부터 범위를 지정했으므로 최소인 2는 고려할 것도 없이 가지치기가 된다.

Min hirarchy에 의해 최종적으로 Max는 3을 가져가게 된다. 마찬가지로 Alpha-beta pruning은 탐색 시에 DFS를 사용하나 가지치기 하면서 탐색하기에 이전 Minmax에 비해 더 나은 복잡도를 보인다.

• Time and Space complexity
  • Time complexity: $O(b^d)$ as worst case $O(b^{\frac{d}{2}})$ as best case

실질적으로는 best case가 평균적이라고 할정도로 시간 복잡도가 좋은 편이다. 여기서 더 개선하고 싶다면 탐색 우선순위를 부여하는 방법이 있다.

Utility or Evaluation function

이전 정보 있는 탐색에서는 전도유망성을 측정하는 함수가 있었다면 게임 전략에서는 utility 효용성을 따지는 함수를 사용한다. 현 상태에서 얼마나 플레이어에게 유리한지 평가한다.
예를 들어 체스에서는 utility function을 이렇게 세울 수 있다.
$w_nf_n(s) = n(white Q)-n(black Q)$

보통 zero sum game이므로 전체 합을 0으로 세우는데 범위가 무한대 무한이거나 [-1,1] 등등 세울 수 있다.

Wrap up & Conclusion

이번 탐색 전략은 이전 탐색과 달리 한정된 시공간에서 2개의 적대 관계의 플레이어들이 승패를 가루는 전략에 대해 알아보았다. 여기서 정의하는 게임은 "턴제"이어야 하며 "상대방의 전략"을 볼 수 있는 게임이 이에 해당한다.

• Minmax strategy: down to top으로 상대방과 차례대로 올라오게 된다. 하지만 모두 상태 공간들을 DFS 탐색해야 하므로 exponential 하다는 점에서 비효율적이다.
• Alpha-beta pruning: Minmax에서 비슷하나 범위를 줄여나가면서 불필요한 상태공간은 탐색하지 않아 sqrt()배 만큼 시간 복잡도를 줄인 것을 확인해볼 수 있었다. 실질적으로는 베스트 케이스에 해당이 되기 때문에 확실히 효율적이다라고 볼 수 있었다.

다음 시간에는 Constraint Satisfaction Problem을 포스팅해보겠다!