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

https://startagainbornagain.tistory.com/113

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

알파베타 가지치기

  최소최대 검색의 문제는 조사해야 할 게임 상태의 수가 게임트리 깊이에 지수적이라는 점입니다. 안타깝게도 그 지수를 제거 할 수는 없습니다. 그러나 지수를 실질적으로 반감하는 것은 가능합니다. 여기서 핵심은, 게임 트리의 모든 노드를 조사하지 않고도 최소최대 결정을 정확히 계산할 수 있다는 점입니다. 좀 더 구체적으로 말하면, 저번에 말한 가지치기 개념을 이용해서 트리의 커다란 부분을 고려대상에서 제외할 수 있습니다. 이번에 살펴볼 구체적인 기법은 알파베타 가지치기(alpha-beta  pruning)라고 부르는 것입니다. 이를 표준 최소최대 트리에 적용하면 보통의 최소최대 알고리즘에서와 동일한 수를 돌려준다. 그러나 탐색 관정에서 최종 결정에 영향을 줄 수 없는 가지들을 잘라내버린다는 종요한 차이가 있습니다. 

 

수들의 순서 결정

  알파베타 가지치기의 효과는 상태들을 조사하는 순서에 크게 의존합니다. 과거에 최선이라고 판명된 수들을 먼저 시도하는 등의 동적인 조사 순서 결정 방안들을 추가하면 이론적 한계에 상당히 가까워집니다. '과거의 수'는 직전의 수일 수도 있고(같은 위협이 여전히 남아 있는 경우가 있다.) 현재 수의 이전 탐험에서 조사한 수들일 수도 있습니다. 현재 수로부터 정보를 얻는 한 가지 방법은 반복 심화 검색을 이용하는 것입니다 우선 한 겹 깊이로 검색을 수행해서 최선의 수들의 경로를 기록합니다. 그런 다음 한겹 더 깊게 검색하되, 기록된 경로를 활용해서 수들의 순서를 결정합니다.  더 나은 수 순서 덕분에 그런 추가 시간이 상쇄될 수 도 있습니다. 최선의 수들을 흔히 킬러 수(killer move)라고 부르고, 그런 수들을 먼저 고려하는 방식을 킬러 수 발견법이라고 부릅니다.

 

불완전한 실시간 결정

  최소최대 알고리즘은 게임 검색 공간 전체를 생성하나, 알파베타 알고리즘을 이용하면 그 공간의 커다란 부분을 잘라 낼 수 있습니다. 그렇긴 하지만 알파베타에서도 검색 공간의 적어도 한 부분을 위한 말단 상태들을 모두 검색해야 합니다. 일반적으로 그러한 깊이는 실용적이지 않습니다. 실제 응용에서는 수들을 적당한 시간 안에(흔히 몇 분 이내로) 결정해야 하기 때문입니다. 그 대안으로, 클로드 새넌은 논문 Programming a Computer for Playing Chess에서 프로그램이 검색을 일찍 차단하고 검색 중인 상태들에 발견법적 평가 함수(evaluation function)를 적용해서 비말단 노드들을 말단 잎 노드들로 전환해야 한다고 제안했습니다.

https://slideplayer.com/slide/4380369/ -> 출처

다른 말로 하면, 그의 제안은 최소최대나 알파베타를 다음 두 가지 방식으로 수정하자는 것입니다.

하나는 효용 함수를 발견법적 평가 함수 EVAL로 대체하는 것이고, 또 하나는 말단 판정을 차단 판정(cutoff test; 또는 중단 판정) 으로 대체하는 것 입니다. EVAL함수는 주어진 국면의 효용 추정치를 돌려주고, 차단 판정은 그 함수를 적용할 시점을 결정합니다.

 

평가 함수

  평가 함수는 주어진 국면에서 게임의 기대 효용의 추정치를 돌려줍니다. 이는 저번에 했던 발견법적 함수가 목표로의 거리에 대한 추정치를 돌려주는 것과 비슷합니다. 추정기(estimator) 개념은 섀넌이 이를 제안 했을 대 이미 알려져 있었습니다. 수 세기 동안 체스 플레이어들은(그리고 다른 게임의 애호가들은) 주어진 국면의 가치를 판정하는 당양한 방법을 개발해 왔습니다. 이는, 컴퓨터 프로그램에 비해 사람이 할 수 있는 검색의 양이 제한적이기 때문입니다. 게임 플레이 프로그램의 성능이 그 평가 함수의 품질에 크게 의존한다는 점은 명백합니다. 부정확한 평가 함수는 에이전트를 패배로 이어지는 국면으로 이끕니다. 그렇다면 좋은 평가 함수를 설계하려면 구체적으로 어떻게 해야 할까요?

 

첫째로, 평가 함수는 말단 상태들의 순위를 진짜 효용 함수와 같은 방식으로 매길 수 있어야 합니다. 즉, 승리에 해당하는 상태들을 무승부에 해당하는 상태보다 더 높게 평가해야 하며, 무승부 상태들은 패배 사ㅣㅇ태들보다 더 높게 평가 해야합니다. 그렇지 않은 평가 함수를 사용하는 에이전트는 게임의 끝까지 내다볼 수 있다고 해도 실수르 저지르게 됩니다. 둘째로, 그러한 계산에 너무 많은 시간이 걸려서도 안 됩니다. (애초에 목적은 검색을 더 빠르게 수행하는 것입니다.) 셋째로, 비말단 상태들에 대해 평가 함수는 실제 승리 확률과 상관관계가 높은 추정치를 돌려주어야 합니다.

 

앞 문단에 나온 '승리 확률'이 구체적으로 무엇일까요? 사실 체스는 확률의 게임이 아닙니다. 플레이어는 현재 상황을 확실하게 알 수 있으며, 주사위는 전혀 관여하지 않습니다. 그러나 검색이 비말단 상태들에서 중단되어야 한다면, 알고리즘은 그 상태들의 최종 결과를 확실하게는 알 수 없습니다. 이런 종류의 불확실성은 정보의 제약이 아니라 계삭의 제약에서 비롯된 것입니다. 주어진 상태에 대해 평가 함수가 소비할 수 있는 계산의 양이 제한되어 있다면 최종 결과를 추측할 수밖에 없습니다.

 

 

오늘은 이렇게 평가함수까지 했습니다. 다음 시간에는 검색의 차단에 대해 알아보도록 하겠습니다.