(전공복습) 인공지능 1. 적대적 게임

차례

• 차례
• 들어가기 전에
• 게임
  • 게임의 공식화
  • Value of State
  • 적대적 게임(Adversarial Game)
    • 미니맥스(Minimax)
      • Depth Limited Search
    • 알파-베타 프루닝(Alpha-Beta Pruning)
    • Expectimax
  • 유틸리티
• 정리

들어가기 전에

이 글은 컴퓨터학과 이중전공생으로서 배운 것들을 다시 한번 정리하고자 남기는 글입니다. 불완전한 기억 등의 이유로 오류가 있을 수 있으며, 참조 내지 이정표로만 사용해주세요.
본 게시글은 고려대학교의 인공지능 강의를 기반으로 작성자의 추가적인 설명이 덧붙여진 글입니다. 또한 해당 강의는 UC 버클리 CS188을 기반으로 함을 밝힙니다.

게임

이 강의에서 다루는 팩맨이나, 바둑, 체스와 같이 인공지능에게 맡기는 게임들을 구분하는 데에는 아래와 같은 것들을 고려할 수 있다.

• 결정적인가 무작위적인가?
  • 주사위 던지기 게임은 운의 영역이 있다. 하지만 바둑과 같은 게임은 운의 영역이 없다.
• 플레이어의 수가 몇 명인가?
• 제로섬 게임인가?
  • 각각의 에이전트가 가지는 보상의 합이 항상 0인지, 그렇지 않은지.
• 정보가 완벽하게 주어지는가?

게임의 공식화

게임의 요소를 아래와 같이 수학적으로 나타낼 수 있다.

• 상태(States) \(S\): 가능한 상태 \(s_0,\;s_1,\;,s_2,\;...\)의 집합.
  • \(s_0\)이 시작 상태를 의미.
• 플레이어(Players) \(P\): 게임의 플레이어들 \(P=\{1,\;,2\;,\;...,\;N\}\)
• 행동(Actions) \(A\): 각 상태마다 플레이어가 할 수 있는 행동들.
• Transition Function: \(S \times A \to S\)인 함수.
  • 다시 말해, 현재 상태와 행동에 기반해서 상태의 변화를 나타내는 함수.
• Terminal Test: \(S \to \{t,\;f\}\)인 함수.
  • 특정 상태가 종료 상태(Terminal State)인지 판정하는 함수.
• Terminal Utility: \(S \times P \to R\)인 함수.
  • 즉, 각 상태에 대해 플레이어들이 갖게 되는 보상을 계산하는 함수.
• 정책(Policy): 우리가 알고 싶은 솔루션 \(S \to A\).
  • 각 상태 \(S\)에 대해, 어떤 행동 \(A\)를 해야 하는지 알려주는 함수.

Value of State

어떤 상태에서, 얻을 수 있는 최고의 점수(유틸리티, 보상)를 Value of State라 한다. 예를 들어, 먹은 음식의 개수가 점수인 팩맨 게임에서, 음식이 9개가 있다면 최대 9점까지 획득할 수 있다는 의미이므로 Value of State는 9가 된다. 현재 점수가 3점이고, 남은 음식이 3개라면, 얻을 수 있는 최고의 점수는 6점이므로 Value of State는 6이 된다.
이때, 중요한 건 Value of State는 얻을 수 있는 점수 중 최대의 점수를 의미한다는 것이다. 예를 들어, 게임보드에 음식이 10개가 있지만, 그 중 3개는 팩맨이 접근할 수 없는 위치에 있다고 하자. 어떤 선택을 해도 팩맨이 최대 7개의 음식만 먹을 수 있다면 Value of State는 7이 된다.
결과적으로, Value of State는 현재 상태에서 얻을 수 있는 최대 점수이고, 이는 현재 노드의 후손인 리프 노드 중 가장 높은 점수(유틸리티, 보상)를 의미한다.

적대적 게임(Adversarial Game)

우리는 적대적 게임을 생각할 수 있다. 여기서 적대적 게임이란, 복수의 플레이어가 서로 반대되는 유틸리티를 가지는 경우를 의미한다. 예를 들어, 팩맨과 유령은 적대적인데, 팩맨의 점수를 낮게 만드는 것이 유령의 목적이기 때문이다. 즉, 제로섬 게임의 참여자들은 상호 적대적이라 할 수 있다(내 점수가 높아지는 것과 상대 점수가 낮아지는 것이 동치이므로).

미니맥스(Minimax)

적대적 플레이어가 존재를 고려하지 않고 단순히 내 점수(정확히는 Value of State)만을 최대화시키는 전략을 고르는 것은 그다지 좋은 선택지가 아니다. 팩맨으로 따지면, 유령의 존재를 무시하고 음식만 먹으러 다니는 팩맨 에이전트인 셈이다. 적대적 플레이어의 행동을 고려해야 효율적으로 움직일 수 있다.

그럴 때 필요한 전략이 바로 미니맥스이다. 우리말로는 최소최대라고 할 수 있는데, 상대 에이전트가 내 에이전트의 Value of State를 최소화하려고 할 때, 내가 도달할 수 있는 최댓값을 구하는 게 미니맥스 알고리즘이라 할 수 있다.

위 사진에서, 단순히 Value of State의 최댓값인 +8을 얻기 위해 움직이는 것은 현명하지 못하다. 루트에서 시작해서, 내가 먼저 오른쪽으로 이동하면 그 다음은 상대 에이전트의 차례가 되고, 상대 에이전트는 -10을 선택할 것이므로 나는 최악의 유틸리티를 갖게 된다. 반면, 내가 왼쪽으로 이동하면 상대 에이전트의 선택지는 -8과 -5이므로 내 손해를 최대화시키기 위해 -8을 선택할 것이다. 이는 비록 내가 얻을 수 있는 이상적인 값인 +8보다는 훨씬 작은 값이지만, 이를 얻기 위해 움직였을 때 얻는 -10보다는 더 나은 값이다.

미니맥스 알고리즘은 대략적으로 아래와 같은 수도코드(파이썬 스타일)로 나타낼 수 있다.

def get_max(state):
    v = -INF
    for successor in state:
        v = max(v, get_min(state))
    return v

def get_min(state):
    v = INF
    for successor in state:
        v = min(v, get_max(state))
    return v

위 코드에서 볼 수 있다시피, 미니맥스 알고리즘은 상대가 효율적으로(즉, 미니맥스 알고리즘에 기반하여) 움직일 것이라고 가정한다. 상대 에이전트가 어디 나사가 하나 빠져서 움직인다면, 이전 사진의 예시에서 내가 오른쪽으로 움직여도 +8을 획득할 기회가 있을 수 있다. 하지만 상대 에이전트가 충분히 효율적인 에이전트라면 +8과 -10중에서 -10을 고를 것이다(상대 입장에선 내 점수가 낮을수록 좋다). 즉, 상대 에이전트가 충분히 효율적이라면 미니맥스 알고리즘을 따르는 게 내가 원하는 점수만 좇는 것보다 효율적이다.

위 사진이 보여주는 것처럼, 미니맥스 알고리즘은 상대가 미니맥스 알고리즘에 기반해 행동할 것이라고 가정한다. 즉, 미니맥스 알고리즘은 상호재귀적이다. 이러한 미니맥스 알고리즘은 두 명이 번갈아 행동하는 제로섬 게임(체스, 오목, 팩맨 등)에서 좋은 선택이 된다. 물론 에이전트의 수가 여럿이라면 거기에 맞게 알고리즘을 달리 구현할 수도 있다.

Depth Limited Search

미니맥스 알고리즘은 DFS를 이용한 탐색을 하기 때문에(상호재귀적인 위 구현을 참조하라), 실제 상황에서는 모든 경우의 수를 계산하기에는 시간, 공간이 부족할 수 있다. 그렇기 때문에 실제 상황에서는 리프 노드까지의 모든 경우의 수를 계산하지 않고, 가능한 단계까지만 계산하고 행동을 선택해야 한다.
즉, 적당한 레벨만큼 내려가면 해당 레벨에서의 유틸리티 추정치를 구해서 이를 사용해야 한다. 당연하지만 이는 추정치이므로 실제 최적해(Value of State나 미니맥스 알고리즘의 유틸리티)와는 다를 수 있다.
따라서 우리의 선택 알고리즘이 Anytime Algorithm이 될 필요가 있는데, Anytime Algorithm이란 중간에 중단되더라도 유효한 답을 낼 수 있는 알고리즘을 의미한다. 미니맥스 알고리즘에 기반해서 가능한 경우의 수를 탐색하다가, 자원의 한계로 결정을 내려야 되는 상황이 오면, 지금까지 탐색한 상황들의 유틸리티를 적당히 추정해서 가장 좋을 것으로 예상되는 선택을 하도록 해야 한다는 것이다.
이때, 특정 상태에 대해 예상되는 유틸리티를 계산하는 함수를 Evaluation Function이라고 하는데, 일반적으로 각 피처에 대한 가중치가 있는 선형 결합으로 이루어진다(즉, \(w_1f_1(s) + ... + w_nf_n(s)\)).

알파-베타 프루닝(Alpha-Beta Pruning)

위 트리를 기반으로 미니맥스 알고리즘을 돌려보자. 미니맥스 알고리즘은 상호재귀적이므로 아래쪽부터 계산하는 게 쉽다.
아래쪽 에이전트는 MIN 에이전트다. 3, 12, 8 중에서는 3을, 2, 4, 6 중에서는 2를, 14, 5, 2 중에서는 2를 선택할 것이다.
그 위는 MAX 에이전트다. MIN 에이전트가 선택한 3, 2, 2 중 최댓값을 고르면 되므로 MAX 에이전트는 3으로 가는 오른쪽 간선을 선택할 것이다. 따라서 최우측의 3이 적힌 리프 노드가 미니맥스 알고리즘의 결과가 된다.

그런데 사실, 어떤 노드들은 미니맥스 알고리즘의 결과를 바꾸지 않음을 보장할 수 있다. 위 트리를 다시 살펴보자.
좌에서 우로 미니맥스 값을 계산한다고 할 때, 처음에 MIN 에이전트가 3, 12, 8 중에서 3을 선택할 것이다. 그 다음 형제 노드의 값은 2, 4, 6 중 하나인데, 사실 2를 만난 순간 그 노드는 더이상 값을 살필 필요가 없다. 왜냐하면 현재 에이전트는 MIN 에이전트이고, 따라서 2를 만난 시점에서 이 노드의 값은 2 이하라는 것을 알 수 있다. 2 이후에 오는 다른 형제 노드가 몇이든 2보다 높다면 MIN 에이전트에 의해 선택되지 않을 것이기 때문이다. 그런데 이전에 3, 12, 8 중 3이 MIN 에이전트에 의해 선택되었기 때문에, 다음 단계에서 MAX 에이전트가 적어도 3 이상의 값을 가진 노드를 선택하리라는 것을 알 수 있다. 따라서 2를 만난 이후 그 형제 리프 노드들은 2보다 크든 작든 선택될 일이 없다.

위 사진에서 보듯이, 2 옆의 형제 노드들(원래 값은 4, 6)은 전부 확인할 필요가 없다. 즉 가지치기(Prune)된 것이다. 그 노드들이 4, 6처럼 2보다 큰 값이어도 MIN 에이전트는 2를 선택할 것이고, 그 노드들이 1, 2처럼 2 이하의 값이어면 다음 단계의 MAX 에이전트가 3을 선택할 것이기 때문에, 루트 노드의 최적해만 찾으면 되는 미니맥스 알고리즘 관점에서 그 값은 중요하지 않다.

즉, 알파-베타 프루닝이란 미니맥스 알고리즘의 최종 결과를 바꾸지 않는 것이 보장된 노드들을 살피지 않고 잘라내는 것인데, 이때 알파는 지금까지 계산한 값 중 MAX 에이전트가 선택할 값, 베타는 지금까지 계산한 값 중 MIN 에이전트가 선택할 값이 된다. 구체적인 알고리즘은 아래를 참조하자.

# alpha = -INf, beta = INF

def get_max(state, alpha, beta):
  v = -INF
  for successor in state:
    v = max(v, get_min(successor, alpha, beta))
    if v >= beta: return v
    alpha = max(alpha, v)
  return v

def get_min(state, alpha, beta):
  v = INF
  for successor in state:
    v = min(v, get_max(successor, alpha, beta))
    if v <= alpha: return v
    beta = min(beta, v)
  return v

기존 미니맥스 알고리즘에서 실행 중 현재 노드의 값이 선택될 가망이 없으면 더이상 계산하지 않고 다음 노드로 넘어가는 방식의 구현이다. 이때 선택될 가망이 없다는 것은 두 가지 경우 중 하나에 해당하는 것을 의미한다.

1. 현재 MAX 에이전트에서 베타보다 커서 다음 단계 MIN 에이전트가 선택할 가망이 없다.
2. 현재 MIN 에이전트에서 알파보다 작아서 다음 단계 MAX 에이전트가 선택할 가망이 없다.

알파-베타 프루닝을 수행하면 중간 노드의 값은 바뀔 수 있다. 하지만 어차피 그 중간 노드는 두 에이전트가 미니맥스 알고리즘에 기반한다면 선택되지 않는 노드이고, 따라서 최종 결과(루트 노드의 값)에는 변화를 주지 않게 된다.

또한, 최적의 경우 알파-베타 프루닝을 수행한 미니맥스 알고리즘의 수행시간은 \(O(b^{m \over 2})\)까지 감소할 수 있다. 리프 노드의 값이 최적으로 배열되어 있다면, 매 단계에서 첫 번째 노드만 보고도 그 노드의 선택 여부를 알 수 있기 때문이다.

Expectimax

위에서 다룬 미니맥스 알고리즘은 결정적인(Deterministic) 게임에서 사용한다. 즉, 선택(행동)의 결과가 단일하고, 운이 개입하지 않는다. 하지만 현실 세계는 결정적이기보다는 무작위적인 부분이 있다. 이런 경우 Expectimax 알고리즘을 사용하는 것이 방안이 될 수 있다.

Expectimax는 미니맥스와 매우 유사하나, MAX 에이전트와 MIN 에이전트가 번갈아 행동하는 대신, MAX 에이전트와 EXP 에이전트가 번갈아 행동한다. MAX 에이전트는 미니맥스와 마찬가지로 행동하고, EXP 에이전트는 기댓값을 계산하는 역할을 한다.

def get_exp(state):
  v = 0
  for successor in state:
     v += successor.probability * successor.value
  return v

위는 Expectimax 알고리즘에서 기댓값을 구하는 방법이다. 사실 크게 어려울 것은 없고, 그냥 각 값들의 확률에 따른 가중합을 구했을 뿐이다.

위 간단한 예제를 살펴보자. 위의 EXP 에이전트 노드는 \(8 \times {1 \over 2} + 24 \times {1 \over 3} - 12 \times {1 \over 6} = 10\)의 값을 가지게 된다.

Expectimax는 그 특징상 알파-베타 프루닝처럼 중간에 트리를 프루닝할 수 없다. MAX나 MIN 연산은 여러 값 중 하나의 값만 결과에 영향을 미치지만, 기댓값 연산은 모든 값이 결과에 영향을 미칠 수 있기 때문이다.
비슷하게, MIN 에이전트와 MAX 에이전트는 단조변환에 무감하다(Insensitive to Monotonoic Transform). 그말인즉슨, 예를 들어 모든 노드의 값이 원래 노드의 제곱이 된다고 해도, 미니맥스 알고리즘은 같은 선택을 한다는 것이다. 반면, EXP 에이전트는 모든 노드의 값을 제곱하면 선택지가 바뀔 수 있다.
한편, EXP 에이전트는 MAX 에이전트와 MIN 에이전트의 일반화이기도 한데, MAX 에이전트는 자식 노드 중 최댓값만 1의 확률을 가지고 나머지는 0의 확률을 가지는 EXP 에이전트로, MIN 에이전트는 자식 노드 중 최솟값만 1의 확률을 가지고 나머지는 0의 확률을 가지는 EXP 에이전트로 환원할 수 있다. 즉, 미니맥스는 Expectimax의 특수한 경우이다.

유틸리티

결과의 선호 관계는 유틸리티로 나타날 수 있다. 유틸리티란 특정 상태에 대한 어떤 숫자로의 함수이다(\(S \to \mathbb{R}\)). 유틸리티와 관련된 표현 및 성질들을 몇가지 알아보자.

• \(A \succ B\): A를 B보다 더 선호한다는 것을 의미한다.
  • \(A > B\)와 비슷하게 생겼다. 의미도 비슷한 부분이 있다.
• \(A \sim B\): A와 B의 선호도가 같다(어느쪽이든 상관없다)는 것을 의미한다.

어떤 선호도가 합리적이라고 말하기 위해서는, 아래와 같은 성질을 가지고 있어야 한다고 할 수 있다. 이러한 합리적인 선호도가 주어진다면 유틸리티를 계산할 수 있다.

• 순서성(Orderability): \((A \succ B) \lor (B \succ A ) \lor (A \sim B)\)
  • \(A\)와 \(B\)가 있다면, 둘 중 하나를 선호하거나, 둘의 선호도가 같거나, 그 중 하나여야 한다.
• 이행성(Transitivity): \((A \succ B) \land (B \succ C) \Rightarrow (A \succ C)\)
  • \(A\)가 \(B\)보다 낫고, \(B\)가 \(C\)보다 나으면, \(A\)도 \(C\)보다 나아야 한다.
• 연속성(Continuity): \(A \succ B \succ C \Rightarrow \exists p[p, A;1-p,C] \sim B\)
  • \(A \succ B \succ C\)면, \(A\)와 \(C\)의 선호도를 적당히 가중합해서 \(B\)와 같은 선호도를 만들 수 있다.
• 대체성(Substitutability): \(A \sim B \Rightarrow [p, A;1-p, C] \sim [p, B; 1-p, C]\)
  • \(A\)와 \(B\)의 선호도가 같으면, 다른 선택지 \(C\)를 각각 가중합해도 선호도는 여전히 같다.
• 단조성(Monotonicity): \(A \succ B \Rightarrow (p \ge q \Leftrightarrow [p, A; 1-p,B] \succeq [q, A; 1-q, B]\)
  • \(A\)가 \(B\)보다 낫다면, \(A\)의 비중이 \(p\)일 때가 \(q\)일 때보다 선호된다는 것과 \(p\)가 \(q\)보다 크다는 말은 동치이다.

다만 인간의 선호가 정말로 이러한 조건을 만족하는가? 예를 들어 인간의 돈에 대한 선호는 그다지 합리적이지 않은데, 일반적으로 인간은 손실을 회피(Risk Averse)하는 경향이 있다. 즉, 합리적인 기댓값을 가진 도박에 참여하지 않고 안정적인 수익을 추구한다는 뜻이다. 반면, 큰 빚을 지닌 사람들은 손실을 감수(Risk Prone)하는 경향이 있다. 즉, 소위 인생한방이나 인생역전을 노릴 확률이 높아진다는 뜻이다. 이처럼 수학적으로 합리적인 선호도는 실제 인간의 행동과는 동떨어지는 경우도 있다.

정리

이번 게시글에서는 특정 조건의 게임을 플레이하는 에이전트에 대해 알아보았다. 특히 미니맥스와 Expectimax에 대해 잘 알아두자.

다음 게시글에서는 불확실성과 관련된 MDP(마르코프 결정 과정) 등 강화학습과 관련된 여러 내용을 다루어 보겠다.

• 2024 18
• 2023 143