스튜어드 러셀의 인공지능을 읽어보자(15) : 대항 검색2

https://startagainbornagain.tistory.com/111

스튜어드 러셀의 인공지능을 읽어보자(14) : 대항 검색1

 

게임의 최적 결정

 보통 검색 문제 (검색에 관한 URL)에서 최적해는 목표 상태로 가는 동작들의 순차열 형태입니다. 게임의 경우 목표 상태는 승리에 해당하는 말단 상태이고요. 대항 검색에서는 MIN이 게임에 변화를 줍니다. 따라서 MAX는 고정된 동작 열이 아니라 우발적 전략(strategy)을 찾아내야 합니다. 그 전략은 초기 상태에서의 MAX의 수들과, ㄱ에 대한 MIN의 모든 가능한 응수에서 비롯되는 상태들에서의 MAX의 수들, 그리고 그 수들에 대한 MIN의 모든 가능한 응수에서 비롯되는 상태들에서의 MAX의 수들 등등을 모두 지정합니다. 이는 and-or 검색과 아주 비슷합니다. MAX가 OR의 역할을 하고 MIN이 AND 역할을 한다고 생각하면 이해하시면 됩니다.

 

딕택토 같은 간단한 게임도 게임 트리 전체를 한 페이지에 그릴 수 없을 정도로 복잡합니다. 

 

 

틱택토 이미지

 

 

 

그래서 이제부터는 위에 있는 게임을 예로 사용하겠습니다. 뿌리 노드에서 MAX가 둘 수 있는 수는 a1, a2, a3입니다. a1에 대한 MIN의 응수는 b1, b2, b3 등입니다. 이 게임은 MAX와 MIN이 각각 한 수씩 두고 나면 끝납니다(게임 트리의 어법에서는 이 트리를 깊이가 한 수이고 반수(HALF-MOVE)가 둘인 트리라고 부르고, 그러한 반수를 겹(ply)이라고 부릅니다.) 이 게임의 말단 상태의 효용 값은 2에서 14까지입니다.

 

주어진 게임 트리에 대한 최적 전략은 MINIMAX(n)이라고 표기하는 각 노드의 최소 최대값(minmax value)에 기초해서 결정할 수 있습니다. 한 노드의 최소 최대 값은, 두 플레이어가 그 노드로부터 게임의 끝까지 최적으로 플레이한다는 가정하에서, 해당 상태에서의 효용 값(MAX를 위한)입니다. 말단 상태의 최소 최대 값이 그냥 해당 상태의 효용 값임은 자명합니다. 더 나아가서, 선택의 기회가 주어졌을 때 MAX는 최소 최대 값이 최대인 상태로의 수를 선호하는 반면 MIN은 그 값이 최소인 상태로의 수를  선호합니다. 이를 다음과 같이 표현할 수 있습니다.

 

그럼 이 정의들을 위 그림에 적용해보면 최하단 말단 노드들의 효용 값은 게임의 UTILITY 함수로 결정됩니다. 첫 번째 MIN노드 B의 세 후행 상태의 효용 값은 3, 12, 8 이므로, 그 노드의 최소최대 값은 3입니다. 마찬가지로, 다른 두 MIN 노드의 최소 최대 값은 둘 다 2입니다. 뿌리 노드는 MAX 노드입니다. 그 후행 상태들의 최소 최대 값은  3, 2, 2 이므로 뿌리 노드의 최소 최대 값은 3입니다. 이제 뿌리 노드에서의 최소 최대 결정(minimax decision)이 가능합니다. MAX에게는 a1 동작이 최적의 선택입니다. 그 동작이 최소 최대 값이 최대인 상태로 이어지기 때문입니다.

 

최소 최대 알고리즘

 최소최대 알고리즘(minimax algorithm; 또는 최소 극대화 알고리즘)은 현재 상태에서의 최소 최대 결정을 계산합니다. 이 알고리즘은 그냥 각각의 후행 상태의 최소 최댓값을 재귀적으로 계산합니다. 이 알고리즘은 그냥 각각의 후행 상태의 최소 최댓값을 재귀적으로 계산합니다. 이는 앞에 나온 최소 최대 공식을 그대로 구현한 것입니다. 이 알고리즘은 재귀를 통해서 트리의 말단 노드까지 나아가고, 재귀가 풀리면서 트리를 타고 최소 최대 값들을 되짚어 나갑니다.(백업개념)

 

다인용 게임의 최적 결정

 인기 있는 게임들 중에는 셋 이상의 플레이어가 참여할 수 있는 게임도 많습니다. 그럼 최소 최대 개념을 그런 다중 플레이어 게임으로 확장하는 방법을 살펴봅시다.  그러한 확장은 기술적인 관점에서는 간단하지만, 개념적으로는 몇 가지 흥미로운 새 주제를 던져줍니다. 우선, 각 노드에 하나의 값을 부여하는 것이 아니라 값들의 벡터를 부여해야 합니다. 예를 들어 플레이어 A, B, C가 참여하는 3인용 게임에서는 각 노드에 벡터(ua, ub, uc)를 부여합니다. 말단 상태에서 이 벡터는 각 플레이어의 관점에서 본 상태의 효용 값을 제공합니다.(2인용 영합 게임에서는 두 플레이어의 값이 항상 서로 반대이므로, 2 성분 벡터를 하나의 값으로 줄일 수 있습니다.) 이를 구현하는 가장 간단한 방법은 UTILITY가 효용 값들의 벡터를 돌려주게 하는 것입니다.

 

오늘은 여기까지구요 다음에는 알파 베타 가지치기에 대해 알아보도록 하겠습니다.