Minimax search

다음 두 플레이어가 존재한다.

• Maximizer (Player) : utility(보상)을 최대화하는 선택을 내림
• Minimizer (Opponent) : Player를 방해하는 방향으로, 즉 utility를 최소화하는 선택을 내림

두 플레이어가 서로 턴을 주고받으며 의사결정을 내리는 구조로, 이와 같은 탐색을 Adversary search(적대적 탐색)이라고 한다.

Minimax 알고리즘은 주로 다음과 같은 Tree 형태로 표현한다.

루트 노드에서 Player는 좌측 서브노드로 이동하던가 우측 서브노드로 이동하는 두 가지 선택을 내릴 수 있다. 이 때 Player는 최대한 높은 보상을 원한다.

보상 (10, 10, 9, 100)의 최대값은 100이므로 오른쪽으로 가고싶을 수도 있지만 우리는 Opponent가 우리의 결정에 훼방을 놓을 것이라는 사실을 이미 알고 있다.

Player가 우측 노드로 이동할 경우 Opponent는 100방향 서브노드가 아닌 9방향 서브노드를 선택할 것이고, 결과적으로 Player는 가장 작은 보상을 얻게 된다. 따라서 Max값인 100을 포기하고 이동하여 최소한 10이라는 값이 보장되는 좌측 노드로 이동하는 것이 가장 합리적이고 Optimal한 선택일 것이다.

Expectimax search

위 Minimax는 Minimizer, 즉 Opponent가 항상 optimal하고 deterministic하게 움직인다는 전제 하에 성립된다. 만약 Minimizer가 실수로 잘못된 결정을 내릴 가능성이 존재한다면, 좌측노드 대신 우측노드로 이동하는 것이 나름 괜찮은 선택이 될 지도 모른다. 물론 Risk가 존재하지만, 그만큼 큰 Return이 기다리고 있는 셈이다.

Expectimax는 이 점을 이용해 각 utility(보상)의 평균을 계산해 보상 평균을 최대화하는 지점으로 이동한다.

위 그림에서 루트의 서브노드가 Min 노드 대신 Chance 노드로 바뀐 것을 확인할 수 있다.
Chance 노드의 좌측, 우측 서브노드의 평균 utility는 각각 (10+10)/2=10과 (100+9)/54.5가 되겠다. 따라서 Maximizer는 54.5에 해당하는 우측 노드로 이동하는 선택을 내릴 것이다.

장점 (vs. Minimax)

• Non-optimal한 opponent에 대해 효과적이다.
• Minimax에 비해 더 높은 utility를 얻게될 가능성이 있다. (그만큼 risk도 있지만)

단점

• Optimal하지 않다.
• 느리다; 모든 트리 노드에 대해 탐색을 수행해야 한다. Minimax의 경우 $\alpha-\beta$ Pruning을 통해 수행 시간을 단축할 수 있지만, Expectimax는 이와 같은 pruning이 불가능하다.