AI의 스타크래프트 도전기③ 스타크래프트 인공지능 연구, 어디까지 왔나?

AI의 스타크래프트 도전기3- 
스타크래프트 인공지능 연구, 어디까지 왔나?

먼 미래에 범용 인공지능(GAI: General AI)이 개발된다면 우리 생활에 어떤 변화가 올까요?
마치 사람이 복잡한 문제를 해결하듯이, 인공지능도 아무리 복잡한 문제라도 알아서 작게 나눠서 해결하고, 이를 종합해 전체 문제를 해결하게 될 것입니다. 하지만 안타깝게도 아직까지 어떠한 인공지능도 복잡한 문제를 알아서 나누어 해결하는 능력이 없습니다.
실제로 인공지능을 통해 어떤 복잡한 문제를 해결하려고 한다면, 해결 가능한 가장 작은 문제로 쪼개어 해결을 시도하게 됩니다. 복잡한 문제를 어떻게 나누고 어떤 부분에 학습(Learning)을 적용할 것인지 개발자와 연구자, 도메인 전문가의 조언을 종합하고 반영해 나가며 전체 문제로의 해결을 시도하게 됩니다.

인공지능의 문제 해결 단계

1편에서 설명드린 바와 같이 스타크래프트(101685)는 바둑(10170)보다도 훨씬 경우의 수가 많은, 매우 복잡한 문제입니다. 때문에 한번에 전체 문제를 해결할 수 없고 해결 가능한 작은 문제로 나누어 해결을 시도해야 하는 것이죠.

스타크래프트를 보다 작은 문제들로 나누기

스타크래프트를 잘 플레이 하는 인공지능을 구현하기 위해서는 크게 전략(Strategy: Macro), 전술, 반응 컨트롤(Tactics & React control: Micro) 이 3가지에 대한 분석이 필요합니다.

① 전략(Strategy): 게임에 전반적으로 영향을 미치며, 테크트리(Technology tree), 빌드오더(Build-order), 업그레이드(Upgrade), 유닛 조합 (Unit composition) 등에 대한 결정을 포함한다.
② 전술(Tactics): 전략(Strategy)에서의 결정에 따라 짧은 시간 안에 처리할 세부적인 행동 등 작은 결정을 한다.
③컨트롤(React control):유닛을 상황에 맞게 컨트롤 하는 것으로, 유닛이 오래 살아남아서 자원을 최대한 획득하거나 적의 유닛을 잡도록 한다.

대표적인 스타크래프트 인공지능 연구자인 David Churchill(AIIDE대회 운영자)과 Gabriel Synnaeve (Facebook의 CherryPi 개발 리더)등이 2013년 IEEE CIG 학회에 발표한 논문 ‘A Survey of Real-Time Strategy Game AI Research and Competition in StarCraft’에서는 전략과 전술, 반응 컨트롤에 대한 관계를 아래 그림과 같이 잘 설명하고 있습니다.

전략과 전술, 반응 컨트롤에 대한 관계 전략과 전술, 반응 컨트롤에 대한 관계

전략적 결정은 확인된 정보가 적더라도 큰 계획을 세우는 것으로 3분 이내로 결정을 내리게 됩니다. 전술적 결정은 약간의 정보가 확인된 상태에서 30초 이내로 결정을 내리고, 반응 컨트롤은 확실한 정보를 바탕으로 1초 이내에 즉각적인 행동을 하는 것입니다. 전략적 결정은 시간적 추론을 바탕으로 하고 전술적 결정은 시간적 & 공간적 추론을 통해 하게 됩니다. 반응 컨트롤은 공간적 추론만 하면 됩니다.

공간적 추론 (Spatial Reasoning) 시간적 추론 (Temporal Reasoning)
맵의 특성에 따른 추론으로 건물을 지을 위치를 정하는 문제가 대표적
Ex1) 스타크래프트 게임에서는 언덕 위를 점령하는 것이 언덕 아래에 있는 것보다 훨씬 유리
Ex2) 상대의 공격을 방어하기 위해 건물로 벽(Wall)을 만든다든지, 건물의 간격은 어떻게 할 것인지, 확장은 어디로 할 것인지 등을 추론
Ex3) 유닛을 어떤 지역으로 보낼 것인지, 어떤 위치에서 전투를 벌일 것인지 정하는 문제도 공간적 추론에 해당
전술적(tactical) 또는 전략적(strategic) 추론

Ex1) 이득을 얻기 위해 타이밍을 맞춰 공격 또는 후퇴를 결정하는 것
Ex2) 전략 전환, 기술 업그레이드, 건물 건설 등 장기적 전략을 가지고 실행하는 것



스타크래프트가 바둑과 같은 보드 게임보다 더 어려운 점은, 게임이 플레이 되는 맵이 매우 다양하다는 것입니다. 따라서 맵의 특성을 반영하여 그에 맞는 전략, 전술, 반응 컨트롤을 조절해야 하며 추가적으로 아래 2가지 문제에 대한 해결도 필요합니다.

④ 지형 분석 (Terrain analysis): 맵의 각 지역들을 분석하는 것으로 초크 포인트(Choke-Points: 언덕이나 좁은 지역을 벗어나는 지점), 미네랄과 가스의 위치, 언덕 위와 아래, 섬 지역, 건물을 지을 수 있는 지역, 이동 가능한 지역 등을 파악하는 것을 말한다.
⑤ 정보 수집 (Intelligence gathering): 적에 대한 정보를 모으는 활동으로 전장의 안개(fog of war)로 인해 주기적으로 정찰을 보내야 하며, 적의 기지를 감시해야 한다. 이를 통해 적의 확장 기지와 유닛의 조합과 숫자를 파악하고 적의 전략과 전술 등을 추론해 내야 한다.

2편에서 소개해 드린 세계대회 상위권의 스타크래프트 인공지능 봇들은 앞서 말씀 드린 5가지, “전략(Strategy), 전술(Tactics), 반응 컨트롤(React control), 지형 분석(Terrain analysis), 정보 수집(Intelligence gathering)”이 대부분 매우 정교한 규칙(rule)에 따라 개발되었다고 볼 수 있습니다. 현재 부분적으로 학습 기능이 적용되었거나, 전체 게임이 아닌 특정한 미니 게임 환경에서만 학습을 통해 일부 가능성을 탐색해 보는 연구 정도만 진행된 상황입니다. 사실 이것은 초기 인공지능 개발에 있어 가장 보편적인 접근 방식입니다. 한번에 스타크래프트 전체를 학습으로만 구현하기는 매우 어렵기 때문에, 먼저 시뮬레이터를 잘 만들고 여러 번의 실험을 반복해야 합니다. 그리고 어떤 부분에 학습을 적용하면 효과적일지 찾아내고, 학습이 잘 될 경우 해당 모듈을 학습하여 처리하도록 교체해 나가는 프로세스를 거치게 됩니다.

그럼 최근 스타크래프트 학습과 관련한 대표적인 연구 사례 몇 가지를 소개해 드리겠습니다.

연구사례 1. 다중 에이전트 양방향 조정 네트워크 연구 (Alibaba & University College London)

2017년 3월 인터넷 논문 저장소인 arXiv에 등록된 알리바바(Alibaba)와 유니버시티 칼리지 런던(University College London) 연구원들의 논문을 살펴보죠. 이 논문에서는 미리 정의된 스타크래프트의 미니게임에서 다중 유닛들을 사람이 컨트롤하는 것 같은 정교한 반응 컨트롤(React control)을 많은 시행착오 끝에 개발했다고 합니다. 강화학습을 통해서 말이죠.

BiCNet 알고리즘 BiCNet 알고리즘

BiCNet for Playing Starcraft

위의 영상을 보시면 다양한 유닛 조합의 전투를 수행할 때, 강화학습을 통해 세밀한 반응 컨트롤의 가능성을 보여주었다고 할 수 있습니다.

그리고 스타크래프트에 적용되진 않았지만, 멀티에이전트 강화학습 연구의 OpenAI에서 나온 알고리즘이 있습니다. 현재 성능이 가장 잘 나오는 멀티 에이전트 알고리즘, MADDPG 알고리즘과 COMA라는 알고리즘이죠.

MADDPG 알고리즘과 COMA라는 알고리즘

하지만 본 사례는 아직 한가지 종류의 유닛들 간 전투에만 강화학습이 적용되었습니다. 미니게임의 많은 제약 사항을 전제로 하고, 컴퓨터 AI의 난이도를 낮춰서 학습한 사례이므로 전체 게임에 적용하기에는 아직 한계가 있는 것이죠. 그리고 이런 멀티에이전트 알고리즘을 검증하는 환경도 아직 표준이 없습니다. 따라서 많은 회사들이 이런 환경을 구축하기 위해 파트너십을 구축하고 자체적인 연구를 진행하고 있습니다.

저희 SAIDA팀에서도 이 문제의 해결책을 찾아보기 위해 스타크래프트의 강화학습이 가능한 환경을 구축하기 위해 노력했습니다. 그리고 수차례의 시행착오를 거듭한 끝에, 멀티에이전트를 비롯한 다양한 모델을 학습할 수 있게 하는, 강화학습이 가능한 환경을 자체 구축하는데 성공했습니다. 이를 기반으로 게임에 적용 가능한 모델을 확보하기 위해 고려대학교 산업경영학과 DMQA 랩과 협력하여 아래와 같은 강화학습 연구를 수행했습니다.

연구사례 2. 글로벌 보상에 따른 다중 유닛 강화학습 연구 (Samsung SDS & Korea University)

우리는 스타크래프트의 이기종 멀티에이전트보다 앞서, 동일 기종의 멀티 에이전트 컨트롤을 목표로 모델을 제작했습니다. 먼저 기본 강화학습 모델의 대표격인 DQN과 A2C의 모델을 멀티 에이전트 모델로 변경하여 실험을 시작했습니다. 구현을 위해 다양하게 논문을 리서치하고 시행착오를 겪은 끝에, 위 모델들이 저희 최종 모델의 시작점이 되었습니다.
그렇게 Actor-Critic 아키텍처를 채용한 대표적인 off policy Deep Deterministic Policy Gradient(DDPG) 모델을 제작했습니다. BiCNet 기반의 Decentralized actor와 Centralized critic의 구조를 취했고, 여기에 유닛 개수에 따라서 모델의 파라메터가 늘어나지 않도록 디자인했습니다. 또한 협동 능력을 최대치로 끌어올리도록 글로벌 리워드를 취하여 에이전트 간 협동을 가장 우선순위로 생각하게끔 했습니다. 그리고 Model-based RL을 참조하여 모델이 환경을 예측하는 기능을 추가하며 성능을 더 끌어올렸습니다.

Actor-Critic Network Architecture Actor-Critic Network Architecture

이 모델은 OpenAI에서 제공되는 Multi-agent Particle Environment(MPE)라는 환경 중, SimpleSpread라는 시나리오를 가지고 1차 검증을 했습니다. 이 환경에서 6만 번의 에피소드를 플레이 하면서 얻은 학습 결과는 아래와 같습니다.

OpenAI에서 제공되는 Multi-agent Particle Environment(MPE)라는 환경 중, SimpleSpread라는 시나리오를 가지고 6만 번의 에피소드를 플레이 하면서 얻은 학습 결과

우측의 그래프를 보시면 개발한 강화학습 알고리즘(Proposed/Proposed+model)이 최신 기법인 MADDPG를 앞서는 결과를 얻었습니다. 특히 individual reward로 학습한 BicNet 대비해서도 global reward 만으로 학습한 제안기법 (Proposed+model)이 매우 근접한 성능을 갖는 것으로 확인했습니다. 우리는 이 모델을 스타크래프트의 다양한 상황에 적용하였습니다. 실제 게임에서 일어날 수 있는 생존, 탐색, 그리고 전투 등의 시나리오에 다양한 유닛 조합을 이용하여 학습을 하고 있습니다. 현재 간단한 미니게임에서 적용 가능성을 확인하였고, 이후 Full Game에 적용하기 위해 계층적 강화학습 및 이기종 멀티 에이전트 학습을 위해 모델 리서치 및 학습 성능 최적화에 몰두 하고 있습니다.

다음으로 많은 연구 성과가 나올 것으로 기대되는 부분인, 바둑의 기보에 해당하는 스타크래프트 리플레이 파일을 이용한 지도/비지도 학습 연구 분야에 대해 살펴보겠습니다.

연구사례 3. STARDATA: A StarCraft AI Research Dataset (Facebook AI Research)

2017년 8월 인터넷 논문 저장소인 arXiv에 등록된 페이스북 인공지능연구소 Facebook AI Research)의 연구원들의 논문에서는, 스타크래프트 게임의 문제를 학습을 통해 해결하는데 꼭 필요한 리플레이 데이터 65646개를 인터넷 사이트에서 수집해 공개했습니다. 이 논문에서는 리플레이 데이터를 활용하면 아래의 문제들을 학습을 통해 해결할 수 있을 것이라 제시했죠.

① 전략 분류 (Strategy classification)
② 인버스 강화학습 (Inverse reinforcement learning)
③ 이미테이션 학습 (Imitation learning)
④ 포워드 모델링 (Forward modeling)
⑤ 부분 정보 추출 (Partial information extraction)

저희 SAIDA 팀에서도 한국의 프로게이머들로부터 약 11만건의 리플레이 데이터를 수집했으며, 이를 활용해 아래와 같은 연구를 수행했습니다.

연구사례 4. Convolution Encorder-Decoder Model을 통한 승세 예측 모델 연구
(Samsung SDS & Korea University)

스타크래프트와 같은 실시간 전략(RTS) 게임에서는 상대방의 정보를 완전히 알 수 없는 불완전한 정보 상황에 놓여집니다. 사람은 오랜 경험을 통해 상대방의 정보를 유추할 수 있지만, 인공지능 플레이어는 어렵습니다.
이 문제를 해결하기 위해 스타크래프트 리플레이 데이터를 활용해, 상대방의 불완전한 정보를 추론 할 수 있는 Convolutional Encoder-Decoder network를 구성했습니다. 이를 통해 나온 상대방의 정보를 바탕으로 전투에서 가치 판단을 할 수 있는 모델을 구현했고, 실제 적용 후 승률이 5% 이상 향상되는 결과를 확인했습니다.

이처럼 스타크래프트를 기반으로 매우 다양한 인공지능 연구가 수행되고 있습니다. 하지만 아직 프로게이머 수준의 플레이를 보여주는 봇은 없습니다.
이에 저희 SAIDA 팀에서는 이미테이션 학습 (Imitation Learning) 기법에 주목하고 있습니다. 이는 기존에 만들어진 봇이나 사람의 플레이를 흉내내면서 학습하는 기법입니다. 마치 스승과 제자를 두고 도제식으로 장인들이 기술을 전수하던 것과 매우 흡사한 학습 방식이죠.
기존의 강화학습 모델로는 스타크래프트와 같이 복잡한 게임에서, 전체 게임은 너무나도 많은 경우의 수로 인해 학습이 거의 불가능한 수준입니다. 하지만 이미테이션 학습은 이러한 경우의 수를 줄여 주어 학습이 성공할 가능성을 높여줄 수 있습니다. 특히 우리나라는 뛰어난 프로게이머가 많기 때문에 이미테이션 학습을 통해 프로게이머와 흡사한 플레이를 보여줄 인공지능 봇 개발 가능성이 매우 높다고 볼 수 있습니다.

저희 SAIDA 팀의 도전이 계속되어 프로게이머 수준의 인공지능 봇을 개발할 수 있도록 독자 여러분들의 많은 응원 부탁드립니다. 그 동안 저의 부족한 글 솜씨에도 불구하고 1,2,3편의 아티클을 읽어 주신 독자 분들께 감사드리며 다음 기회에 더욱 흥미로운 주제로 다시 찾아 뵙겠습니다.


[깜짝소식]
배창현 프로가 속한 SAIDA팀(사이다, Samsung SDS AI & Data Analytics)
세계 최고 권위 AIIDE 대회에서 한국팀 최초로 우승
(자세한 소식은 아래 사진 클릭해서 확인!)
삼성SDS SAIda팀 사진
[봇 개발 가이드 및 SAIDA 봇 다운로드 방법]
http://github.com/TeamSAIDA/GUIDE/wiki


[참고]
- Ontanón, Santiago, et al. "A survey of real-time strategy game AI research and competition in StarCraft." IEEE Transactions on Computational Intelligence and AI in games 5.4 (2013): 293-311.
- ng, Peng, et al. "Multiagent bidirectionally-coordinated nets for learning to play starcraft combat games." arXiv preprint arXiv:1703.10069 (2017).
- Lowe, Ryan, et al. "Multi-agent actor-critic for mixed cooperative-competitive environments." Advances in Neural Information Processing Systems. 2017.
- Foerster, Jakob, et al. "Counterfactual multi-agent policy gradients." arXiv preprint arXiv:1705.08926 (2017).- J. N. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson, “Counterfactual Multi-Agent Policy Gradients.”
- Multi-Agent Particle Environment, OpenAI, https://github.com/openai/multiagent-particle-envs
- Comparison with proposed model and other state of art models in simple spread environment

▶   해당 콘텐츠는 저작권법에 의하여 보호받는 저작물로 기고자에 저작권이 있습니다.
▶   해당 콘텐츠는 사전 동의없이 2차 가공 및 영리적인 이용을 금하고 있습니다.


배창현 프로
배창현 프로 인공지능 전문가
삼성SDS XEED-LAB

배창현 프로는 KAIST에서 학부를 마치고 대학원에서 수학을 전공하였습니다.
삼성SDS 입사 후 CAD S/W, PDM 서비스, 안드로이드 앱 개발 등 다양한 개발 업무를 담당하였으며, 현재는 사내 벤처 프로그램인 XEED-LAB에서 스타크래프트 인공지능 봇을 개발하는 SAIDA팀 리더를 맡고 있습니다.

구독하기

인사이트 리포트 소식을 메일로 받아보세요