게임 프로그래밍
Received: May. 10. 2021 Revised: Jun. 10. 2021 Accepted: Jun. 13. 2021
Corresponding Author: Byung-Doo Lee (YongIn University) E-mail: [email protected]
ISSN: 1598-4540 / eISSN: 2287-8211
Ⓒ The Korea Game Society. All rights reserved. This is an open-access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.otg/licenses/by-nc/3.0), which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
세력 함수를 활용한 알파고 간의 50개 대국에 대한 형세 판단※
이병두 용인대학교 AI학부 [email protected]
Full-board position evaluation of 50 AlphaGo vs AlphaGo games, using influence function
Byung-Doo Lee
School of Artificial Intelligence, Yong-In University
요 약
바둑에서의 형세 판단은 현재 대국 중인 흑백 대국자 간의 유불리를 판단하는 척도가 되며, 이를 통해 곧바로 적절한 전술과 전략을 구사하게 된다. 본 논문에서는 거리에 따라 반감하는 세력 함수를 활용하여 알파고 간의 50개 대국의 형세 판단을 하고자 했다. 실험 결과에 따르면 단지 세력 함수만을 사용하여 형세 판단을 하게 되면 정확한 판단을 함에 한계가 있음이 밝혀 졌다. 이를 극복하기 위해 사석 처리를 위한 사활문제 해결이 필요하며, 이를 보강하게 되면 바 둑에서의 정밀한 형세 판단을 할 수 있음을 보였다.
ABSTRACT
Full-board position evaluation in Go is a measurement of judging the advantages and disadvantages between black and white players during a game playing, and through this, the proper tactics and strategies would be undertaken in the near future. In this paper, we tried to evaluate the full-board positions of the 50 AlphaGo vs AlphaGo games using influence function that halved according to the distance. According to the experimental results, there is a limit to making accurate evaluation when the full-board position is assessed only by influence function. In order to overcome this, it is necessary to solve life-and-death problems to deal with dead stones, and it showed that if this is reinforced, we can precisely evaluate the full-board position in Go.
Keywords : Go(바둑), full-board position evaluation(형세 판단), influence function(세력함수),
life-and-death problems(사활문제)
1. 서 론
2,500년 이상의 역사를 가진 바둑은 오랫동안 컴퓨터가 인간을 제압하지 못했던 마지막 보드게 임이었으나, 2016년 알파고는 세계 최정상급 프로 기사인 이세돌 9단을 4:1로 완승하고 인간이 범접 할 수 없는 수준으로 진화했다[1].
바둑에서의 형세 판단(full-board position evaluation)은 매우 중요한 상위 개념이 되며[2], 형세 판단을 통해 현재 대국 1) 의 유불리를 판단할 수 있고, 이를 통해 향후 적절한 대응 전략과 전술 을 구사할 수 있다. 참고로 [Fig. 1]은 백16까지 진행 중인 대국으로 흑이 16집 정도를 이기고 있 는 장면이 된다[3].
[Fig. 1] Exemplary full-board position evaluation with a result favoring black[3]
본 연구에서는 [Fig. 2]와 같이 이미지 형태의 기보 2) 를 문자형 기보로 변환한 후 세력 함수를 이 용하여 흑백 간의 세력을 계산하였고, 이에 대한 세력 지도와 형세 판단을 하였다.
[Fig. 2] Procedure of influence utilization
2. 관련 연구
바둑에서의 형세 판단을 위해 K. Chen은 거리
에 따른 간단한 세력 함수인
를 제안 하여 그의 컴퓨터 바둑 3) 인 Go Intellect에서 형세 판단을 했다[4]. M. Müller는 그의 컴퓨터 바둑인 Explorer를 통해, (1) 분리자(divider)와 잠재 분리 자(potential divider) 개념을 도입하여 현재 대국 상태에서의 흑백 간의 영역을 분리한 후 (2) 분리 된 각 영역에 대한 계가 4) 를 통해 전체 국면 5) 에 대한 형세 판단을 했다[2]. 또한 A. Hwang 등은 12계층의 합성곱 신경망(CNN: Convolutional Neural Network)을 이용하여 현재 대국 상황에서 의 형세 판단 및 차기 착점 6) 을 예측했으며, 차기 착점에 대한 예측률은 프로 5단의 실력인 55% 정 도의 높은 정확도를 보였다[5].
본 연구에서는 2017년 인류사 최고의 명국들을 남기고 은퇴한 알파고 간의 50개 대국에 대해 세 력함수를 적용하여 대국 결과에 대한 유불리를 파 악하고자 했다[6].
3. 배경 이론
3.1 세력 함수
세력은 바둑판 내에 놓은 흑돌과 백돌이 빈 곳 에 미치는 잠재적인 영향력의 정도를 파악하는 바 둑의 상위 개념이 된다[7]. 인간 대국자는 세력을 통해 대략의 형세 판단을 하며, 이를 통해 공격과 수비와 같은 대응 전략과 전술을 짜게 된다. 세력 의 크기를 추정하는 세력 함수는 주로 흑백 간의 가상 경계를 확정 짓는 데 사용되고 있으며, 대부 분의 컴퓨터 바둑 역시 세력의 크기를 통해 흑백 간의 가상 영역을 구분하고 있다[8]. 1968년에 컴 퓨터 바둑을 최초로 구현한 A.L. Zobrist 박사는 세력 함수를 활용하여 해시 함수(hash function) 를 제안하였다[9]. K. Chen은 간단한 세력 함수인
를 제안하였으나 B.D. Lee는 세력 발생
지와 인접한 세력을 더욱 중시하여 식 (1)과 같은 세력 함수를 제안하였다[4].
′ ×exp
′ (1)
여기서
′ 는 세력 발생지인
와 세력의 영 향을 받는 곳인
′와의 거리가 되며, 상수
는 흑 돌과 백돌에 대해 각각 +64와 -64를 부여했다.
[Fig. 3] Two influence functions[4]
바둑판 내의 빈 곳인
′는 바둑판 위에 놓인 모 든 흑돌과 백돌로부터 세력
′ 를 받고 있으며, 그 크기는 식 (2)와 같이 계산된다.
′
′
′
∀
∈
∈(2)
즉, 바둑판 내의 모든 빈 곳인
′의 세력값
′ 는 바둑판 위에 있는 모든 흑돌
와 백돌
간의 세력값인
′ 와
′ 의 합으로 계
산된다.
3.2 세력 계산 알고리즘
[Fig. 4]에서 보듯이 바둑판 내 모든 빈 곳의 세력은 바둑판 내 놓인 모든 흑돌과 백돌에 의해
계산된다. 참고로 S는 1개의 빈 곳이 되며, F는 1 개의 흑돌이 놓인 위치가 된다.
[Fig. 4] Distance between two points
[Fig. 5]는 바둑판 내 모든 빈 곳들에 대한 세 력 값을 계산하는 알고리즘이 된다.
Algorithm 1 Influence Calculation(IC) 1: procedure IC
2: let Stones and Empties be queue 3:
Stones ← all colored stones in board4:
Empties← all emptypoints in board5: while
Empties ≠ nulldo 6:
start ← node in Empties7: while
Stones ≠ nulldo 8:
finish ← node in Stones9:
distance ← BFSstart finish10: sum_influence += influence by finish [Fig. 5] Procedure of IC
자료구조인 큐(queue)를 사용하기 위해 놓인 돌
들과 빈 곳의 정보를 담는 2개의 큐인 Stones와
Empties를 각각 설정하였다. Empties가 null이 되
기 전까지 모든 빈 곳의 각 점을 시작점(start) 그
리고 모든 돌을 종료점(finish)으로 설정한 후,
BFS() 함수를 활용한 두 점 간의 최단 거리 계산
을 하였다. 이후 식 (1)에 있는 최단 거리에 따른 지수함수를 이용하여 빈 곳의 세력값을 계산했다.
한 예로 [Fig. 4]에서 보듯이 흑돌에 의한 빈 곳의 흑 세력값을 구하기 위해서는 시작점(S)과 종료점 (F) 간의 최단 거리를 먼저 구해야 한다.
너비우선탐색(BFS: Breadth-First Search)은 트리 또는 그래프에서의 특정 노드(node 또는 vertex)를 탐색하거나 방문하는 알고리즘이 되며, 장애물이 있는 두 점 간의 최단 경로를 찾기 위한 알고리즘으로도 사용된다.
[Fig. 6]은 장애물이 있는 두 점(start와 finish) 간의 최단 거리를 계산하는 BFS 알고리즘이 된다.
Algorithm 2 Breadth-First Search(BFS) 1: procedure BFS(start)
2: let Q be a queue 3:
Q ←start4: while
Q ≠ nulldo 5:
v ←Q6: if v is the finish then return distance 7: for all edge w from v do
8: if w is not a valid point then continue 9: if w is a diagonal point then
10: distance +=
11: else if w is a V&H point then 12: distance += 1
13: Q ← w
[Fig. 6] Procedure of BFS[10]
사용되는 자료구조는 큐가 되며, 큐가 null이 되 거나 finish 점을 찾을 때까지 작업을 계속 수행한 다. 현재 노드에서 모든 이웃 노드를 방문하여 유 효한 노드에 대한 거리 계산을 수행한다. 참고로 유효하지 않은 노드는 바둑판에 놓인 흑돌과 백돌 이 되거나 이미 방문한 노드들이 해당이 된다. 거 리 계산을 위해서는 이웃 노드가 수직 또는 수평 (V&H)으로 배치되었는지와 대각선으로 배치되었 는지를 고려해야 하며, 최단 거리 계산을 위해 대 각선 노드(diagonal node)를 먼저 처리해야 하며, 이후 수직 또는 수평으로 이웃하는 노드를 큐에 추가시켜야 한다.
3.3 계가법
바둑에서의 계가법은 두 가지로 (1) 집을 세는 계가법(territory scoring)과 (2) 집과 돌을 세는 계가법(area scoring)으로 구분된다[11,12]. 한국과 일본에서는 집을 세는 계가법을 사용하며, 중국에 서는 집과 돌을 세는 계가법을 사용하고 있다.
[Fig. 7]과 같이 종료된 7줄 바둑에서의 계가를 살 펴보면
(1) 집을 세는 계가법: ⏹ 으로 표시된 흑의 집 은 19집, ○으로 표시된 백의 집은 9집이 되어 백 에게 6.5집의 공제 7) (komi)가 주어지면 흑은 3.5집 이기게 된다.
(2) 집과 돌을 세는 계가법: ⏹ 으로 표시된 흑 의 집 19점과 흑돌의 갯수인 11점을 합하면 흑은 30점이 되며, ○으로 표시된 백의 집 9점과 백돌 의 갯수인 10점을 합하면 19점이 되니, 백에게 7.5 집의 공제가 주어지면 흑은 3.5점 승이 되어 집을 세는 계가법의 결과와 같게 된다.
[Fig. 7] Final position
4. 실험방법 및 결과
4.1 실험방법
본 실험에서는 바둑에서의 형세 판단을 위해 세
력 함수를 이용하여 흑백 대국자 간의 우위를 계
산했다. 세력 함수 적용을 위한 컴퓨터 환경은
[Table 1]과 같고, 사용된 소스 프로그램은 C++이
되며 이미지와 그래픽 처리를 위한 유틸리티는 각 각 OpenCV 4.2와 MATLAB R2020b가 된다.
Desktop computer
CPU Intel(R) Core(TM) i5-8265U CPU ＠1.60 GHz
RAM 8.00GB
System 64 bit OS, x64 based processor
OS Windows 10 Pro
Compiler C++ in Microsoft Visual Studio 2019 Utilities OpenCV 4.2, MATLAB R2020b
[Table 1] Computer configurations
4.2 실험결과
4.2.1 기보 변환
[Fig. 2], [Fig. 8](a)에서 보듯이 우선 sgf 파일 형식으로 된 50개의 알파고 간의 초기 이미지 기 보를 OpenCV를 활용하여 [Fig. 8](b)와 같이 문 자형 데이터로 변환하였고, 이때 흑돌은 b , 백돌은
w, 빈 곳은
으로 처리하였다.
(a) (b)
[Fig. 8] (a) Original image. (b) Text data
4.2.2 세력 계산
[Fig. 8](b)에 있는 문자형 데이터에 대해 [Fig.
5], [Fig. 6]에 있는 세력 계산 알고리즘과 너비우 선탐색 알고리즘을 적용하여 바둑판 내 빈 곳의 세력값을 구한 결과는 [Fig. 9]와 같다. [Fig. 9]에 서 보듯이 바둑판 내 놓인 흑돌과 백돌의 세력값 은 각각 +64, -64로 처리하였으며, 빈 곳의 세력 값이 양수이면 흑의 세력권, 음수이면 백의 세력권 이 된다.
4.2.3 세력 지도
세력 함수에 의해 생성된 [Fig. 9]와 같은 바둑 판 내 모든 곳의 세력값을 갖고 MATLAB을 활 용하여 3차원 세력 지도를 그려보면 [Fig. 10]과 같다. 참고로 봉우리가 높을수록 흑의 세력이 크 며, 반대로 골짜기가 깊을수록 백의 세력이 크다.
[Fig. 10] The 3-dimensional influence map
[Fig. 9] Influence values after applying the influence function to the full-board positions
4.2.4 형세 판단
형세 판단을 위해 중국식 계가법을 적용하였다.
즉, 흑백 대국자 각각에 대해 바둑판 내에 있는 돌 들과 집을 세어 계가하였으며, 이후 공제(또는 덤) 는 7.5집을 적용하였다.
흑백 대국자 각각에 대해 집의 규모를 파악하기 위해 [Fig. 9]에 있는 세력값을 갖고, 바둑판 내 빈 곳의 세력값이 +49.0 이상이면 흑의 집, -49.0 이하면 백의 집으로 간주하였다. 적용한 결과 [Fig. 11]과 같이 흑의 점수는 189.0점, 백의 점수 는 168.5점이 되어 흑이 20.5점을 앞서고 있다.
[Fig. 11] Full-board position evaluation
이와 같은 방법을 알파고 간의 50개 대국에 적 용 시 형세 판단의 실제 결과와 실험 결과는 [Table 2]와 같다. [Table 2]에서 보듯이 실제 결 과와 실험 결과는 상당한 오차를 보이고 있는데, 그 이유는 형세 판단을 위한 사석 8) 처리에 대한 부재가 된다. 한 예로 [Fig. 11]에서 보듯이 좌하 귀와 좌하변에 걸쳐 원으로 표시된 죽은 흑돌에 대해 사석 처리를 하여야 하나, 이를 수행하지 못 해 잘못된 형세 판단을 하고 있다. 참고로 [Table 2]에 있는 ‘백불계승’은 백이 절대 우세, ‘흑불계승’
은 흑이 절대 우세를 의미하며, 실험 결과의 양수 는 흑이 우세, 음수는 백의 우세를 의미한다.
대국 실제 결과 실험 결과 대국 실제 결과 실험 결과 1 백불계승 20.5 26 백불계승 22.5 2 백불계승 43.5 27 백불계승 -1.5
3 백불계승 -10.5 28 흑불계승 -17.5
4 백불계승 -17.5 29 백불계승 -35.5
5 흑불계승 -5.5 30 백불계승 -16.5
6 백불계승 8.5 31 백불계승 -4.5
7 백불계승 -1.5 32 백불계승 -0.5
8 백불계승 -32.5 33 백불계승 2.5
9 흑불계승 -3.5 34 흑불계승 18.5
10 백불계승 -31.5 35 백불계승 27.5
11 흑불계승 8.5 36 흑불계승 7.5
12 백불계승 -1.5 37 백불계승 -25.5
13 백불계승 10.5 38 백불계승 6.5
14 백불계승 -33.5 39 백불계승 -14.5
15 흑불계승 -17.5 40 백불계승 -5.5
16 백불계승 -7.5 41 백불계승 -17.5
17 백불계승 10.5 42 흑불계승 -0.5
18 백불계승 9.5 43 백불계승 7.5
19 백불계승 3.5 44 백불계승 11.5
20 흑불계승 0.5 45 백불계승 2.5
21 백불계승 1.5 46 흑불계승 -15.5
22 흑불계승 44.5 47 흑불계승 12.5
23 백불계승 -27.5 48 백불계승 -39.5
24 백불계승 13.5 49 백불계승 -4.5
25 백불계승 -37.5 50 백불계승 2.5
[Table 2] Comparison between actual and experimental results
5. 결론 및 제언
바둑에서의 형세 판단은 현재 대국의 유불리를 판단할 수 있고, 적절한 대응 전략과 전술을 구사 할 수 있는 바둑에서의 상위 개념이다. 본 실험에 서는 세력 함수를 활용하여 50개 알파고 간의 대 국에 대한 형세 판단을 하고자 하였다.
실험 결과에 의하면 단지 세력 함수만을 갖고 형세 판단을 하는 것은 한계가 있음이 입증되었다.
이를 보강하기 위해서는 사석 처리를 위한 사활 9)
문제 해결이 우선되어야 함을 알게 되었다. 결국
이러한 문제가 해결된다면 상당히 정밀한 형세 판
단을 할 수 있음을 보였다. 아울러 보완된 형세 판
단 기법은 대국 종료뿐만 아니라 대국 중에서도
유용하게 사용되어, 대국 중 적절한 대응 전략과
전술을 구사할 수 있음을 알 수 있었다.
[Fig. 12] Image data, text data, influence map, and territories of 50 alphaGo games(part 1)
[Fig. 13] Image data, text data, influence map, and territories of 50 alphaGo games(part 2)
ACKNOWLEDGMENTS
이 논문은 2020년도 용인대학교 학술연구조성비 재원으로 수행된 연구임
REFERENCES
[1] B.D. Lee, “Contour Tracing to Solve Life-and-Death Problem in Go”, Journal of Korea Game Society, Vol. 20, No. 2, pp.
91-100, 2020.
[2] M. Müller, “Counting the Score：
Evaluation in Computer Go”, from https://webdocs.cs.ualberta.ca/~mmueller/ps/g oeval.pdf, 2021.
[3] Baduk Time, “How to compute full-board
evaulation”, from
https://baduktime.com/g2/bbs/board.php?bo_ta ble=research2&wr_id=950, 2021.
[4] B.D. Lee, “Multi-Strategic Learning, Reasoning and Searching in the Game of Go”, PhD thesis, Auckland University, 2005.
[5] A. Hwang et al., “Move Evaluation in Go Using Deep Convolutional Neural Network”, ICLR conference paper, pp. 1-8, 2015.
[6] DeepMind, “AlphaGo vs AlphaGo”, from https://deepmind.com/alphago-vs-alphago, 2021.
[7] J. Burmeister and J. Wiles, “AI Techniques
Used in Computer Go”, from
http://www.google.com/url?sa=t&rct=j&q=&esrc
=s&source=web&cd=&ved=2ahUKEwid3riq1Zjw AhUGGqYKHQqgDOMQFjABegQIAhAD&url=f tp%3A%2F%2Fftp.cse.ucsc.edu%2Fpub%2Fcom pgo%2FPAPERS%2Fcomp-go.AI.ps&usg=AOv Vaw2EeByNtMJvaoMWfH8my7PA, 2021.
[8] Sensei's Library, “Influence function”, from
[Fig. 14] Image data, text data, influence map, and territories of 50 alphaGo games(part 3)
https://senseis.xmp.net/?InfluenceFunction, 2021.
[9] A. Zobrist, “Feature Extraction and Representation for Pattern Recognition and the Game of Go”, PhD thesis, University of Wisconsin, 1970.
[10] Wikipedia, “Breadth-first search", from https://en.wikipedia.org/wiki/Breadth-first_sea rch, 2021.
[11] B.D. Lee, “The Best Sequence of Moves and the Size of Komi on a Very Small Go Board, using Monte Carlo Tree Search”, Journal of Korea Game Society, Vol. 10, No.
5, pp. 77-82, 2018.
[12] J.U. Kim, “Understanding the Rules of Baduk”, PUBPLE Press, 2017.
미 주(바둑 용어 해설)
