바둑/인공지능

• 상위 문서: 바둑

1 개요

지금까지 사용되었던 바둑프로그램의 인공지능을 요약하면 다음과 같다. 출처는 기사를 참고, 요약하였다.

• 1940 ~ 1950년대 : 컴퓨터 개발 및 인공지능 연구의 시작.
• 1960 ~ 1970년대 : 바둑을 연구하는 과학자 등장, 1969년 알버트 린지(Albert L. Zobrist) 박사는 "A model of visual organization for the game of GO" 논문을 통해 세계 최초로 컴퓨터 바둑 프로그램을 발표했다. 초기 인공지능 바둑은 패턴인식 방식으로 제작되었다.
• 1990, 2000년대 : 이전의 인공지능 프로그램은 데이터베이스(DB)를 축적한 후 그 DB를 기반으로 다음 착수점을 찾는 방식이다.
• 2006년 이후 : 아마추어의 수준도 가지지 못했던 컴퓨터 바둑은 실반 젤리(Sylvain Gelly), 아자 왕(Yizao Wang), 아자 황(Aja Huang)에 의해 도입된 몬테카를로 트리 탐색(MCTS) 방식"Modification of UCT with Patterns in Monte-Carlo Go"을 통해 비약적 발전을 한다. 최초로 몬테카를로 방식(Monte Carlo method)을 사용한 'MOGO' 라는 프로그램이 2008년 알려졌고, 이전까지 있었던 모든 인공지능바둑 프로그램을 몬테 카를로 방식으로 전환하는 선구적 역할을 했다.
• 2015년 ~ 현재 : 하지만 알파고가 등장하면서 다시한번 세대교체를 이루었다. 구글 딥마인드 알파고(AlphaGo)의 인공지능 알고리즘은 기존 몬테카를로 트리 탐색(MCTS) 방식에 컨볼루션 신경망(CNN)과 강화학습을 통한 딥러닝 방식이 적용됐다. 또한, 프로 바둑기사를 상대로 최초로 승리를 따낸 프로그램이라는 타이틀도 획득하였다.

2 상세

체스에서 인공지능이 이미 오래 전에 인간 플레이어들을 압도하기 시작한 것과는 대조적으로 바둑에서의 인공지능은 2010년대 이전까지만 해도 초보적인 단계에 머물러 있었다. 몰판 항목의 스샷에도 나온 것처럼 1980년대 패미컴으로 개발된 인공지능 바둑 엔진에서 괴이한 수를 연발하는 경우가 많았다.

하지만 몬테 카를로 알고리즘을 적용한 몬테 카를로 엔진이 개발되면서 바둑 인공지능에 혁신적인 발전이 이루어졌다. 그러나 몬테 카를로 엔진에도 결점이 있는데 몬테 카를로 알고리즘의 기본 원리가 임의의 수를 이용하여 반복적인 연산을 통해 최적의 결과를 도출해내는 방식이기 때문에 엔진 자체만으론 의미 없는 떡수를 연발할 수밖에 없다. 또한 이전의 인공지능 엔진과는 달리 굉장한 반복 연산을 요하기 때문에 높은 연산능력을 가진 하드웨어를 요구하며 연산 시간도 길다. 이 때문에 하드웨어의 성능에 따라 기력 편차가 심하다. 같은 엔진이라도 서버급 컴퓨터에서 돌리는 것과 가정용 PC에서 돌리는 것과의 차이는 3급 이상의 차이가 날 때도 있다. 이를 보완하기 위해 바둑 프로그램 개발자들은 기보집과 정석집에 대한 데이터에서 수를 검색하도록 하여 연산 시간을 단축하고 의미있는 수를 둘 수 있도록 한다.

의외로 북한이 이 분야에서 주요 선진국 중 하나였다. 바둑 인공지능 대회에서 우승 전력도 다수 가지고 있을 정도이다. 하지만 대규모 병렬 서버자원을 요구하는 신경망 인공지능 시대가 와서 이제 북한이 바둑 인공지능 강하다는 이야기도 옛 이야기가 되었다.

바둑의 인공지능이 체스와는 달리 발전이 느린 것에 대해 여러 의견이 있었다. 체스에 비해 경우의 수가 많기 때문이라는 주장에서부터, 바둑은 동아시아 철학의 결정체기 때문이라는 국뽕스러운 주장, 수치화하기 힘든 부분들(형세판단, 맥)이 존재하기 때문에 힘들다고 보는 견해, 단순히 체스에 비해 바둑 인공지능 개발에 대한 관심과 투자가 부족했기 때문이라는 주장도 있다. 위에서도 말했지만 '그' 북한이 한동안 바둑 연구 최첨단을 달리고 있었을 정도로 바둑 인공지능에 대한 투자는 전 세계적으로 주목 받지 못하고 있었다. 실제로 2010년 중반부터 구글 등 거대 IT 기업들이 바둑 인공지능 연구에 뛰어든 이후부턴 급속도로 기력이 증가하게 된다.

그러나 2010년 중반부터 바둑 인공지능이 발전한 것을 단순히 그때부터 돈을 처바르기 시작했다고 보기에는 그전까지는 돈을 처발라도 성능이 올라갈 것 같지가 않아서 투자가 미미했다고 여기는 관점도 있다. 이에 따르면 이런 바둑 인공지능의 발전의 열쇠는 신기술이라 할 수 있는 딥 러닝이다. 2014년 중후반부터 딥러닝을 이용한 알고리즘으로 이미지 인식/ 음성 인식 등이 비약적으로 정확도가 향상된것 처럼 바둑에서도 딥러닝을 이용해 갑자기 비약적으로 기력이 향상되게 되는데, 이에 페이스북, 구글등의 딥러닝 과학자들이 뛰어 들었다는것을 발표했고, 해당기사 링크해당 연구가 계속되고 있는 토론토 대학과 구글 딥마인드의 논문에는 프로 기사들의 움직임을 55%까지 예측하여 인간 기준으로 아마 6단 정도 수준까지 가능했고, 기존이 GnuGo같은 프로그램과 대결했을때 97%의 승률을 보인다고 한다. 해당논문 이 논문이 2015년 5월에 출간되었고, 실제 논문 작성은 그보다 반년은 먼저 이루어 졌을테니 2016년 1월 기준으로 이미 1년이 넘는 시간이 흘렀다. 그동안 기력이 얼마나 더 향상 되었을지는 아무도 모르는일.

2016년 1월 28일, 주커버그의 페이스북에 그동안의 연구진행 결과가 올라왔다. 꽤나 발전한 듯. 주커버그 페북 같은날 구글 발표에 의하면 구글에서 개발한 인공지능 AlphaGo가 유럽 바둑 챔피언에 3회 오른 중국 출신 프로기사 판후이 2단을 5:0으로 관광보냈다고 한다(...) 해당 내용은 네이처지에 논문 형태로 게재됐다. 각기 다른 역할(수읽기, 우열 분석 등)을 하는 인공 뉴럴 네트워크를 여러개 연결하고 사람과의 대결 및 자가 대결을 통한 학습에 구글 클라우드의 컴퓨팅 파워를 갈아넣은(...) 결과물이라고 한다. 가장 경악스러운 점은 알파고를 학습시키기 위해 사용된 기보의 출처인데, 기보의 확보/ 저작권 문제 등으로 인해 진짜 프로들의 기보를 대상으로 훈련한게 아니라 KGS서버의 수많은 공개 아마추어게임이나 컴퓨터 봇들의 기보, 그리고 알파고가 혼자 백/흑돌을 쥐고 미러매치를 했던 기보들만을 가지고 학습을 했는데도 이정도의 기력이 나왔다는 이야기이다. 2016년 3월에는 이세돌과 승부했다. 상세한 내용은 구글 딥마인드 챌린지 매치 참조. 참고로 여기서는 알파고가 이세돌을 상대로 이겼다.

2.1 바둑의 경우의 수

바둑 경기 진행의 경우의 수는 무한할 수 있지만, 이론적으로 인공지능이 고려해야 되는 바둑의 경우의 수는 유한하다. 컴퓨터 용어를 사용하여 한 줄로 설명하자면, 인공지능이 고려해야 되는 바둑의 경우의 수는 Finite State Machine(FSM; 유한 상태 기계)의 state 수이지, FSM의 가능한 transition의 수가 아니기 때문이다.

이렇게 계산되는 이유는 인공지능은 바둑판의 현재 상태(state) 하나하나를 경우의 수로 계산할 수 있기 때문이다. 바둑판의 격자의 수는 361(=19*19)개이고, 각각의 격자가 가질 수 있는 값은 총 3개이므로 (검정돌, 흰돌, 공백), 바둑의 가능한 경우의 수는 3^(19*19)로 유한한 것. (패 같은 것을 통하여) 각자의 플레이어가 잡아먹은 돌의 갯수가 변할 수 있지만, 이것은 state에 포함되는 하나의 정수로 처리해버리기 때문에 별도의 경우의 수로 판단되지 않는다. 마치 자연수가 무한하지만 하나의 변수로 표현되고 인식되며, 컴퓨터가 무한한 경우의 수의 자연수의 덧셈을 무한한 방식으로 풀지는 않는 것과 비슷하다고 보면 된다. 실질적으로 인공지능이 고려해야 되는 상태(state)의 수는 더 줄어들 수 있는데, 3^19*19는 가능한 상태(state)의 상한값이고, 바둑판은 좌우상하 및 점대칭이며, 대칭적으로 동일한 상태들은 제외할 수 있기 때문.

이론적으로 보자면, 인공지능은 이 3^19*19 (≈10¹⁷²)가지의 서로 다른 state에 대해서만 전략을 마련하면 된다. 즉, 총 3^19*19의 유한한 경우에 대한 알파고의 추천값만 거대한 하드디스크에 저장하고 있으면 알파고와 똑같은 바둑을 둘 수 있다는 이야기.

하지만, 3^19*19 (≈10¹⁷²)은 매우 큰 수이고, 이 많은 수를 다 하드디스크에 캐싱할 수는 없으며, 실제 바둑 인공지능은 각 바둑 경기의 상태(state)마다 최적값을 저장하고 있는 방식이 아닌, 현재 상태(state)로부터의 가능한 바둑 경기 진행(transition sequence 또는 next space의 tree)을 검색 공간(search space)로 설정하고 검색 및 계산하는 것으로 알려져 있다. 위키백과의 바둑 항목에서 언급하는 경우의 수는 이 검색 공간의 경우의 수이다. 다시 말하지만 바둑의 경우의 수는 일단 무한대로 근사해도 된다.

패는 바둑 진행의 경우의 수를 많이 늘려주지만, 이론상 인공지능이 고려해야 되는 경우의 수를 늘려주지는 못한다. 컴퓨터 용어를 사용하자면, 패는 바둑이 FSM 사이의 state를 무한히 돌아다니게 해 줘서 가능한 transition sequence의 갯수를 늘려줄 뿐, state의 수를 늘리지 않기 때문이다. 하지만, 바둑판의 상태(state)를 미리 저장할 수 없고 바둑 경기 진행(transition)을 실시간으로 검색해야 하는 시간 및 현재의 하드 디스크 용량의 한계 때문에, 패가 인공 지능의 시간을 끊임 없이 소모하게 만들 수는 있다.

덧붙이자면, 패와 비슷하게 체스도 두 선수들이 말을 하나도 먹지 않고 말들을 빙빙 돌리며 무한하게 게임을 할 수 있지만, 컴퓨터 입장에서 이러한 행동은 state 사이를 옮겨다니는 transition일 뿐, 새로운 state가 늘어나는 것은 아니다.

그리고 사실 바둑이 3^19*19 의 경우의 수를 가지고 있다고 하여 컴퓨터가 인간을 이기지 못한다는 주장으로까지 이어지는 경우도 있는데, 그 어떤 인간도 3^19*19 을 다 고려하는 경우는 없기 때문에 이런 논리는 신빙성은 없다.

좀 더 현실적으로 접근한 바둑의 경우의 수는 다음과 같다. (19*19)! 이니 3^19*19 모두 무한대의 상상할 수 없는 숫자들인데, 실제 바둑에서는 대세점, 절대점 등의 바둑 내용에 따라 두는 꼭 두어야만 하는 착점들이 있기 때문에 이 정도의 경우의 수가 다 나올 수가 없다. 예를 들면 처음 포석 과정에서 화점 주변이나 천원점 근처도 아니고 세력 형성에도 관계없는 전혀 생뚱맞는 곳에 착수를 하는 경우는 거의 없다고 봐도 되고, 상대방의 특정 돌을 견제하며 공격이나 방어를 할 때도 붙이기, 걸치기, 들여다보기 등 의외로 합리적으로 둘 수 있는 경우의 수는 그때그때 한정돼있다.

보통 프로 레벨의 바둑에서는 첫수에 10여개의 선택 가능한 착점지가 있으며, 그 후 포석이 마무리되는 단계까지 매 수마다 약 10~30여개의 착점지가 존재한다. 이 착점지의 수가 바둑 초중반을 지나면서 점차 줄어드는데 서로가 최선을 바둑을 두었다고 가정하면 보통 200여 수 까지 진행된다. 프로 수준의 바둑이므로 중반 이후에는 매 수마다 평균적으로 3개의 선택지가 있다고 가정하자. 그러면 프로 레벨에서 나올 수 있는 바둑의 경우의 수는 2⁴⁰⁰ ≈ 10¹²⁰ 정도가 된다. 그러나 이 정도 경우의 수만해도 우주 전체의 원자수보다 10⁴⁰ 배 만큼이나 많다! 즉, 바둑은 그냥 인간 두뇌 (그리고 현재 컴퓨터의 컴퓨팅 파워 수준에서도) 에서 보면 무한한 경우의 수를 가진다고 보면 된다. (전 70억 인류가 죽을 때까지 100년 동안 하루에 바둑 100판씩 두어도 판수는 대략 2.5X10¹⁶, 즉 이렇게 해도 똑같은 바둑은 확률적으로 나올 수가 없다)

3 주요 바둑 인공지능 프로그램

• AlphaGo - 아래에 나오는 다른 AI들을 493승 1패로 이겨버리며 AI의 최강자로 등극한 AI 프로그램이다. 2016년 3월 이세돌 9단과 대결한다고 해서 화제가 되고 있다. 그리고 3월 9일(수), 3월 10일(목) 3월 12일(토) 다섯번의 대국 중 세 대국에서 알파고가 승리했다. 3월 13일(일)에 드디어 처음으로 이세돌에게 졌다(!!) 3월15일(화) 마지막 대국에서 알파고가 승리했다. 추정 기력은 프로 五단이었으나, 이 대결로 인해 정상급 프로 기사의 실력을 갖고 있다는 평가도 나오는 상황이다. 결국 한국기원은 알파고를 명예 프로 九단으로 인정하였다.링크 자세한 사항은 알파고 및 구글 딥마인드 챌린지 매치 문서 참조.

• 은별 - 국내에 가장 잘 알려진 바둑 프로그램으로 북한에서 개발되었다. 인공지능 국제 바둑 대회인 UEC 2009 우승자이기도 하다. 국내에서는 은별 2010을 마지막으로 발매를 하지 않고 있으나 일본에서는 '은성위기'라는 이름으로 2015 버전까지 출시하고 있는 중이다.

• ZEN - Zenith Go. 天頂の囲碁 현재 상용 바둑 인공지능 프로그램 중 최강자로 인정받고 있다 . 2009년, 2011년 컴퓨터 올림피아드 우승자. 2012년에 다케미야 마사키 九단(90년대초 우주류를 유행시킨 다케미야 九단)에게 5점, 4점 접바둑으로 각각 11집, 20집 승을 거둔 바가 있다. 안정적인 실리 위주의 기풍으로 수읽기에 탁월하다는 평가를 받는다. 2013년 3월 제1회 전성전(電聖戦)에서 4점 접바둑으로 이시다 요시오 九단에게 불계패했다. ZEN5의 기력은 타이젬 기준으로 7단 정도이다. 아마 6단이라는 평가도 있다.링크 2016년 6월 현재 ZEN6가 최신 버전이다. 기력은 타이젬 기준으로 강8단 ~ 약9단 정도. 2016년 7월, 19A 버전이 공개되고 조혜연 九단과 속기 대국을 7월 27일에 연다.관련기사 젠이 흑으로 두 점을 놓고 대국했고(백에 덤 0.5집 부여), 조혜연을 1.5집 차이로 이겼다. 참고로 대국에 사용한 버전은 19x 버전이라고 한다. 관련기사

• Crazystone(최강바둑) - 은별 다음으로 국내에 잘 알려진 상용 바둑 프로그램이다. 2007, 2008 UEC컵 우승자. 제니스, 은성위기와 함께 3대 인공지능으로 평가받고 있다. 특이하게도 실리 위주인 다른 인공지능과는 달리 세력 위주의 힘바둑을 구사한다. ZEN 항목에서 언급한 제1회 전성전에서 같은 조건으로 이시다 九단에게 3집 승리했다. 아마 6단으로 평가된다. 2016년 크레이지스톤 딥러닝 버전이 출시 되었다. 안드로이드 유료앱으로도 출시되어있으며 힘바둑 인공지능답게 굉장히 공격적인 바둑을 구사한다. 기력이 약한 사람이 최고레벨 인공지능을 상대로 플레이하면 스타크래프트에서 테란에게 시즈탱크 조이기를 당하는 느낌을 느낄정도로 막기에 급급하다.

• The Many Face of Go - 1980녇대부터 DOS용으로 개발된 이후 지금까지도 명맥을 이어고오 있으며, ZEN 이전의 상용 바둑 인공지능 최강자로 인정받았던 프로그램이다. 2008 컴퓨터 올림피아드 우승자. 김명완 八단에게 7점 접바둑에서 승리한 적이 있다.# 가장 인간에 가까운 바둑을 둔다고 평가받았었다.

• Fuego - 오픈 소스 바둑 프로그램 중 최강 인공지능. 9줄 바둑에서 인공지능으로는 최초로 호선으로 프로 기사에게 승리를 거둔 적이 있다. 2010 UEC 컵 우승자. 2011년 이후로 현재까지 업데이트가 이루어지지 않고 있다. PC판은 2014년에 업데이트 되었으나 엔진이 업데이트 된 것인지는 알 수 없다. 아마 2단으로 평가된다.

• Pachi - 오픈 소스 바둑 인공지능 프로그램. Fuego 가 상당 기간 업데이트가 이루어지지 않고 있는 것에 비해 활발한 업데이트로 꾸준한 개선으로 바둑 인공지능계의 신흥 강자로 자리매김하고 있다. 2015년 4월 Pachi 11 버전이 최근 버전. 특이하게도 매 버전마다 일본의 유명 바둑기사들의 이름을 붙이고 있다. 메이저 프로그램에 비해 떨어지는 기력이지만 개선이 매우 빨라 주목할 만하다. 아마 2단으로 평가된다.

• MoGo - 대만과 프랑스 대학의 협동 연구로 만들어진 몬테 카를로 엔진 기반의 바둑 인공지능 프로그램. 개발자 중 일부가 Crazystone의 개발에 참여한 경력이 있기 때문에 상당히 유사한 기풍을 보인다. 2007 컴퓨터 올림피아드 우승자. 2008년 버전3을 이후로 업데이트가 중단되다시피 했기 때문에 현재는 주류에서 도태되었다. 전형적인 인공지능스러운 수를 두기 때문에 정석으로 두면 상당히 골치 아프다. 최근 바둑 인공지능 개발 추세가 사람에 가까운 수를 두도록 개발되는 거에 비하면 그렇다. 아마 2급으로 평가된다.

• GNU Go - 한때 오픈소스 바둑 인공지능의 최강자였다. 다른 바둑 프로그램의 몬테 카를로 엔진의 도입 이후로는 완전히 비주류로 떨어졌지만. 2003년, 2006년 컴퓨터 올림피아드 우승자. 2009년 3.8 버전이후 업데이트가 이루어지고 있지 않다. 몬테 카를로 엔진이 아니기 때문에 기력은 낮지만 가볍고 연산이 적기 때문에 아직도 낮은 기력의 아마추어에게는 많이 쓰이고 있다. 기풍은 실리 위주의 바둑. 전투에 약한 대신 초반 형세 판단이 좋은 편이다. 아마 5급으로 평가된다.

• Aya - 일본인 프로그래머에 의해 개발되고 있는 프리웨어 바둑 프로그램. 윈도우용으로 개발되었다. 꽤 일찍부터 개발된 바둑 인공지능이였지만 GNU Go에 밀려서 빛을 보지 못했었다. 사실상 업데이트가 정지된 GNU Go와는 달리 아직까지도 꾸준한 업데이트가 이루어지고 있다. 그런데 문제는 지속적인 업데이트에도 불구하고 아직도 GNU Go에게 10~20집 차이로 깨진다. 비교적 균형 잡힌 기풍이지만 세력을 더 추구하는 편이다.

• Leela - 유럽의 유명한 체스 프로그램 개발사에서 만든 최초의 몬테 카를로 엔진을 도입한 상용 바둑 프로그램. 초기형 몬테 카를로 엔진이라서 엉뚱한 수를 자주 두는 편이다. 몬테 카를로 엔진 덕에 수읽기는 좋은 편이지만 작은 집을 다투다가 대마를 잡히는 삽질을 많이 하는 경향이 있다. 즉 형세 판단이 정말 안 좋은 인공지능. 몬테 카를로 엔진이 아닌 GNU Go와 자웅을 겨루는 기력이다.

• Steenvreter - Erik van der Werf라는 네덜란드 프로그래머가 개발한 몬테 카를로 기반의 바둑 인공지능 프로그램. 비교적 최근에 개발된 프로그램임에도 쟁쟁한 경쟁자들을 물리치고 2011년 컴퓨터 올림피아드 준우승을 차지했다. 사활에 강하다고 한다.

• 다크포레스트(darkforest) - 구글에 대항마인 페이스북에서도 바둑 프로그램을 만들고 있다. 강한 편이지만 아직 프로기사를 이긴 적은 없다.

• 돌바람 - 국내 누리그림 대표인 임재범씨가 개발한 프로그램. 제작자가 Zen에 자극을 받아서 만들었다고 밝혔다. 중국에서 열린 세계컴퓨터바둑대회에서 Zen을 꺾고 우승을 차지했다. 다만 상용화는 아직 계획에 없다고 한다. 추정기력은 아마 5단. [[[홈페이지]

4 인공지능 프로그램의 폐해

요즘엔 온라인 바둑게임에서 인공지능 프로그램을 이용하여 플레이하는 사람들이 속출하고있다. 바둑 갤러리를 중심으로 급속히인공지능 프로그램이 유포 되었으며 컴퓨터에 기본으로 깔려있는 바둑게임을 최고 난이도로 맞추고 상대의 놓는 위치를 내가 따라하면 알아서 이겨준다. 이걸로 하루만에 고랭크찍는 유저도 나오는중이다. 하지만 그래봐야 온라인 바둑 중저단 수준이다. 온라인 바둑 5단 이상이 천지라 과연 고랭크라고 할 수 있을지 의문... 하지만 이건 기존 몬테 카를로 기반의 알고리즘을 사용할 떄 그렇다는 거고 상술한 알파고와 같은 인공신경망 기반의 알고리즘이 공개될 경우...더 이상의 자세한 설명은 생략한다. 물론 알파고급은 아직까지 일반 PC로 돌릴 수 있는 수준이 아니기에 먼 이야기이다. 허나, 오픈소스로 알파고와 비슷한 알고리즘을 PC에서 구현해보려는 움직임이 있긴 하다.

이미 AI가 인간을 뛰어넘은 지 한참 된 체스계에서는 예전부터 쭉 있어왔던 문제로, 세계 체스 챔피언보다 AI의 Elo 레이팅이 몇백점 가량 앞설 정도로 AI가 강해진데다 그런 프로그램을 슈퍼컴퓨터 수준의 하드웨어가 아닌 일반 가정의 PC로도 구현이 가능할 정도까지 온 상황에서 굉장히 골머리를 앓아왔다. 결국 중요한 건 이러한 변칙적 플레이를 배제할 수 있는 플레이어의 양심이다.

오토를 사용하는 고랩들로 MMORPG들이 몸살을 앓고 있는 것처럼, 봇 프로그램이 바둑까지 번져 버린다면, 사람들이 바둑에 급격히 흥미를 잃게 될 수도 있다.

이 문서의 내용 중 전체 또는 일부는 바둑문서에서 가져왔습니다.</div></div>