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

https://startagainbornagain.tistory.com/126

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

 

확률론적 게임

  실생활에서는 예측할 수 없는 여러 외부 사건들 때문에 의외의 상황에 처하기도 합니다. 여러 게임들은 주사위 굴림 같은 무작위 요소를 도입해서 이러한 예측 불가능성을 반영합니다. 그런 게임을 확률론적 게임(stochastic game)이라고 부릅니다. 운과 기술(skill)이 결합된 전형적인 게임으로 백개먼이 있습니다.

https://ko.wikipedia.org/wiki/%EB%B0%B1%EA%B0%9C%EB%A8%BC 여기서 붉은 색인 것을 흰색(백)으로 보겠습니다.

백개먼에서, 각 플레이어의 차례에서 플레이어는 먼저 주사위를 한 번 굴려서 적법한 수들을 결정합니다. 백이 자신의 적법한 수들을 알긴 하지만. 다음에 흑의 주사위 굴림 결과를 알지는 못하며, 따라서 흑의 적법한 수들을 알 수 없습니다. 이는 백이 체스와 틱택토에서 본 표준적인 게임 트리를 구축할 수 없음을 뜻합니다. 백개먼의 게임 트리는 MAX노드들과 MIN노드들은 물론 우연 노드(chance node; 또는 기회 노드)들도 포함해야 합니다. 이러한 방향으로 나아가다 보면, 결정론적 게임의 최소최대 값을 우연 노드가 있는 게임의 기대최소최대 값(expectiminimax value)으로 일반화하게 됩니다. 말단 노드들과 MAX, MIN노드들(주사위 굴림이 알려진 노드들에 대한)은 이전과 정확히 동일한 방식으로 취급합니다. 우연 노드들에 대해서는 기댓값을 계산합니다. 여기서 기댓값은 각 우연동작의 확률을 가중치로 적용해서 모든 가능한 결괏값을 합산한 것 입니다.

 

우연이 있는 게임을 위한 평가 함수

  최소최대에서 처럼, 기대최소최대에 대한 명시적 근사는 특정 지점에서 검색을 차단하고 각 잎 노드에 평가 함수를 적용하는 것입니다. 체스를 위한 평가 함수 처럼 백개먼 같은 게임을 위한 평가 함수도 더 나은 국면을 더 높게 평가 해야 합니다. 그러나 백개먼 같은 게임에는 우연 노드가 존재하기 때문에, '평가'의 의미를 좀 더 세심하게 다룰 필요가 있습니다. 프로그램이 게임의 나머지 과정에서 나올 모든 주사위 굴림을 미리 안다면, 주사위를 사용하는 게임을 푸는 것은 그냥 주사위 없는 게임을 푸는 것과 동일합니다. 이때 최소최대의 시간 복잡도는 O(b의 m승)으로, 여기서  b는 분기 계수이고 m은 게임 트리의 최대 깊이입니다. 기대최소최대는 모든 가능한 주사위 굴림 순차열도 고려하므로, 시간 복잡도는 O(b의 m승 n의 m승)입니다.

검색 깊이를 어떤 작은 깊이 d로 제한한다고 해도, 최소최대에 비한 추가 비용 때문에 대부분의 우연이 있는 게임에서는 수를 아주 멀리 내다보는 것이 비현실적입니다(모든걸 계산하기 어렵기 때문에). 백개먼에서 n은 21이고 b는 흔히 20정도 이니, 주사 굴림이 더블일 때는 4000까지 올라갈 수 있습니다. 그런 경우 감당할 수 있는 깊이는 세 겹입니다.

  알파베타의 장점은 최선의 플레이가 주어졌을 때 어차피 발생하지 않을 미래의 전개를 무시한다는 것입니다. 즉, 알파베타는 발생할 가능성이 있는 사건들에 집중합니다. 주사위를 사용하는 게임에서는 발생할 가능성이 있는 수들의 순차열이라는 것이 존재하지 않습니다. 그런 수들이 실제로 발생하려면 주사위를 굴렸을 때 그런 수들이 적법해지는 결과가 나와야 하기 때문입니다. 이는 불확실성이 관여하는 상황에서 일반적으로 발생하는 문제입니다. 그런 상황에서는 가능성들이 크게 증폭되며, 동작들을 구체적으로 계획한다는 것이 의미가 없어집니다(어차피 세상이 플레이어가 계획한 대로 돌아가지 않을 것이므로).

  알파베타 가지치기 같은 알고리즘을 우연 노드가 있는 게임 트리에 적용할 수 있지 않을까 생각하시는 분들이 계실텐데, 실제로 가능합니다. 이 경우 MIN노드들과 MAX노드들에 대한 분석은 이전과 동일하며, 약간의 창의성을 가미하면 우연 노드들도 쳐낼 수 있습니다. 

 

그 이후는 몬테카를로 시뮬레이션과  부분 관찰 가능 게임에 대해 이야기합니다. 이 부분은 아마 제가 프로젝트하면서 설명하게 될 것 같아서 나중에 자세히 알아보도록 하겠습니다.