Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding

논문 요약: Deep Surrogate Assisted MAP-Elites 를 활용한 자동화된 하스스톤 덱 빌딩

1. 연구 문제 (Problem)

• 목표: 게임 내에서 고품질이고 다양한 콘텐츠 (이 경우 하스스톤 덱) 를 효율적으로 생성하는 것.
• 배경: 하스스톤과 같은 수집형 카드 게임 (CCG) 은 플레이어 경험 향상과 밸런스 테스트를 위해 다양한 전략을 가진 고성능 덱을 자동 생성하는 것이 중요함.
• 도전 과제:
  • 높은 평가 비용: 하스스톤 덱의 성능을 평가하려면 확률적 요소 (초기 상태, 플레이어 행동 등) 로 인해 최소 200 게임 이상의 시뮬레이션이 필요함. 이는 계산 비용이 매우 큼.
  • 기존 방법의 한계: 기존에 하스스톤 덱 빌딩에 적용된 품질 다양성 (Quality Diversity, QD) 알고리즘인 MAP-Elites는 다양한 전략의 덱을 생성할 수 있지만, 이를 발견하기 위해 너무 많은 평가 (시뮬레이션) 가 필요하여 비효율적임.
  • 기존 대리 모델 (Surrogate Model) 의 문제: 오프라인에서 학습된 대리 모델은 검색 알고리즘이 모델의 오류를 악용하는 '적대적 예시 (adversarial examples)'를 발견할 수 있으며, 고차원 이산 데이터 (수백 장의 카드) 에 적용하기 어려움.

2. 제안 방법 (Methodology)

저자는 **Deep Surrogate Assisted MAP-Elites (DSA-ME)**라는 새로운 모델 기반 QD 알고리즘을 제안합니다. 이는 MAP-Elites 와 온라인으로 학습되는 심층 신경망 (Deep Neural Network) 기반의 대리 모델을 결합한 접근법입니다.

• 핵심 구조 (Inner Loop & Outer Loop):

  • 내부 루프 (Inner Loop): 학습된 심층 대리 모델을 사용하여 MAP-Elites 알고리즘을 실행합니다. 실제 게임 엔진 대신 대리 모델을 통해 덱의 성능 (목표 함수) 과 특성 (측정 함수) 을 빠르게 예측하여 다양한 '엘리트 (elite)' 덱을 탐색합니다.
  • 외부 루프 (Outer Loop): 내부 루프에서 발견된 후보 덱들을 실제 하스스톤 시뮬레이터 (SabberStone) 에서 200 게임씩 평가하여 'Ground-truth(실제 정답)' 데이터를 얻습니다.
  • 온라인 학습 (Online Training): 외부 루프에서 얻은 실제 평가 데이터를 대리 모델의 학습 데이터 버퍼에 추가하여 모델을 재학습시킵니다. 이 과정을 반복하며 대리 모델의 정확도를 높이고, MAP-Elites 가 더 나은 방향으로 탐색하도록 유도합니다.

• 구체적 구현:

  • 입력 표현: 덱을 'Bag-of-Cards' 방식으로 인코딩 (각 카드의 포함 횟수: 0, 1, 2) 하여 벡터로 표현.
  • 대리 모델: 다층 퍼셉트론 (MLP) 을 사용하여 목표 함수 (승률/체력 차이) 와 측정 함수 (게임 길이, 손에 든 카드 수) 를 동시에 예측.
  • 전략적 상호작용: 초기에는 대리 모델의 오류를 exploiting 하는 덱이 발견되지만, 이를 학습 데이터로 포함시킴으로써 모델이 점차 정확해지고, 결과적으로 고품질의 다양한 덱을 생성하게 됨.

3. 주요 기여 (Key Contributions)

1. 새로운 알고리즘 제안: 고차원 이산 공간 (카드 덱) 에서 온라인 학습이 가능한 심층 대리 모델을 MAP-Elites 에 통합한 DSA-ME 알고리즘 개발.
2. 샘플 효율성 향상: 오프라인 학습 모델이나 선형 모델 기반의 접근법보다 훨씬 적은 수의 실제 게임 평가로 고품질 및 다양한 덱을 발견함.
3. State-of-the-Art 달성: 하스스톤 자동 덱 빌딩 분야에서 품질 다양성 (QD) 접근법의 새로운 최고 성능을 기록.
4. 온라인 학습의 효과 입증: 오프라인 데이터만으로는 달성할 수 없는 성능 향상이, MAP-Elites 가 생성한 다양한 데이터로 모델을 지속적으로 업데이트하는 과정에서 발생함을 증명.

4. 실험 결과 (Results)

• 실험 설정: 하스스톤 '로그 (Rogue)' 클래스의 기본/클래식 카드를 대상으로, 6 개의 다양한 상대 덱 (공격형/통제형) 과 대결.
• 비교 대상:
  • 기본 MAP-Elites (대리 모델 없음)
  • LSA-ME (선형 대리 모델 사용)
  • Offline DSA-ME (오프라인 무작위 데이터로 학습된 심층 모델)
  • DSA-ME (제안 방법)
• 성과 지표:
  • QD-Score (품질 다양성 점수): DSA-ME 가 다른 모든 방법보다 압도적으로 높은 점수를 기록 (약 338 vs 기본 MAP-Elites 136).
  • 최대 승률 및 체력 차이: DSA-ME 가 가장 높은 성능을 보임 (승률 98.4%, 평균 체력 차이 22.30).
  • 채워진 셀 비율 (다양성): DSA-ME 가 아카이브의 더 많은 영역을 채움 (31.86%).
• 부수적 데이터 (Ancillary Data) 분석: 승률, 데미지, 매너 소모 등 추가 데이터를 학습에 포함시켰으나, 오히려 성능이 저하되거나 유의미한 향상이 없었음 (하스스톤 덱의 단순한 'Bag-of-Cards' 인코딩 방식이 한계로 작용한 것으로 추정).
• 모델 품질 분석: DSA-ME 로 학습된 최종 모델은 테스트 데이터에서 높은 정확도를 보였으며, MAP-Elites 를 초기화 (Reset) 하는 것이 탐색 공간의 균일한 커버리지에 중요함을 확인.

5. 의의 및 결론 (Significance)

• 게임 디자인 및 밸런싱: 게임 개발자가 자동화된 도구를 통해 다양한 전략을 가진 덱을 빠르게 생성하고, 이를 통해 게임의 밸런스를 조정하거나 플레이어 경험을 풍부하게 하는 데 기여할 수 있음.
• 모델 기반 QD 의 확장: 기존에 저차원 연속 공간에 국한되었던 모델 기반 QD (MBQD) 를 고차원 이산 공간 (게임 콘텐츠 생성) 으로 확장하는 성공적인 사례를 제시함.
• 효율성: 실제 게임 엔진의 높은 평가 비용을 줄이면서도, 오프라인 학습 모델의 한계를 극복하고 더 정교한 콘텐츠를 생성할 수 있음을 입증.

이 논문은 하스스톤이라는 구체적인 도메인을 통해, 온라인 학습이 가능한 심층 대리 모델과 MAP-Elites의 결합이 게임 콘텐츠 생성의 효율성과 다양성을 동시에 극대화할 수 있음을 보여줍니다.