2008.09.10 22:18

스타크래프트의 컴퓨터 인공지능 프로그래밍 방법 소개

본 글은, 스타크래프트 인공지능의 프로그래밍 방법을 소개하기 위하여 쓰게 되었다.

(이 글은, 실제로 2006년 1월에 열렸던, 한국게임학회 동계학술대회에 논문으로 발표된 바 있는 내용이다.)
- 이상호, 허준영, 조유근, 홍지만 저, "스타크래프트의 인공지능 성능 향상을 위한 프로그래밍 방법" 참조
shyi_star(kcgs06).pdf

KCGS 2006 발표 슬라이드



먼저, 스타크래프트 라는 게임을 모르는 네티즌은 거의 없으리라 생각한다.

하지만, 일부의 독자를 위해서 스타크래프트가 무엇인지, 간략히 요약해 보겠다.

n스타크래프트 등장
n  1998년 4월 10일, “Blizzard Entertainment” 발표
  1998년 12월, Brood War (확장팩) 의 등장


스타크래프트 중요성
  게임 시장에 큰 변화를 가져옴 (온라인 게임 산업의 발전에 지대한 영향을 줌)
  e-Sports의 발전에 큰 영향을 줌 (KeSPA 협회의 등장)
  몇 년째 최상의 인기 유지 (e-Sports 시장을 보라! 스타크래프트 만한 게임이 아직도 없다.)
  안정적인 사용자 집단 유지 (2008년 현재에도 아직 동시 접속자 수만명을 기록 중이다.)
  상당한 고용 창출 효과 (프로게이머, 게임 옵저버, 해설가, 캐스터, 기타 e-Sports 종사자 등)


사용자 삽입 이미지

그렇다면, 현존하는, 아직 잘 나가고 있는 스타크래프트 게임의 문제는 무엇일까?

이것을 파헤쳐 보자.

스타크래프트 문제점?
n
 1.  발전하는 사용자들의 수준에 미치지 못하는 시스템/인공지능
 2.  발전하지 않는 시스템으로 인한 퇴출 가능성 존재

이러한 문제가 있었다!

사실, 스타크래프트의 유저들은, 컴퓨터 인공지능에 기대하지 않는 것이 일반적인 통념 처럼 되어왔다.

그러나 이것은 단지 블리자드 엔터테인먼트에서 지원을 하지 않는 것일 뿐, 컴퓨터 인공지능이 개선된다면, 게임에 더 큰 재미를 가져다 줄 수도 있을 것이다.

따라서 본 논문 및 글을 작성하게 되었다.

2006년 1월에 발표한 논문을 이제야 포스팅 하는 것이 약간 민망하지만, 그래도 해 보겠다.


일단, 기존에도 스타크래프트의 인공지능 관련 연구는 진행된 바 있다.

예를 들어보자.

1) ‘스타크래프트’의 인공지능 프로그래밍 관련 연구
     ScAIEdit(StarCraft A.I. Editing Tool):

2) 인공지능 스크립트를 바이너리 파일로 변환해 주는 도구
    WinMPQ(MPQ Archiving Tool):
    *.MPQ 파일의 압축을 풀거나 압축을 수행해주는 도구

3) Brood War A.I. Project:
    기존의 인공지능 성능 개선 목적의 연구 (Insane A.I.)

와, 대단하다. 스타크래프트의 인공지능 프로그래밍 방법이 존재했다니!

특히 더 놀라운 것은 1)의 항목은 2000년도에 Gold Dragon 이라는 어떤 익명의 외국 프로그래머가 개발한 것으로, 상당히 오래 전에 만들어졌다는 것이 심히 놀라운 것이다.

이후, 2003년에는 위의 스크립트를 사용하여 3)의 프로젝트를 외국의 모 프로그래머가 개발하였다.

그러나, 3)의 경우에는 무한한 자원(미네랄 및 개스)을 제공하는 치트 코드를 사용하였기에, 질적인 인공지능의 향상을 꾀하기는 어려웠다.

이러한 인공지능 연구와는 별개로, 사람대 사람의 전투에서 보다 나은 빌드 오더, 전략 전술을 찾기 위한 여러 연구가 이루어지고 있었다.

‘스타크래프트’의 전략전술 관련 연구들:

A) http://pgr21.com/
    다양한 사용자들에 의한 여러 가지 전략전술 연구

B) http://gzprotoss.com/
    프로토스 종족의 전략전술과 관련한 포럼

C) 기타 (와이고수 사이트 등)




그럼, 이제 본론으로 들어가도 좋겠다.

먼저, 게임에 대한 간략한 소개를 하도록 하겠다.

--------------------------------------------------------------------------------------
게임 개요:
    세 가지의 다른 종족들(테란, 저그, 프로토스)간의 우주 전쟁
    실시간 전략 시뮬레이션(Real-time Strategy Simulation) 게임

기본 구성:
    전장(Field):
      게임을 수행하는 공간

    자원(Resources):
      고정적인 미네랄 및 가스 자원 존재
      이 자원을 사용하여 유닛, 건물 생산 및 특수기술을 연구할 수 있음

    유닛(Units):
      자원 채취, 건물 짓기
      공격 및 방어

    건물(Buildings):
      유닛 생산
      마법 및 특수기술 연구
      공격 및 방어

    마법 및 특수기술(Magical or Technical Skills):
      유닛들 혹은 건물들에 부여되는 여러 종류의 기술

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

그러면, 게임 방법은 어떠한가? 이미 다 알고 있는 분들은 간단히 넘어가시기 바란다.


--------------------------------------------------------------------------------------
게임 방법:
    실시간으로 작업 명령을 내리고, 이를 통하여 상대방과의 전투를 수행
    상대방보다 효율적인 전략전술을 사용해야 전투에서 승리할 수 있음

사용자 삽입 이미지

예> 초반 마린(Marine) 공격을 감행할 경우,
    마린을 생산하기 위하여 배럭스(Barracks)를 지어야 한다.
    여러 기의 마린을 생산하려면 서플라이 데포(Supply Depot)를 지어야 한다.
    위의 유닛 생산 및 건물 짓기에는 일정 자원이 필요하다.
    SCV를 통하여 자원을 채취한다.
    초반 공격은 빠른 시간 내에 이루어져야 한다.
    빠른 시간 내로 마린을 생산하기 위해서는 자원 수급이 원활해야 한다.
    자원 수급의 속도를 높이기 위해서는 SCV를 생산해 주어야 한다.
    SCV의 생산 또한 자원을 소모하므로, 적절한 수를 생산해 주어야 한다.
    …

위의 모든 것을 효과적으로 하려면 어떻게 하겠는가???? 

이러한 것은 최적화 된 ‘빌드 오더’를 사용함으로써 해결할 수 있다! (^^) 

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

그렇다면, 이 빌드 오더의 수정 외에,  기존 게임 인공지능 중, 어떠한 것을 수정해야 할 지를 좀 더 살펴보겠다.


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

게임에서의 인공지능 (개선 되어야 할 인공지능):
   빌드 오더
      목적에 맞는 최적화 된 방법의 사용
  
   공격 유닛들의 구성
      공격 대상 및 방법에 따른 공격 유닛들의 효율적 구성

   공격 및 방어 시점
      효과적인 공격 및 방어 시점의 선택

   유닛 컨트롤
      유닛의 특성을 활용한 효율적인 유닛 공격 및 이동(회피기동) 명령 제어

   전투 진형
      효율적인 전투를 위한 진형

   지형 활용
      언덕 및 구조물 등의 지형을 활용

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

위의 6 가지 사항 중, 본 논문 (포스팅된 글)에서 다룰 내용은 빨간색을 표기된 빌드 오더, 공격 유닛들의 구성, 공격 및 방어 시점 등이다.

나머지 세 항목인 유닛 컨트롤, 전투 진형, 그리고 지형의 활용 등은 인공지능 스크립트를 통해 수정할 수 있는 것이 아니므로 이번 연구에서는 제외하였다.

위의 세 항목을 다시 보자면, 전략적 측면에서의 게임 인공지능으로 볼 수 있다.

전략적 측면에서의 게임 인공지능: (본 논문에서 다루는 주제)
- 빌드 오더
- 생산된 공격 유닛들의 구성
- 공격 및 방어 시점

전술적 측면에서의 게임 인공지능: (본 논문에서 제외된 주제)

- 유닛 컨트롤
- 생산된 공격 유닛들의 전투 진형
- 지형을 이용한 자리 배치

그럼, 이제, 어떠한 방식으로 프로그래밍을 할 수 있는지 살펴본다.


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

사용자 삽입 이미지














스타크래프트 게임의 인공지능 이미지는 ‘Patch_rt.mpq'의 내부에 존재한다.

이 파일은 WinMPQ[6]를 통하여 압축을 풀어낼 수 있고, 추후에 재 압축을 수행할 수 있다.

이제 이 파일을 WinMPQ 프로그램을 통하여 압축을 풀어내면, scripts 폴더에서 aiscript.bin 파일을 찾을 수 있다.

** (WinMPQ 프로그램을 찾을 수 없다면, 본인에게 메일 혹은 커멘트를 달아주세요. 그럼 보내드립니다.)



사용자 삽입 이미지
이 파일, 'aiscript.bin'은 바이너리 이미지 형태의 스크립트 코드를 담고 있다.

이 파일을 ScAIEdit를 이용하여 열면, 여러 가지 상황에 대한 현존하는 스타크래프트 게임의 인공지능 소스코드를 참조할 수 있다.


예를 들어서,위의 그림을 자세히 살펴보면 리스트 항목 중에서,

‘Protoss Expansion Custom Level’ 이라는 이름을 갖는 항목이 존재한다.

이 항목은, 프로토스 종족의 확장팩에서의 커스텀 시나리오에 해당되는 인공지능 스크립트이며,  이것을 클릭하면 다음에 보이는 바와 같이,

ScAIEdit 툴이 지원하는 스크립트 언어로 표현된 프로토스 종족의 인공지능 스크립트가 나타난다.



사용자 삽입 이미지

이러한 스크립트들을 수정하여, 각 종족에 해당되는 인공지능을 수정할 수 있다.

또한, 기존의 스타크래프트 인공지능에 해당되는 소스코드를 직접 볼 수 있으므로,

기존의 인공지능에서 보다 성능을 개선시켜볼 수도 있게 된다.


먼저, 본 논문에서는 ScAIEdit 툴이 지원하는 스크립트 언어의 형태에 대하여 보인 후에,

여러 가지 예제 상황의 프로그래밍 방법 등을 보일 것이다.




ScAIEdit 스크립트 언어의 형태:
   어셈블리 언어와 비슷한 형태를 갖는다.
   문법의 기본적인 형태와 대표적인 명령어의 예는 다음과 같다.

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

문법:
- command (param1) (param2) (param3) ...
 * command: 명령어의 연산자
 * (paramN): 명령어의 피연산자들
명령어 예:
- attack_add (숫자) (공격유닛)
 * (숫자)만큼의 (공격유닛)을 현재의 공격 부대에 추가한다.
- attack_do
 * 현재의 공격 부대를 이용하여 적을 공격한다.
- build (숫자) (건물) (우선순위)
 * (숫자)만큼의 (건물)을 (우선순위)에 따라 짓는다.
- defenseuse_aa (숫자) (공격유닛)
 * (숫자)만큼의 (공격유닛)을 공대공 방어에 사용한다.
- defenseuse_ag (숫자) (공격유닛)
 * (숫자)만큼의 (공격유닛)을 공대지 방어에 사용한다.
- defenseuse_ga (숫자) (공격유닛)
 * (숫자)만큼의 (공격유닛)을 지대공 방어에 사용한다.
- defenseuse_gg (숫자) (공격유닛)
 * (숫자)만큼의 (공격유닛)을 지대지 방어에 사용한다.
- train (숫자) (공격유닛)
 * (숫자)만큼의 (공격유닛)을 생산한다.
- wait (시간)
 * (시간)만큼 기다린다.
- wait_build (숫자) (건물)
 * (숫자)만큼의 (건물)이 완성될 때 까지 기다린다.

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

다음으로, 프로그래밍의 이해를 돕기 위하여 간단한 몇 가지 예제들을 보인다.

먼저, 유닛 생산 및 건물 짓기와 관련한 예제를 보인 후에,

공격력 및 방어력의 업그레이드, 기술의 리서치 예, 더 나아가 공격 유닛들의 집결 및

공격 방법을 담은 예제를 보인다.

마지막으로, 조건에 따른 분기 명령과 관련한 예제를 보이고, 이것의 효과적인 사용 예를 간략히 설명한다

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

예제1. 마린 2기, 메딕 2기 생산:

train 2 marine

wait_train 2 marine

train 2 medic

; 설명> 마린을 2기 생산 후, 메딕을 2기 생산한다.

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

train 1 marine

train 1 medic

wait_train 1 marine

train 2 marine

wait_train 1 medic

train 2 medic

; 설명> 마린과 메딕을 1기씩 생산 후, 각각 1기씩 더 생산한다.

 

예제2. 빌드 오더에 따른 순차적 건물 짓기:

build 1 barracks 80

wait_build 1 barracks

build 1 academy 80

build 1 refinery 80

wait_build 1 academy

build 1 engineering_bay 80

; 설명> 하나의 배럭스가 완성되면 하나의 아카데미와 리파이너리를 짓기 시작한다. 아카데미가 완성되면 엔지니어링 베이를 짓기 시작한다. 여기에서, 80은 우선순위이다.

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

build 1 barracks 80

wait_build 1 barracks

build 2 factory 80

wait_build 1 factory

build 1 starport 80

; 설명> 하나의 배럭스가 완성되면 두개의 팩토리를 짓기 시작한다. 그리고 팩토리 하나가 완성되면 바로 스타포트를 짓기 시작한다. 결과적으로 하나의 배럭스와 두개의 팩토리, 그리고 하나의 스타포트가 지어진다. 여기에서, 80은 우선순위이다.

 

예제3. 공격력 및 방어력 업그레이드, 기술 리서치:

build 1 academy 80

build 1 engineering_bay 80

wait_build 1 academy

tech stimpack 40

wait_build 1 engineering_bay

upgrade 1 t_infantry_armor 40

wait_upgrade 1 t_infantry_armor

upgrade 1 t_infantry_weapon 40

; 설명> 아카데미와 엔지니어링 베이를 짓고, 아카데미가 완성되면 스팀팩 연구를 하고, 엔지니어링 베이가 완성되면 보병의 방어력 1단계 업그레이드를 하고, 방어력 업그레이드가 완료되면, 공격력 1단계 업그레이드를 수행한다.

 

예제4. 유닛 집결 및 공격 부대 생성, 및 공격 루프:

:loop

attack_add 18 marine

attack_add 12 firebat

attack_prepare

attack_do

attack_clear

wait 1500

goto loop

; 설명> 18기의 마린과 12기의 파이어뱃을 공격 부대에 추가하고, 공격 준비를 수행한다. 그리고 적진으로의 공격을 수행한 후에, 공격이 완료되면 공격 명령을 해제한다. 150초를 기다린 후에, loop 문을 통하여 다시 공격을 수행한다.

 

예제5. 여러 가지의 조건 분기:

random_jump 128 rush_mode

...

rush_mode:

...

; 설명> 확률 분기로, 128/256=0.5의 확률로 rush_mode의 레이블로 분기한다.

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

resource_jump 100 50 label_one

...

label_one:

...

; 설명> 자원 량에 따른 분기로, 미네랄이 100, 개스 50이상일 때 label_one의 레이블로 분기한다.

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

enemyowns_jump barracks label_bar

...

label_bar:

...

; 설명> 상대방 건물 및 유닛에 따른 분기로, 상대방이 배럭스 건물이 있을 때 분기한다.

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

enemyresource_jump 100 50 label_res

...

label_res:

...

; 설명> 상대방 자원 량에 따른 분기로, 상대방이 가진 미네랄이 100, 개스가 50 이상일 때 label_res의 레이블로 분기한다.

 

예제6. 멀티 쓰레드로 병행 수행:

multirun thread_code

...

thread_code:

...

; 설명> upgrade_code의 레이블로 시작하는 함수를 쓰레드를 생성하여 실행시킨다. 이를 통하여 다중 작업을 병행적으로 처리할 수 있다.

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

티스토리의 블로그 에디터가 그다지 좋지 않아서, 코드를 보기가 약간 어려울 듯 싶다.

시간이 되면, 좀 더 보기 쉬운 형태로 수정하도록 하겠다.



그래서, 무엇을 수정하였는가?

먼저, 기존 컴퓨터의 인공지능에 있어 큰 문제점들은 다음과 같다.

컴퓨터 인공지능의 문제점:
- 1. 단순 주사위 굴리기 식의 빌드 오더 선택
- 2. 비효율적인 빌드 오더
- 3. 공격 유닛들의 생산의 비효율성
- 4. 공격 유닛들의 구성에 있어서의 비효율성
- 5. 공격 및 방어 시점의 비적합성


본 논문에서는 이러한 것들을 수정하였고, 아래는 수정된 인공지능을 반영한 성능 평가 결과를 보인다.

먼저, 실험 환경이다.
--------------------------------------------------------------------------------------

실험 환경:

    사용한 게임 버전:
      스타크래프트-브루드워 1.13e

    사용한 맵:
      신 개마고원 2.1 (http://www.ongamenet.com)

    사용한 인공지능:
      프로토스: 제안한 프로그래밍 기법을 사용하여 개선한 것
      테란, 저그: 기존의 인공지능

    실험 방법:
      Top vs Bottom 으로 컴퓨터 간의 전투를 가능케 하고, 옵저버 모드로 관람

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

실험 결과:

     본 논문의 첫 번째 실험은, 제안한 인공지능을 사용하는 프로토스 종족과,
     기존 인공지능을 사용하는 테란 종족의 ‘1 대 1’ 대결이다.

총 10회를 수행하였다.

사용자 삽입 이미지


   



















 

프로토스

(개선한 인공지능)

테란

(기존 인공지능)

사용한 맵

신 개마고원 ver.2.1

평균 게임 시간

24분 13초

전적

9승 1패

1승 9패

평균 자원 채취량

26401.04

18295.60





    두 번째 실험으로는, 위의 실험에서 기존 인공지능을 사용하는
    테란 종족의 수를 둘로 늘렸다.

    즉, 제안한 인공지능을 사용하는 프로토스 종족 하나와 기존 인공지능을
    사용하는 테란 종족 둘의 ‘1 대 2’ 대결이다.

    총 10회를 수행하였다.

사용자 삽입 이미지




























 

프로토스

(개선한 인공지능)

테란 + 테란

(기존 인공지능)

사용한 맵

신 개마고원 ver.2.1

평균 게임 시간

35분 11초

전적

4승 6패

6승 4패

평균 자원 채취량

33960.46

53859.16





대 저그전도 이와 비슷한 결과를 보였다. ^^ (자세한 것은 논문 및 발표자료 참조)

사용자 삽입 이미지
사용자 삽입 이미지



컴퓨터가 다른 컴퓨터를 1대 2로 이길 수 있다니, 놀랍지 않은가?

실제로 이 패치를 적용해서 실험해 보고 싶은 사람이 있다면, 커멘트 (답글)로 요청하시기 바란다.

원래 계획은, 블리자드 사에 1.14 패치를 보내는 것이었으나 (그 당시 버전은 1.13), 게으름증이 도져서 그렇게 하지 못한 것이 너무 아쉽다. ;;;

아래는 참고 문헌들이다. ^^


[참고문헌]
[1] World Cyber Games Homepage, http://www.worldcybe rgames.com/
[2] StarCraft Homepage, http://www.battle.net/scc/
[3] 한국게임산업협회 설문 조사, http://www.gamek.or.kr/
[4] I. Wright, J. Marshall, RC++: a rule-based language for game AI, Proceedings of the First International Conference on Intelligent Games and Simulation, 2000.
[5] ScAIEdit and Tools, http://www.camsys.org
[6] WinMPQ Download, http://shadowflare.gameproc.com/dw nload.html
[7] Protoss Strategy Homepage, http://gzprotoss.com
[8] StarCraft Strategy Homepage, http://pgr21.com
[9] Protoss Unit Statistics, http://www.battle.net/scc/protoss/ps tats.shtml
[10] Terran Unit Statistics, http://www.battle.net/scc/terran/ust ats.shtml


/* PS: 추가적인 업데이트 및 이후에 연구한 여러 기법들도 곧 오픈할 예정.
        기다려 주시기 바랍니다. ^^

          멀티라인 주석을 남발하는 copyleft yi_sang */
Trackback 1 Comment 240
  1. 이전 댓글 더보기
  2. 2011.05.08 19:19 address edit & del reply

    비밀댓글입니다

  3. kkanchu 2011.08.20 00:58 신고 address edit & del reply

    인공지능에대해서 알고 싶어서... 자료 부탁드립니다 ㅠ (paran7568@naver.com)

  4. kkanchu 2011.08.20 00:58 신고 address edit & del reply

    인공지능에대해서 알고 싶어서... 자료 부탁드립니다 ㅠ (paran7568@naver.com)

  5. 2011.11.24 13:54 address edit & del reply

    비밀댓글입니다

  6. 2012.01.31 08:19 address edit & del reply

    비밀댓글입니다

  7. 정재훈 2012.02.17 18:49 신고 address edit & del reply

    show1067@gmail.com 부탁드립니다.

  8. 2012.08.09 19:21 address edit & del reply

    비밀댓글입니다

  9. 키세르 2012.12.19 13:24 신고 address edit & del reply

    님 WINMPQ로 압축이 안 풀리는거 같습니다. AISCRIPT.BIN 파일을 어떻게 압축을 해체해야 할지 모르겠습니다. 방법을 알려주세요 ㅠㅠ

  10. 재삐 2013.03.27 14:05 신고 address edit & del reply

    인공지능 공부하고있습니다ㅜㅠ
    usopp1004@naver.com으로 보내주시면고맙겠습니다ㅜ

  11. 재삐 2013.03.27 14:37 신고 address edit & del reply

    인공지능 공부하고있습니다ㅜㅠ
    usopp1004@naver.com으로 보내주시면고맙겠습니다ㅜ

  12. 강승현 2014.07.02 17:10 신고 address edit & del reply

    mimiiq500@naver.com으로
    보내주세요

  13. 천재일까 2014.10.26 17:11 신고 address edit & del reply

    aiscript.bin 수정후 스타에 적용시키는것은 어떻게 하나요?

  14. 천재일까 2014.10.26 17:11 신고 address edit & del reply

    aiscript.bin 수정후 스타에 적용시키는것은 어떻게 하나요?

  15. 2014.11.24 23:01 address edit & del reply

    비밀댓글입니다

  16. hyperion 2015.01.11 20:02 신고 address edit & del reply

    아직 보내주시나요? sinzzang525@daum.net으로 보내주시면 정말 감사하겠습니다.

  17. Intense 2015.01.19 22:56 신고 address edit & del reply

    아직 보내주신다면 sonsamuel99@naver.com 부탁드립니다

  18. 홍근선 2015.02.06 00:27 신고 address edit & del reply

    인공지능 파일 받고 싶습니다.

    zardiz@hanmail.net
    으로 부탁드립니다

  19. 2015.02.25 21:56 신고 address edit & del reply

    블로그에 스크랩 해갈께요 감사합니다 !

  20. 루습히 2016.03.17 14:03 신고 address edit & del reply

    pinchocodia@tistory.com
    저도 인공지능에 관심이 큽니다.
    바쁘시겠지만.... 저도 보내주시면 도움이 될듯 합니다.

  21. Rocket 2017.01.24 15:36 신고 address edit & del reply

    tekseon.shin@gmail.com
    스타크래프트 인공지능 개발에 대해 공부하고 있는데요, 보내주시면 정말 감사하겠습니다~