Expectimax Algorithm과 간단한 예제

댓글 남기기

Expectimax는 동전 던지기나 카드 뒤집기 혹은 주사위 게임 처럼 “운”(확률)이 개입되는 게임에서 컴퓨터 프로그램으로 어떤 선택을 해야 최적의 결정을 내릴 수 있을지에 대해 정의하는 알고리즘이다.

서로 경쟁하는 두 플레이어의 합리적 결정을 가정하는 Minimax algorithm과 달리 이 문제에서는 확률적 요소가 있기 때문에, 내가 얻을 점수를 최대화하는 선택을 하기 위한 Max 노드와 더불어 발생할 수 있는 모든 시나리오의 기대값을 계산하는 Chance 노드가 등장한다.

Chance 노드의 기댓값은 다음의 수식으로 계산된다.

V(S)=∑iP(Si)⋅V(Si)V(S) = \sum_i P(S_i) \cdot V(S_i)

여기에서 V(S)는 Chance 노드에서의 기대값이고 , P(Si)는 어떤 사건 i가 발생할 확률, V(Si)는 그 사건이 발생 했을 때의 얻게 되는 가치를 의미한다. 즉 발생확률과 이익의 곱을 모두 더한 것이다.

Max와 Chance

Max가 하는 일은 minimax와 동일하게 자신에게 최대한의 이익이 되는 선택을 하는 것이다. 반면 Chance 노드의 경우는 각 노드가 발생할 확률과 그 사건이 발생했을 때의 이익으로 계산된다.

사건이 발생할 확률이 0.5로 동일하고 그 결과값이 각각 10, 2, 6, 5인 아래와 같은 tree가 있다고 하자.

각 Chance node의 선택 값은 다음과 같이 계산된다.

왼쪽 노드(L)의 값

(10×0.5)+(2×0.5)=6(10 \times 0.5) + (2 \times 0.5) = 6

오른쪽 노드(R)의 값

(6×0.5)+(5×0.5)=5.5(6 \times 0.5) + (5 \times 0.5) = 5.5

이에 따라 Max는 6점인 왼쪽(L) 노드를 선택하게 된다.

주사위 게임 예제

주사위를 던져서 나온 눈의 수 만큼 점수를 가져가는 단순한 게임이 있다고 해보자. 규칙은 다음과 같다.

  • 주사위 게임규칙
    • 번갈아 가며 주사위를 던진다.
    • 주사위는 멈추고 싶을 때까지 원하는 만큼 던질 수 있다.
    • 주사위를 던저서 나오는 눈의 수 만큼이 자기 점수에 합산된다.
    • 다만, 눈이 1이 나오면 지금까지의 모든 점수를 다 잃고 0점이 된다.

이 게임에서 해결하고자 하는 문제는 컴퓨터가 주사위를 더 던질지 아니면 멈출지에 대한 결정이다. 이 결정을 위해 Expectimax 알고리즘을 적용해 보자.

현재까지 획득한 점수가 5점이라고 가정한다면, 각 선택 tree에 대한 chance node계산은 다음과 같다.

  • 선택 1 – 그만 던지기: 최종 획득 5점
  • 선택 2 – 던지기
    • 1이 나올 확률 1/6: 최종 획득 0점
    • 2 ~ 6이 나올 확률 5/6: 최종 획득 7.5점
16×0+16×(7+8+9+10+11)=7.5\frac{1}{6} \times 0 + \frac{1}{6} \times (7 + 8 + 9 + 10 + 11) = 7.5

주사위를 던지지 않으면 획득가치는 5점, 던지면 7.5점이므로 Expectimax 알고리즘은 주사위를 던지는 결정을 선택 한다.

그렇다면 현재 점수가 30점일 때는 어떨까?

  • 선택 1 – 그만 던지기: 최종 획득 30점
  • 선택 2 – 던지기
    • 1이 나올 확률 1/5: 최종 획득 0점
    • 2 ~ 6이 나올 확률 5/6: 최종 획득 28.33
16×0+16×(32+33+34+35+36)≈28.33\frac{1}{6} \times 0 + \frac{1}{6} \times {(32+33+34+35+36)} \approx 28.33

주사위를 던지지 않으면 획득가치는 30점, 던지면 28.33점이므로 Expectimax 알고리즘은 이번에는 주사위를 던지지 않는 결정을 선택 한다.

파이썬 코드 구현

Conclusion

이상으로 단순한 주사위 게임을 예로들어 Expectimax를 살펴 보았다. 확률이 개입되는 BlackJack이나 2048게임의 solver 같은 것을 구현 할 때에도 Expectimax는 어떤 결정을 해야할 것인 가에 대한 합리적인 해답을 제시해 주는 기본 토대가 되어 줄 수 있을 것이다. 보다 복잡한 문제를 푸는데 실제 적용을 위해서는 다양한 heuristic들이 보다 정교하게 고려되어야 하기는 하겠지만 상대가 두는 최악의 수만 고려하는 Minimax와 달리 확률적 환경의 무작위 성을 ‘개댓값’이라는 계산 가능한 값으로 받아들이는 Expectimax는 불확실성이 개입되는 많은 현실의 문제를 해결하는데 있어서 강력한 모델링 도구가 되어 줄 수 있을 것이다.

아마도 비슷한 글:

  1. Minimax Algorithm과 간단한 예제
  2. Alpha-Beta Pruning으로 Minimax 탐색시간 개선
  3. OpenVINO Object Detection Model의 전처리와 후처리를 간단하게
  4. Jinja2의 UnicodeDecodeError

Alpha-Beta Pruning으로 Minimax 탐색시간 개선

댓글 남기기

Minimax Algorithm과 간단한 예제 포스팅에서 사용했던 예제에서 main()함수에 있는 total_coins 변수의 값을 12에서 32이로 증가시켜서 실행해 보면 컴퓨터가 답을 내는 시간이 기하 급수적으로 늘어나서 첫 대답을 탐색하는데 대략 30초 정도 시간이 걸리는 것을 볼 수 있다(Macbook Pro M5 기준).

def main():
    total_coins = 32 # 원래는 12임.
    ...

이는 각 노드들의 선택가능한 조건이 3개씩이어서 32개의 코인을 가정하는 경우 이론상 대략 1000조가지가 넘는 노드들을 탐색해야 하기 때문이다.

Pruning(가지치기)

하지만, 실제로는 모든 노드들을 탐색해야 하는 것은 아니다. 개중에는 어차피 탐색해 들어가 봤자 선택되지 않을 값을 가진 것들이 있기 때문에 이러한 것들을 미리 알 수만 있다면 탐색 할 필요가 없는 경로들에 대해 탐색을 수행하지 않음으로써 소요되는 시간을 아끼고 효율적인 탐색을 수행할 수 있다. 이러한 동작을 “가지치기”라고 하는데, alpha와 beta라는 두개의 경계값을 유지하는 것으로 이루어진다.

  • α(alpha): 현재까지 Max(컴퓨터)가 확보한 가장 높은 점수
  • β(beta): 현재까지 Min(사용자)가 확보한 가장 낮은 점수

탐색 도중에 α >= β가 되는 순간이 있다면, 이러한 경로는 선택될 리가 없다고 가정하고 탐색을 중단한다.

구현 예제

다음의 코드는 “변형 nim game” 예제에 Alpha-Beta purining을 적용한 것이다.

실행결과 및 결론

이 프로그램을 실행하고 컴퓨터의 턴으로 게임을 시작하면 기존에 30초 가량 걸리던 탐색시간이 2초 정도로 줄어드는 것을 확인할 수 있다.

아마도 비슷한 글:

  1. Minimax Algorithm과 간단한 예제
  2. Heap tree 만들기
  3. OpenVINO Object Detection Model의 전처리와 후처리를 간단하게
  4. Jinja2의 UnicodeDecodeError

Minimax Algorithm과 간단한 예제

댓글 남기기

Minimax algorithm은 체스나 장기, 틱택토 혹은 오목 처럼 두 명의 플레이어가 번갈아 가면서 턴을 주고받는 유한 제로섬 게임(Finite zero-sum game)에서 최적의 선택을 내리기 위해 사용 할 수 있는 결정 트리 탐색 알고 리즘이다. 다시말해, 내가 얻는 이득이 상대의 손실이 되고, 내가 보는 손실이 상대의 이득이 되는 구조에서, “상대방은 항상 자신에게 유리한 선택을 하고 나에게는 불리한 선택을 한다”는 가정하에 자기 자신의 손실을 최소화(minimize)하고 이득을 최대화(maximize)하는 전략을 찾는 것이다.

이 포스팅에서는 minimax algorithm의 개념을 이해하고 간단한 게임에 적용시켜 최적의 해법을 찾아내는 과정을 확인해 본다.

Max Player와 Min Player

Minimax 알고리즘에서는 두 플레이어를 각각 Max와 Min으로 정의한다.

  • Max Player (컴퓨터): 자신의 점수를 maximize하려는 플레이어.
  • Min Player (상대방): Max의 점수를 minimize하려는 플레이어.

이 그림은 Max와 Min 두 플레이어가 서로 턴을 바꿔가며 결정하는 예제를 단순화 해서 트리로 그린 것이다. 각 선택 들의 최종 결과 값이 3, 5, 2, 9로 귀결된다고 할 때, Min은 Max의 이득을 최소화 하는 결정을 선택을 하게 될 것이므로, 왼쪽 노드의 3과 5중에서는 3, 오른쪽 노드의 2와 9중에서는 2를 선택할 것이다. 그렇다면 Max 입장에서는 Min이 결정 할 3과 2중에 이득을 최대화 하는 3을 고르게 되는 것이다.

전체 트리 상에는 Max가 이 게임에서 얻을 수 있는 더 큰 이득인 5와 9가 있지만 이들은 Min에 의해 버려지게 될 것이므로, Max 입장에서는 3을 얻기위한 결정을 수행하는 것이 최적이라고 할 수 있다.

변형 Nim 게임에 적용

Nim game은 “베스킨라빈스31” 게임과 유사한 것인데 판에 올려진 물체(코인)을 1개, 2개 혹은 3개씩 돌아가면서 가져가서 결국 마지막 남은 하나를 가져가는 사람이 지게되는 게임이다.

이것을 약간 변형해서 7개의 코인을 가정하고 컴퓨터와 번갈아 가면서 1개, 2개 혹은 3개씩 가져가서 최종적으로 남은 코인을 0개로 만드는 쪽이 이기는 게임을 “변형 Nim 게임”이라고 하고 여기에 minimax를 적용해 보도록 하자.

결정 트리의 모든 노드를 그리면 공간이 부족하니 Max(컴퓨터)가 3개를 가져가는 경우를 탐색하는 상황을 살펴보자. Max와 Min은 각각 번갈아 가면서 코인을 1개, 2개 혹은 3개를 가져가는 상황에 대하여 남은 coin이 0이 되는 상황을 탐색한다.

Max 입장에서 남은 코인이 0개가 되도록 만드는 node가 Min이 되도록 하는 조건이 유리하다고 판단하고, 이 때 큰 점수 +1을 매겨서 결정을 유도하고, 그 반대의 경우에는 -1 점수를 매겨서 이 상황을 피하도록 한다.

구현코드

이러한 트리 탐색 과정을 재귀함수로 나타내면 다음과 같다.

실행 결과 및 결론

다음은 전체 코인의 갯수를 설정하는 total_coins의 값을 12로 해서 수행한 결과이다.

결과를 보면 12 / 8 / 4개를 남기도록 하는 규칙을 명시적으로 주지 않았음에도 컴퓨터는 minimax tree로 부터 이러한 값들이 승부에 유리하다는 것을 탐색해서 항상 이러한 값에 가장 가까운 선택을 하려하는 것 처럼 보이는 약간의 지능적(?) 결과를 볼 수 있다.

아마도 비슷한 글:

  1. Heap tree 만들기
  2. OpenVINO Object Detection Model의 전처리와 후처리를 간단하게
  3. 한글 텍스트 추출을 위한 Python PDF module
  4. OpenVINO python을 이용한 inference 예제