게임에서의 인공지능 추세

제목 : 게임을 통해서 본 Game AI

작성자 : 임영일

 

AI에 대해서 관심을 가지고 있는 분들은 많을  것이다. 공상과학소설이나 SF영화에서 자주 다루어지는 소재이기도 하고 왠지 신비롭게까지 느껴지는 분들도 있을 것이다. 나 또한 이런 환상을 쫓아서 지금은 Game AI에 전념하고 있다. Game에서도 AI는 점점 더 중요한  비중을 차지하고 있다. 사실 초기 Game AI는 거의 전부가 hard coding(if문 등으로 처리)로 처리하는 것이 대부분 이었다. 하지만 이제는 좀 더 체계적이고 학술적인 측면으로 접근하고 있다. 이전까지 AI는 학술적인 연구분야의 전유물처럼 어렵게만 느껴졌지만 점차 우리 생활과 지금 얘기하려는  Game에서도 점점 AI요소가 적용되고 있다.

Game에서 AI가 들어가는 부분은 일단은 유저가 조작하지 않는 NPC(Non-Player Character)를 Control 하는 데에 기본적으로 적용되고 있다. 예전에 나왔던 간단한 2D Game에서는 단순한 랜덤 알고리즘도 많이 사용되었지만 지금의 Game에서는 다양한 장르를 소화할 수 있는 적절한 AI 기법들이 적용되고 있다.

 

해외 게임들을 보면 인공지능의 비중이 늘고 있다는 것을 확인할 수 있다. 하드웨어의 발전에 따른 것도 있을 것이고 게임에서의 재미요소로서 인공지능의 중요성이 높아지고 있는 것도 하나의 이유일 것이다.

 

Figure 1: AI poll results from the GDC 2000 roundtables

게임에서의 CPU 점유율을 예로 들면 2000 GDC에서 발표된 결과에서 1997년도에는 거의 몇 %에 지나지 않던 것이 2000년 들어서면서 거의 30%에 육박하고 있다. 이런 조사결과를 보면 이전에 3D Engine에 투자하던 CPU 점유율을 하드웨어의 발전과 게임에서의 AI의 중요성에 의해서 AI 쪽으로 비중을 실어 주고 있다고 생각된다.

그리고 AI를 전담하는 개발자를 두는 경우가 예전에는 20%정도에 그쳤지만 현재는 80%정도의 개발사가 AI 전담 개발자를 두고 있는 실정이다. 국내에서는 아직 클라이언트에 포함된 정도로 인식하고 있지만 이대로의 추세라면 바뀔 것이 분명하다고 본다.

 

게임에서의 AI는 어떤 한 두 가지의 알고리즘으로 구현되기는 힘들다. 게임의 수준과 장르에 따라 다르겠지만 여러 가지의 AI 기법들을 조합해서 하나의 게임에 필요한 AI를 적용할 수 있는 것이다.

 

그럼 최근 게임들을 통해서 게임에 사용된 AI 기법들을 소개하고 간단한 설명을 해 보도록 하겠다.

 

 

Black & White

피터 몰리뉴가 파퓰러스 등의 게임을 거쳐서 최근에 내놓은 화제작. God 게임의 창시자로서 이 게임에서는 특히 크리쳐의 인공지능이 돋보인다. 이 게임에서는 A-Life(Artificial Life 인공생명) 기술이 도입되었는데 크리쳐 자신의 욕구와 상태에 따라 유저의 행동에 대한 반응이 다이나믹하게 나타난다. 더 놀라운 것은 유저가 크리쳐를 가르칠 수 있다는 점이다. 어떤 행동을 크리쳐에게 반복해서 보여 주었을 경우 그 행동을 똑같이 따라 하는 것과 칭찬과 벌을 병행함으로써 선과 악 양 방향으로 교육이 가능하다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Black & White 에서 사용한 belief/desire/intention architecture

 

위의 아키텍쳐를 살펴보면 크리쳐의 욕망과 의견, 믿음 등이 행동을 결정하는데 영향을 준다. 특히 Opinions에 해당하는 Decision tree를 이용해서 교육의 효과를 구현했다. Black & White에서는 Dynamically Building Decision Trees (다이나믹 하게 제작된 결정 트리)라는 방식을 이용했는데 일반적인 Decision Tree 방식을 응용해서 좀 더 다이나믹한 형태로 바꾸었다.

먼저 Decision Tree 방식을 설명하자면 게임에서 어떤 논리적인 계획을 좀 더 효율적으로 구현하기 위한 구조이다. Hard coding(if 문 등)으로 처리할 수도 있으나 좀 더 효율 적인 구조로 만들어서 코드를 직접 변경하지 않고도 외부에서 변경 가능한 구조로 만드는 것이다.

 

아래의 계획을 Decision Tree로 작성한다고 가정해보자.

플레이어가 가까이 있고 손상정도가 적으면 플레이어에 공격한다.

플레이어가 멀리 있고 연료가 많으면 플레이어가 있는지 수색한다.

위의 계획을 Decision Tree로 나타내면 다음과 같다.

 

 

 

변경 가능한 입력 요소

Distance : 플레이어와 NPC 사이의 거리

Fuel : 남은 연료

Damage : 현재 손상 정도

 

행동

Search : 플레이어 수색

Attack : 플레이어를 공격

 

 

 

노드 실행 시 사용할 수 있는 구조

typedef struct DECNODE_TYP

{

             int operand1, operand2;   // the first  operands

             int comp1;                        // the comparison operator

 

             int operator;                     // the conjuctive operator

            

             int operand3, operand4;   // the second pair of operands

             int comp2;                        // the comparison to perform

 

             ACTION *act_true;           // action lists for true and false

             ACTION *act_false;

 

             DECNODE_PTR *dec_true;            // branches to take if true or false

 

             DECNODE_PTR *dec_false;

} DECNODE, *DECNODE_PTR;

 

이와 같은 Decision Tree는 단순한 방식이지만 응용하기에 따라서 편리하게 사용할 수 있을 것이다.

 

The Sims

EA에서 내놓은 시뮬레이션 장르의 게임이다. Sim City시리즈로 유명한 Will Write가 심혈을 기울여 만든 게임이다. 우리의 실생활을 게임에 재미있게 옮겨놓았는데 각 Character의 욕구가 있어서 그것들을 잘 충족시켜 주어야지 Game Play를 순조롭게 할 수 있다. Sims 에서

특징적인 것은 캐릭터의 욕구에 기반한 AI기법이 사용된 것과 어떤 행동에 대한 정보들을 각각의 오브젝트가 가지고 있는 방식이 독특하다. 욕구 기반의 AI 기법은 Gamasutra에도 소개되었지만 내부상태에 대한 욕구한계점(threshold)을 조절해서 적절한 효과를 얻을 수 있는 방식으로서 생물의 행동과 유사하도록 그 한계점들을 적절히 조절하면서 적용했다.

오브젝트가 이벤트를 발생시키는 방식을 Will Write는 smart terrain이란 말로 표현을 했는데 그 비유가 적절한 것 같다. 주체가 아니라 객체인 Object들이 각각 주체가 해야 할 행동들에 대한 이벤트 정보를 발생시킨다. 말하자면 배고픈 캐릭터가 지나가면 냉장고에서 꺼내 먹어라라는 명령을 내리는 것과 같은 방식이라고 말할 수 있다. 어떻게 보면 웃기지만 아주 적절하게 그 효과를 보고 있다고 말할 수 있다.

이 게임은 A-Life 와 Fuzzy-State Machine을 이용한 AI를 선보이고 있다. 특히 이 게임에서는 smart terrain이라는 Will Write의 말처럼 각 오브젝트들이 상태와 행동을 발생시키는 방식. 즉 object-oriented 방식으로 각 오브젝트가 캐릭터에게 여러 가지 행동에 대한 이벤트를 발생시키는 event-driven 방식이다.

 

Black&White나 The Sims에 A-Life라는 말이 언급되는데 조금 설명을 해보자면 지금까지의 AI는 위에서 아래로 그러니까 위에서 계획한 대로 아래에서 행해지는 계획되지 않은 행동은 일어날 수 없는 방식인데 A-Life 는 밑에서 위로라는 말로 표현되는데 각각의 세부적인 단순한 규칙들이 모여서 하나의 커다란 특성을 나타내는 것으로 정해주지 않은 행동이 창발적으로 발생하는 특징을 가지고 있다. 좀 더 자연의 생물을 흉내낸 방식이라고 할 수 있다.

 

Half Life

Half Life는 게임 중에서도 명작으로 꼽히는 게임이다. 이 게임은 무엇보다 스토리와 연출로 플레이어들을 사로잡았다. 이 게임 또한 AI가 Game에 재미를 더해 주고 있는데 몬스터나 특수부대원들이 나올 때면 정말 만만한 상대들이 아니다라는 느낌을 받을 수 있는데 그 들의 움직임 또한 모두 AI로 처리되었다.

Half Life에서 적용한 방식은 일련의 행동들을 Schedule로 묶어서 처리한 방식인데, 이것은  HFSM(Hierarchy Finite State Machine)이란 방법으로 볼 수 있는데 FSM을 개념에 따라 계층을 나누어 놓았다고 볼 수 있다. 하나 하나의 구체적인 행동들을 Task State라고 하면 그 task들이 여러 개 모여있는 State가 Schedule State인 것이다.

 

 여기서 간단하게 State Machine이란 개념을 소개하자면 State들을 어떤 조건에 따라 연결해 놓은 것이다. 각각의 State에는 여러 가지가 들어갈 수 있다. 캐릭터의 내부상태가 될 수도 있고 행동 패턴이 될 수도 있고 심리 상태가 될 수도 있다. 이런 각각의 State들이 어떤 조건에 따라 연결되어 있는 것이 State Machine 이다.

 

State Machine 중에서도 유한한 개수의 상태를 가진 것을 FSM(Finite State Machine)이라고 하는데, 이 것의 한 예를 들어 보겠다.

 

 

 

 

 

 

 

 

몬스터의 상태전이 규칙

 

현재 상태

입력

출력 상태

보통

플레이어 등장

불쾌

보통

플레이어의 공격

흥분

흥분

몬스터 다침

분노

흥분

몬스터 치료됨

보통

분노

몬스터 다침

광분

분노

몬스터 치료됨

불쾌

광분

몬스터 다침

광분

광분

몬스터 치료됨

분노

불쾌

플레이어 떠남

보통

불쾌

플레이어의 공격

분노

불쾌

몬스터 치료됨

보통

 

위의 전이 규칙을 FSM으로 표현하면,

 

 

 

                                                        

위의 예에서 보듯이 FSM은 현재의 State에서 입력값에 따라 다음의 State가 결정되는 형태로 동작한다.

 

다음은 FSM의 하나의 상태를 표현하는 데 쓰이는 클래스 이다.

 

class FSMstate

{

unsigned  m_usNumberOfTransistions;                   // 이 상태가 담을 수있는 상태전이// 들의 개수

    int  *m_piInputs;                                                    // 상태전이를 위한 입력 배열

    int  *m_piOutputState;                                           // 출력 상태 배열

    int  m_iStateID;                                                      // 이 상태의 고유 ID

 

public:

    // 생성자는 이 상태에 대한 ID와 이 상태가 지원하는 상태 전이들의 개수를 받는다.

    FSMstate (int  iStateID, unsigned  usTransitions);

    // 소멸자는 할당된 모든 배열들을 해제한다.

    ~FSMstate ();

 

    // 상태 ID를 돌려준다.

    int GetID () { return  m_iStateID; }

    // 배열에 하나의 상태 전이를 추가한다.

    void AddTransition (int iInput, int iOutputID);

    // 배열로부터 상태 전이를 제거한다.

    void DeleteTransition (int iOutputID);

    // 상태 전이를 일으키고 출력 상태를 돌려준다.

    int GetOutput (int iInput);

}

 

 

Creature

내가 처음으로 게임 인공지능에 대해서 대단하다고 느낀 게임이다.

이 게임에서의 AI는 흉내내기를 넘어서서 모델링 수준에 가깝다고 할 수 있다.

이 게임에서는 생물을 모델링하기 위한 갖가지 AI Algorithm들을 사용하고 있는데, 일단 이 게임에서는 Character들 간에 교배도 가능하다는 점이 가장 흥미롭다. 특히 이 교배라는 것을 구현하기 위해 Genetic Algorithm(유전자 알고리즘)을 사용했는데 여기서 Character의 여러 가지 특징들을 gene(유전자)에 저장하고 이 정보들을 Genetic Algorithm을 이용해 교배할 때 적절히 섞어줌으로써 실제 생물에서 볼 수 있는 교배의 효과를 구현했다.

이 게임은 앞에서도 얘기했듯이 생물을 구현하려고 노력했다. 개발자에 따르면 교육적 효과도 기대하면서 제작했다고 한다. 충분히 그럴 것이 캐릭터들은 내부에 갖가지 욕구와 질병, 영양소(비타민 등)을 가지고 있고 그것에 따라 여러 가지 반응들을 나타낸다. 그리고 크리쳐가 사고 판단할 때 인간의 뇌를 흉내낸 Neural Net Algorithm을 간단하게 적용했는데 이 또한 굉장하게 느껴진다. Neural Net(신경망 이론)은 인간의 뇌의 학습, 추론 원리를 흉내낸 알고리즘으로서 실제 학계에서는 패턴인식에 주로 사용하고 있다.

 

참고 자료

1)      GAME PROGRAMMING GEMS Mark Deloura 외 공저/류광 역

-> FSM에 대한 내용 참조

2)      tricks of the WINDOWS Game Programming Gurus Andre LaMothe 지음,     이주리 역, 비너시안 개발팀 감수

-> Decision Tree에 대한 내용 참조

3)      http://www.gamasutra.com/features/index_ai.htm

-> Game AI의 추세 참조

4)      http://www.gameai.com/

-> Game별 AI의 특징 참조

5)      http://www.gpgstudy.com/gpgiki/gpgiki.php/AILove.html

-> 욕구기반 AI 내용 참조, Black & White AI 참조

6)      인공생명 스티븐 레비 지음, 김동광/과학세대 옮김 출판사: 사민서각

-> 인공생명에 대한 설명 참조

7)      Game Developer Magazine   AUGUST 2001

-> Black & White AI 참조

8)      http://www.creatures.co.uk/

-> Creature 게임 AI 참조