게임프로그래밍 박현수경동정보대학컴퓨터정보기술과 hspark@kdtc.ac.kr A Study of Stone Influence, Influence Point, and Influence Area in Computer Go Hyun-Soo Park Dept. of Computer Information Technology, Kyungdong College of Techno-Information 요약 본논문은컴퓨터바둑에서돌의영향력 (Stone Influence) 과영향력점 (Influence Point) 그리고영향력영역 (Influence Area) 을제안한다. 돌의영향력은놓인돌과빈정점사이의거리에따라정의하며, 영향력점은돌의영향력에대해임계치를이용하여정의한다. 형세평가를위한요소로영향력영역을영향력점덩어리와코어를이용하여정의한다. 저자는정석자료를이용한실험을통해서영향력점의임계치를구하였으며, 영향력영역이바둑게임에서세력으로성공적으로적용가능하였습니다. ABSTRACT This paper presents the Stone Influence, the Influence Point, and the Influence Area on computer Go. The Stone Influence is defined using the distance between stone and empty point. The Influence Point is defined using threshold value on the Stone Influence. The Influence Area is defined using lump of the Influence Points and its Core. In experiments using the Jeongseok data, the author obtained the threshold of Influence Points. The proposed method was verified by experiments where it was success fully applied to the influence in game of Go. Keyword : Stone Influence, Influence Point, Influence Area, Evaluation, Computer Go 117
118 1. 서론바둑은흑과백이번갈아두어영역을많이가지는편이이기는게임이다. 컴퓨터바둑에서현재의바둑판의우세를평가하는것이형세판단으로매우중요한요소중의하나이다. 형세판단은게임트리탐색을이용하는사활문제와는다르게일반적인접근방법을찾기가매우힘들다. 상용화된컴퓨터바둑프로그램은정석이나패턴과같은정형화되어진것은잘연구되어구현되어졌지만현재상태에대한평가를위한형세판단의방법에관해서는연구가많이이루어지지않고있다. 컴퓨터바둑에서형세판단은전략과전술적으로매우중요하다. 현재바둑판의상태에대한형세판단은흑과백이차지하고있는영역과앞으로차지가능한영역을계산한다. 그러나영역의결정과미래의영역계산은매우어려우며정형화되어진방법은아직없다. 영역결정의경우정적인사활과빅에대한평가 [1,2] 와동적인수읽기가동반된사활평가가있을수있다. 그리고미래의영역계산은영향력과두터움그리고끝내기등과같은문제를해결해야한다. 그러므로형세판단은종합적인바둑판의정보처리를전제하며매우중요하고어려운것이다. Ken Chen[3] 은 Go Intellect에서형세평가함수를개발하여컴퓨터가스스로현재의국면을평가하도록구현하였다. M ller[4] 는 Full-Board Evaluation에서 score를계산하는방법에서아래와같은방법을사용하였다. 특히, Potential territory와 near point의경우집은아니지만전체형세평가에 ±1/2로계산함으로마치영향력과도같은역할을한다. 그의논문에서 Safe territory의각점이흑이면 +1로백이면 -1로정의하고, Potential territory의각점을 ± 1/2로정의하고, Each near point는 ±1/2로정의하였으며 Junction points와 far-away points는 0으로정의하였다. M ller의방법에서 Potential territory는 potential dividers 에의해분리된것으로 safe territory보다더약하여내부전체에대해통제하기에충분히강하지못하다. 즉, 그림1의좌측그림에서좌하귀의경우에해당하는것으로틈이너무많아Safe하지는못한경우이다. 그러나실제로형세판단을위해서이와같은값을제외하면매우큰오차가발생되어진다. 그러므로적당하게그영역의값을설정할필요가있다. 여기서의적당한값은실제영역이아니지만영역이될수있는가능성이대단히높은것으로판단했다. 김영상 [5] 은돌의세기, 영향력, 안정도, 자리값, PM, 등의요소를정의하여임의의국면에대한형세를평가하는시스템을제안하였다. 김광인 [6] 은기본적으로영향력함수의값을세력의근원지인돌로부터거리가멀어짐에따라지수적으로감소되고빈자리에누적되는것으로보았다. 영향력은돌이반면에놓일때그돌의세기를계수적으로표현한것이다. 프로기사는반면에대해어느정도크기의영향력을형세평가의근거로삼는다. 이것또한표준적으로정해진모양이나값이없다. 그러나돌들의안정도와분포에큰영향을받는다. 단순히돌이많다고해서영향력이크다고할수는없으며또한돌이적다고해서영향력이약하다라고는말할수없다. 그때의상황에따라그크기도달라지는것이다. 그리고이러한영향력을기반으로하여전략을구사하기도한다. 즉, 영향력을이용한공격이나영향력을집으로확보하는전략을사용하기도한다. 그림2는본논문에서제시하는방법을설명한다. 제안한방법은입력되어진 board에대해서빈정점에대한돌의영향력을계산하고이를이용하여영향력점을찾고영향력점의값을계산하고영향력점들로이루어진이웃한점들인영향력덩어리를찾는다. 이러한영향력덩어리에포함된코어를찾고마지막으로영향력영역을계산한다. 본논문은 2장에서돌의영향력, 영향력점, 그리고영향력영역을정의한다. 3장에서실험을통해서영향력점의임계치를구하고형세평가의적절히이용될수있음을검토한다. 그리고 4장에서는결론적으로제안한방법의요약하고앞으로의과제에대해서논의한다. [ 그림 1] Safe(dark shade), potential(light shade), 그리고 threatened( ) zones 표시
119 [ 그림 3] 거리에따른돌의세기계산방법 [ 그림 2] 제안한방법의절차 2. 돌의영향력과영향력점그리고영향력영역 2.1 돌의영향력 (Stone Influence) 돌의영향력 (Stone Influence, SI) 은돌이임의의빈정점까지미치는힘을정의한것으로돌의세기와그돌이속한 Group의안정도 [7] 로정의한다. 일반적으로돌의세기는그거리의증가에대해상대적으로약해지는데, 저자는돌의세기 (Stone Power, SP) 를피보나치수열의값의역수로정의하였다. 즉, 돌의현재위치는 1이고, 돌과이웃한빈정점일경우는 1, 한칸의거리의빈정점일경우는 1/2, 두칸거리빈정점일경우는 1/3, 세칸거리의빈정점일경우는 1/5, 그리고네칸빈정점일경우는 1/8로정의하였다. 그리고임의의돌에서대각선방향의빈정점까지의돌의세기는돌과빈정점까지의거리를피타고라스정의에의해구하고이것의역수를돌의세기로정의한다. 그러므로아래의 ( 식1) 에서와같이d는피보나치수열의값이며, SP는돌의세기를나타낸다. 그림3에서와같이돌 (S) 이있을경우 S에서 V2까지의돌의세기는 S에서 V1까지의거리의제곱과 V1과 V2의거리의제곱의제곱근의역수이다. 예를들어그림3의우측에서위치 (3,s) 에 S이고빈정점 A에미치는세기는 S에서빈정점 (5,c) 까지의거리인 2와 (5,2) 에서 A위치인 (5,e) 까지의거리 2에대해각각의제곱의합을제곱근한수의역수이다. 그림4는돌의세기에대한예를보여주는것으로세기값에대해가독성을높이기위해 100을곱한것으로표시를하였다. [ 그림 4] 돌의세기의예또한빈정점의영향력은돌들의세기와그돌들이속한각 Group의안정도에따라빈정점에영향을미칠수있다. 돌들이속한 Group의안정도가죽음이라면돌들은빈정점에영향을미치질못할것이지만완전한삶이확정된돌들이라면정의한값만큼의영향을미칠것이다. 아래 ( 식2) 에서와같이빈정점 (v) 의영향력 (SI) 이란돌의세기와그돌이속한Group의안정도에비례하게정의한다.
120 2.2 영향력점 (Influence Point) 돌들의영향력의값이있을때과연어디까지를영향력으로정할수있는가는매우어려운문제이다. 즉, 돌에대한임의의빈정점이영향력을가지기위해서는일정한값이상이어야한다. 그러므로저자는빈정점이일정한영향력을가지는때이것을영향력점이라정한다. 즉, 영향력점 (IP, Influence Point) 은임의의빈점이가지는돌들의영향력 (SI) 값의합으로임계치이상이면영향력점이라정의한다. 아래 ( 식3) 에서빈정점 (v) 에서의영향력값 (SI) 는임계치τ에의해영향력점으로결정되어진다. 다. 그러므로아래식은돌의영향력에대하여임계치를고려하여흑과백의 IP들을찾는방법을설명한다. IP B 는흑의영향력점의집합을의미하고 IP W 는백의영향력점의집합을의미한다. 그림5는정석자료 [8] 를이용하여임계치를각각 20, 50, 100, 140, 200에대해실험한결과이다. (a) 에서보는것과같이빈정점의영향력값이존재할때임계치 20를정한 (b) 의경우세력위주인흑의영향력점이과다하게나타나고있다. 그리고임계치가커짐에따라영향력점의수도감소함을알수있다. 임계치 200인 (f) 의경우에는백의영향력점은 0개이나흑의영향력점은 8개로나타난다. 그러므로영향력점이실제형세평가에이용되기위해서는가장적당한임계치를정해주어야한다. (a) (b) (c) (d) (e) (f) [ 그림 5] 임계치에따른영향력점 (B: 흑의영향력점, W: 백의영향력점 ) (a) 모든 SI (b) 임계치 20 (c) 임계치 50 (d) 임계치 100 (e) 임계치 140 (f) 임계치 200 하나의빈정점이같은색의다수개의돌에의해둘러싸였다할지라도그빈정점은일정한한계치를넘게되면초과되어지는영향력은별의미가없으며, 반대로너무나미약한값이있다면이것역시영향력으로고려할필요가없 2.3 영향력영역 (Influence Area) 세력과영역은서로다른것이다. 세력은영역이될수도있고아닐수도있다. 그러나초반과중반의형세평가에서세력은두터움이라든지영역으로의가치로평가한다. 그러므로본논문은세력을영역으로의평가를하기위해영향력점을이용하여영향력점덩어리와영향력점덩어리의코어를정의하고이로써영향력영역을정의한다. 그러므로세력에해당하는영향력점들중에영향력영역에해당하는것을찾아서영역으로평가를한다. 세력이라는것이형세평가를하기위해사용되는것이므로이세력을형세평가의단위인집으로환산이되어야하겠다. 그래서저자는세력을집으로하는방법을영향력점의코어가존재할때만이영향력영역으로인정하여형세평가를하고자한다. 즉, 영향력영역 (Influence Area) 은영향력점들의덩어리에코어 (Core) 을가지고있으며이덩어리의코어와연결되어진점에속하는모든영향력점은영향력영역에속한다. [ 영향력점덩어리 (LI, Lump of Influence) 정의 ] 영향력점덩어리는영향력점들이이웃한관계로연결되어진그래프이다. [ 영향력점덩어리의코어 (CLI, Core of LI) 정의 ] 영향력점덩어리에서영향력점을꼭지점으로하는사각형을영향력점덩어리의코어라한다.
121 [ 영향력영역 (IA, Influence Area) 정의 ] 영향력점덩어리들중에서영향력점덩어리의코어가존재하는그래프를영향력영역이라한다. [ 그림 6] 영향력점덩어리 ( 세모, 네모, 마름모, 오각형, 육각형 ) [ 그림 7] 영향력점덩어리의코어 ( 속이찬사각형과속이찬마름모 ) 3. 실험저자는적절한임계치를정석자료들을이용하여찾는다. 왜냐하면정석자료는영역과영역그리고영역과세력으로구분되는수나누기가이루어진검증된자료이기때문이다. 서로불만이없는상태로두어지는정형화된수순에서실리와세력으로구분되어지는결과가많으며이러한엄격한구분이면영역과세력으로계산이가능하다. 표1은제안한논문에서정의한영향력의값을사용하여임의의한빈정점에임계치를 0에서 200까지를증가시켜영향력점과영향력영역에대해실험하였다. 예를들면, 임계치를 80일경우에합의값이흑은 80 그리고백은 -80이상이면각각영향력점과영향력영역이된다. 바둑정석사전 [8] 중정석 83개를자료로사용하여산술평균과평균편차와표준편차를구하였다. [ 표1] 은실험의결과를나타내었다. 정석은외부의상황을고려하지않고귀의지역적인상황에서양쪽이서로손해보지않는것으로정의한것이기때문에선수의이득은인정하지않는다. 그러므로덤을 0으로계산한다. 그림6에서보는것같이흑의영향력점덩어리는세모와네모로표시하고있으며, 백은마름모, 오각형, 그리고육각형으로표시하고있다. 단순히영역과영향력점으로계산하였을경우는백은영역이 5이고영향력점이 17이고흑은영역이 8이고영향력점이 16이다. 그러므로백은 22이고흑은 24이다. 그림7에서는영향력점덩어리의코어표시를속이찬사각형과속이찬마름모로표시하였다. 영향력영역 (IA) 는속이찬마름모를포함한사각형덩어리와속이찬마름모덩어리가포함된다. 영향력점덩어리의코어를포함한것을영향력영역으로계산한것은영역은변화가당연히없고백의코어를포함한영향력점은 14이고흑의코어를포함한영향력점도 14이다. 그러므로백은 19이고흑은 22이다. 영향력점덩어리의코어를정의한것은영향력점이다수존재할때어느정도의일정한폭을가지고있는것이세력의특성이므로이를반영하기위해서영향력점이이루는사각형으로정의하였다.
122 그림9의경우는그림8의경우와다르게좌하의흑의영향력영역이다수감소하였다. 그이유는흑이하변에서중앙으로펼쳐지는돌들이없고대신백의돌이하변을차지하고있기때문이다. 이것은흑의영향력영역을감소시키기충분한적의위치이다. [ 표 1] 영향력점과영향력영역을이용한임계치표1에서와같이임계치를 140인경우에영향력점산술평균이 5.0이고평균편차가 5.0 그리고표준편차가 5.9이고영향력영역은산술평균은 11이고평균편차는 8이고표준편차가 10.5로가장낮은값이나왔다. 이러한실험결과를바탕으로임계치를 140으로정하고영향력영역을영역으로사용하기로한다. 그러므로각점의영향력의합은 140을초과할때는형세평가할경우에영역이된다. 실험을통한임계치 140을이용하여 Game에적용하였다. 그림8과그림9는임계치 140을영향력을집으로환산한예이다. [ 그림 8] 임계치 140을사용한형세평가의예그림8의예에서보면, 좌하귀에서백이영역을차지할때흑은세력을구축한상황이다. 좌하의백영역은 23이고흑의영향력영역이 23이다. 이것은프로기사가평가한세력의평가치와매우유사한결과이다. 4. 결론본논문에서는컴퓨터바둑에서돌의영향력 (Stone Influence) 과영향력점 (Influence Point) 그리고영향력영역 (Influence Area) 을제안하였다. SI는놓인돌과빈정점사이의거리에따라정의하며, IP는 SI에대해임계치를이용하여정의하였다. 임계치는정석자료를이용한실험에서가장적절한값을찾았다. IA는영향력점덩어리와코어를이용하여정의하였다. 영향력점덩어리는이웃한영향력점들의그래프를덩어리로정의하였으며코어는이웃한영향력점을꼭지점으로하는사각형으로정의하였다. 저자는실험을통해서정석자료와다양한임계치를이용하여실험한결과영향력점과영향력영역의오차의산술평균, 표준편차등을구한결과임계치 140에서가장좋은결과가나왔다. 구해진임계치를이용하여바둑게임에적용한결과형세평가에중세력의해당하는영향력영역의결과가매우타당한것으로나왔다. 실제세력을형세평가에서영역으로계산하는것처럼실험에서구한임계치를이용하여정의한영향력영역을게임에서검토하여영향력영역이실제로형세평가에사용이적절함을보았다. 제안한방법은돌의영향력과그돌이속한 Group의안정도를이용하여영향력점그리고영향력영역을제안하였다. 앞으로의과제는초반과중반의세력을사용한다음수선택기법과세력을이용한전술의선택기법을연구하는것이다. [ 그림 9] 임계치 140 을사용한형세평가의예
123 참고문헌 [1] Hyun-Soo Park, Kyung-Woo Kang, and Hang-Joon Kim, Judgment of Static Life and Death in Computer Go Using String Graph, LNCS 3611, pp.547-555, 2005 [2] Hyun-Soo Park and Kyung-Woo Kang, Evaluation of String in Computer Go Using Articulation Points Check and Seki Judgment, LNAI 3809, pp.197-206, 2005 [3] K. Chen, The move decision process of Go Intellect, Computer Go, No. 14, pp. 9-17, 1990 [4] M. M ller, Counting the Score: Position Evaluation in Computer Go, ICGA Journal, 25(4):, 219-228, 2002 [5] 김영상, 컴퓨터바둑에서돌의세기와영향력분포에기반한형세평가시스템, 컴퓨터산업교육기술학회논문지, 제3권제3호, 259-270 쪽, 2002년. 3월 [6] 김광인, 이재욱, 이종국, 이종철, 영향력함수를이용한컴퓨터바둑의형세판단, 대한전자공학회추계종합학술대회논문집 (B), 제19권제2호, 1996년 11월 [7] 박현수, 이두한, 김항준, 컴퓨터바둑에서 String 안정도와 Group영역에의한정적분석, 전자공학회논문지 (CI편), 제40권제6호, pp76-86, 2003 [8] 심종식, 바둑정석사전, 일신서적출판사, 1994 박현수 (Hyun-Soo Park) 1992 년경성대학교전산통계학과이학사 1995 년경북대학교컴퓨터공학과공학석사 2005 년경북대학교컴퓨터공학과박사. 1997 년 ~ 현재경동정보대학컴퓨터정보기술과전임강사. 관심분야 : 컴퓨터바둑, 게임프로그래밍, 인공지능게임