관심있는 내용을 정리해봤는데 이걸 공유하고 싶어서 인벤에 처음 글을 써봄. 이 곳에 적는게 맞는지 이렇게 쓰는게 맞는지는 모르겠는 상황이니 문제가 있다면 댓글로 적어주시면 감사하겠음. 


하스스톤은 과연 운빨 좆망겜일까? 실력 갓흥겜일까? 나는 하스스톤이 실력 갓흥겜이라고 생각함. 전설을 찍고 랭크를 올리면서 그 생각이 강해졌음. 그러다 이런 생각이 문득 드는 거임. 바둑의 신은 알파고인거 같은데 하스스톤에도 신이 있지않을까? 알파고도 있는데 돌파고가 없을 이유는 뭘까?

공돌이인 나는 돌파고를 만들면 재밌겠다고 생각했고, 사전연구를 위해 자료들을 찾기 시작했음. 그리고, 놀랍게도 이미 하스스톤 AI에 관한 논문들이 있다는것을 알게됐음. 이 글은 그 자료들을 보고 공유하기 위해 작성함. 문체나 내용이 심히 공돌이스럽고, 논문형식을 따를 것이라 지루할 수도 있겠지만 양해 부탁함. 내가 공돌이라 이런 글 밖에 못 씀. 그래도 최대한 재미있게 설명할 수 있게 노력해보겠음. 뒤에 세 줄 요약 있으니까 바쁘며 그거 보고. 영어 잘하는 친구들은 뒤에 레퍼로 단 논문 원문 보는걸 추천함.

0) 글에 앞서 주의할 점

나는 공대생이긴 하지만 분야가 달라서 전산관련 공부라고는 독학밖에 안해봄. 때문에 전문용어나 깊이가 부족할 수 있음. 때문에 이 글은 알고리즘에 대한 자세한 내용보다는 이런게 있다~정도만 설명할거임. 더 좋은 설명이 있다 싶으면 댓글에다가 의견 남겨주셈.

1) 하스스톤이 봇을 만들기 매력적인 이유

알파고가 이미 바둑을 정복했는데 하스스톤은 바둑에 비해 ㅈ밥아님? 이라고 생각할 수 있지만 하스스톤은 아래의 이유들 때문에 바둑보다 더 어려움.

- 카드의 종류가 다양하고 각 카드들이 가지는 효과가 다르며, 운적 요소가 포함되어 있음

- 플레이어는 상대의 패와 다음 턴에 뽑을 카드를 모름

- 플레이어는 매 턴 다양한 행동을 취할 수 있으며 그 행동의 순서가 승리에 큰 영향을 끼친다. (중요)

때문에 하스스톤은 운빨ㅈ망겜이면서 동시에 실력갓흥겜이기도 함. 이런 운빨을 통제하면서 봇이 스스로의 실력을 기를 수 있는지는 여전히 도전적이고 공돌이들에게 흥미로운 주제일 수 밖에 없음.


<하스스톤이 실력갓흥겜이라는 증거>

2) 봇은 여관 주인이랑 대결하면서 학습하는거임?

하스스톤에서 공식적으로 시뮬레이션을 제공하지는 않음. 그렇다고 게임에 들어가서 여관주인이랑 10000판씩 하고 있으려면 시간이 되게 오래걸리겠지? 그래서 HearthSim 프로젝트가 있음. 이 프로젝트는 하스스톤 AI를 만들기 위해 만들어진 시뮬레이터임.(https://hearthsim.info/) 참고로, 이 프로젝트를 하면서 하스스톤 디버깅 툴을 분석하다가 파생되어 나온 프로젝트가 우리가 알고 있는 Hearthstone Deck Tracker와 Hsreplay.net임. 이 외에도 Metastone이라는 오픈소스 하스스톤 AI 시뮬레이터가 있음. 이후 설명할 논문은 이 Metastone을 이용해서 실험함.


<이젠 모르는 돌린이가 없는 하스스톤 덱 트래커>

하스스톤 봇은 크게 두가지로 분류할 수 있음.

- 덱은 이미 주어지고, 그 덱을 좋게 플레이하는 AI (흔히 아는 오토)

- 메타에 따라 좋은 덱을 짜는 AI (덱 빌딩 AI)

이 글에서는 덱을 짜는 AI에 대해 먼저 다뤄보려 함. 내가 여기 더 관심이 있기 때문임. 사실 덱을 짜는 AI를 이해하기 위해서는 오토에 대한 이해도 필요하지만 알게 머임. 대충 오토 같은 프로그램이 있다고 생각하고 밑에 글을 보셈. 오토에 대해서는 2부가 있다면 거기서 자세히 다룰거임.

3) 그럼 덱 메이킹 AI는 어떻게 만듬?

덱 메이킹 AI에 대한 논문은 지금까지 2개를 봤음. 하나는 2017년에 출판된 ‘Evolutionary deckbuilding in Hearthstone’, 다른 하나는 2018년 8월에 출판된 ‘Automated playtesting in collectible card games using evolutionary algorithms : A case study in hearthstone’. 두 논문 모두 진화 알고리즘(evolutionary algorithm)을 사용하였음. 진화 알고리즘은 우리가 이미 아는 진화를 알고리즘으로 옮겨놓은 거임. 여러 개의 봇을 만들어서 테스트를 해보고 좋은 놈들은 살리고 나쁜 놈들은 죽이고, 중간중간에 일부러 돌연변이도 만들고, 봇들끼리 교배도 시키면서 세대를 거듭해 나가면 좋은 봇만 살아남겠지?라고 생각하는거임. 영상으로 보면 감이 확실히 올거임. 진화 알고리즘은 이미 알고 있는 정보를 이용하는 알고리즘들에 비해서 사전 정보가 필요 없기 때문에 사람(전문가)이 찾기 힘든 문제에 대한 해답을 찾을 수 있다는 것이 장점임.


<진화 알고리즘으로 모델 걷게 만들기. 영상도 재밌음>

https://www.youtube.com/watch?v=pgaEE27nsQw


---------------------------------------------------

(자세한 알고리즘 얘기, 존나 진지함, 스킵해도 무방)

2018년의 논문이 가장 최신이기도 하고, 가장 진보된 것 같아서 이 논문을 기준으로 알고리즘을 설명함.


<알고리즘의 pseudo 코드>

- 진화 알고리즘에서는 무엇이 최선인가를 알기 위해서 ‘fitness function’을 이용함. 이 function이 최대가 되는 방향으로 진화를 하게 되는 거지. 하스스톤 덱 메이킹 AI에서는 현재 메타에 가장 좋은 덱을 만들게 하기 위해서, 총 세 개의 개념을 순서대로 적용함. 1) 편의상 덱을 모든 카드를 이용해 짤 수 있게 해두었는데, 실제 하스스톤은 전설은 한장만 들어가고, 직업 카드 개념이 있기 때문에 이러한 규칙을 어긋난 덱은 점수를 0점으로 만듬. 2) 각 상대마다 16번의 경기를 해 승률이 최대가 되도록 함. 3) 한 덱한테만 높은 승률을 기록하는게 좋은 덱은 아니라고 생각함. 때문에 모든 덱을 상대로 골고루 좋은 승률을 가지는지 판단하기 위해 승률의 표준 편차가 최소가 되도록 함.

- 여기서 순서대로 적용했다고 하는건 덱들 끼리 비교할 때 1번 개념의 점수를 보고 비교해서 같은 점수를 가지고 있으면 2번 개념의 점수를 비교하는 식으로 했다는 걸 뜻함.

- 좀 더 사람과 유사한 덱 메이킹 알고리즘을 만들기 위해 ‘Smart mutation’이라는 operator를 도입함. 이 operater는 마나 커브를 유지하는 방향으로 돌연변이를 발생시키는 것임. 예를 들어 빅 드루이드 덱을 좋다고 판단해서 덱을 짜는데 이세라를 넣은 버전의 승률이 낮다고 대신 요정용을 넣는다던지 하는 짓을 줄이기 위함임.

- 근데 결국 이 덱을 플레이할 AI가 필요하지 않겠음? 때문에 이 논문에서는 총 4가지 타입의 AI를 준비함. 1) Play Random Behavior : 매 턴마다 랜덤하게 플레이하는 AI, 2) Greedy Optimize Move : 매 행동 중 가장 쎈 플레이를 하는 AI, 3) Greedy Optimize Turn : 매 턴 마다 눈에 보이는 모든 가능성 중에서 가장 쎈 플레이를 하는 AI (우리가 흔히 아는 오토), 4) Flat MonteCarlo Tree : 여러 개의 랜덤한 플레이를 미리 계산해보고 그 중 가장 높은 승률을 보이는 플레이를 하는 AI

--------------------------------------------------

이 연구에서 저격하고자 하는 메타는 야생을 가기 전 메타임. 논문 연구 시작하던 시기가 옛날이라 어쩔 수 없나봄. 포함된 확장팩은 낙스라마스, 검바산, 고놈, 대마상까지 해서 694개의 카드로 구성됨. 이 당시 메타는 템포스톰을 참고했음.


<하스스톤 시즌 18 메타표 및 덱 리스트>

한 직업에 대해 계산을 하는데만 30일가까이 걸렸다고 하네 ㄷㄷ 어쨌든 이런 과정을 거쳐서 덱 메이킹을 하는 AI를 만들게 됨!


<각 직업에 대해 각 덱의 승률>

만들어진 AI가 만든 덱의 승률을 보면 확실히 AI가 만든 덱(w or w/o smart mutation)이 사람이 만든 덱(human)보다 더 높은 승률을 기록하는걸 볼 수 있음! 와 그럼 이제 똥덱 실험실은 다 없어지고 이 AI를 통해 만들어진 갓덱들만 남게 되는건가? 한번 살펴보자구~

4) 이제 덱 메이킹 AI가 만든 덱을 소개함.

각 직업에서 얻은 덱의 마나커브는 아래와 같음.


그리고 대망의 덱 리스트는 먼저 노루부터 보자.

왼쪽이 AI가 짠 덱이고, 오른쪽이 당시 메타에 사용되던 각 직업의 1티어 덱리스트야.(템포스톰참고)

너네 보기 쉬우라고 하스스톤탑덱 들어가서 덱 하나하나 짜서 가져왔다.


윽… 똥냄새남. 생각보단 실망스러운 결과임. 오리지널의 향수가 느껴지기도 하고 투기장덱같아 보이기도 함. 혹시 이걸 직접 써보고 싶어하는 사람이 있을것 같아서 덱 코드를 한땀한땀 만들어왔으니 야생에 써보던지.


Druid

AAEBAZICEP4BjRCeAcIO1QH3A8QG1xOxEeYF3BW+D9kTVosI0AIHmgjoFdkHgRCeB0DREQA=

Hunter

AAEBAR8OlwiWBvoFnBDFCN4FzhSkAo0IigPREdoG0AKeEAjtBogFlBSxCLUDqALTEf4PAA==

Mage

AAEBAf0EFrQEkgWVA7wIlgaWBbEI5gTXE9wP5BPyBcYE7BG+D9sKjQSABawE0ALsB8UVBIIWhw+7ApMQAA==

paladin

AAEBAZ8FEPUFRoIQwg7rD+UTjxCCBZUQnRWbEKS2AoUI0RGABcUEB5oHthPqD+0PrwfcA88GAA==

priest

AAEBAa0GDJcC5QTJE9gBnBDzBdcTgQK5BpkC0AKeEAmND8IO+gWhBLoT3gWPD8kG1QoA

rogue

AAEBAaIHEIwCuwOeAYoHmgKUD5cQ+Q6XBoIFWoIS3w+lA5AHpAcHtAHOFYgH3wLNA/4PngUA

shaman

AAEBAaoIDpoH+QOeAYUQ1g+NA+AG4AS1FCL1D+cRrwSeEAirAsIOlBSxCO4B9QSCBbcUAA==

worlock

AAEBAf0GDr8BrRDnE9AHpwjxD5cGghLAFd0PrATMCMgF9gIIxAjiB+IM2AGUFPwQkxDBDwA=

warrior

AAEBAQcQuwOSBfwEgRDvByWRA54HkBTuBqQGkBDwA80T5Q+5DQfyAZYG1AiXBhywAr4PAA==


그 외 이 덱들을 플레이했을 때 소요된 마나, 턴 수, 처치한 하수인, 주문 등에 대한 통계도 있는데 이건 레퍼런스 논문 찾아가서 보면 댐.

 

5) 저자(10등급)들의 덱에 대한 평가

- 따로 조건을 주지 않았는데도 AI가 두장씩 카드를 넣는게 보임. 좋은 카드는 많이 쓸수록 좋고 덱의 안정성을 높혀주니까 그런걸로 보임.

- 검제작의 대가나, 모병관, 아이디스 다크베인처럼 살려두면 이득보는 카드들을 다수 채용함. 그 이유는 greedy AI가 잠재적인 위협을 평가하지 못해 이런 카드들을 굳이 제거하지 않고 명치로 많이 가기 때문으로 보임. 그래서 이 카드들을 쓰면 승률이 좋아지는 거지.

- 8개의 덱 중 3개에서 박사붐을 채용함. 당시 박사붐은 사기였으니 당연함.

- 라그나로스와 실바나스 또한 2개의 덱에서 볼 수 있음. 이 또한 좋은 카드이니 놀랍지 않음.

- 아케나이트와 진은검이 전사와 성기사 덱에 포함되었는데 이 카드들은 게임에서 가장 이펙트 있는 카드들이였다.(??)

- 게돈이 되게 많이 사용되었는데, 짜여진 덱들이 어그로성 덱들이라 필드 클리어에 용이해서 그런 것 같음. 또한, AI가 게돈의 능력을 잘 이해하지 못해서 필드위의 게돈을 잘 정리하지 않는 경우도 많았다고 함.

 

7) 내가 생각하는 덱 메이킹 AI의 한계

- 결과가 너무 실망스러움. 만들어진 덱이 쎄보이지도 않고, 실제로 플레이해봤을때도 카드 뭉치에 불과하다고 생각했음. 왜 이런 결과가 나왔는지, 그리고 어떻게 하면 이걸 더 개선해서 좋은 AI를 만들 수 있을지 생각해봄.

- 일단, 저자들이 돌겜을 잘한다고 생각하지는 않음. 17년 논문을 보면 저자 중 가장 높은 등급이 10등급이라 그 사람이 플레이하면서 AI를 테스트했다고 함.(여기서 신뢰도 확 떨어짐) 그렇기 때문에 놓친 부분들이 보임.

- Smart  mutation 이라는 개념을 도입했는데 결국 마나 커브를 유지하면서 진화시키는거임. 근데 생각해보면 컨법에 알라나를 대체하기 위해 같은 코스트의 이세라를 넣지는 않음. 대신 다른 식으로 변수를 창출할 수 있는 카드를 넣겠지. 플러리님처럼 토키를 넣는다던가… 그런 식으로 생각해보면 이게 오히려 창의적인 덱 메이킹을 방해할 수도 있다고 생각함.

- 결국 만들어진 덱을 돌려봐야 좋은 덱인지 아닌지 알 수 있는데, 이 덱을 돌리는걸 AI가 하도록 함. 근데 적용한 하스스톤 AI가 우리가 아는 오토 수준밖에 되지 않기 때문에 아무리 좋은 덱을 짜도 승률이 낮을 수 밖에 없음. 더더욱 콤보 덱이나 컨트롤 덱 같이 경우의 수가 많은 덱일수록 점수가 낮게 평가되겠지. 그래서 AI가 잘 플레이하는 투기장 덱들이 만들어질 수 밖에 없었던 것 같음.


< 옆동네 게임에서의 그래프 / 게임 실력에 따라 좋은 덱도 다를 수 밖에 없음 >

- 모든 덱을 상대로 골고루 승률을 보이는 덱을 만들려고 했는데, 한 덱 상대라도 승률 90프로씩 기록하면 그것도 충분히 좋은 덱이라고 생각함. 특히 대회에서는 이런 덱이 중요하잖아?  그렇기 때문에 내가 AI 만들게 되면 이건 꼭 확인해보고 싶음. 예를 들어 짝흑만 저격하고 싶다면 어떤 덱이 제일 좋을까? 라는 질문에 답을 할 수 있게.

 

어떻게 마무리 할지 모르겠네. 길고 긴 글을 읽느라 수고 많았음. 반응이 좋다면 다음에는 덱을 플레이하는 AI가 어떻게 개발되고 있는지에 대한 칼럼으로 돌아올거임. 많은 사람들이 이 글을 보고 하스스톤 AI에 도전했으면 함. 그리고 너네들의 의견이 어떤지 댓글로 적어줘. 그럼 바이바이~

 

작성자 : 디아드

 

레퍼런스 논문

‘Improving Hearthstone AI by Combining MCTS and Supervised Learning Algorithms’

‘Automated playtesting in collectible card games using evolutionary algorithms : A case study in hearthstone’

 

세줄요약

1. 오토, 그것도 존나 쎈 오토를 만들고 싶음

2. 오토가 자기 스스로 메타 분석해서 덱도 짜는 거임

3. 누가 이미 해놨는데 별로임. 하늘선장 크라그를 쓰는 템법이라니…