게임 놀이
인공지능 : Elaine Rich 저서, 유석인.전주식.한상영 편역, 상조사, 1986 (원서 : Artificial Intelligence, McGraw-Hill, 1983, Artificial Intelligence (2nd ed, 1991)), Page 125~144
(1) 순조로움의 기다림 (Waiting Quiescence)
게임은 많은 사람들에게 흥미를 끌어 왔고, 컴퓨터가 게임을 한다는 개념은 컴퓨터가 처음 만들어졌을 때부터 존재해 왔다. 찰스 배비지 (Charles Babbage) 는 그의 수리 엔진 (Analytic Engine) 을 사용하여 체스를 두는 프로그램을 작성하려 했으며, 후에 삼목놀이 (tic-tac-toe) 를 하는 기계를 만들었다. 클라우드 셰논 (Claude Shannon) 은 체스 프로그램에 사용될 수 있는 기법과 관련된 논문을 발표했으며, 몇 년후, 앨런 튜링은 체스 프로그램을 작성했다. 1960 년대 초기에, 아더 사무엘 (Arthur Samuel) 에 의해 실제로 사용이 가능한 게임 프로그램이 처음으로 만들어졌다. 그의 프로그램은 단순히 체스를 두는 것 뿐만 아니라, 실수를 깨닫고 수행 능력을 향상시킬 수 있다.
게임이 기계의 지능을 조사하기에 적합한 분야로 생각되는데는 두 가지 이유가 있다.
위의 두 가지 이유중 첫번째 이유는 타당하며, 기계에 의한 게임 분야에 대해 계속적인 관심을 두는 것도 이것 때문이다. 그러나 두 번째 이유는 매우 단순한 게임을 제외한 어느 게임도 적용되지 못한다. 예를 들어 체스를 살펴 보자.
단순히 게임 트리만을 탐색하는 프로그램은 상대방이 살아있는 동안 단 한 수도 두지 못할 것이 분명하다. 이를 해결하기 위해 일종의 경험적 탐색 방법이 필요하다.
지금까지 논의된 탐색 과정을 통해 가능한 모든 풀이를 만든 후, 테스트 과정에서 이 풀이의 가치를 평가할 수 있다. 또 다른 극단적인 면에서 볼 때, 해답의 생성 과정을 사용하여 탐색 공간내에서의 개개 움직임을 만들고,, 테스트 과정에 의해 각 움직임의 가치를 평가하면서, 가장 유망한 움직임을 선택하는 방법을 이용할 수 있다. 다음 두 가지를 수행하여 탐색을 기초로 한 문제 풀이 프로그램의 효율성을 향상시킬 수 있다.
위의 두 작업은 게임 프로그램에서 특히 중요한 역할을 한다. 체스 문제를 다시 살펴 보자. 매번 이용 가능한 움직임은 35 개 정도이다. 만약 단순히 움직임만을 만드는 과정을 사용한다면, 테스트 과정 (이 과정은 탐색과 경험적 지식에 사용되는 평가 함수를 적절히 결합하여 사용한다) 에서 이들 각각을 조사해야 한다. 이 경우 테스트 과정은 매우 많은 가능성을 조사해야 하기 때문에, 엄청나게 빨리 수행되어야 한다. 따라서 테스트 과정은 수행되어야 할 일을 모두 정확하게 처리하지 못할 경우도 있다. 반면 움직임만을 만드는 과정 대신, 이길 가능성이 있는 이동을 만들어 내는 과정 (plausible-move generator) 을 사용하여, 유망한 몇 개의 움직임만을 만들어 낸다고 가정하자. 이러한 경우에는, 움직임의 수가 증가할수록, 유망한 움직임을 선택하기 위해 경험적 지식을 사용하는 것이 더욱 더 중요해진다. 이것은 체스 프로그램에서 특히 중요한 역할을 한다. 상당히 선택적인 움직임을 만들어 내는 테스트 과정을 사용할 경우, 주어진 각 움직임의 가치를 평가하기 위해 필요한 시간이 증가할 수 있다. 따라서 신뢰도가 높은 결과를 얻을 수 있다. 경험적 지식을 해답의 생성과 테스트 과정과 함께 결합하여, 전체적인 시스템의 수행 능력을 향상시킬 수 있다.
물론, 다른 분야에서의 문제에서 처럼 게임에서도, 탐색만이 이용 가능한 기법인 것은 아니다. 일부 게임에서는, 상당히 직접적인 기법을 사용하는 것이 바람직한 경우도 있다. 예를 들어, 체스의 경우, 체스를 처음 시작할 때와 끝날 때는 흔히 일정한 양식에 따라 수행되기 때문에, 저장된 패턴의 데이터 베이스를 사용하여 게임을 최적으로 수행할 수 있다. 게임을 수행할 때 탐색을 기초로 한 방법과 탐색을 필요로 하지 않는 기법을 함께 적절히 사용하는 것이 효과적이다.
문제에 대한 풀이를 찾기 위해 탐색 과정을 사용할 때 이상적인 방법은 목표 상태에 도착할 때까지 문제 공간내에서의 움직임을 만들어 내는 것이다. 게임 프로그램의 목표 상태는 승리의 상태이다. 그러나, 체스와 같은 게임의 경우, 비록 이길 수 있는 움직임을 효과적으로 만들어 내는 과정을 사용한다 하더라도, 목표 상태를 찾아 낼 때까지 탐색하는 것은 대체로 불가능하다. 장기에 대한 게임 트리 (그래프) 의 깊이와 분기 계수가 매우 크기 때문에 허용된 시간 내에 기껏해야 깊이 10 정도 까지의 움직임밖에 탐색할 수 없다.
최적 움직임을 선택하기 위해서는 정적 평가 함수를 사용하여 만들어진 장기판의 위치를 비교함으로써 유망한 움직임을 찾는다. 개개의 장기판 위치로부터 궁극적인 승리를 획득할 가능성을 추정하는 정적 평가 함수 (static evaluation function) 는 이용할 수 있는 모든 정보를 사용하여, 각 장기판의 위치에 대한 가치를 평가한다. 정적 평가 함수의 기능은 A* 알고리즘의 경험적 방법에 사용되는 함수 h' 의 기능과 유사하다 - 불완전한 정보를 이용하여, 이길 가능성이 가장 큰 위치를 선택한다. 물론 유망한 움직임의 결과로 만들어진 장기판의 상태를 직접 정적 평가 함수를 적용할 수도 있지만, 그러나 매우 효율적인 정적평가 함수를 만든다는 것이 어렵기 때문에, 가능한 한 게임 트리의 많은 레벨에 이 평가 함수를 적용하는 것이 좋다.
적합한 정적 평가 함수를 만드는 작업은 게임 프로그램에서 하는 일의 대부분을 차지한다. 튜링 (Turing) 은 장기말의 장점을 바탕으로 한 매우 단순한 정적 평가 함수를 제안하였는데, 이 정적 평가 함수는 단순히 검정색 장기말의 값 (B) 과 흰색 장기말의 값 (W) 을 구해, 몫 W/B 를 계산한다. 사무엘 (Samuel) 의 장기 프로그램에서는, 의미가 있는 몇몇 간단한 함수들을 선형적으로 결합한 복잡한 정적 평가 함수가 사용되었다. 사무엘의 함수에는, 전진 능력, 중앙 본래의 제어, 겹장 (fork) 의 위협 및 이용성과 같이 체스를 둘 때 고려해야 할 요인들이 반영되어 있다. 이 요인들 각각에 적절한 가중 값을 주고 이것을 모두 더해 결합하였다. 즉 완전한 정적 평가 함수의 형태는
C1* 장기말의 장점 + C2* 전진 + C3* 중앙 본래의 제어 ……
이다. 여기에는 이러한 요인들의 조합을 반영하는 비선형 항도 있다. 그러나 사무엘은 각 성분에 지정될 가중값을 정확하게 알 수 없었기 때문에 승리로 이끈 움직임을 제공한 성분에는 증가된 가중값을 주었고 실패로 유도한 움직임의 성분에 대한 가중값은 감소시키는 단순한 기법을 사용하였다. 그러나 주어진 한 움직임이 승리로 이끌 움직임인지 실패로 이끌 움직임인지 결정하는 것이 항상 쉬운 일은 아니다. 체스를 둘 때, 한쪽이 패착이 되는 움직임을 수행했다고 가정하자. 그러나 그 다음 상대방도 실수를 저질러, 결국에 가서는 이길 수 있었다고 하자. 수행된 일련의 움직임 가운데, 실제로 발생한 특정한 결과에 책임이 있는 움직임을 결정하는 문제를 책임 배정 문제 (credit assignment problem) 이라 한다. 이러한 문제는 게임뿐만 아니라, 학습 기법 (learning mechanism) 에도 관련된다. 사무엘의 체스 프로그램은 그 프로그램의 작성자를 이길 수 있는데, 이를 위해 사용된 기법이 제 11 장에서 더욱 자세히 설명된다.
지금까지, 게임 프로그램 중 지식을 토대로 한, 두 가지 중요한 성분에 대해 논의했다. 이 두 가지 요소는 이길 수 있는 장기말의 움직임을 만드는 과정과 정적 평가 함수로써, 수행될 특정한 게임과 관련된 지식과 결합하여 사용되어야 한다. 그러나 위 두 성분의 기능에 결함이 있다면, 앞으로 발생될 일을 예측하기 위해, 가능한 한 많은 움직임들을 미리 조사하는 탐색 과정이 필요하다. 물론, 다른 분야의 문제풀이에서 처럼 탐색에 이용될 수 있는 지식의 양을 변경시킴으로써, 탐색의 역할을 상당히 바꿀 수 있다. 그러나 게임 프로그램은 여전히 탐색에 의존한다.
어떤 탐색 방법을 이용할 수 있는가? 간단한 1 인용 게임이나 퍼즐의 경우, 제 3 장에서 소개된 A* 알고리즘을 사용하여, 허용된 시간내에 현재 상태로부터 가능한 한 멀리까지 전진 추론할 수 있다 (다음에 수행될 최적 움직임을 선택할 수 있도록). 경험적 방법에 사용되는 함수 h' 를 단말 노드에 적용한 후, 탐색 그래프를 후진하면서, 각 노드 값에 이 값을 반영시킨다. 그러나 상대방의 특성 때문에, 체스와 같은 2 인용 게임에 이 과정을 적용하는 것은 부적합하다. 그래프를 후진하며, 값을 변경시킬 때, 프로그램에 의해 선택될 움직임의 레벨과 상대방에 의해 선택될 움직임의 레벨에 대해, 각기 다른 가정이 만들어 져야 한다. 이를 위해 여러 가지 방법이 사용되는데, 다음 절에서는 가장 흔히 사용되는 최대 최소 과정을 소개하였다. 또 하나의 방법은 B* 알고리즘인데, 이것은 표준 문제 트리 (standard problem-solving tree) 와 게임 트리 (game tree) 에 모두 적용된다.
최대 최소 탐색 과정 (minimax search procedure) 은 깊이가 제한된, 깊이 우선의 탐색 과정으로 1-3-1 절에서 간단히 소개되었다. 현재 위치에서 출발하여, 이길 수 있는 움직임을 만들어 내는 과정을 사용하여, 가능한 다음 번 위치를 만드는 것이 과정의 개념이다. 이들 위치에 정적 평가 함수를 적용하여, 최적 위치를 선택한 후, 출발 위치를 향해 후진하며, 평가된 값을 전달한다. 좋은 상황에 대해 높은 정적 평가 함수의 값이 주어진다고 가정할 경우, 체스에서는 다음 장기판의 위치에 대한 정적 평가 함수의 값을 최대화하는 것이 목표이다.
그림 1 1 단계 탐색
그림 1 을 예로 하여 이 과정의 작용을 살펴 보자. 정적 평가 함수의 범위를 -10 에서 10 사이로 할 때, 10 은 우리의 승리를, -10 은 상대방의 승리를, 0 은 비기는 경우를 나타낸다. 경험적 방법에 사용되는 함수의 값을 최대화하는 것이 목표이기 때문에, 위의 그림에서는 B 로의 움직임을 선택한다. B 의 값을 A 로 후진 전달하면, 8 의 값을 가진 위치로 움직일 수 있다는 것을 알게 되어 A 의 값을 8 로 수정한다.
그림 2 2 단계 탐색
그러나, 체스에서는 상대방에 의해 다음 번에 수행될 움직임과, 위의 레벨로 후진될 단말 값을 고려해야 한다. 우리가 B 로 움직였다고 가정하자. 이때 상대방은 E, F 와 G 중의 하나를 선택한다. 상대방의 목표는 평가 함수의 값을 최소화하는 것이기 때문에 F 로 움직일 것이다. 만약 B 로 움직인다면, 한번 움직인 후, 연이어 발생될 실제 위치는 우리에게 매우 불리하다. 만약 상대방이 노드 E 를 선택한다면 우리에게 유리하지만, 이 단계는 상대방이 움직일 차례이기 때문에, 상대방은 노드 E 를 택하지 않을 것이다. 그림 3 은 새로운 값을 트리의 위쪽으로 전달한 결과를 나타낸다. 상대방이 선택할 차례에서는 그 레벨에서 가장 작은 값이 선택되어 후진 전달되며, 우리가 선택할 차례에서는 그 레벨에서 가장 큰 값이 선택되어 후진 전달된다.
그림 3 2 단계 탐색의 값의 후진 전달
두번 움직였을 때의 값을 후진시키면 우리는 C 로 움직이는 것이 유리하다는 것을 알 수 있다. 왜냐하면, 이용 가능한 정보가 주어졌을 때, 상대방이, -2 보다 더 낮은 값을 만들기 위해, 그곳에서 할 수 있는 일이 전혀 없기 때문이다. 시간이 허용하는 한 이러한 과정을 여러번 반복 수행하고, 루트 노드가 있는 레벨에서 최적의 움직임을 선택하기 위해, 이 과정의 실행에 의해 만들어진 좀 더 자세한 평가를 사용한다. 평가로부터 얻은 값을 후진시킬 때 교대로 최대값과 최소값을 선택하는 것은 두 경기자의 상반되는 전략을 설명하며, 이로 인해 이 과정이 최대 최소 방법이라 불려진다.
지금까지 최대 최소 과정의 작용 방법을 대략적으로 설명하였는데, 이제 이 과정을 정확히 알아 보자. 최대 최소 과정을 수행할 게임에 따른 두 개의 특정한 보조 과정에 의해 결정되는 순환적인 과정이다 :
|
MOVEGEN(Pos) : 이길 수 있는 움직임을 만들어 내는 과정으로, Pos 에서 출발하여 갈 수 있는 움직임을 나타내는 노드들의 목록을 돌려 준다. STATIC (Pos, Depth) : 정적 평가 함수로서, Pos 의 유용성을 나타내는 숫자를 돌려준다. 높은 값은 Depth 가 홀수인지 짝수인지에 따라, 움직일 방향에 대해 좋은 움직임을 알린다. STATIC 을 부른 과정은 그 점수를 최대화하려 한다. 계산된 값을 위쪽 레벨로 후진시킬 때, 상대 경기자의 가망성에서 볼 때, 상황의 유리함을 반영하기 위해 그 값에 음수 부호를 붙힌다. 각 단계마다 교대로 값의 역을 취함으로써 MINIMAX 과정을 매우 간단히 할 수 있다. 사실상 이용 가능한 값중 항상 최대값을 선택하면 된다. |
어느 순환적인 프로그램에서나 처럼, MINIMAX 작성시 가장 중요한 문제점은 순환을 중단하고 정적 평가 함수를 불러야 할 때를 결정하는 것이다. 많은 요인들이 이 시기의 결정에 영향을 미치는 데, 여기에는 다음과 같은 것이 포함된다 :
일반적인 MINIMAX 과정의 경우, DEEP-ENOUGH 라는 함수가 사용되는데, 이 함수는 위의 요인 모두를 평가하여 현재 레벨에서 탐색이 중단될 수 있다면 TRUE 를, 그렇지 않다면 FALSE 를 돌려 준다. 함수 DEEP-ENOUGH 의 수행을 위해, 탐색의 현재 깊이를 나타내는 값 하나만, 이 함수에 알려 주면 된다. 다른 여러 정보를 사용하여 좀 더 복잡한 DEEP-ENOUGH 를 만들 수 있다.
MINIMAX 를 순환 과정으로 정의할 때 발생하는 한 가지 문제는, MINIMAX 가 하나가 아닌 두 개의 결과를 돌려 주어야만 한다는 것이다 :
MINIMAX 가 위의 두 결과를 포함하는 구조를 돌려 준다는 것과 이 구조로부터 개개의 성분을 뽑아내는 함수 VALUE 와 PATH 가 사용된다고 가정하자.
MINIMAX 과정을 순환 함수로 정의하였기 때문에 이것을 처음 어떻게 불러야 하는지, 이에 대한 방법을 규정해야 한다. 이를 위해, 장기판의 위치와 탐색의 현재 깊이라는 두 개의 매개 변수를 사용한다. 위치 CURRENT 로 부터 최적 움직임을 결정하기 위해 수행될 과정의 초기 호출은 다음과 같다 :
MINIMAX (CURRENT, 0)
▷▶▷ MINIMAX (Position, Depth)
1. 만약 DEEP-ENOUGH (DEPTH) 가 참이면, 다음과 같은 구조를 돌려 주어라. 이것은 이 노드로부터 시작되는 경로가 존재하지 않으며, 정적 평가 함수에 의해 이것의 값이 결정된다는 것을 의미한다.
2. 그렇지 않다면, MOVEGEN (POSITION) 을 불러, 이것으로부터 얻은 목록을 SUCCESSORS 로 함으로써, 트리의 레벨을 하나 더 만들어라.
3. 만약, SUCCESSORS 가 빈 목록이라면, 어떤 움직임도 만들어 질 수 없다. 이 경우에는, DEEP-ENOUGH 가 참의 값을 가진다고 가정할 때 얻을 수 있는 구조를 돌려 주어라.
4. 만약, SUCCESSORS 가 빈 목록이 아니라면, 이것의 각 원소를 조사하여 최적 원소를 선택해 기억하라. 이것은 다음에 따라 수행된다.
5. BEST-SCORE 의 초기값으로 STATIC 에 의해 얻을 수 있는 최소값을 배정하라. SUCCESSORS 의 원소로부터 얻을 수 있는 최적 점수를 반영하기 위해, 이 값은 수정된다.
6. SUCCESSORS (SUCC 이라 하자.) 의 각 원소에 대해 다음을 수행하라 :
1) RESULT-SUCC 에 MINIMAX (SUCC, DEPTH+1) 의 값을 지정하라. MINIMAX 를 순환적으로 호출하여 SUCC 를 조사한다.
2) NEW-VALUE 에 -VALUE (RESULT-SUCC) 을 지정하라.
3) 만약 NEW-VALUE > BEST-SCORE 하면, 지금까지 조사된 어느 후계 위치보다도 유리한 후계 위치를 찾은 것이다. 이를 기록하기 위해 다음을 수행하라.
① BEST-SCORE 에 NEW-VALUE 를 지정하라.
② 지금까지 알려진 최적 경로는 CURRENT 로부터 SUCC 까지의 경로이며, MINIMAX 를 순환적으로 호출하여, SUCC 으로 부터의 적절한 경로를 찾을 수 있다. 따라서 PATH (RESULT-SUCC) 에 SUCC 을 결합시킨 결과를 BEST-PATH 로 지정한다.
7. 모든 후계 위치를 조사하였기 때문에, NODE 의 값을 알 수 있고, 그 NODE 로부터 택한 경로도 알 수 있다. 따라서 다음과 같은 구조를 돌려 주어라.
VALUE = BEST-SCORE ;
PATH = BEST-PATH
그림 2 에 보여진 게임 트리에 위 과정을 적용, 수행시켜 이 과정이 어떻게 작용하는지, 그 작용 방법에 대해 알 수 있다.
위에서 설명된 MINIMAX 과정은 매우 간단한 것이지만, 일부를 수정하여 이것의 수행 능력을 향상시킬 수 있다. 이들 중 몇 개가 다음 절에서 소개된다.
최대 최소 과정은 깊이 우선 탐색 과정이다. 시간이 허용되는 범위내에서 가능한 한 많은 경로를 조사하고 정적 평가 함수를 경로의 마지막 레벨의 게임 위치에 적용하여 얻어진 값을 한번에 한 레벨씩 경로 위로 후진하며 전달한다. 깊이 우선 탐색 과정의 한 가지 장점은 이미 알려진 해답보다 부적합한 것으로 판명된 부분적인 해답은 조사하지 않는 분기와 한계 방법을 사용하여, 이 과정의 효율성을 향상시킬 수 있다는 점이다. 2-1-2 절에서 이 기법을 응용한 세일즈 맨의 방문 문제를 소개하였다. 이 문제의 경우, 지금까지 발견된 최적 경로를 기억하는 것만이 필요한 작업이다. 만약, 후에 조사된 부분적인 경로가 이 한계보다 커지면, 이 경로의 탐색을 중단한다. 경기자의 최대화와 최소화를 모두 처리할 수 있도록 탐색 과정을 수정했던 것처럼, 각 경기자에 대해 하나씩 두 개의 한계를 포함하도록 분기와 한계 방법을 수정할 필요가 있다. 이 수정된 방법을 알파-베타 자르기 (alpha-beta pruning) 라 한다. 알파-베타 자르기의 수행을 위해 두 개의 출발 값이 사용되는데, 한 값은 최대화를 목표로 하는 노드에 배정될 값의 하한값 (알파라 부른다) 이며, 다른 한 값은 최소화를 목표로 하는 노드에 배정될 값의 상한값 (베타라 부른다) 을 나타낸다.
그림 4 알파 자르기
그림 4 에 보여진 예를 사용하여 알파-베타 자르기의 작용 방법을 알아 보자. 노드 F 를 조사하고 우리는 상대방이 -5 이하의 값을 배정받을 노드 C 를 선택할 것임을 알 수 있다 (상대방은 최소화를 목표로 하기 때문이다). 그러나 또한 우리는, 만약 노드 B 로 움직인다면, 노드 A 에 적어도 3 의 값이 배정된다는 것도 알 수 있다. 3 보다 적은 값을 만드는 노드로 움직이는 것은 노드 B 로 움직이는 것보다 부적합하다.
따라서 그러한 노드로의 움직임은 무시할 수 있다. 또한 노드 F 만을 조사하고도 노드 G 의 값에 관계없이, 노드 C 로 가는 것은 부적합하다는 것을 확신할 수 있다. 그러므로 노드 G 를 조사할 필요가 없다. 물론, 하나의 노드를 잘라 버림으로써 한계를 기억하고, 이들을 조사하기 위해 필요한 비용을 정당화할 수 있는 것은 아니지만, 만약 여섯 단계 이상의 트리를 조사해야 한다면, 단 하나의 노드만이 제거되는 것이 아니라, 전체 트리의 세 단계를 조사하지 않을 수도 있다.
알파와 베타가 모두 사용되는 방법을 보기 위해, 그림 5 에 소개된 예를 살펴 보자. 이 트리를 탐색할 때, 노드 B 를 루트로 한 부분 트리를 모두 조사하여, 노드 A 에 적어도 3 의 값이 배정될 것임을 예측할 수 있다. 노드 F 를 지나 아래로 탐색해 갈 때, 알파 값을 사용하여 노드 L 은 조사할 필요가 없음을 알 수 있다. 이것의 이유를 알아보자. 노드 K 를 조사한 후, 노드 I 의 최대값으로 0 으로 주어져, 노드 F 의 최소값은 0 이 된다. 그러나 이 값은 알파 값 3 보다 적기 때문에 노드 I 의 후계 노드들은 조사할 필요가 없다. 최대화를 목표로 하는 경기자는 노드 C 를 지나 노드 I 로 가는 움직임을 택하면, 결과적으로 획득한 값이 0 보다 좋지 못하다는 것을 예측할 수 있기 때문에, 노드 B 로 움지인다. 다음은 베타 값이 어떻게 사용되는 지 알아 보자. 노드 I 에 대한 탐색을 중단한 후, 노드 J 를 조사하여 노드 F 의 값을 지정될 5 를 얻는데, 이 값은 노드 C 에 대한 베타 값이 된다. 이것은 노드 C 의 값으로 5 이하의 값이 배정됨을 의미한다. 노드 G 를 전개 팽창하여 노드 M 을 조사하고 7 의 값을 얻어, 이 값을 노드 G 에 후진 전달한다. 노드 C 에서 움직일 차례가 된 경기자는 최소화를 목표로 하기 때문에, 7 과 베타 (5) 를 비교하여 5 보다 큰 값 7 을 갖고 있는 노드 G 를 선택하지 않고, 5 를 갖는 노드 F 로 움직인다. 따라서 노드 G 의 후계 노드들은 탐색할 필요가 없다.
그림 5 알파-베타 자르기
앞의 예로 부터, 최대화를 목표로 하는 단계에서는 현재의 하한값보다 작은 값을 가진 노드로의 탐색은 중단되고 최소화를 목표로 하는 단계에서는 현재의 상한값보다 큰 값을 가진 노드로의 움직임은 제거됨을 알 수 있다. 최대화를 목표로 하는 경기자에 대해 가능한 움직임을 제거하는 것은 사실상 최소화를 목표로 하는 단계에 대한 탐색의 중단을 의미한다. 다시 그림 4 의 예를 살펴 보자. 일단 노드 C 가 노드 A 로 부터의 부적합한 움직임으로 결정되면, 노드 C 이하의 최소화를 목표로 하는 단계에 있는 노드 G 나 혹은 다른 어떤 경로도 조사할 필요가 없다. 알파와 베타가 실제로 사용되는 방법은 최소화를 목표로 하는 단계에서 알파 값보다 작은 값을 가진 노드가 발견되면, 그 노드로의 탐색을 중단하고, 최대화를 목표로 하는 단계에서 베타 값보다 큰 값을 가진 노드가 발견되면 그 노드로의 탐색을 중단하는 것이다. 최대화를 목표로 하는 단계에서 높은 값이 발견되면 탐색을 중단한다는 것은 언뜻 보아서는 이상하게 여겨지겠지만, 이것은 최대화를 목표로 하는 단계 위에 있는 최소화를 목표로 하는 경기자가 특정한 노드를 선택할 경우, 최대화를 목표로 하는 단계에서 그 노드를 찾아야만 하기 때문이다.
예를 사용하여 알파-베타 자르기의 작용 방법을 설명하였는데, 여기서는 이 기법을 수행할 수 있도록, 2 절에서 소개된 MINIMAX 과정을 어떻게 수정해야 되는 지에 대해 살펴 보자. 최대화를 목표로 하는 단계에서는 탐색의 중단 여부를 결정하기 위해서 베타만이 사용되고, 최소화를 목표로 하는 단계에서는 알파만이 사용된다. 그러나 최대화를 목표로 하는 단계에서 MINIMAX 를 순환적으로 부르면 최소화를 목표로 하는, 단계가 만들어지기 때문에, 최대화를 목표로 하는 단계에서도 알파를 알아야 하며, 최소화를 목표로 하는 단계에서도 또한 베타를 알아야 한다. 각 레벨이 알파와 베타를 모두 알아야 하는데, 하나는 사용을 위해, 다른 하나는 다음 레벨에서 사용하기 위해서이다.
MINIMAX 과정에서는 레벨이 바뀔 때마다, 단순히 평가된 값의 부호만 바꾸면 되기 때문에, 최대화를 목표로 하는 단계와 최소화를 목표로 하는 단계를 서로 다르게 처리할 필요가 없다. 두 경기자에 대해 각각의 과정을 쓸 필요가 없도록 알파와 베타를 처리하는 기법을 찾는다면 효과적이다. 이를 위해, 알파와 베타를 사용하는 대신, USE-THRESH 와 PASS-THRESH 라는 두 값을 MINIMAX 에서 사용한다. USE-THRESH 는 탐색의 중단을 계산하기 위해 사용되고, PASS-THRESH 는 단순히 다음 레벨로 전달되어, 그 곳에서 USE-THRESH 로 사용된다. 물론 USE-THRESH 도 다음 레벨에 전달되어, PASS-THRESH 로서 세번째 레벨로 전달된다. 레벨을 따라 전달될 때마다, 값들의 부호가 바뀌는 것처럼, 이 출발값들의 부호도 바뀌어야 한다. 최대화 목표로 하는 레벨에서 요구되는 코드와 최소화를 목표로 하는 레벨에서 요구되는 코드 간에 차이를 둘 필요가 없다.
지금까지, 알파와 베타가 트리를 따라 전달되는 방법에 대해 알아보았다. 이제 알파와 베타의 값을 정하는 방법에 대해 살펴 보자. 이를 위해 그림 4 의 간단한 예를 다시 살펴 보자. 노드 A 가 있는 레벨과 같이 최대화를 목표로 하는 레벨에서, 알파는 지금까지 발견된 최적 후계 노드의 값으로 정해진다 (비록 최대화를 목표로 하는 레벨에서 탐색의 중단을 결정하기 위해 사용되는 것이 베타라 할지라도, 새로운 값으로 계산되는 것은 알파이다. 따라서 어느 레벨에서라도, USE-THRESH 가 탐색의 중단을 위해 조사되고, PASS-THRESH 는 후에 사용되기 위해 수정된다. 그러나 만약 최대화를 목표로 하는 레벨이 정상 레벨이 아니라면, 더 높은 레벨의 노드로부터 밑으로 전달된 알파 값을 고려해야만 한다. 이것의 작용 방법을 알아 보기 위해, 그림 5 의 노드 F 에서 발생될 일을 살펴 보자. 노드 K 를 조사하여, 노드 I 에 0 을 배정한다. 이것은 지금까지 발견된 노드 F 의 최적 후계 노드이다. 그러나 노드 B 로부터 나온 부분 트리를 먼저 조사하여, 알파를 3 으로 정하고, 노드 A 로부터 노드 F 로 이 값을 전달한다. 알파는 노드 I 를 토대로 하여, 다시 0 으로 배정될 수 없다. 지금까지 발견된 최적 움직임을 전체 트리에 반영하기 위해, 알파는 그대로 3 의 값을 유지한다. 최대화를 목표로 하는 레벨에서, 알파는 최대화를 목표로 하는 다음의 가장 놓ㅍ은 레벨에서 가진 값과 이 레벨에서 발견된 최적 값중 더 큰 값으로 정해진다. 최소화를 목표로 하는 레벨에서, 베타도 위와 같은 방법으로 정해진다. 사실상 어느 레벨에서든지 PASS-THRESH 는 위로부터 전달받은 값과, 새로운 값을 낮은 레벨로 전달하고 또한 높은 레벨로도 후진 전달하여 트리의 어느 곳에서 든지 발견된 최적 움직임을 반영할 수 있도록 한다.
이러한 점에서 볼 때, PASS-THRESH 를 계산할 때도 MINIMAX 에서 BEST-SCORE 를 계산하기 위해 행했던 것과 같은 작업을 수행한다. 또한 BEST-SCORE 를 제거하고, 그 자리를 PASS-THRESH 로 대치할 수 있다.
네 개의 인자, POSITION, DEPTH, USE-THRESH 와 PASS-THRESH 를 필요로 하는 함수 MINIMAX-A-B 의 연산 작용을 살펴 보자. CURRENT 로 표시된 위치로 부터의 움직임을 선택하는 첫번째 호출은 다음과 같다.
MINIMAX-A-B(CURRENT,
0,
maximum
value STATIC can compute,
maximum
value STATIC can compute)
USE-THRESH 와 PASS-THRESH 의 초기값은 각 면이 가질 수 있는 가장 나쁜 값으로 주어진다.
Minimax-A-B(Position, Depth, Use-Thresh, Pass-Thresh)
1. 만약 DEEP-ENOUGH(DEPTH) 가 참이면, 다음 구조를 돌려 주어라.
VALUE = STATIC (POSITION, DEPTH) ;
PATH = nil
2. 그렇지 않다면, MOVEGEN (POSITION) 을 호출하여, 이것으로부터 얻은 목록을 SUCCESSORS 로 하여 트리의 레벨을 하나 더 만든다.
3. 만약 SUCCESSORS 가 빈 목록이라면, 어떤 움직임도 만들어질 수 없기 때문에, DEEP-ENOUGH 를 참으로 가정할 때 얻어지는 구조를 돌려 주어라.
4. 만약 SUCCESSORS 가 빈 목록이 아니라면, 그것의 각 원소를 조사하여, 최적 원소를 기억하라. 이것의 수행은 다음과 같다.
5. (SUCC 이라 불리는) SUCCESSORS 의 각 원소에 대해, 다음을 수행하라 :
1) MINIMAX-A-B(SUCC, DEPTH+1, -PASS-THRESH, -USE-THRESH) 를 RESULT-SUCC 으로 하라.
2) NEW-VALUE 에 -VALUE(RESULT-SUCC) 을 지정하라.
3) 만약 NEW-VALUE> PASS-THRESH 이면, 지금까지 발견된 어느 노드보다도 효과적인 후계 노드를 찾은 것으로써, 이것을 기록하기 위해 다음을 수행하라 :
① PASS-THRESH 에 NEW-VALUE 를 지정하라.
② 알려진 최적 경로는 현재 CURRENT 로부터 SUCC 이며 MINIMAX-A-B 를 순환적으로 호출하여, SUCC 으로부터의 적절한 결론을 찾을 수 있다. 따라서 BEST-PATH 에, PATH (RESULT-SUCC) 에 SUCC 을 덧붙인 결과를 지정하라.
4) 만약 PASS-THRESH (현재의 최적값을 반영하고 있다) 가 USE-THRESH 보다 비효율적이라면, 이 분지의 탐색을 중단할 수 있다. 그러나 출발값과 값들의 부호가 모두 바뀌어져야 한다. 따라서 PASS-THRESH > = USE-THRESH 이면 즉시 다음 값을 돌려 주어라 :
VALUE = PASS-THRESH ;
PATH = BEST-PATH
6. 다음 구조를 돌려 주어라 :
VALUE = PASS-THRESH ;
PATH = BEST-PATH
알파-베타 자르기 과정의 효율성은 조사되는 경로의 순서에 크게 좌우된다. 만약 가장 나쁜 경로가 가장 먼저 조사된다면, 어떤 탐색의 중단도 발생되지 않을 것이다. 그러나 물론 최적 경로를 예측하여, 그것을 항상 가장 먼저 조사한다면, 탐색 과정은 불필요하다. 그러나 완전한 상황에서 자르기 기법이 얼마나 효과적인지 알 수 있다면, 다른 상황에서 이 기법의 수행 능력에 대한 상한값을 정할 수 있다. 만약 노드가 완전하게 순서화되어 있다면, 알파-베타 자르기를 사용하여 깊이 D 까지의 탐색에 의해 조사될 단말 노드의 수는 알파-베타를 사용하지 않고, 깊이 D/2 까지의 탐색에 의해 만들어진 단말 노드 수의 거의 2 배이다. 탐색을 수행할 깊이를 두 배로 하면, 더욱 중요한 이득을 얻게 된다. 비록 일반적으로 이러한 향상을 모두 실현할 수는 없지만, 알파-베타 자르기 기법은 최대 최소 탐색 과정을 효율적으로 향상시킨 기법이다.
이미 조사된 경로에 비해 매우 적게 향상된 부수적인 경로를 조사하지 않는 것으로까지 알파-베타 자르기 과정의 개념을 확장시킬 수 있다. 5-4 단계에서, 조사중인 경로가 이미 발견된 다른 경로보다 비효율적이라면, 탐색을 중단한다. 그러나 그림 6 에 보여진 상황을 살펴 보자. 노드 G 를 조사한 후 노드 C 로 움직일 때 얻을 수 있는 최적값이 3.2 임을 알게 된다. 만약, 노드 B 로 움직인다면, 3 점을 얻는다. 3.2 으로부터 얻어지는 효율성과 3 으로부터 얻어지는 효율성 간에 별다른 차이가 존재하지 않기 때문에 노드 C 에 대한 탐색을 중단하고, 더 많은 이득을 얻을 수 있는 트리의 다른 부분을 조사한다. 이미 알려진 경로에 비해 향상에 대한 가능성이 거의 없는 부분 투리의 탐색을 중단하는 것을 효과없는 탐색의 중단 (futility cutoff) 이라 한다.
그림 6 효과없는 탐색의 중단
알파-베타 자르기 기법 뿐만 아니라, 최대 최소 과정을 수정하여, 수행 능력을 향상 시킨 여러 기법들이 있다. 이들 기법중 세 가지를 다음에 간단히 소개한다.
위에서 제안된 것처럼 트리의 더 깊은 탐색을 중단할 시기를 결정하기 위해 고려할 요인중의 하나는 상황의 안정성에 대한 여부이다. 그림 7 에 보여진 트리를 살펴 보자. 노드 B 를 한 레벨 더 전개 확장하였을 때의 결과가 그림 8 과 같다고 가정하자.
그림 7 탐색의 시작
그림 8 값의 대체 시작
한 움직임을 미리 조사할 때, 노드 B 에 대한 추정값이 급격히 변한다. 이러한 경우는 상대방의 장기말을 서로 잡을 때 발생할 수 있다. 상대방은 서로의 장기말을 잡아, 자신에게 유리한 방향으로 장기판의 상태를 유도한다. 만약 이 레벨에서 트리에 대한 조사를 중단할 경우, 노드 B 에 -4 의 값을 지정하여, 노드 B 가 유리한 움직임이 아니라는 것을 결정할 수 있다.
단기적인 측정이 움직임의 선택에 과도한 영향을 미치지 않았다는 것을 확실히 하기 위해, 한 레벨에서 다음 레벨로 갈 때, 어떤 극적인 변화도 발생하지 않을 때까지 탐색을 계속한다. 이것을 순조로움의 기다림이라 한다. 만약 그렇게 한다면 그림 9 에 보여진 상황을 얻는다. 서로 상대방의 장기말을 잡을 경우 이미 절반 과정이 발생하였기 때문에 노드 B 로의 움직임은 다시 매우 합리적인 움직임처럼 보인다.
그림 9 잠잠해진 상태
최대 최소 과정의 정확성을 높일 수 있는 또 다른 방법은, 조사된 원래의 탐색보다 더 많은 레벨을 조사할 때 발생할 수 있는 함정이 존재하지 않는다는 것을 확실히 하기 위해서, 선택된 움직임을 다시 한번 조사하여 재확인하는 것이다. 평균 여섯 단계의 깊이까지 게임 트리를 조사하여, 이 탐색을 기초로 하여 특정한 움직임을 선택한다고 가정하자. 비록 전체 트리의 여덟 단계 깊이까지 탐색하는데 소요되는 비용이 엄청나기 때문에, 이 단계까지 트리를 탐색할 수는 없다 할지라도, 하나의 선택된 분기가 올바로 선택되어 있는지를 확인하기 위해 그 분기에서 두 단계 탐색하는 것은 그다지 큰 비용을 요구하지 않는다. 이 기법을 보조 탐색이라 한다.
일반적으로 행해지는 복잡한 게임의 경우 물론 단순히 목록으로부터 현재 게임의 상태를 찾아 올바른 움직임을 선택하는 것이 실현 가능한 것은 아니다. 목록은 매우 광대한 것이기 때문에 어느 누구도 이 목록을 만들 수 없다. 그러나 이 기법을 게임의 일부분에 적용하는 것은 가능하다. 예를 들어, 체스의 경우, 처음 시작할 때와 게임이 끝날 때는 대부분 모두 일정한 양식에 다라 장기말이 움직이게 된다. 이러한 상황하에서 만들어질 움직임의 목록을 준비하여 프로그램의 수행 능력을 향상시킬 수 있다. 게임의 시작과 끝에는 움직임에 대한 목록을 사용하고, 게임의 중간에는 최대 최소 탐색 과정을 사용할 경우, 지식과 탐색을 하나의 프로그램에 결합하여, 이들 기법을 각각 개별적으로 사용할 때 얻어지는 결과보다 더욱 효과적인 결과를 얻을 수 있다.
위와 같이 향상된 기법을 사용한다해도, 체스와 같은 게임을 할 때 관계되는 추론 과정을 모두 알 수는 없다. 예를 들어, 움직임을 생성하는 과정과 정적 평가를 용이하게 하기 위해서, 개개의 게임 위치를 어떻게 표기하는가의 질문은 지금까지 거의 언급되지 않은 문제중의 하나이다. 비록 이 질문에 대한 답을 알지 못한다 하더라도, 게임의 전문가와 비전문가가 위치를 표기하는 방법에는 분명히 차이가 있을 것이다. 체스에 능통한 경기자는 짧은 시간 동안 장기판의 상태를 보고도 정확하게 장기판을 재현할 수 있다. 같은 시간동안 같은 장기판의 상태를 체스에 미숙한 경기자에게 보여 주고, 이 장기판의 상태를 재현할 경우 이 경기자는 단지 몇 개의 장기말만을 원래 위치에 놓을 것이다. 이것은 전문가가 64 개의 정사각형을 하나씩 개별적으로 보는 것이 아니라, 서로 구별되는 여러 개의 패턴의 집합으로 장기판을 보는 것을 의미한다.
게임 트리를 탐색하기 위한 방법으로서의 최대 최소 과정 자체에는 몇 가지 결점이 포함되어 있다. 이들 중의 하나는 최대 최소 과정이 탐색하는 게임 트리의 일부분에 필연적으로 나쁜 사건이 나타나지 않을 때까지 다양한 지연 전략을 사용하여, 이것의 발생을 지연시킬 때, 최대 최소 과정은 수평 효과 (horizon effect) 를 받기 쉽다는 것이다.
예를 들어, 체스의 경우, 경기자들이 서로 상대방의 장기말을 잡기 위해 두 수를 두어야 이 쪽의 장기말을 잡는 작전을 상대방이 시도하고자 한다고 가정하자. 상대방의 차례가 되면 상대방은 이러한 두 수중 한 수를 둔다. 그러나 이때 이쪽의 차례가 되어, 게임의 다른 부분에 대한 공격을 시도할 수 있다. 상대방은 이 공격에 응수해야 하기 때문에, 이 작전을 즉시 완성할 수는 없지만, 이를 달성할 기회를 기다린다. 이 쪽의 다음 차례가 되어 또 다른 곳에 대한 공격을 시도함으로써 상대방의 응수를 요구한다. 만약 이 점에서 탐색을 중단한다면, 이 쪽 장기말들 중의 하나가 불가피하게 희생되어야 한다는 사실을 결코 알 수 없게 된다. 수평 효과는 유리한 움직임에 대한 프로그램의 인식에도 또한 영향을 미칠 수 있다.
최대 최소 기법의 또 다른 문제점은, 상대방이 항상 최적 움직임을 선택하리라는 가정에 최대 최소 기법이 크게 의존한다는 점이다. 이러한 가정은 유리한 움직임이 발견되어 이길 수 있는 상황에서 받아 들일 수 있다. 두 개의 움직임 중 하나를 선택해야만 한다고 가정하자. 이 때 두 움직임은 만약 상대방이 완벽하게 게임을 이끌어 간다면 이 쪽에게 모두 매우 불리한 상황이 되지만, 하나가 다른 하나보다 약간 덜 불리한 상황이 될 수 있고, 또한 만약 상대방이 실수를 범한다면, 상당히 불리한 움직임이 이쪽에게 매우 유리한 상황을 이끌 수 있다고 가정하자. 비록 최대 최소 과정에 의해서는 언제나 불리한 상황이 되는 움직임이 선택된다 할지라도, 둘 중 좀더 유리한 움직임을 선택할 수 있다. 상대방이 완벽하게 게임을 유도한다고 가정할 때, 한 움직임이 다른 한 움직임보다 약간 유리한 것처럼 보이는 경우, 이와 유사한 상황이 발생한다. 상대방이 실수를 저지를 경우, 더 불리한 움직임이 이쪽에게 더욱 유리한 상황으로 될 때, 이 움직임을 택하는 것은 효과적이다. 이러한 결정을 적절히 내리기 위해, 체스를 두는 사람의 경기 방식에 대한 모델을 구성하여 다양한 실수의 가능성을 평가하는 것은 매우 중요한 일이다. 그러나 이 작업은 매우 어려운 작업이다.
이 장에서는 게임에 사용되는 탐색을 기초로 한 기법들이 논의되었다. 기본적인 최대 최소 과정의 알고리즘을 소개하였고, 이것을 향상시킨 여러 알고리즘을 논의하였다.
그러나 이렇게 향상된 알고리즘으로도, 체스와 같이 어려운 게임을 위한 적절한 프로그램을 작성하는 것은 어렵다.
컴퓨터를 사용하여, 체스와 같은 게임을 쉽게 할 수 있다 할지라도, 만약 잘못 작용할 경우 발생될 실행 시간의 폭발적 급증 문제에 직면하여 이를 잘 처리하기 위해 두가지 중요한 문제 즉, 정보를 표기하는 방법과 해답을 위한 탐색 과정에서 이 정보를 효율적으로 사용하는 방법에 대한 적절한 해답을 구해야 한다.
1. 다음 게임 트리를 살펴 보자.
A 가 최대화를 목표로 하는 경기자라고 가정하자. 이때 그는 어느 노드로의 움직임을 선택할까?
2. 앞 문제에서 보여진 게임 트리에서, 알파-베타 자르기 과정을 사용할 경우, 어떤 노드는 탐색할 필요가 없는가?
3. 게임 프로그램에서 항상 탐색이 목표 상태로부터 후진 수행되는 것보다 현재 상태로부터 전진 수행되는 이유는?
4. 최대 최소 과정은 깊이 우선 탐색 과정인가, 나비 우선 탐색 과정인가?
5. 지금까지 논의된 최대 최소 알고리즘은 게임 트리의 탐색을 수행한다. 그러나 일부 게임의 경우, 그래프를 탐색하고 위치가 만들어질 때마다, 이것이 이전에 만들어져 이미 평가된 것인지를 조사하는 것이 더욱 효과적일 수 있다. 어떠한 상황에서 이 개념이 유용한가? 이를 위해 최대 최소 과정을 수정하라.
6. 세 사람 혹은 네 사람에 의해 행해지는 게임 프로그램에 사용되기 위해 최대 최소 방법을 어떻게 수정해야 하는가?
7. 3 절에서 설명한
탐색 과정 면에서 볼 때, MOVEGEN 에 의해 만들어진 후계 위치의 목록을 순서화하는
것이 중요한가? 이유는?
만약 이것이 중요하다면, 그것이 어느 정도 중요한가?
(즉, 그것을 순서화하기 위해 어느 정도의 노력을 필요로 하는 것이 합리적인가?)
8. 알파-베타 탐색 과정을 구현하라. 틱-택-토와 같이 간단한 게임을 위해 이것을 이용하라.