편집자 주. 지난 7월 26일, 인터넷 커뮤니티 디시인사이드 하스스톤 갤러리(이하 돌갤)에 “고2때 하스스톤으로 진화론 연구했던 썰.evolution“이라는 게시물이 올라왔다. 이 게시물은 한 고등학생의 자유연구 과제를 다룬 것으로, “카드게임에서 인공지능이 스스로 덱을 짜는 단계까지 발전할 수 있을까?”라는 문제의식에서 시작되었다고 한다.
글쓴이 ‘집부릉’이 설명한 연구의 핵심은 덱을 생명체로, 카드를 유전자로 대입해 유전 알고리즘을 응용하는 것이다. 1세대 덱 10개를 무작위로 만들고, 인공지능 상대와 20회 게임 후 승패를 기록한다. 이후 승률이 가장 높았던 4개 덱의 카드를 설정한 함수에 따라 자녀 덱으로 재구성(교배)한다. 이렇게 5세대까지 반복하니 승률이 예상보다 더 가파르게 상승했다는 것이 글쓴이의 설명이다.
이 연구는 “교내 과학 자유연구 발표대회”에 출품된 것으로, 아쉽게도 순위권에는 들지 못했다고 한다. 또한 “(선생님들께서) 이해하기 힘들어 하거나 뾰로통했다”, “한 분은 ‘게임’이라는 사실에 큰 적의를 보였다”며 아쉬움을 토로하기도 했다. 이와 관련해 여러 인터넷 커뮤니티에서는 한국 교육 제도에 대한 토로와 비판이 이어지기도 했다.
1년 동안 묻혀 있던 연구가 빛을 발한 것은 연구 내용이 돌갤에 올라오면서부터였다. 하스스톤의 제작사인 블리자드를 비롯해 여러 게임 회사들이 연구에 큰 관심을 보였으며, 특히 블리자드는 글쓴이 집부릉을 직접 자사로 초청까지 한 것으로 알려졌다.
전문가들의 평가는 구체적인 내용과 연구 의의에 있어 다소 부정적인 부분은 있었지만, “전문적인 훈련도 받지 않은 고등학생이 스스로 이 정도 연구를 설계하고 검증까지 해낸 것 자체만으로 굉장히 훌륭하고 대단하다”는 부분에서는 이견이 없었다.
ㅍㅍㅅㅅ는 저자의 동의를 얻어 논문 전문을 게재한다.
자연선택의 원리를 이용한 전략 카드게임
인공지능 향상 가능성에 대한 연구
초 록
한정된 게임판과 정해진 덱(카드뭉치)을 사용하는 여러 보드게임들과는 달리, 수많은 카드들 중 원하는 카드들을 수집하여 자신만의 덱을 만들어 상대와 겨루는“전략 카드게임”에서는 플레이어들에게는 준비해온 덱을 플레이하면서 매 순간 상대에게 응수하는 능력뿐 아니라, 상대하게 될 것이라 예상되는 상대의 덱에게 승리하기 쉽도록 끊임없이 자신의 덱의 카드구성을 수정 및 보완하는 능력 또한 요구된다.
많은 보드게임들에서 인공지능들이 숙련자들을 능가하는 높은 성능을 지니는데 비해, 수백~수천 종 이상의 카드들과 그 사이의 상호관계를 컴퓨터에 입력하고 연산시키기는 너무 복잡하기 때문에, 전략 카드게임 인공지능들은 주어진 덱을 가지고 플레이하는 기능은 있어도, 스스로 덱을 수정하지는 못한다는 한계가 항상 존재해왔다.
본 연구는 이러한 한계를 극복하기 위해서 생물계의 자연선택 원리를 활용할 수 있을 것이라는 가설을 세우고, 생물계에서 자연선택이 일어나도록 유도하는 환경을 전략 카드게임의 덱에 모방하여 조성해 줌으로써, 점진적으로 상대에 맞추어 덱을 변화시켜 승률을 높이는 활동에 대한 인공적인 메커니즘을 구현할 수 있음을 확인하였다.
I. 서론
전략 카드게임
보드게임이란 통상적으로 게임판(보드)을 두고 그 위에 몇 개의 말을 올려 정해진 규칙에 따라 진행하거나, 포커나 화투처럼 정해진 숫자의 카드를 통해 일정한 규칙에 따라 게임을 진행하는 종류의 게임을 말한다. 최근의 보드게임은 그 종류가 매우 다양해져서 1만여 종에 이르고 있으며, 인터넷의 발달과 더불어 플레이어들이 직접 만나지 않아도 온라인으로 즐길 수 있는 보드게임들도 인기를 끌고 있다.
이러한 보드게임들 중엔 특정한 테마나 규칙을 바탕으로 디자인 된 수집요소가 존재하는 많은 카드들을 사용하는 카드게임 장르로써 TCG(Trading Card Game)와 그와 유사한 CCG(Collectable Card Game)가 존재하며, 사용자간 카드거래가 가능한 것을 TCG, 불가능한 것을 CCG라고 부른다.
이들 중 대부분은 게임회사에서 발매한 수백~수만 장의 카드들 중 수십 장 내외의 카드들을 수집하여 자신만의 덱(카드뭉치)를 만들고, 사용자 둘이 마주하여 특정한 규칙에 따라 자신의 카드를 내고 순서를 주고받으며 특정한 승리 조건을 먼저 만족시키는 방식으로 플레이하게 되는데, 여러 턴을 거치면서 서로의 수를 예측하는 등의 전략적인 플레이가 요구되므로 이러한 게임들을 “전략 카드게임”이라고 통칭한다.
64칸의 한정된 게임판과 16개의 말을 사용하는 체스나 50장 내외의 정해진 덱(카드뭉치)을 사용하는 화투나 트럼프 등의 다른 보드게임들과는 달리, 전략 카드게임에서는 게임회사에서 발매한 수천 장 이상의 다양한 카드들 중에서 원하는 수십여 장만을 선별하여 덱을 자신만의 만들기 때문에, 플레이어들에게는 준비해온 덱을 플레이하면서 매 순간 상대에게 응수하는 능력뿐 아니라, 상대하게 될 것이라 예상되는 상대의 덱에게 승리하기 쉽도록 끊임없이 자신의 덱의 카드구성을 수정 및 보완하는 능력 또한 요구된다.
전략 카드게임 인공지능의 근본적 한계
여러 학자들과 게임회사들은 수학연구, 플레이어들을 위한 편한 연습상대, 게임규칙 검토, 후속 게임의 연구개발 등의 다양한 수요로 인해 인간 플레이어를 대신하여 보드게임을 플레이 할 수 있는 인공지능들을 개발해 왔으며, 정교하게 만들어진 인공지능은 숙련된 실제 플레이어들을 상대로 승리를 거두기도 한다.
게리 카스파로프에게서 승리를 거두는 모습
전략 카드게임 장르에서도 다양한 인공지능들이 개발되어 왔으나, 수천 장 이상의 전체 카드들과 그 사이의 복잡한 상호작용들을 모두 입력하여 컴퓨터 알고리즘으로 표현하는 것이 매우 힘들기 때문에, 현재까지 개발된 모든 전략 카드게임 인공지능들은 주어진 덱을 사용해 플레이할 수는 있지만, 스스로 덱을 수정하는 능력은 없다는 근본적인 한계를 가지고 있다.
다시 말해 실제 플레이어들은 한 상대에게 패하면 그 상대의 덱을 공략하기 쉽도록 자신의 덱을 재구성하여 다시 도전할 수 있지만, 현재까지 개발된 인공지능들은 아직 그런 기능이 존재하지 않는다.
자연선택
자연선택이란 동종의 생물 개체 사이에 일어나는 생존경쟁에서 환경에 적응한 개체들이 생존하여 자손을 남기게 되면서 시간이 지날수록 전체 개체군의 환경 적응도가 높아지는 것이다. 생물체는 낳은 자손은 부모와 유사하면서도 어느 정도의 다양성을 가지게 되는데, 이러한 다양한 유전형질들 중 생존에 유리한 형질들을 가지고 있던 개체들은 그렇지 못한 개체들보다 더 많이 살아남아 번식하고, 시간이 지나면 개체군에 생존에 유리한 그러한 유전자가 개체군 전체에 퍼지게 된다.
자연선택이 일어나기 위해서는 각각의 개체들이 자신과 닮은 자손을 낳으면서도 어느 정도의 다양성이 존재해야한다. 이러한 다양성을 유지되는 기제로는 유성생식에 의한 것과 돌연변이에 의한 것이 있다.
유성생식을 하는 생물들은 짝을 이룬 생물의 유전형질과 자신의 유전형질을 절반씩 뒤섞어 후손의 유전형질을 결정한다. 그렇게 태어난 후손들 중 일부는 각 부모에게서 물려받은 절반의 유전형질들 중에 생존에 유리한 유전자들을 많이 유전된 개체도 있을 것이고, 생존에 불리한 형질들이 많이 들어있는 절반을 유전 받은 개체도 있을 것이다. 전자가 생존경쟁에서 후자를 누르면서 세대가 거듭될수록 전체 개체군에서 생존에 유리한 유전형질들을 가지고 있는 개체들이 점진적으로 늘어난다.
또한 모종의 이유로 자녀 개체의 유전자의 특정한 곳에서 돌연변이가 일어나 부모 세대에서는 찾아볼 수 없었던 유전형질이 나타나기도 하는데, 이 유전형질이 생존에 도움이 될 경우 전체 개체군에 퍼지고, 그 반대일 경우 도태될 가능성이 커지게 되면서 나타난다.
자연선택에서 이러한 개체군의 적응도 증가는 어떤 유전형질이 생존에 유리하고 어떤 것이 불리한지에 대한 구체적인 정보를 알고 있는 행위자의 작위적인 개입이 필요 없는, 맹목적이고 자연적인 현상이라는 것이 특징이다.
연구 가설
스스로 덱을 짜고 수정하는 능력을 가진 전략 카드게임 인공지능의 개발이 부진한 이유가 지나치게 많은 카드들과 그 사이의 복잡한 상호관계들을 컴퓨터 내에 구현하기가 어렵기 때문이라면, 각각의 카드들의 정보를 입력해줄 필요가 없는 귀납적인 방법을 생각해 볼 수 있고, 그 방법으로는 자연선택의 원리가 활용가치가 높을 것이다.
따라서 전략 카드게임의 덱을 하나의 생명체에 대응시켜, 서로 다른 여러 덱들 중 각각의 덱을 계속 플레이하여 승률이 높은 덱들과 그와 유사한 덱들만 다음 세대로 선별하여 남기고 승률이 좋지 않았던 덱들은 제거하는 작업을 통해 생물계를 모방하여 자연선택이 일어날 수 있는 환경을 조성해주면, 세대가 거듭될수록 덱들의 평균승률이 증가할 것이고, 인공적으로 승률이 낮은 덱을 승률이 높은 덱으로 수정하도록 하는 기능을 구현할 수 있을 것이다.
II. 연구 방법
하스스톤
연구에 활용할 전략 카드게임은“하스스톤”이다. 하스스톤은 PC와 iPad 플랫폼을 통해 플레이 할 수 있는 비교적 간단한 규칙과 직관적인 게임성이 특징인 온라인 전략 카드게임으로, 전 세계 2000만 명이상의 플레이어들이 회원으로 등록되어있는 같은 장르에서 가장 인기 있는 게임 중 하나이다.
하스스톤의 대략적인 플레이 규칙은 다음과 같다.
1. 각 플레이어는 30의 생명력을 가지고 있고, 생명력이 0이하로 떨어지면 패배한다.
2. 각 플레이어는 미리 30장의 카드로 이루어진 덱을 준비해야하며, 같은 카드는 세장 이상 넣을 수 없다.
3. 동전을 던져 선공/후공을 정하여 번갈아가며 턴을 가지며, 모든 행동은 자신의 턴에만 할 수 있다.
4. 처음에는 세장의 카드를 뽑으며, 후공 플레이어는 한 장을 더 뽑는다. 이후 자신의 턴이 시작될 때마다 카드를 한 장씩 뽑는다.
5. 자신의 턴이 시작될 때마다 “마나수정”을 하나씩 얻게 되며, 최대 10개까지 보유 가능하다.
6. 카드는 자신의 턴에 몇 장이든 낼 수 있으나, 각각의 카드들은 음수가 아닌 “마나비용”을 가지고 있으며, 한턴에 내는 카드들의 마나비용의 합은 그 턴 자신의 마나수정 수를 넘을 수 없다.
7. 카드는 주문과 하수인 두 종류가 있으며, 주문카드를 내면 그 카드에 쓰여 있는 효과를 발동시키고, 하수인 카드를 내면 그 하수인을 아군 전장에 내보낸다.
8. 하수인은 공격력과 생명력을 가지고 있으며, 생명력이 0이하가 되면 파괴된다.
9. 하수인은 전장에 나오면 다음 자신의 턴부터 한 턴에 한 번씩만 공격을 할 수 있으며, 공격한 대상의 생명력에 자신의 공격력만큼 피해를 주고, 자신도 공격한 대상의 공격력만큼 생명력에 피해를 입는다. (2.4)
현재까지 하스스톤에는 총 장의 카드가 존재하며, 실험에서는 “마법사”직업이 플레이할 수 있는 기본카드와 일반카드로만 98장만을 사용할 것이다.
하스스톤 인공지능 프로그램 ‘HearthCrawler’
하스스톤은 각 플레이어들에게 9개의 덱 보관함을 제공한다. 플레이어들은 자신이 수집한 카드들 중 같은 카드가 두 장을 넘지 않도록 30장을 선택하여 덱을 만들고, 보관함중 하나에 보관한 뒤, 상대를 만나면 그 중 하나를 선택하여 플레이하게 된다. 현재까지 개발된 모든 하스스톤 인공지능들은 상술한 바와 같이 스스로 덱을 수정, 보완하는 능력이 없이 “제공해준 덱을 플레이하는 능력”만을 갖추고 있으며, 회사 외에서 개발된 다른 인공지능들도 마찬가지이다. 그 중“HearthCrawler”는 하스스톤과 연동시키고 자신이 보관한 덱을 선택하면 그 덱을 사용해 대신 게임을 플레이 해주는 인공지능 프로그램이다. 연구과정에서 플레이어의 실수나 덱 운용능력 차이로 인한 편차가 생기는 것을 방지하기 위하여, 모든 게임은 HearthCrawler(버전28.0823)를 통해서 플레이 할 것이다.
자연선택이 발현될 환경을 조성하기 위한 생물계 모방
- 1부터 7까지의 마나비용 중 하나를 무작위로 선택하고, 그 마나비용을 가지는 카드들 중에서 하나를 무작위로 선택하여 덱에 추가하고, 같은 카드가 세 번 선택되면 다시 선택하는 방법으로 “Microsoft Excel”프로그램을 통해 열개의 무작위 덱을 만들고, “제 1세대”라고 칭한다.
- 모든 카드에 백의자리가 그 카드의 마나비용으로 정해진 세 자리 수를 번호로 단다. 덱은 항상 카드번호에 따라 오름차순으로 정렬해놓으며, 이후 모든 과정에서 만들어진 덱들은 그 카드구성을 번호를 이용하여 기록한다.
- 각각의 덱에 번호를 붙이고, 다섯 개는 게임 계정A에, 남은 다섯 개는 게임 계정B에 저장한다. PC1에서 계정A로 로그인하고, PC2에서 계정B로 로그인하여 HearthCrawler를 사용해 각각의 덱을 게임프로그램에서 제공하는“전문가 마법사 인공지능”을 상대로 20번씩 플레이하고 승수와 패수를 기록한다.
- 가장 승률이 높았던 네 개의 덱은 그대로“제 2세대”에 포함시키고 덱 번호를 1,2,3,4로 재설정한다. (승률이 같은 덱이 있어 넷 이상이 될 경우, 그 중에서 무작위로 선택하여 넷이 되도록 한다)
- 네 개의 덱을 두 개씩 짝지어 나열하고, 서로 같은 행에 있는 두 카드 중 무작위로 하나씩만 선택한다. 선택된 카드들로“자손 덱”을 구성하고, 5번부터 번호를 붙인다. 모든 덱이 다른 덱들과 한 번씩 자손 덱을 만들 때까지 반복하여 여섯 개를 만든다. – 유성생식 모방
- 만들어진 자손 덱 여섯 개 중 반수인 셋을 무작위로 선택하여, 그 덱의 카드들 중 셋을 무작위로 선택하고, 무작위 카드 세장으로 바꾸어 놓는다. – 돌연변이 모방
- 만들어진 새로운 세대에 대해서 위의 과정을 반복한다.
III. 결과
- 2014년 11월 14일부터 24일까지 간헐적으로 실험실시, 약 70시간 소요.
카드 번호
덱 구성
세대별 덱 승률
세대별 덱 승률 그래프
IV. 고찰
세대가 거듭되면서 평균승률은 48% – 61.5% – 64% – 68% – 71% 다섯 세대동안 23% 증가하였다. 최다승 덱의 승률은 70% 에서 85%로 증가하였으며, 최소승 덱의 승률은 20%에서 45%로 증가하였다. 평균승률은 모든 구간에서 증가하였으며, 한 세대의 게임 횟수가 200회였던 본 연구가 다룰 수 있었던 범위 내에서는, II.에서 설정해주었던 자연선택 유발 환경이 실험에서 확인된 수준의 자연선택을 일으키는데 충분한 효과가 있었다고 생각된다.
본 연구는 하스스톤의 9가지 직업들 중 하나인“마법사”가 HearthCrawler R28 프로그램을 이용하여 기본카드와 일반카드 98종을 가지고 짠 덱으로,“전문가 마법사 인공지능”을 상대로 거둔 전적을 바탕으로 진행되었으므로, 다른 상대, 다른 가용 카드 종류, 다른 인공지능 프로그램, 다른 직업을 상대로 같은 실험을 진행할 경우에는 유사한 긍정적인 결과를 얻기 위해서 덱당 20회보다 더 많은 플레이 횟수가 요구되거나, 더 많은 세대를 만들어야 하거나, 다른 결과가 나올 수도 있으나, 본 연구에서 설정한 상황에서는 충분한 5세대라는 짧은 기간 동안 세대의 평균 패배확률이 절반가까이 떨어진 것으로 보아 연구 가설의 타당성이 검증되었다고 생각된다.
V. 결론 및 활용방안
연구에서 확인된 범위 내에서는 전략 카드게임의 덱을 하나의 생명체에, 카드를 유전형질에 대응시켜, 생물계를 모방하여 자연선택이 일어날 수 있는 환경을 조성해 줄 수 있었으며, 세대가 거듭될수록 덱들의 평균승률이 크게 증가했고, 인공지능이 카드들의 상호작용에 대한 정보가 전혀 없이도 스스로 승률이 낮은 덱을 승률이 높아지도록 수정하는 기능을 해낼 수 있음을 확인하였다.
인공지능의 또 다른 장점은 사람과는 달리 지치거나 지루해하지 않는다는 것이다. 이를 활용해 앞으로 본 연구에서 제시한 메커니즘을 더 개선하고 자동화하여, 두 대가 아니라 수백 대의 컴퓨터가 쉬지 않고 전적정보를 수집한다면, 본 연구보다 더 넓은 범위에서 더 똑똑한 인공지능을 개발하여 전략 카드게임 플레이어들의 실력향상과 다양한 콘텐츠 이용에 도움을 줄 수 있을 것이고, 진화생물학 연구나 자연선택에 대한 교육용으로도 도움이 될 수 있을 것으로 기대된다.
Ⅶ. 과제 연구 활동 중 느낀 점
게임을 주제로 한 연구라서 비교적 즐겁게 진행할 수 있을 줄 알았으나, 많은 데이터를 정확히 기록하고 처리하는 작업을 한 시간에 한번 꼴로 약 열흘을 지속적으로 해야 하니, 여느 주제들보다 더욱 힘이 든다는 것을 알 수 있었다. 오히려 계속 게임 계정으로 프로그램을 돌리고 있어야하기 때문에 원하는 시간에 게임을 즐길 수 없어지는 일이 많았다.
