Reversi 게임 제작하기 - 1

게임 트리

 

게임이론의 소개

 

게임이론(Game theory)은 자신의 이득을 극대화하기 위해서 수학적 분석 방법을 사용하는 기법이다. 게임이론은 경제학에서 많은 발전을 이루었고, 게임에서는 인공지능을 구현하기 위해서 사용한다. 게임이론을 알기 위해서는 몇가지 예를 통하여 이해하는 것이 좋다.

 

몬티홀 문제(Monty hall dilemma)는 잘못된 확률 상식을 발생시킬 수 있는 좋은 예이다. 몬티홀은 퀴즈에서 우승한 사람을 대상으로 상품을 고르도록 한다. 세개의 문이 있는데, 이 세개의 문중에 하나에는 비싼 스포츠 자동차와 다른 두개의 문 뒤에는 염소가 있다. 결국 우승자는 스포츠 자동차를 뽑기를 원한다.

 

몬티홀 문제

단순하게 선택한 문을 열어서 상품을 확인한다면, 3개중에 하나에만 상품이 있기 때문에 확률은 \(\frac{1}{3}\)이 된다. 그런데 여기서 몬티홀 문제가 시작한다. 사회자는 우승자가 선택한 문을 제외하고 다른 두 문중에 하나를 열어보이는데, 여기에는 염소가 있다. 그런 후 사회자는 우승자에게 자신의 선택을 바꿀 것인가를 물어본다. 열려있지 않은 두개의 문중 하나는 염소 하나는 스포츠카, 결국 두개 중 하나를 선택하는 것이기 때문에 확률은 \(\frac{1}{2}\)가 되는 것이 맞을 것 같다. 과연 그러한가?

 

두번째 문제는 죄수들의 딜레마(Prisoner's dilemma) 문제이다. 범죄를 저지른 것으로 예상되는 공범 두명을 심문한다. 그 둘에게 자백을 받아야 하는데 과연 어떻게 해야 할 것인가? 이 때, 두명의 용의자를 각각 다른 방에 떼어놓고 심문을 하게 된다. 이 때 용의자 A, 용의자 B에 대해서 각각의 자백에 대해서 다음과 같이 적용한다면, 어찌 될 것인가?

 

	A의 침묵	A의 자백
B의 침묵	A, B 6개월형	A 석방 B 10년형
B의 자백	A 10년형 B 석방	A, B 5년형

 

여기서 B의 입장에서 생각을 해보자. B는 A가 침묵할 경우 자백을 하면 석방되므로 자백이 유리하다. A가 자백할 경우에도 B는 자백하는 것이 유리하다. 결국 자신의 입장에서 자백을 하는 것이 여러모로 유리하다. 역으로도 이것은 적용이 된다. 결국 이 게임이론에서 보면 A, B 모두 자백하는 것이 바람직하다. 그러나 과연 그럴까?

 

일반적으로 둘이서 진행하는 게임인 경우, 한사람이 이득을 보는 경우 다른 사람은 손해를 보게 된다. 바둑, 장기, 체스 등이 좋은 예이다. 바둑의 경우 서로 집을 넓힌다고 해서 서로 이득을 보는 것이 아니다. 결국 두사람의 집차이에 의해서 승패가 갈린다. 장기, 체스의 경우에도 상대방의 말을 먹음으로써 보다 유리한 위치에 설 수 있다. 이러한 게임 규칙을 가진 경우 제로섬(Zero-sum) 게임이라고 한다.

 

여기서 우리가 적용하는 방법이 확장형 트리를 이용한 게임 트리이다. 게임트리는 게임의 승패를 판단하는데 있어서 유용하다.

 

게임 트리의 알고리즘

 

상대방이 있는 게임이 확률적 분포를 따르든 바둑, 장기 등과 같이 규칙에만 의해서 선택하든 우리는 게임 트리로 최선의 선택을 할 수 있다. 그러나 게임 트리는 앞을 내다보아야 할 트리의 깊이가 깊어질수록 기하급수적으로 더 많은 계산을 해야 한다.

 

예를 들어서 틱택토(Tic-Tac-Toe) 게임을 보자. 틱택토 게임은 3x3 공간에 두 사람이 O, X를 번갈아 그리게 된다. 가로줄, 세로줄, 대각선에 같은 기호가 3개 있게 되면 게임을 이기게 된다. 이 게임은 최대 9번 돌을 놓으면 게임이 종료된다. 이것을 기초로 계산하면 9!의 수를 계산해야지 게임의 승패를 알 수 있다. 9!은 362,880으로 비교적 작은 경우의 수이다.

 

 

Tic-Tac-Toc

게임트리의 모든 경우를 다 계산해주면 반드시 게임을 이기거나 적어도 최선의 선택을 할 수 있다. 그러나 그러한 계산을 현실적으로 하는 것은 불가능하다. 오델로 게임의 경우 평균 4군데 놓을 수 있는 자리가 있다고 가정하면, 말단 노드의 갯수는 어림잡아도 \(4^{60}\)정도이며, 이것을 계산하면 \(10^{36}\)이 된다. 초당 1억번 계산할 수 있다고 가정해도 약 \(10^{28}\)초의 시간이 소모되며, \(10^{18}\)년정도의 시간이 소모된다. 결국 평생 계산을 해도 결과를 볼 수 없다. 설사 컴퓨터 속도가 지금보다 백만배 빨라진다고 해도, 1조년 이상의 시간이 소요된다.  태양계의 나이가 45억년인 것을 생각한다면, 그 시간의 20배의 시간이 소모된다.  바둑의 경우에는 훨씬 더 어렵다.

 

수가 적은 것으로 알려져 있는 체스의 경우, 컴퓨터가 체스 챔피언을 이겨서 화제가 된 적이 있다. 하지만 이 경우에도 컴퓨터가 모든 경우의 수를 계산한 것은 아니다. 이와 같이 게임트리에는 많은 최적화 알고리즘이 소개되고 있으며, 여기에서는 게임트리를 계산하는 알고리즘과 가장 보편적인 최적화 알고리즘을 소개하도록 한다.

 

미니맥스(Minimax) 알고리즘은 게임트리에서 최적화 경로를 결정하는 역할을 한다. 두명의 플레이어가 서로 이기기 위한 게임을 한다면, 한명의 플레이어가 이기면 상대방 플레이어는 지게 된다. 이때 플레이어 1을 기준으로 할 때, 플레이어1은 한수준 아래의 트리에서는 최대점수를 추구하게 되며, 두번째 수준 아래의 트리에서는 최소점수를 추구하게 될 것이라는 것이다. 이는 각자의 플레이어가 최선의 선택을 할 경우 당연하다.

 

게임트리

첫번째 수준에서는 최대값을 찾아서 9라는 값을 얻을 것이다. 두번째 수준에서는 갈 수 있는 경로에서 최소값을 찾아서 각각 9와 6이라는 값을 얻게 된다. 두번째 플레이어는 플레이1에게 불리한 방향으로 선택하는 것이 최선의 선택히기 때문이다. 세번째 수준에서는 최대값을 찾아서 각각 10, 9, 6, 12란 값을 가지게 된다. 마지막 노드에서는 정해진 방법에 따라서 점수를 계산한다.

 

이 방법으로는 원하는 수준의 값들에 대해서 최선의 선택을 할 수 있지만, 이보다 더 계산량을 줄일 수 없을까를 생각해야 한다. 미니맥스 알고리즘에서 푸른색 노드에서는 자식노드에서 최소값을 선택함을 알고 있다. 그러나 그 윗단계에서는 최대값을 선택하기 때문에 두번째 트리의 첫번째 녹색 노드에서 6의 값이 나왔기 때문에 그 다음 서브 트리에서 어떤 값이 나오던 9가 선택되는 것은 당연하다. 6보다 큰 값이 나와보았자, 위의 트리에서는 최소값을 선택하므로 당연히 6이 선택될 것이고, 6보다 작은 값이 나오면 그 값으로 선택되겠지만 9란 그 위의 노드에서는 최대값을 선택하므로 9가 선택되는 것이 당연하다. 이와 같이 트리 계산을 줄이는 방법을 알파-베타 가지치기(Alpha-beta pruning) 기법이라 한다.

 

알파-베타 가지치기

컴퓨터가 모든 경우를 다 놓지 못하기 때문에 중간에 점수를 계산하는 로직이 들어가야 한다. 점수를 계산하는 로직은 대부분의 경우 경험적으로 얻어진다. 바둑의 경우에는 가장 복잡한 경우중 하나이다. 점수 계산을 잘 짜면 그만큼 추측한 결과가 실제 해에 더 접근하므로 좀 더 적은 경우를 검사하더라도 좋은 결과를 얻을 수 있다.