[=] Analyzing GNU Go's moves

Analyzing GNU Go's moves

Park Young-ki (cncpp@hanmail.net)

KAIST, South Korea

August 11, 2004

Abstract. GNU Go는 바둑을 두는 free program이며 top commercial go program에게 1-2점 놓고 두면 비슷한 수준이다. 이 논문에서는 GNU Go가 바둑을 두는 기본적인 과정을 살펴보고, GNU Go와 바둑을 둔 사례를 통하여 컴퓨터 바둑의 문제점과, 앞으로 해야 할 연구방향을 제시하고자 한다.

1. Introduction

1장에서는 컴퓨터 바둑과 GNU Go에 대한 소개를 한다. 1장 1절에서는 체스와 바둑의 비교를 하고 1장 2절에서는 Go++를 간략히 소개한다. 1장 3절에서는 GNU Go에 대해 설명하고, 1.4절에서는 GNU Go가 각종 대회에서 어떤 성과를 올렸는지 알아본다.

2장 1절에서는 GNU Go가 어떠한 과정을 거쳐서 착점을 결정하는지 기본적인 설명을 제시하고, 2장 2절에서는 GNU Go와 바둑을 둔 사례를 통해 구체적으로 어떻게 착점을 하는지 분석한다.

그리고 3장 1절에서는 GNU Go가 2.2절에서 제시했던 방식에 항상 당할 수밖에 없는지 알아보고, 3장 2절에서는 미래의 컴퓨터 바둑연구는 어떻게 진행되어야 할지 간략하게 논의한다.

1.1. A Comparison the Features of Chess and Go

체스는 컴퓨터가 세계 정상급 플레이를 할 수 있지만, 바둑은 아직 초보자 수준에 머물러 있다. 전통적이지만, 바둑 프로그램을 만드는 것이 얼마나 어려운지를 설명하기 위해 Burmeister & Wiles의 논문을 인용하여 체스와 비교해 보고자 한다.

1) 체스판은 네모꼴로 8x8이지만, 바둑판은 격자로 19x19이다.

2) 체스는 한 게임당 80수 정도까지 두지만, 바둑은 300수는 걸린다.

3) 체스는 branching factor(‘평균적으로 할 수 있는 행동의 수’ 정도로 이해하면 될 듯하다.)가 35수 정도까지지만 바둑은 200수 정도까지다.

4) 체스는 checkmate로 끝나지만 바둑은 집 계산으로 끝난다.

5) 체스는 pieces가 장거리 이동할 수 있으나 바둑돌은 움직이지 않는다.

6) 체스판의 상태는 pieces가 이동함에 따라 급속히 바뀌지만, 바둑판의 상태는 대부분 점차 변한다.

7) 체스는 체스판을 평가할 때 pieces의 수와 종류에 큰 상관관계가 있지만, 바둑은 그렇지 않다.

8) chess는 좋은 평가 기준이 있어서 tree search하기 편하지만, 바둑은 brute force search(휴리스틱을 사용하지 않고 무작정 search하는 것을 말함)하기에는 가지가 너무 많고, 가지치기는 좋은 평가 기준의 결여로 행해지기 힘들다.

9) 바둑은 시작하는 사람조차 60수를 검토하지만 체스는 10수를 검토한다.

10) 체스는 최고수 단계지만 바둑은 초보자 단계이다.

11) 체스는 계급 제도의 grouping인데, 바둑돌은 동시에 많은 group에 포함된다.

12) 체스는 덤이 없지만 바둑은 덤이 있다.

1.2. Go++

Go++은 Michael Reiss가 만들었으며 가장 널리 알려진 프로그램이다. 1983년에 상점에서 computing magazine을 읽던 중 천 파운드가 걸린 바둑 프로그램 콘테스트가 있다는 것을 알게 되어 바둑이 뭔지도 모르는 상태에서 참가하려고 결정했다고 한다. 1984년에 있었던 대회에서 10~12명이 참가했고 8명이 토너먼트로 경쟁하게 되었는데, 그의 바둑실력이 초보자 수준이어서 컴퓨터 바둑 프로그램도 성능이 뛰어나질 않았고, 결국 첫 번째 라운드에서 떨어지고 말았다. 그는 지금도 바둑 프로그램을 만드는 일을 하고 있으며 다른 수입원 없이 프로그램 판매에서 오는 로열티를 받아(주로 일본에서 많이 팔린다) 생활하고 있다. 개발자는 Go++의 기력이 영국기준으로 7급, 미국기준으로 6급이라고 주장한다.

Go++ FAQ에서는 2002년 당시 Computer Go Ladder 1위 프로그램이었다고 말하고 있는데 2004년인 지금도 (비공식적인 자료이지만) 그렇다.

1.3. GNU Go

GNU Go는 바둑을 두는 free program이며 top commercial go program에게 1-2점 놓고 두면 비슷한 수준이다. Open Source이기 때문에 누구나 개발에 참여할 수 있고, 개발자도 상당히 많다. 가장 마지막으로 나온 stable version이 GNU Go 3.4인데, 2003년 7월 31일에 만들어졌다. 본 논문은 GNU Go 3.4를 기반으로 작성되었다. 가장 최근의 development version은 3.5.10으로, 불과 며칠 전인 2004년 8월 7일에 만들어졌다. 연구는 꾸준히 진행되고 있다. 현재 기력은 10급 정도라고 하는데, 컴퓨터 바둑의 수준에 대해서는 좀 더 논의가 되어야 한다. 본 논문의 Discussion에서 이에 대해 언급한다.

1.4. GNU Go in tournaments

GNU Go가 각종 대회에서 거둔 성적이다. 최근에 있었던 대회 5개를 소개한다.

1. Computer Olympiad 2004.

19x19: 1위 Go Intellect, 2위 Many Faces of Go, 3위 IndiGo, 4위 Gnu Go, 5위 Jimmy.

　9x9: 1위 Go Intellect, 2위 Gnu Go, 3위 Magog, 공동 4위 Indigo, MFGO, Neurogo,

7위 Atarist, 8위 DumbGo, 9위 GoKing.

2. Computer Olympiad 2003

19x19: 1위 GNU Go, 2위 GoAhead, 3위 Dariush, 4위 Go Intellect, 5위 IndiGo,

6위 NeuroGo, 7위 Aya, 8위 Jimmy, 9위 Explorer, 10위 SmartGo, 11위 GoLois.

3. Gifu Challenge 2003

1위 KCC Igo, 2위 HARUKA, 3위 Go++, 4위 Goemate, 5위 The Many Faces of Go, 6위 Gnu Go, 7위 NeuroGo, 8위 GORO, 9위 Go Intellect 2003, 10위 Katsunari, 11위 AYA, 12위 Shikou Sakugo, 13위 GoWind, 14위 Padook Invincible, 15위 TSGO, 16위 Carens Whisper, 17위martha.

4. 21st Century cup in York Pennsylvania에서 8위를 했다. 의외로 Wulu에게는 이겼지만 결정적으로 Go4++에게 졌다.

5. The European Go Congress.

1위 GoAhead, 2위 GnuGo, 3위 Dariush, 4위 TurboGo, 5위 TS-Go, 6위 GoSymier, 7위 Augos.

2. Analyzing GNU Go's moves

2.1절에서는 GNU Go가 어떤 과정으로 착점을 결정하게 되는지 설명한다. 2.2절에서는 territory를 포기하고 moyo를 만드는 전략으로 GNU Go를 무력화한 사례를 통해, GNU Go가 왜 그러한 착점을 하게 되었는지 분석한다.

2.1. 착점을 결정하는 과정

먼저 GNU Go는 현재의 바둑판에서 정보를 얻는다. 여기서 얻어진 정보와 추가적인 move generators를 이용하여 후보 착점들이 생성된다. 마지막으로 각각의 후보 착점들은 territoal value(life-and-death effects, 잡은 것 등을 포함), strategical effects에 의해 값이 매겨진다. 그리고 가장 값이 높은 착점이 선택된다.

당연히 어떤 걸 잡을 수 있을지, 어떤 게 죽고 사는 것인지 수읽기를 하지만, 바둑판 전체를 바라보는 것은 아직 하지 못하고 있다.

2.1.1. Gathering Information

이것은 단연 Move generation에서 가장 중요한 단계이다. 생사를 잘못 판단하면 큰일이 날지도 모르고, 집을 잘못 평가하면 어떤 착점이 좋은지 잘못 평가하게 될지도 모른다. 또한 돌이 약하고 강한 것을 잘못 판단한다면 전략적으로 실수하게 될 수도 있다.

먼저, worms를 찾아서 크기(the sizes)가 어떻게 되는지, 이 worm을 잡으려면 얼마나 많은 돌이 필요한지(the number of liberties) 측정한다. 그 다음으로 worm을 분석한다. 전술적 수읽기 코드(tactical reading code)가 worms가 당장 잡힐 수 있는지 파악하는 것이다. 이 과정은 worm이 다섯 개의 liberties를 가질 수 있으면 그만둔다. 어떤 worm이 잡힐 수 있으면, 어떻게 하면 안 잡힐 수 있을지 알아본다. 이것 뿐만 아니라, worm을 잡고 방어하는 사실상 모든 착점들을 찾기 위해 많은 노력들이 행해진다.

어떤 worms가 전술적으로 안정되었는지 알게된 후에는, 바둑판 전체의 균형을 알아보기 위해 Influcence Function code를 부른다.

그리고 이번에는 dragons를 분석한다. dragons를 파악하고 어떤 dragons가 각각 떨어질 수가 없는지 결정한다. 이건 부분적으로 패턴에 의해 행해지는 것이다. 이 module은 서로에게서 각각 떨어진 두 주어진 worms가 연결될 수 있는지 결정하기 위해 minimax search를 행한다.

그런 뒤 주어진 dragon이 얼마나 강하고 약한지 알아보기 위해 다양한 시도를 해본다. 그리고 약하다고 판단된 dragons에게 owl code에 의해 생사 분석이 이루어진다. 두 dragons가 있는데 둘다 살지 못했다면 semeai(수상전) module을 사용하여 이 상황을 해결하려 해본다.

그리고 influcence code를 다시 불러서 territory일것 같은 지역에 대해 자세한 분석을 한다. 이때 당연히 dragons의 생사도 고려된다.

이런 influence moudle의 territorial results는 break-in module에게 전해져서, 어디서 상대방이 침입할 수 있는지 분석한다.

2.1.2. Move generators

상태에 대한 모든 걸 알게 된 다음에는, 어떤 곳이 가장 좋은 착점일지 생각해야 할 것이다. 착점들은 많은 move generators에 의해 제안된다. move generator 스스로는 착점에 대한 값을 설정할 수 없지만, 그들이 정당하다는 증거는 제시할 수 있는데, 그것이 바로 move reasons이다. 착점들에 대한 평가는 모든 착점들이 고려되고 move reasons가 제시된 후에 마지막으로 행해진다.

앞에서 얻어진 정보들을 이용하는 move generators는 worm_reasons(), owl_reasons, semeai_move_reasons(), break_in_move_reasons, fuseki(), shapes(), combinations(), revise_thrashing_dragon(), endgame_shapes(), revise_semeai(), fill_liberty() 등이 있다.

2.1.3. Move Valuation

move generation module이 실행된 후에는, 각각의 제안된 후보 착점들이 review_move_reasons 함수에 의해 자세한 평가를 받게 된다. 이 함수는 빠뜨린 move reasons를 발견하기 위해 약간의 분석을 한다.

착점에 있어서 가장 중요한 값은 territorial effect이다. 이 값은 territory란 말로 바로 표현될 수 없는(예를 들어 combination attacks, strategical effects, connection moves 따위) 모든 move reasons를 위해 수정된다.

2.2. 사례 분석

GNU Go를 상대로 실리를 내주는 대신 세력을 착실히 쌓아나간다면 간단하게 모든 중앙 집을 차지할 수 있다. 그 사례 중 하나를 선택하여, 왜 GNU Go가 그러한 착점을 하게 되었는지 분석하고자 한다.

2.1.1에서는 2수, 2.1.2에서는 16수, 2.1.3에서는 26수까지 진행된 대국에 대해 분석한다. 2.1.4에서는 그 이후의 대국에 대해 (중복되는 내용이 많으므로) 간략한 언급을 한다.

2.1.1. 2수 진행된 대국

그림 1: 백이 두 번째 착점으로 화점에 둔 상황

① 그림 1을 보자. GNU Go가 백을 쥔 상황이다. GNU Go는 왜 화점에 두었는가?

GNU Go가 백을 쥔 상황이다. GNU Go는 왜 화점에 두었는가? 먼저 GNU Go는 Fuseki(포석) database에서 흑이 둔 5x4에 둔 수와 일치하는 패턴을 찾는다. 찾아보니 이 상황과 똑같은 패턴은 존재하지 않지만 적당히 변경을 가하면 이 상황에 쓰일만한 패턴 3개를 찾을 수 있었다. 그것이 바로 백이 둔 ‘2’와, A와 B이다. 즉 GNU Go는 흑이 5x4에 둘 경우 무조건 화점에 두게 된다. 그러면 '2‘와 A, B. 세 곳 중 어떤 곳이 더 좋은 수인가? 각 패턴에는 미리 입력된 relative weight가 존재하는데, '백 2’는 relative weight가 28, A는 47, B는 10이다. 이 중 가장 relative weight가 큰 값인 47의 20%인 9.4보다 큰 값을 가진 패턴과 매치되는 착점들에 한해 랜덤으로 선택한다. 세 착점 모두 relative weight가 9.4보다 크므로 세 곳 중 랜덤으로 한 곳이 선택된다. 선택되면 75의 값이 부여되고 그렇지 않으면 74의 값이 부여된다. 개발자는 이러한 요소(랜덤으로 선택하는 것)가 GNU를 예측 불가능하게 만드는 장점이라 주장한다. (이에 대해서는 논의가 있어야 할 것이다.)

GNU Go는 물론 Fuseki database에 없는 다른 수도 고려한다. move reasons를 가진 착점은 a, b, c 세 가지가 있는데, a의 경우 territory와 moyo를 확장하는 수이며, 흑 1을 전략적으로 공격하는 수라 평가된다. 또 b는 침입하는 수이며 territory, moyo를 확장하는 수로, c는 territory와 moyo를 확장하는 수로 평가된다. 이들 각각은 change in territory, strategic effect, followup value가 평가되어 값이 매겨지지만 Fuseki database에서 찾아진 pattern과 매치되는 착점(‘백 2’, ‘A’, ‘B’)들이 워낙 큰 값을 부여받기 때문에 선택되지 않는다. 그 외에 패턴과 매치되었으나 낮게 평가된 20여개의 착점들 또한 마찬가지이다.

Fuseki database는 언제까지 쓰이는가? 경험적으로는 4~5수 정도이며, 현존하는 패턴도 4~5수 정도까지만 고려되어 있는 것 같지만 프로그램에는 20수 이후로는 쓰이지 않도록 설정되어 있다. Fuseki database가 더 이상 쓰이지 않게 되면, a, b, c 따위의 수들도 쓰일 수 있게 된다.

2.1.2. 16수 진행된 대국

그림2: 16수까지 진행된 상황

② 그림 2를 보자. 세력이 강한 쪽으로 날 일자 걸침을 한 이유는?

이번 경우에는 Fuseki database가 더 이상 영향을 미치지 않고, 앞에서 고려되었던 c(백 16), a, b가 순서대로 각각 가장 큰 값을 가진다. 각 경우의 값을 비교해 본 것이 표 1이다.

	c (C7)	a (D3)	b (C3)	d (G17)	f (N18)	e (P8)	f (R8)
change in territory	25.04	12.66	16.31	31.85	13.40	15.93	15.94
added due to followup	3.79	4.22	4.16	4.55	7.06	5.65	5.00
strategical effect	-	4.46	-	3.42	-	-	-
connects string	-	-	-	-	0.41	-	-
shape	-	-	-	-	-	-0.98	-0.95
minimum accepted value	-	24.71	24.46	-	-	-	-
maximum accepted value	-	24.60	24.36	24.12	-	-	-
Move generation values	28.84	24.60	24.36	24.12	20.87	20.60	19.98

표1: Move generation values

밑줄 친 값이 최종 값에 영향을 미친 값, 굵은 값이 최종값이다.

strategical value는 바둑판의 모든 group의 안전성 면에서 착점이 지닌 일정량의 효과를 말하는데 ‘a' 또는 'd' type을 가진 pattern과 매치되는 착점에 strategical defense 또는 attack reasons가 할당된다.

shape는 순수하게 국부적인 shape를 분석한 값이다. 이것은 territoral values의 예측에 의해 만들어지는 잘못을 보완하기 위해 측정된다. 패턴에 값이 할당될 수 있다.

followup value는 worm이나 dragon을 attack, defend 하려고 하는 것에 대해 값을 할당하는데, influence module이 평가하게 된다. followup value의 contribution은 ggmin(ggmin(0.5*followup_value + 0.5*move[pos].reverse_followup_value, 1.0 * tot_value ＋ followup_value), 1.1 * tot_value + move[pos].reverse_followup_value)에 의해 정해지는데(ggmin 함수는 두 개의 값중 작은 값을 리턴한다.) 위의 표에서는 모두 followup value의 1/2 값으로 사용되었다. 만약 바둑판에 패가 났다면, 팻감으로 쓰기에 좋으며 모든 followup value가 계산에 포함된다.

또 패턴은 minimum value나 maximum value를 할당할 수 있는데, a와 b는 minimum value에 의해 더 큰 값이 되었고, d는 maximum value에 의해 더 작은 값이 되었다. 만약 maximum value가 없었다면 착점 d가 착점 c 대신에 선택되었을 것이다. 이 값들을 사용하지 않는 편이 좋다는 사람들도 있다. GNU Go 3.0이 나왔을 무렵 GNU Go development Archives에서 2001년 11월에 있었던 논의인데, Arend Bayer는 maximum value가 없어도 Gnu Go가 이 값들을 생각하는 것에 있어서 이치에 맞는 일을 한다며 자신은 maximum value가 필요하다는 것을 이해하지 못하겠다고 말한다. 그에 대한 답변 중 하나로 Gunnar Farneback는 maximum value가 존재하는 본질적인 두 가지 이유가 있다고 말한다. 첫째로 influence function의 기묘한 습성 때문에 어떤 포석 착점이 현저하게 과대평가될 수 있으며 이것은 매우 나쁜 결과로 이어질 수 있다는 것이다. 둘째로 GNU Go의 다양성이 증가될 수 있다고 하는데, 이것은 같은 maximum(혹은 minimum) 값을 가지는 패턴들이 있을 경우 랜덤으로 선택하여 GNU Go의 행마를 좀 더 예측 불가능하게 할 수 있다는 뜻이다. 착점 d는 후에도 종종 등장하고 territorial value도 그때마다 항상 최고를 자랑하지만 번번이 maximum value 때문에 다른 착점이 선택되는 것을 볼 수 있다. maximum value가 설정되는 이유는 착점 d와 매치되는 패턴 'EB209'+7이 fuseki pattern으로 분류되기 때문이다. 여러 fuseki pattern이 있을 경우 그것들은 maximum value에 의해 모두 같은 값을 가지게 되고 결국 그 중 하나를 랜덤으로 선택하게 되는데, Gunnar Farneback이 말하는 것처럼 랜덤으로 선택하는 것에 의해 GNU Go의 행마가 예측 불가능하게 된다는 것이다.

마지막으로, change in territory는 territorial value가 얼마나 변했는가를 말해준다. 각각의 바둑판 intersection은 어떤 돌의 집이 될 것인지 평가되어서 -1.0에서 1.0까지의 값을 가지게 되는데 이 값의 합계의 변화로 계산될 수 있다. (dragon이 죽은 경우 -2, +2로 계산된다.) 그림 3은, 흑의 착점 15의 territorial valuation과 백의 착점 16의 territorial valuation을 비교하여, 백의 착점 16으로 인해 얻어질 수 있는 효과(change in territory)를 나타낸다.

그림3: 백 16수에 의한 change in territory.

앞에서 의문점으로 제기되었듯, 날 일자 공격을 한 것은 그곳이 가장 territorial value가 커지는 지점이기 때문이다. (d는 예외) 이 경우 외에 앞으로 할 대부분의 착점에서도 change in territory는 가장 큰 영향력을 지닌다.

2.1.3. 26수 진행된 대국

그렇다면, change in territory, added due to followup, strategical effect, connects string, shape와 shape factor, 또 그 외의 다른 요소들의 값을 다 합한 것도 모자라서 잘못 계산할 것을 우려하여 maximum value와 minimum value까지 할당한 것을 적용한 결과는 어떠한가? 좀 더 대국을 진행시킨 그림 4를 보자. 그렇게 많이 고려를 했음에도 불구하고 백은 흑에게 두터운 세력을 제공하고 말았다.

그림4: 백이 26수까지 진행한 모습.

③ 백 26을 두기 전에 백은 흑의 중앙 세력이 두텁다는 것을 몰랐는가? 알고 있었다면, 왜 그랬는가?

백 26처럼 날 일자 행마를 해서 실리를 취하는 것 보다는 흑의 중앙 세력을 적당히 견제하는 쪽이 좋았을 것이다. 백은 26수 이후로도 더욱 탄탄한 세력을 흑에게 주게 되고, 전세를 뒤집기 위해 무모하게 흑의 진영에 침입을 시도하고, 돌은 점점 무거워져서 거대한 대마가 잡혀서 대패한다. GNU Go가 중앙세력을 집으로 취급하지 않는 거라 생각할 수 있으나 이미 프로그램은 흑의 moyo가 상당히 많다는 것을 알고 있었다 (그림 5).

그림 5: GNU Go가 평가한 흑과 백의 territory, moyo, area 그림 6: GNU Go가 고려하는 착점들

그림 5을 보자. GNU Go는 형세를 위와 같이 판단한다. 청록색이 territory, 노란색이 moyo, 빨간색이 area이며, 바둑판이 지워진 부분이 흑과 백의 경계이다. moyo의 수는 엄청나게 차이가 나며, territory도 백이 불과 10집 정도 많을 뿐이다. (초반이라 흑 25 때문에 흑집이 지나치게 부풀려진 감이 있을 거라 생각할 수 있는데, 흑 25가 없어도 위 상태는 특별히 변하지 않는다.) 주목할 만한 점은 이와 같이 상황에 처했을 때 GNU Go는 무조건 실리를 챙기려 한다는 점이다.

왜 이런 수를 두는지 알아보기 위해, GNU Go가 흑이 25수를 뒀을 때 고려하는 착점들을 조사해 본 그림이 그림 6과 같다. 검은 점들이 백이 26수를 두기 전에 고려하는 착점들이다. 이런 착점들은 현재 상황과 일치하는(또는 변형하여 일치될 수 있는) pattern이 있어야 제시될 수 있는데, 이런 pattern들은 당연히 database에 미리 입력되어 있는 것들이다.

2.1절에서 언급했던 Move generation 과정부터 이미 잘못된 것이라 여겨진다. 충분한 패턴이 없었기 때문일 수도 있고, 패턴을 처리하는 방식이 잘못 되었을 수도 있고, 패턴에 의존하는 방식 자체가 근본적으로 잘못된 것일지도 모른다. 물론 모든 수를 고려할 수는 없겠지만 이렇듯 패턴에 의해 행동의 제약을 받기보다는 좀 더 새로운 접근이 필요해 보인다.

2.1.4. 이후 진행된 대국

그림 7은 이후 진행된 바둑판의 모습을 나타낸다. 왼쪽 위쪽의 그림(a)은 40수까지 진행된 모습, 오른쪽 위쪽의 그림은 98수까지 진행된 모습(b), 왼쪽 아래의 그림(c)은 130수까지 진행된 모습, 오른쪽 아래의 그림(d)은 189수까지 진행된 모습이다.

그림 7: 이후 진행된 바둑판의 모습

그림 a는 앞에서 보았던 분석과 거의 흡사하다. 흑 39의 의도를 눈치챈 것 같이 느껴지기도 했지만, 역시 이번에도 territorial value가 크기 때문에 저 착점이 선택되었고, 실제로 고려한 착점의 수도 극히 제한되어있다.

그림 b의 모습은 중앙에서 사활이 걸린 전투가 벌어진 장면이다. 백이 흑의 세력이 강한 쪽으로 침투해서 집을 지으려고 했는데, 흑이 그것마저 허용하지 않으려고 끊어서 싸움을 걸었다. 그러자 백은 한칸 뛰거나 날일자, 눈목자 등으로(무작위로 중앙으로 뛰쳐나가는 것처럼 보였다.) 행마를 계속했고 그림 b의 형태가 되었다. 관찰하려고 하려는 부분은 위쪽 백과 아래쪽 백을 연결하지 못하게 하려는 의도로 흑 97을 두었을 때, GNU Go가 98로 흑을 막은 부분이다. 이 수는 위와 아래에 있는 백을 직접적으로 연결하는 수는 아니지만(move reasons에 'connects string'이 없다.) 위쪽 아래쪽 백을 방어하고, 왼쪽 흑 세 점을 위와 오른쪽의 흑과 끊어서(왼쪽 흑과 끊었다는 생각은 하지 않는다.) 공격하려 하는 수이다. (위쪽 백 두 점을 효율적으로 방어하는 것 같지 않다고 생각하기도 한다. 이것은 착점에 대해 평가할 때 감점요인이다.) 이때부터는 territorial value보다 strategical value가 더 큰 값을 가진다 (상대방을 위협하는 수도 중요하기에 followup value도 비중도 높아진다.). 백 98이 가지는 최종 값은 47.24인데, territorial value는 불과 16.15의 값을 가진다. 그런데, 지금은 대마가 살면 백이 이기고, 대마가 죽으면 백이 지는 상황인데, 굳이 territorial value를 감안할 필요가 있었냐는 의문점이 든다. 하지만 전투 상황에서 대부분 전투에 관련된 수만 두는 것은 대마의 중요성을 어느 정도는 인식하고 있다는 뜻으로 해석될 수 있다. (높은 값을 가진 착점들은 모두 백을 살리려는 수이다.)

그림 c의 모습은 백이 살 곳을 찾기 위해 밖으로 뛰어나오는 모습이다. GNU Go는 위쪽에 있는 흑과 아래쪽에 있는 흑을 끊어 놓으려는 수라고 인식하지만, 그렇게 전략적으로 중요한 일이라고 평가받지는 못했다. 그렇지만 followup value가 커서 착점으로 선택되었다. 그밖에 흑을 공격하는 수도 많이 찾아보는데, 깊게는 10수까지도 바라본다. 40개 정도의 공격하는 수를 찾았지만 흑이 별 위협을 받지 못하는 수여서 착점으로 선택되지 못했다. (그림 b의 모습에서도 이렇게 흑을 공격하기 위한 수읽기를 시도한다.)

그림 d는 끝내기를 하는 장면인데, 흑이 187로 먹여쳐서 백 5점을 잡았다. 그런데 백은 백 다섯 점이 잡혔다고 생각하지 못하고 188로 흑 187을 먹는다. 아직 GNU Go는 먹여쳐서 돌을 잡는 개념을 이해하지 못했다. GNU Go는 백 188이 백 다섯점을 살리는 방법이라고 생각한다. 그렇기에 무려 27.81라는 territorial value를 가지며, 최고의 착점으로 인식되어 흑이 187로 먹여치자마자 188로 먹여친 흑을 바로 먹는다.

결과는 덤 없이 흑의 101집 승리였다. 그림 8은 최종 기보이다.

그림 8: 박영기(흑) vs GNU Go(백). 덤 없이 흑의 101집 승리로 끝났다.

3. Discussion

3.1. GNU Go는 항상 세력을 쌓아 나가는 방식을 당해낼 수 없는가?

Appendix에 정리해둔 The GNU Go Task List의 Long term issues 5번을 보면, GNU Go는 상대방 moyo를 줄이고 침입하는 것들을 명확하게 시도하는 move generator를 가지지 않았다고 말한다. 흑이 엄청난 moyo를 가지고 있음에도 끝까지 자신의 territory를 늘려가고자 했던 앞의 예가 대표적인 예라 할 수 있겠다. 또 다른 예를 그림 9에 보였다.(a) (b)(c) (d)

그림 9: 같은 방식으로 GNU Go를 이긴 대국들

이렇게 하지 않고, 아주 단순한 방식으로 세력을 쌓아도 무방하다. 예를 들어 첫 수를 화점에다 둔 뒤, 다른 화점을 향해 계속 한 칸을 뛴다. 그리고 그 화점 근처에 도착하면, 다른 화점을 향해 또 반복한다. 이런 방식으로 간단하게 중앙집을 모두 차지할 수 있다. 아래 그림이 그 예다. 아래 그림(그림 10)에서는 흑이 47을 둔 뒤 백 48로 중앙 집이 공격당하는데, 날일 자나 눈목 자로 요령있게 뛰면 이런 점도 방지할 수 있다.

그림 10: 무조건 한칸 뛰는 방식으로 모든 중앙집을 차지한 모습. (백 3점은 죽었다고 가정)

하지만 모든 경우에 GNU Go가 당하고만 있는 것은 아니다. 이미 move reasons 중의 하나로 'expand moyo'가 자주 등장한다. 실제로, 경우에 따라 GNU Go가 moyo를 확장하는 행동을 보여줄 때도 있으며, 상대방의 moyo를 줄이려고 하거나, 조금 어설프지만 상대방의 넓은 moyo를 가진 지역에 침입하는 행동을 보여주기도 한다. 이런 현상은 상대방이 컴퓨터 바둑 프로그램이라는 것을 모르고 대국을 하게 될 경우 더욱 자주 나타난다(그림 9의 a). 얼마 전에 있었던 computer olympiad 2004에서 GNU Go는 Go Intellect를 상대로 세력작전을 펼친다(그림 9의 b).

그림 9: (a) 흑이 박영기, 백이 GNU Go. 백 42와 44는 GNU Go가 중앙 집을 지으려는 의도를 가지고 있음을 보여준다. (b) 흑이 Go Intellect, 백이 GNU Go. GNU Go는 중앙 집을 지으려고 한다.

3.2. 컴퓨터 바둑 프로그램의 미래

컴퓨터바둑은 기력이 정확히 몇 급이라 말하기가 상당히 힘들다. 컴퓨터바둑의 기력이 2002년에 아마 1단에 미치지 못한다는 말도 있고 , 2000년에 바둑 프로그램들이 못 두는 것은 17급, 잘 두는 것은 5급까지 둔다는 주장도 있으며, 2002년에 Go++이 6~7급이라는 주장도 있고, GNU Go가 2003년에 10급이라는 주장도 있다. 하지만 GNU Go 3.4가 기력이 13급인 사람들과 대국을 많이 해 보았더니, 대부분 50집 이상으로 패했다. 이에 대해 GNU Go의 기력은 GNU Go의 약점을 얼마나 잘 아느냐에 크게 의존한다고 반박할지 모르지만, 이 결과는 컴퓨터 바둑 프로그램이라는 것을 알리지 않고 한 사람당 한 번씩만 대국을 했을 때 나타난 것이었다. 만약 GNU Go라는 것을 알고 위와 사례에서 밝힌 방식으로 두게 되면 18급도 GNU Go를 이길 수 있을지 모른다. 만약 모른다고 하더라도 세력을 주로 쌓는 방식으로 잘 두는 18급이라면 GNU Go를 크게 이길 수 있으리란 예측을 하게 된다. 이렇듯 컴퓨터 바둑의 기력은 과대평가 되어왔다. 그리고 그 결과로, 한국에서 만들어진 컴퓨터 바둑 프로그램 Fungo는 각종 국제대회에서 상위 입상하는 성과를 거뒀지만, 일반인에게 판매되자마자 회사 게시판에서 컴퓨터 바둑의 수준이 형편없다는 비판을 들어야 했다.

11년 전에 컴퓨터 바둑 프로그램의 수준이 9급이라는 말이 있었다. 또한 9년 전에 Dan Liu와 Richard Brown은 10년 후에 컴퓨터 바둑의 수준이 프로의 수준에 도달할 것이라 예측했다. 그러나 ‘현재 컴퓨터 바둑의 수준이 5~10급의 위치에 있다‘라는 주장은 11년 전과 다를 바가 없고, 실제 기력도 크게 차이가 없는 듯하다. (가장 마지막으로 나온 stable version이 GNU Go 3.4이며, 1년 전에 나온 프로그램이라는 것도 이런 걸 의미하는 게 아닌가 싶다.)

Appendix에 GNU Go가 앞으로 해야 할 일에 대한 언급이 있는데, 내 생각엔 저런 방법으론 앞으로 10년 후에도 컴퓨터 바둑의 기력은 크게 변하지 않으리라 생각한다. Pattern과 관련된 내용이 상당히 많은데, 먼저 Pattern의 필요에 대해서도 다시 한번 생각해 볼 필요가 있다. (앞에서도 Pattern database 때문에 흑에게 중앙 세력을 모두 내주고 말았다.)

로드니 브룩스의 로봇연구는 컴퓨터 바둑 프로그램과 많은 연관이 있다고 생각한다. 그의 책에서 그는 어떤 로봇이 진정한 인공지능을 가지고 있다고 볼 수 있는지 언급한다. 그의 방식은 너무나도 단순했기 때문에 학계의 인정을 받기가 힘들었지만, 실제로 훨씬 좋은 결과를 낳았다. 컴퓨터 바둑 프로그램도 비슷하지 않을까 싶다. 전산학에 쓰이는 복잡한 알고리즘을 적용하려는 생각을 하지 말고, 어떠한 접근방식이 괜찮을지 근본적으로 많은 생각을 해봐야 할 필요가 있을 것 같다. 하드웨어의 발전에 비해 컴퓨터 바둑 소프트웨어의 발전은 너무나도 느리다.

하지만 꼭 그렇다고 해서 지금의 컴퓨터 바둑 프로그램이 진정한 인공지능을 가지고 있지 못하다고 단정하기도 힘들다. 기존의 프로그램에도 로드니 브룩스가 말하는 ‘창의적인 행동’이 가끔씩 존재한다. 예를 들면 중앙에서 큰 전투가 일어나면, 그것에 집중한다. 그래도 대부분의 경우에 사람의 사고와 너무나도 다른 착점을 선택하는 건 사실이다. 바둑판 전체를 보지 못하는 것은 분명히 커다란 문제다.

Hollgor는 로드니 브룩스의 책에서 소개된 로봇 토터스와 비슷한 바둑 프로그램을 제안한다. 세 가지 규칙에 의거하여 바둑을 진행하는 것이다. 위에서 언급된 그림 10(한 칸씩 뛰어 중앙 집을 차지한 사례)도 그러한 생각을 통해 만들어진 것이다. 이런 단순한 규칙들도 충분히 고려해볼 필요가 있다고 생각한다.

4. Conclusion

지금까지 컴퓨터 바둑 프로그램 GNU Go가 어떻게 착점을 하는지 간단히 살펴보았다. 대표적으로 GNU Go는 Pattern Databases를 사용함에 따른 문제를 가지고 있었고, Move generation values를 계산하는 것도 큰 문제로 인식된다. 또한 GNU Go는 상대방이 세력을 쌓아 나가면 속수무책으로 당했고, 그것은 컴퓨터 바둑이 중반전에 문제가 있을 뿐 아니라 포석에서조차 커다란 문제가 있음을 밝혔다. 마지막으로 미래의 컴퓨터 바둑 프로그램에는 새로운 방식의 접근이 필요하다는 것을 밝혔다.

5. Acknowledgements

먼저 이 논문을 쓸 수 있게 해주신 박우석 교수님께 감사드립니다. 비록 좋은 결과를 내진 못했지만, 교수님께서 해주신 격려는 무엇보다 큰 힘이 되었습니다. 로드니 브룩스의 책을 소개해 주신 것도 논문에 많이 쓰이지는 못했지만 앞으로 큰 도움이 되리라 생각합니다. 그리고 제 연구방향을 조언해 주시는 등 직접적으로 많은 도움을 주신 bud1027 님께 정말 감사드립니다. 논문에 쓰인 내용 대부분이 bud1027 님께 영향을 받았습니다.

References

[1] Burmeister & Wiles. 'An Introduction to the Computer Go Field and Associated Internet Resources'. http://www2.psy.uq.edu.au/~jay/go/CS-TR-339.html

[2] Go++ by Dr Michael Reiss - FAQ. http://www.goplusplus.com//go4ppfaq.htm

[3] The Computer Go Ladder. http://www.cgl.ucsf.edu/go/ladder.html

[4] GNU Go Homepage. http://www.gnu.org/software/gnugo/gnugo.html

[5] GNU Go 3.4 Documentation. http://www.gnu.org/software/gnugo/gnugo_toc.html

[6] GNU Go in tournaments. http://www.gnu.org/software/gnugo/tournaments.html

[7] Computer Olympiad 2004. http://www.cs.unimaas.nl/olympiad2004.

[8] Computer Olympiad 2003. http://www.cs.unimaas.nl/olympiad2003

[9] The Result of Gifu Challenge 2003. http://www.hiroshima-pu.ac.jp/~sasaki/cgf/gifu2003/resulte.html

[10] The 2001 European Go Congress, Computer Go. http://www.britgo.org/results/computer/egc01.html

[11] GNU Go development Archives. http://lists.gnu.org/archive/html/gnugo-devel

[12] GNU Go development Archives. http://lists.gnu.org/archive/html/gnugo-devel/2001-11/msg00043.html

[13] GNU Go development Archives. http://lists.gnu.org/archive/html/gnugo-devel/2001-11/msg00047.html

[14] 박정아. 컴퓨터바둑의 새로운 미래.

[15] Martin Mueller. Computer Go.

[16] 박우석, 바둑철학

[17] Intelisoft Homepage, http://www.intelisoft.co.kr

[18] 아고라, http://www.agora.co.kr, 바둑철학 란, 335번 글.

[19] Rodney Brooks, 박우석 번역. flesh and machines.

[20] A Novice Tries To Write A Go Program, http://senseis.xmp.net/?ANoviceTriesToWriteAGoProgram

Appendix AThe GNU Go Task List

GNU Go 개발자는, GNU Go 프로그램의 기력을 높이기 위해 필요한 것들로 Small project는 11개, Long term issues는 8개를 제안한다.. 각각은 다음과 같다.

Small Projects

1) main diagram과 constraint diagram이 일치하는지 테스트하는 'patterns/mkpat.c'에 검사를 추가하는 것.

2) movelists를 파일로 처리하는 것을 준비하고 그것을 생성하는 것. Move lists가 그 중 에서도 특히 worms.c에서 worm을 잡고, 지키고, 잡으려고 위협하고, 지키려고 하는 착 점들을 저장하는 데에 쓰인다.

3) worms에 쓰이는 것과 같은 방식으로 dragons와 eyes를 위한 중요한 착점들을 저장하 는 move lists를 구현하는 것. Half eyes는 이미 어느 정도 해냈다. 착점들은 저장되지 만, attack, defend codes (LOSE, KO_A, KO_B and WIN)은 그렇지 않다.

4) 64 bit 환경에서 스토리지를 낭비하지 않는 캐쉬를 만드는 것.

5) superko violation을 파악하는 것을 구현하는 것.

6) eye_data, half_eye_data, worm, dragon을 dragon2 array와 같은 구조로 사용될 수 있게 변환하는 일을 완벽히 끝내는 것.

7) semeai code(수상전 코드)에서 persistent caching을 구현하는 것.

8) eyes.db와 optics.c에 있는 패를 원조하는 것.

9) clock.c에 있는 autolevel code와 play_gtp.c에 있는 time handling code를 통합하는 것. 아니면 그 대신에, 좀 더 좋게 하는 것.

10) 어렵지만, 패의 다른 형식(approach move ko, multi-step ko, etc)을 제어하는 틀을 만들 고 그것들을 제어하는 코드를 작성하는 것.

11) joseki(정석) databases를 통해 행해지는 script를 쓰고, engine이 정말로 데이터베이스에 있는 모든 위치의 정석 착점을 생성하는지 확인하는 것.

Long term issues

1) regression test suites를 확장하는 것.

2) pattern databases를 조율하는 것.

3) joseki database를 확장하고 조율하는 것.

4) semeai module 개선.

5) moyo를 명백하게 build/reduce/invade하는 move generator를 갖는 것.

6) 많은 개선된 combination module을 만드는 것.

7) 전술적 수읽기 속도를 높이는 것.

8) group의 안전성 평가를 위한 휴리스틱을 개선하는 것.