Game AI – Game Design 2015

http://cafe419.daum.net/_c21_/bbs_search_read?grpid=zzq0&fldid=5JRS&datanum=14&contentval=&docid=zzq0%7C5JRS%7C14%7C20090423014816&q=%B0%D4%C0%D3%C1%A6%C0%DB%B4%C9%B7%C2

AI의 등장과 목적

대부분의 사람들이 동의하듯이 게임의 목적이 ‘재미’라는 그 자체만으로 목적이 되는 순간부터 AI는 필연적으로 발생
AI의 발생이 필연적이라 할 수 있는 이유는 게임의 “재미” 자체가 자신외의 객체와의 커뮤니케이션에 기반하고 있기 때문
여기서 객체라 함은 자신 이외의 플레이어(사람일수도 있고 AI일수도 있다), 게임 속의 세계, 게임 속에서 인정되는 유효사물(게임 속에서 게임 플레이에 영향을 미칠 수 있는 모든 사물)을 포괄하는 개념
게임 플레이어는 게임 내에서 유효사물을 이용하여 게임 속의 세계가 정의하는 룰에 따라서 자신 이외의 플레이어와 커뮤니케이션을 통하여 유발될 수 있는 다양한 “재미”를 경험하게 되는 것
전통적인 보드 게임의 관점에서 게임을 플레이할 수 있는 방법은 3가지
- 첫째는 같이 플레이를 하고 싶어할만한 가족이나 친구 혹은 손님을 기다리는 것
- 둘째는 같이 플레이를 하고 싶어할 만한 친구나 손님을 방문하는 것
- 셋째 방법은 혼자서 하는 것
이러한 전통적인 게임들이 컴퓨터라는 새로운 매체와 결합하면서 나타난 가장 큰 특징은 게임을 혼자서 플레이하게 되었다는 점
앞에서 예를 든 바와 같이 약간의 위험과 수고를 감수한다면 전통적인 게임들 또한 혼자하기가 불가능하지는 않았지만 컴퓨터와 결합한 초기 게임들은 몇 가지 이유들(기술적 문제와 같은..) 때문에 “혼자하기(Single Play)” 형태로 구현
게임을 혼자 하게 되면서 본격적으로 게임 속에 AI라 불리는 요소들이 등장하게 되었던 것
물론 아주 당연하게도, AI의 등장은 혼자하기에서 유발되었지만 지금의 “여럿이하기(Multi Play)” 전용 게임에서도 AI는 필수요소
핵심은 AI가 없이는 게임 내에서 커뮤니케이션이 불가능하다는 것
협의적인 측면으로 국한해서 앞의 세 가지 요소 중에 다른 플레이어들만으로 생각한다고 해도 그 플레이어(AI 플레이어)는 우리의 사용자를 즐겁게 하기 위해서 우리의 사용자와 경쟁하거나 협력하거나 심지어는 훼방을 놓을 수 있어야 하는 것
앞에서 언급했듯이 게임에서의 AI의 역할은 여러 가지
- 첫째, 가장 중요한 것은 게임의 상대 역할을 수행하는 것
  - AI는 게이머에게 무조건 이기는 것이 목적이 아니라 유사한 수준의 상대 역할을 수행하는 것
- 둘째, AI는 게임의 보조 역할을 수행한
  - 게임 내에서 플레이어의 보조 역할을 하는 캐릭터를 AI가 담당
- 셋째, NPC의 역할을 담당
  - NPC는 주인공과 상호 작용을 하여 실제로 NPC는 지능적인 객체라는 인식을 게이머에게 심어주어야 함
- 끝으로, AI는 애니메이션 동작의 제어를 담당
본질적으로 AI는 사용자가 재미있는 커뮤니케이션을 경험하기 위한 도구이며 영리한 AI를 만드는 것뿐만 아니라 재미나는 AI를 만드는 것이 중요

AI의 적용 분야와 최적화 전략

AI의 적용 분야

길찾기
- 여러 장르의 게임에서 가장 흔히 접할 수 있는 문제는 타일 혹은 3D기반의 게임 환경(world)에서 목적지까지 이동할 수 있는 길(path)을 찾는 것
- 길찾기 시스템은 캐릭터 행동의 특정 측면들을 보장하는 역할
  - 예를 들어서 캐릭터가 장애물들 사이에 끼어서 움직이지 못하는 상황이 벌어져서는 안 될 것
  - 또한 플레이어가 보기에는 너무 명확한 길을 캐릭터가 쓸데없이 멀리 돌아가는 일도 일어나서는 안 될 것
- 길찾기는 많은 게임들에서 AI의 기초적인 기능이며 특히 전략시뮬레이션(Blizzard의 스타크래프트 게임과 같은..)과 같은 장르에서 목적지를 마우스로 알려주면 가장 빠른 길을 찾아 해당 장소로 이동해야하는 문제로, 거의 모든 게임에서 필요
- 이에 대한 해법으로 A*알고리즘을 주로 사용하는데, 이는 경로 찾기 문제에서 비교적 빠른 시간에 목적지까지의 최적 경로를 찾아줌
- 목적지까지 가는 도중에 게임 진행 중 발생할 수 있는 게임 환경(world)의 변경( 예를 들어, 유일한 경로에 플레이어가 건축물을 건설하여 경로를 차단하는 경우)되는 경우는 A* 알고리즘만으로는 모든 경로 찾기 문제를 해결 할 수 없으며 추가적인 방법이 요구
- 그러나 대부분의 경우 A* 알고리즘과 다른 해법을 병행하여 해결 가능하며 또한 현재 가장 AI 분야에서 가장 많은 연구가 진행된 분야
- 다음은 바닥 격자 공간에서의 간단한 길찾기 방법 예
  - ㉠ 각 격자 단위로 A* 알고리즘을 이용하여 이용 가능한 노드를 찾음
  - ㉡ 직선 이동을 위해 시작점에서부터 직선으로 갈 수 있는 최대 지점까지 노드를 검색해서 그 노드까지 직선으로 이동
  - ㉢ 쉽게 인근 구역(region)들을 찾기 위해 각 구역들의 연결 상태들을 구성
- 다음은 Dijkstra 알고리즘(그래프 이론)을 이용한 최단거리 길찾기의 예
  - Dijkstra 알고리즘은 각각의 선분에 명백한 가중치를 적용하고, 시작 위치와 다른 모든 노드들에게 갈 수 있는 최단 경로를 제공
  - 이 알고리즘에 나타나는 그래프의 각 노드는 부모 노드와 최적 비용값을 데이터로 갖음
  - 최초에 모든 노드들을 위한 보무 값들은 올바르지 않은 값을 가지며 최적 비용은 무한대(infinity)로 설정되며 시작 노드의 최적 비용은 0으로 설정
  - 최적의 경로를 찾기 위한 방법
    - 우선 반복적으로 노드를 대기 행렬로부터의 가장 낮은 최소 비용으로 대체
    - 그리고 그것들의 각 선분에 대해서 어느 선분에 대한 목표 노드를 위한 현재의 최적 비용이 현재 노드의 비용에 선분의 비용을 더한 것보다 크면 목표 노드를 향한 더 나은 경로를 찾아낸 것
    - 그리하여 목표 노드에 대한 비용을 갱신하고 부모 노드의 정보를 갱신하며, 그들을 현재 노드로 향하게 함
    - 다음은 Dijkstra 알고리즘을 위한 의사코드

struct node
	vector< edge > edges
	node parent
	real cost

struct edge
	node dest
	real cost

while( priority_queue is not empty )
	node curr = priority_queue.pop
	for( all eges leaving curr )
		if( edge.dest.cost > curr.cost + edge.cost )
			edge.dest.cost = curr.cost + edge.cost
			edge.dest .parent = curr

세부 과정은 SKIP

지적 행동
- 게임에서 지적인 행동을 일일이 정의 할 수는 없음
- 그러나 앞서 언급한 길찾기 역시 게임에 등장하는 플레이 가능한 유닛들의 지적인 움직임을 위해 반드시 요구되는 부분 중 하나
- 만약 이동 가능한 경로가 있음에도 불구하고 게이머가 원하는 위치로 유닛이 제대로 이동하지 못한다면 게이머는 더 이상 게임을 진행하고 싶지 않을 것
- 또한, 게이머는 게임에서 상대편과 시시한 플레이를 하기를 원치 않을 것
- 따라서 게임의 상대편이 지능적인 행동을 하도록 게임을 제작하여 게임에서 큰 즐거움을 느끼도록 해야함
- 예를 들어, 레이싱 게임의 경우 나와 함께달리는 차량이 너무 느리다거나 너무 앞서 달린다거나 해서는 플레이어의 흥미를 유발할 수 없게 됨
계획
- 게임이 복잡해지고 고도의 지능화된 캐릭터가 등장할수록 캐릭터는 현재의 행동이 앞으로 어떠한 영향을 주는지를 감안하여 전체적인 계획을 세우고 진행
- 예를 들어 전략시뮬레이션 게임에서 상대편이 취할 수 있는 행동(상대편의 종족 형태, 주 병력의 공격 유형 등)이나 특징을 감안하여 전체적인 대응 전략(상대편 주 병력의 취약 유형 등을 파악)을 계획하여야 함

AI 최적화 전략
- 복잡한 AI는 상당한 연산 능력을 요구하며 수많은 자동화 에이전트들이 지능적으로 게임 세계에서 활동하도록 하려면 더욱 더 많은 연산 능력이 필요
- 원래 게임은 기본적으로 실시간에 병렬적인 기능이 크게 요구되는 응용프로그램이지만 AI의 분야는 특히 요구 됨
- 모든 AI 에이전트들이 동시에 자신의 생각을 가지고 움직이는 것처럼 보이게 하는 것은 여전히 어려운 문제이며 이를 위한 AI 최적화는 비교적 미개척 분야
- 그러나 거꾸로 생각하면 이러한 어려움은 병렬성을 AI 분야의 새로운 영역으로 만드는 요인이라 할 수 있음
- 이러한 병렬성은 AI 에이전트들의 다른 고유 특성들과 마찬가지로 AI에서 요구되는 최적화 대상이 될 수 있음

전략 #1 : 폴링 대신 이벤트 주도적 행동을 사용
- 이론적으로, 자동화 에이전트는 자신의 세계를 끊임없이 관찰하고 그에 맞게 행동해야 함
- 게임이 진행되는 매 프레임마다 에이전트들은 자신이 반응해야 할 사건 또는 객체들을 감지
- 이러한 접근 방식은 엄청난 양의 중복된 계산이 발생한다는 점
- 즉 이러한 개별적인 폴링(polling)은 자원 낭비가 심하다고 말할 수 있음
- 이에 대한 대안은 “이벤트 주도적(event-driven) 기법‘을 사용하는 것
  - 예로 골프게임을 들어보자. 골퍼가 버디샷을 준비하고 있으며, 이를 수백명의 관중들이 지켜볼 경우, 만약 공이 홀컵에 들어갔을 때 공이 ”나 들어갔어“라는 메시지를 보낸다고 하자
  - 이는 모든 관중이 공이 움직이는 내내 공을 주시하도록 하는 것 보다 훨씬 더 효율적
  - 만약 이렇게 하나의 공이 아닌 정말 많은 수의 객체가 동시에 발생할 경우(전투에서 수많은 병력이 전쟁을 할 경우와 같은..)엔 더더욱 큰 도움이 될 것
전략 #2 : 중복된 계산을 줄임
- 게임에는 수많은 AI 에이전트들이 존재하며, 그들은 수시로 아주 많은 계산을 수행한다. 이러한 독특한 환경에서의 속도 및 효율적인 AI 처리를 위해서는 고가의 하드웨어 장비가 지원되지 않는 이상 하드코딩으로 극복하거나 지능적 처리 방식을 사용해야 함
- 실제로 이 전략의 목적은 AI 에이전트들이 자신의 계산, 처리 결과를 공유하도록 만들어 불필요한 중복 계산을 줄이는데 그 목표
- AI 에이전트들 각각이 가지고 있는 정보를 공유할 수 있다면 계산 시간을 상당히 줄일 수 있을 것
- 간단한 예로 길찾기
  - 전략 시뮬레이션 게임(예 : BLIZZARD의 스타크래프트)에서는 수많은 유닛들이 존재하며 플레이어는 이를 마우스와키보드를 이용해 제어하게 되며 이때 한꺼번에 많은 수의 유닛을 맵의 다른 한쪽으로 이동하도록 명령
  - 각각의 유닛들은 해당 명령에 따라 길찾기 수행을 통해 이동하게 되며 이때 모든 유닛이 길찾기를 수행하는 것 보다 한 유닛이 길찾기를 수행하고 나머지는 그 유닛의 뒤를 따라가는 것이 훨씬 더 효율적일 것
  - 이럴 경우 길찾기 수행의 횟수가 급감하여 계산상의 시간을 상당히 줄일 수 있음
전략 #3 : 관리자를 통한 협동의 집중화
- AI를 좀더 빠르고 간단하게 만들기 위한 방법의 하나로 게임내의 AI 에이전트들을 하나의 집단(Group)으로 묘사하는 것
- 하나의 집단에는 그 집단을 이끄는 역할을 가진 관리자 에이전트가 있을 수 있으며 게임 흐름상의 일부(특히 각 집단별 행동이 요구되는 경우..) 결정권을 관리자에게 위임하는 것
- 실제로 지시된 역할을 수행하는 것은 관리자 역할을 맡고 있는 에이전트의 AI가 판단하게 됨
- 예를 들어, 축구 게임에서 “3-5-2” 시스템으로 진형을 갖춘다고 했을 때, 공격수(3)와 미드필드(5), 그리고 수비수(2) 역할의 에이전트가 존재하며, 이들이 효과적인 공격과 수비를 펼치기 위해 진형별 관리자를 둘 수 있음
- 이와 같은 방법은 공격수가 공격에만 전담하도록 할 수 있으며 이를 통해 수비수나 미드필드와의 역할 혼동을 피할 수 있고 자칫공만을 쫓아 몰려다니는 “동네 축구”를 탈피할 수 있는 축구 게임을 만들 수 있음
전략 #4 : 처리 부담을 여러 프레임들로 분산
- 이 전략은 길찾기와 같은 CPU의 자원을 많이 소비하는 AI 부분에 사용하면 적절
- 길찾기의 대상이 되는 검색 공간은 몇 프레임만에 크게 변하는 것이 아니므로 계산을 여러 프레임으로 나누어 수행 가능
- 이러한 접근방식은 프레임 당 처리 부담을 줄이는데 효과적
전략 #5 : 힘든 일은 미리 처리
- 고도의 물리학 엔진이 탑재된 게임들이 대거 등장
- 이러한 게임의 특징은 아주 많은 계산이 요구되는 동작을 주로 수행한다는 것
- 비행 시뮬레이션이 그 대표적인 예
  - 이러한 게임은 종종 실시간으로 처리하기엔 너무 어려운 문제에 직면하기도 한함
  - 이러한 문제를 해결하기 위해 복잡한 계산을 미리 수행하여 테이블에 담아주고 참조하는 방식을 사용하는 등의 기법을 사용하여 실행 시점에서 단 한순간의 조회만으로 의사 결정과 판단에 필요한 정보를 얻을 수 있게 만드는 것이 가능
  - 이러한 전략은, 단 몇킬로바이트의 데이터로 엄청난 CPU 자원을 절약할 수 있게 해준다는 점에서 매우 강력한 최적화 전략이라 할 수 있음
이 외에도 AI의 최적화를 위한 전략들은 아주 많음
실제로 AI 시스템에서 직면할 수 있는 문제들을 최적화하려면 좀 다른 시각에서 문제를 바라보는 것이 도움이 될 것

AI 구현 기술

FSM과 FuSM?
- FSM(Finite State Machine)
  - FSM이라는 용어 그대로, 유한한 개수의 상태(state)들로 구성된 기계를 말하며, 가장 널리 사용되는 인공지능 처리 방식
  - 상태 기계(state machine) 즉, 정확히 말하면 유한 상태 머신(FSM)은 장치나 어떤 기술의 순차 로직 혹은 제어 기능에 단순하면서도 정확한 설계를 가능하게 함
  - FSM에 대한 아이디어는 유한한 상태(state)들을 가진 전자 제어 기계들로부터 얻어졌음
  - 여기서 상태(state)라는 말은 하나의 조건이라고 생각하면 됨
  - 놀라운 사실은, 그러한 대부분의 시스템(일종의 간단한 전등 스위치 혹은 게임 내의 지능적인 캐릭터들 등을 포함)들이 유한한 상태들로 표현 가능하다는 것
  - FSM의 알고리즘 자체는 간단하기는 하지만, 상태라는 말을 결코 간과해서는 안됨
  - 거의 모든 시스템들이 상태들로 표현될 수 있음
  - 그렇기 때문에 FSM은 시스템을 제어하는 알고리즘으로 간단하면서 가장 많이 사용됨
  - FSM은 하나의 입력(일반적으로 조건이 변화하는 것을 의미)을 받고 그에 의거해서 현재 상태로부터 다른 어떤 상태로 전이(transition)
  - 간단한 예로, 전등 스위치를 하나의 상태 기계라고 한다면, 스위치의 상태가 “ON”과 ”OFF” 상태가 있을 수 있으며, “Down” 또는 “Up” 이라는 입력이 들어가면 전등 스위치의 상태가 바뀌는 것
  - 게임에서 FSM을 사용할 경우
    - 우리가 알고있는 유명한 게임 중 퀘이크(Quake)도 NPC(Non Player Character)의 행동 제어에 FSM을 사용하였으며, 이와 같은 장르의 게임인 Half Life 역시 계층적 FSM(Hierachical FSM)을 사용한 것으로 알려져 있음
    - 일반적으로 게임 내에서 캐릭터의 행동이나 감정 상태등을 FSM으로 표현 가능
    - 여러 캐릭터 혹은 하나의 캐릭터에 대한 현재 상태가 주어지고 이후 외부의 자극등에 의하여 상태가 바뀔 경우 현재 상태에 따라 그에 대한 반응 방법이 결정
    - 자극과 같은 외부의 상황이 바뀌면 현재 상태가 다른 상태로 전이
    - 또한 전등 스위치에서와 같이 캐릭터는 특정 상태에 있을 경우에는 항상 같은 방식으로 행동
    - 여러 캐릭터가 몇 개의 상태로 주어질 때 캐릭터의 현재상태에 따라 외부에 대처하는 방식이 결정
    - 즉, 외부의 상황이 변화하게 되면 현재상태도 FSM에 의해 다른 상태로 전이
    - 또한, 캐릭터는 특정한 상태에 있을 경우 항상 같은 방식으로 행동
  - 결과적으로 FSM의 전반적인 아이디어는 매우 간단하고 단순하지만, 그 활용 범위와 용도는 너무나도 다양하다 할정도로 시스템 제어에 근본이 되는 알고리즘이라는 것을 알 수 있음
    - 실제로 단순히 switch() 구문 혹은 if 구문을 사용하여 프로그래밍되는 것이 전부
    - 그래서 FSM은 특별한 인공지능 기능을 요구하지 않는 게임에서 많이 사용하며 만약 설계/구현 과정에서 상태의 수가늘어나게 되면 switch() 구문을 사용하는 대신 배열을 사용하여 원하는 루틴에 빠르게 접근
    - FSM의 의사코드 구현
Switch(creature_state) case STATE_ATTACK : 플레이어 쪽으로 이동 20%의 확률로 포 발사 case STATE_RETREATE : 플레이어와 반대 방향으로 이동

FuSM?(Fuzzy State Machine)
- FuSM?은 FSM의 단점을 개선하기 위한 방법으로 퍼지 이론을 FSM의 상태 전이를 위한 조건 판단에 응용한 것
- FuSM?은 상태의 입력과 출력에 퍼지 함수를 적용하여 랜덤 기능을 추가함으로써 동일한 입력에도 다른 상태로의 전이를 얻을 수 있는 방법
- 따라서 퍼지 상태 기계는 “그렇다”와 “아니다”라는 이산적인 상태 대신 “매우 그렇다”, “그저 그렇다”, “다소 아니다”, “매우 아니다”와 같은 상태들을 표현
- 이것은 하나의 (다분이 정량적이지만) 빛을 분산시키는 스팩트럼과 같은 원리라 보면 이해가 빠를 것
- 실제로 FuSM?을 게임에 이용한다면, 예를 들어 하나의 NPC(여기서는 자연 유닛이라 본다면) 는 플레이어에 대해 단순히 “귀찮다”, “조금 귀찮다”, “매우 귀찮다”와 같은 상태로의 전이가 가능한 것
- 이는 또한 게임 안의 상태들이 반드시 구체적이고 이산적일 필요가 없음을 뜻하기도 함
- 일반적으로 FuSM?은 하나의 상태를 표현하기 위해 일정한 범위를 갖는 실수로 표현
- 보통 실수의 범위는 0.0에서 1.0사이의 범위를 갖지만 이것이 퍼지 이론에서 말하는 퍼지의 값을 표현하기 위한 유일한 방법은 아님
- 따라서 사용하고자 하는 수들을 퍼지 값이라고 규정짓고 사용할 수 있음
- 그렇다면 왜 게임에서 FuSM?을 사용하는가? 우리는 게임에 퍼지 논리를 적용시킴으로써 좀더 추상적인 개념을 표현할 수 있으며 이를 통해 게임내의 객체(NPC와 같은..)들로부터 좀더 재미있는 반응을 만들고 좀더 예측하기 힘들게 만듦으로써 게임 전체의 재미를 향상 시킬 수 있기 때문
- 실제로 게임 플레이어는 마주치는 같은 종류의 NPC 혹은 몬스터(monster)들의 각기 다른 행동 패턴을 느낄 수 있게 되며 이로써 게임은 더욱 더 흥미진진해지는 것
- 실제로도 같은 케릭터가 다르게 보이기도 함
- 다양한 게임 장르들에서 FuSM?은 유용하게 사용되고 있음
- RPG 게임중 하나인 디아블(DIABLO)로에서 캐릭터는 적 유닛들로부터 입은 각종 공격 피해로 인해 행동이 느려진다거나 체력이 줄어든다거나 하는 변화를 수시로 겪음
- 이는 상당히 많은 상태값을 요구하는데 실제로 적이 사용한 무기 혹은 마법의 능력치에 따라 피해의 크기와 지속 시간등이 다채롭게 변함
- 레이싱 게임중 하나인 니드포스피드(Need for Speed)에선 경기 도중 코스 이탈을 하거나 차량이 부서지거나하면 피해 위치와 규모에 따라 게임의 속도와 핸들링 등에 다양한 영향을 주게 됨
- 이는 게임의 진행을 좀더 신중하게 하게끔 유도하며 사실감을 더욱더 느끼는 효과까지 제공
- 퍼지논리를 컴퓨터를 통해 게임에 적용하는 것은 그리 어려운 것이 아니며, 퍼지의 특성이 적용될 수 있는 다양한 상태의 결정이 요구되는 곳에서 퍼지 논리는 게임의 한 부분으로서 완벽하게 사용 가능

결정 트리
- 결정트리는 귀납적 학습을 위한 실용적인 방법으로 트리 모양의 구조로 결정의 셋을 나타냄
- 이 결정트리는 데이터 셋의 분류를 위한 규칙을 생성
- 또한 학습 과정을 거쳐 생성된 결정트리를 규칙의 집합으로 이해 가능
- 앞서 설명한 FSM은 상태 수가 많아지면 여러 문제점이 나타남
- 따라서 이를 극복하기 위한 간단하면서도 효과적인 방법이 요구되며, 이중 가장 널리 사용되는 방법이 결정트리
- 결정트리는 현재 상태에 따라 수행할 기능을 트리 형태로 나누어 해당하는 행동을 처리하도록 하는 방법을 말함
- 결정트리는 학습의 과정을 거쳐 트리를 생성하고 이를 규칙의 집합으로 사용하므로 미리 정해진 상태가 없기 때문에 매 프레임마다 게임 로직을 처리해야하는 부담이 있지만, 트리의 구조를 잘 선택하면 게임 로직에 사용되는 시간을 최소로 줄일 수 있기 때문에 널리 사용
- 결정트리는 if then else 구문을 반복적으로 사용하므로 프로그래머의 이해가 빠르고 코딩의 어려움이 없음
- 따라서 상태수의 제한이 없으나 비교적 적은 수의 환경변수를 사용할 때 편리
- 또한 얻어진 결과가 하나 또는 아주 적은 수의 값만을 사용하는데 적합
- 일반적으로, 결정트리는 FSM보다 많은 코딩을 요구하며 FSM 보다 CPU 점유율이 높음
- 게다가 규칙을 만들기 위한 많은 사례를 미리 준비해야하는 단점이 있으며, 이후에 트리의 최적화 과정이 반드시 요구

규칙 기반 시스템(Rule Based System)
- 규칙 기반 시스템은 Allen Newell 과 Herb Simon의 기본 아이디어로부터 도출
- 실제로 규칙기반 시스템은 전통적인 인공지능 학문에 기반을 둔 기법으로 전문가 시스템에 활용
- 규칙 기반 시스템의 기본 개념은, 많은 규칙을 나열하고 현 상황에 해당하는 즉 현 상황에 가장 적합한 규칙을 골라 내어 이 규칙에 따른 결과를 얻는 것을 말함
- 기본개념에서도 알 수 있듯이 어떠한 규칙이 가장 적합한 규칙인지 를 판단하는 것이 중요하며 또한 해당 규칙을 어떻게 생성하였느냐가 시스템의 중요 이슈
- 규칙기반 시스템에서의 규칙 선택은 임의 함수를 조건으로 사용 시 Hashing 함수는 사용이 불가능하며 모든 규칙에 대해 차례로 테스트
- 따라서, 가장 먼저 발견된 규칙을 선택하는 경우가 대부분이며 규칙을 매칭하기까지의 시간은 규칙의 수와 조건의 복잡도 그리고 매칭되지 않는 규칙의 수에 영향을 받음
- 규칙기반 시스템은 FSM이나 결정트리에 비해 높은 지능을 구현할 수 있으며 인간의 사고방식을 그대로 적용 가능 하나 규칙의 수가 늘어날수록 해당 규칙을 찾아내는 매칭 기능에 많은 시간이 소요되므로 단순한 지능만으로 구현 가능한 게임보다는 복잡한 조합으로 이루어진 RPG 게임과 같은 장르에 필요한 시스템
- 실제로 규칙 기반 시스템은 “Baldur‘s Gate”라는 게임의 Infinity 엔진에 처음 사용된 것으로 알려져 있음

스크립트 언어
- 게임 디자이너는 해당되는 인공지능 로직을 프로그래머에게 전달하여 이를 C/C++ 프로그램 언어를 이용하여 프로그램 코드에 포함
- 이때 전체 프로그램 로직에 변화를 주지 않고 해당 캐릭터의 행동만을 바꾸고자할 경우가 생기며 이는 자칫 전체 프로그램을 다시 컴파일해야 할 필요성이 생김
- 따라서 인공지능 구현 기능을 메인게임 프로그램에서 분리하여 스크립트 언어로 표현하는 방식이 등장
- 앞서 설명한 바와 같이 UnrealScript?라는 언어를 사용하여 엔진 이외의 코드를 프로그램 할 수 있도록 하였음
- Quake-C는 단순화시킨 C언어와 같은 느낌인데 반하여 UnrealScript? 언어는 Java 언어의 분위기를 풍김
- 엔진 코드 개발에 사용한 C++ 언어는 인공지능 처리가 어렵다는 것
- 인공지능 처리를 위한 코드는 한 프레임 진행시간에 처리할 수 없기 때문에 이러한 문제를 해결하기 위해서는 스파게티 같은 코딩을 하지 않을 수 없음
- UnrealScript?에서는 상태(state)라는 개념을 두어 특정 상태에서 처리해야 하는 루틴을 해당 상태에서 코딩 처리함
- 이 코드는 하나의 프레임 진행시간 이상 수행할 수 있는 별도의 스레드를 사용하여 처리
- 일반적인 스크립 언어는 기능을 단순하게 하기 위해 객체지향에서의 가장 큰 장점인 상속기능을 지원하지 않으나 UnrealScript?는 상속 기능을 지원하여 여러 가지 인공지능이나 게임로직의 문제를 해결
- 등장하는 캐릭터의 행동과 네트워크 프로토콜의 연결은 대부분 UnrealScript? 언어를 사용
- 특히 캐릭터의 특성을 상속할 수 있도록 하여 저급 수준의 캐릭터 코드를 보스급 몬스터가 상속하며 필요시 이를 오버라이드(Override) 할 수 있도록 하여 전체 코드 개발에 생산성을 높이고 에러 발생의 가능성을 줄이고 있음
- 매우 발전된 수준의 Creature 나 Bots의인공지능을 처리하기 위해 스크립 언어가 설계되어 있어 Bots의 움직임과 무기 그리고 인벤토리를 어떻게 이용하는지 알고 있음
- 그러나 Quake와 Unreal의 스크립트는 인공지능만을 위한 언어는 아니며 네트웍 지원을 기본 기능으로 하고 있어 엄밀한 의미의 인공지능 스크립언어로 보기는 어려움
- 인공지능 기능만을 위한 스크립트 언어는 “Baldur‘s Gate”에서 사용된 스크립트 언어와 ”Age of Kings”에 사용된 스크립트 언어를 들 수 있음

영향력 분포도(influence map) 기법
- 영향력 분포도 기법은 전략적 판단을 내리는데 꼭 필요한 게임 AI 기법으로, 많은 게임들에서 유용함이 입증
- 영향력 분포도는 주로 전략 게임에 쓰이나, 전술적 분석이 필요한 다른 종류의 게임들에서도 유용하게 쓰일 수 있음
- 영향력 분포도란 AI 에이전트가 세계에 대해 지니고 있는 지식을 공간적으로 표한 것
- 실제로 게임 환경의 물리적/지형적 표현과 현재의 게임 상태(유닛 및 조형물의 배치등)에 기반해서 전략적 결정에 필요한 정보만을 적절히 추출한 것이라 할 수 있음
- 컴퓨터 플레이어는 영향력 분포도를 통해 자신의 유닛 배치와 적의 위치, 그리고 적과의 전선 및 전투하기 가장 적절한 곳이 어디인지 등을 파악할 수 있음
- 영향력 분포도를 만들어 내는 방법은 여러 가지가 있으며 적용 방법 역시도 여러 가지가 있음
- 여기서는 가장 간단한 수준에서 개념을 알아볼 것
- 2차원 공간에서의 영향력 분포도
  - 영향력 분포도는 대부분의 게임 구조에 대해서도 적용 가능
  - 여러 가지 타일 기반의 격자(직사각형, 정사각형,육각형 등) 형태를 갖출 수 있으며 3D에서도 적용 가능
  - 여기서는 2차원 공간의 간단한 구조를 통해 이해를 돕겠음
    - 게임 세계는 사격형 칸들로 덮음
    - 그리고 각 칸들의 모든 영향력은 0으로 초기화
    - 그리고 각 칸이 가질 수 있는 영향력 값이 배정
    - 이때 영향력의 값의 기준은 전투 능력등으로 볼 수 있으며 아군은 양수, 적군은 음수의 값을 갖음
    - 하나의 타일로 이루어진 게인 세계에는 고유의 영향력을 갖는 아군과 적군이 공존하며, 이들의 영향력 값을 적절히 더하고 뺌으로써 각 타일에서의 유닛 전투 능력을 평가
    - 일단 각 유닛이 1이라는 전투 능력을 가진다고 하자.
    - 이제 각 칸의 영향력을 인접 칸들로 전파시켜야 함
    - 인접한 칸으로 전파될 때마다 세력(영향력)은 반으로 준다고 가정
    - 두 적군 유닛(비행기)들의 영향력 역시 동일하게 전파되며, 적 유닛의 영향력은 음의 값으로 나타나게 됨
    - 아군 유닛과 적 유닛의 의 영향력을 결합한 분포도를 통해 우리는 아군과 적군의 역관계를 확실히 알 수 있으며 타일 내의 영향력(양의 값과 음의값)을 이용하여 적들의 진형과 전선 형성등을 파악
    - 실제 게임에 쓰이는 분포도의 형태는 좀더 복잡
- 실제 게임에서는 단지 각 칸에 영향력 값만이 아닌 게임의 세계에 대한 또 다른 정보( 전투능력, 지역 가시성, 전사자 수, 자원, 통행성 등)들을 함께 담는 경우가 많음
- 이렇게 구성된 영향력 분포도는 하나의 데이터베이스가 되기도 함
- 일반적으로, 게임에 참여한 플레이어들에게 각자에 해당하는 영향력 분포도가 주어지게 되고 이를 처리하기 위해 분포도를 병렬적으로 처리해야 함
- 물론 모든 플레이어들에 대해 하나의 단일한 영향력분포도를 갱신하고 모든 AI플레이어들이 그것에 접근하게 만들 수도 있음
- 이것은 치팅(cheating) 수단이 될 수 있음

자원 배정 트리
- 영향력 분포도기는 지형 차원의 전술적 자산(asset)을 얻기 위한 수단이라 할 수 있으나 앞으로 살펴볼 자원 배정 트리는 전략적 차원의 결정을 내리는데 사용되는 기법 중 하나라 볼 수 있음
- 자원 배정트리는 플레이어의 제어 하에 있는 모든 자산들의 특정한 기능적 목적을 표현하는 하나의 트리 구조
- 이 트리는 현재 플레이되고 있는 모든 유닛들과 자원들을 기능적 범주들의 계통구조로 조직화한 형태
- 자원 배정 트리를 이용해 플레이어는 자신을 포함한 게임안의 모든 플레이어들의 전략적 강점과 약점을 알아내는 데 사용될 수 있음
- 또한 이 트리는 다양한 범위의 경제적 생산 및 자원 배분 결정을 위해 사용 가능
- 예를 들어 전투 유형에 따라 생산할 유닛을 결정한다든지, 그리고 어떠한 기능적 역할을 맡길 것인지를 판단하는데 사용
- 자원 배정 트리는 기본적으로 어떤 새 유닛들을 생산할 것이며 기존 유닛들에게 어떤 역할을 맡길 것인지를 결정하는데 유용
- 또한 플레이어의 독특한 개성을 창조하는 수단이 될 수도 있음
- 즉 개성적인 AI 플레이어들을 만들어내는데 사용 가능
- 개성적인 AI 플레이어들을 만들어내는 문제는 단지 트리 각 노드의 배분 비율등을 조절하여 해결 가능하며, 또한 각 노드들을 적절히 조절하므로써 전략적 비중을 변경하는 것 또한 가능

응용 사례

게임 장르
- 게임의 장르 분류에 있어서 현재 많은 혼동과 어려움이 뒤따르고 있음
- 왜 그런지에 대한 타당한 이유와 근거를 제시하기엔 어려운 점이 많은 것도 사실
- 현재 개발중인 대부분의 게임은 그 특징들이 너무나도 다양하며 어느 특정한 룰을 지키려는 의지 또한 부족한 것이 사실
- 그렇다면 우리는 대략 어떠한 특징들을 가지고 게임의 장르를 분류할 수 있을까?
- 게임의 장르는 대략 슈팅, 아케이드, 퍼즐, 어드벤처, 롤플레잉, 전략시뮬레이션, 조종시뮬레이션, 온라인 게임, MMORPG등으로 나눌 수 있음
- 이것은 사전적인 분류는 아님
  - 슈팅 슈팅 게임
    - 말 그대로 플레이어의 민첩성에 기반한 회피, 그리고 막대한 화력에 기반한 대량 파괴에 플레이 초점이 맞춰져 있음
    - 목표물을 쏴서(shoot) 맞추는 게임 형태에서 그 명칭이 기원한 것으로 보임
    - 실제로 제비우스, 갤러그와 같은 쏴서 맞추는 형태의 게임에 대한 명칭에서 굳어진 것으로 보임
    - 이러한 슈팅 게임은 플레이어가 한번에 하나의 유닛만 조종해야 하거나, 일반적인 성취도를 점수(score)형태로 계산하여 순위를 부여하고 일반적으로 사냥과 같은 것이 주된 목적
  - 아케이드
    - 민첩성과 순발력에 기반한 캐릭터 조종과 약간의 퍼즐이 가미된 게임으로서 사실상 아케이드란 말은 올바른 명칭은 아님
    - 아케이드는 가정용 비디오 게임이나 PC 기반 게임과 구분이 되는 ‘업소용 게임“을 가리키는 용어
    - 그러나 모든 업소용 게임을 아케이드 게임이라고 칭하기엔 억지가 있음
    - 그래서 생긴 말이 ”액션 아케이드“
    - 그러나 현재는 ”액션“이라는 말이 많이 모호해져 있으며 그 장르를 구분 짓기 어려운 형편
    - 실제로 슈팅 게임의 기원과 같은 게임인 제비우스와 갤러그도 아케이드용 게임
  - 퍼즐
    - 컴퓨터 게임 이전부터 있던 게임의 명칭이 그대로 사용된 형태로 논리적 사고에 기반한 문제 해결이 플레이의 초점
    - 실제로 컴퓨터가 제시하는 문제를 풀이해 나가며 좀더 난이도 있는 문제(게임 진행 속도나 문제 자체의 난이도, 해결을 위한 제한 시간등의 변화를 통한 난이도 조절)를 해결하는 것이 목적
  - 어드벤처
    - 퍼즐에 기반한 스토리 진행형 게임
    - 게임의 진행 및 해결해야할 문제가 주어지는데 이는 모두 스토리에 기반
    - 보통 스토리에 따라서 게임의 목표가 있고, 그 목표를 달성하면 엔딩과 같은 결과물이 주어짐
    - 스토리르 진행해가며 다양한 아이템을 사용할 수 있으며 이러한 진행은 퍼즐과는 또 다른 플레이어의 판단력과 분석력을 요구
  - 롤플레잉
    - 어쩌면 어드벤처와 너무나도 유사한 특징을 가진 장르가 롤플레잉
    - 롤플레잉 역시 스토리와 캐릭터의 성장에 기반한 퀘스트(문제와는 조금 다름) 해결 또는 해결을 통한 캐릭터 성장을 초점
    - 일반적으로 캐릭터를 중심으로 게임이 진행되며 캐릭터를 성장시키는 과정에서 우리가 흔히 알고 있는 경험치나 아이템을 사용할 수 있음
    - 시나리오 중심적인 게임이라는 점에서 어드벤처와 유사하나 자유도의 보장이라는 측면이 강조된 형태를 띄고 있음
    - 롤플레잉 게임에서의 자유도는 “이동의 자유도”, “행동의 자유도”, “캐릭터 성장의 자유도”, “스토리 진행의 자유”, “문제 해결의 자유도”, “게임 진행의 자유도”등으로 대략적인 분류
    - 롤플레잉 게임에는 울티마온라인, 파이널판타지, 드래곤퀘스트등
  - 전략 시뮬레이션
    - 제한된 자원의 효율적 관리와 유닛 제어를 통해 전쟁등과 같은 상황을 재현/가정한 게임이
    - 우리가 흔히 알고 있는 스타크래프트, 워크래프트등이 전략 시뮬레이션의 대표적인 게임
    - 전략 시뮬레이션은 한쪽이 승리하거나 포기할 경우, 혹은 일정한 목표가 달성되면 게임이 종료
    - 대부분의 전략 시뮬레이션 게임은 리얼타임방식(실시간 전략시뮬레이tus : RTS)으로 진행
    - 리얼타임 방식은 턴 방식과 대조적인 것으로 순서에 관계없이 실시간으로 진행
  - 조종 시뮬레이션
    - 실존하는 기계적 시스템에 대한 가상 체험과도 같음
    - 플레이어는 조종 가능한 기체의 조작을 하게 되는데 이 기체는 실제 세계혹은 가상 세계에 이미 존재하는 탈 것을 그대로 재현한 것
    - 시뮬레이션의 가장 큰 특징은 사실적인 세계의 표현과 그리고 그를 위한 운용 역학, 동역학과 같은 자연적 물리적 법칙이 적용되거나 수정되어 구현된다는 것
- 장르별 인공지능의 특징
  - 액션
    - 대상 캐릭터 : 플레이어
    - 처리 기능 : 공격 방어
    - 엔진 구현 : 스키립트
  - RPG
    - 대상 캐릭터 : 플레이어, 종속멤버, NPC
    - 처리 기능 : 그룹내의 개별 공격/방 대화 기능
    - 엔진 구현 : 규칙 기반 시스템
  - 실시간 전략
    - 대상 캐릭터 : 플레이어 그룹 유닛
    - 처리 기능 : 전략 목표 설정, 그룹 경로 계산 및 이동, 유닛 공격 및 방어
    - 엔진 구현 : 규칙 기반 시스템
- 효율적인 인공지능을 구현하기 위해서 ADU 개념을 도입하여 인공지능의 기능을 확장
- 여기서 ADU(Artificial Decision Unit)란 앞서 최적화 전략에서 언급했던 일종의 관리자 역할을 수행하는 유닛
- RTS 게임의 경우 Master ADU는 전체적인 전략차원의 인공지능을 담당하도록 하며, 특정시간에 그룹으로 선택된 여러 가지의 유닛은 Group Commander ADU가 담당
- 반면, 그룹내의 유닛이나 이 그룹에 속하지 않는 일반 유닛은 유닛별 ADU가 인공지능 기능을 담당
- 다음은 인공지능 엔진의 장르별 ADU를 설명한 표
- 인공지능 엔진의 장르별 ADU
  - 기본 모듈
    - FSM의 생성
    - State와 Transition의 추가 기능
  - 장르별 모듈
    - 액션
      - Master 기능 ADU
    - RPG
      - Master 기능 ADU
      - Slave 기능 ADU
      - NPC 기능 ADU
    - RTS
      - Master 기능 ADU
      - Group Commander 기능 ADU
      - Unit 기능 ADU
- 예를 들어, FSM 모듈의 경우, 상태(State)의 수가 10개 미만의 경우에는 Switch 구문을 사용하여 현재의 상태를 검색한 후 이에 해당하는 코드를 수행하면 되지만, 상태의 수가 10개 이상 증가하면 처리속도 면에서 느려질 수 있으므로 ADU 클래스(Class)를 정의하고 여기에 상태나 전이Transition)를 추가하는 방식을 사용하여 문제점을 개선

장르별 응용 사례

RPG 게임의 사례
- RPG 게임에서 사용되는 대표적인 게임 엔진으로 Infinity 엔진
- Infinity 엔진은 Bioware 사에서 개발한 RPG 전용엔진이며 Baldur’s Gate 시리즈, Icewind Dale과 같은 게임에서 사용
- Infinity 엔진은 대표적인 AI 기능만을 다루는 엔진 중 하나로서 AICompile 스크립트 언어를 이용하는 규칙 기반 시스템 구조를 갖고 있음
- AICompile 언어는 IF<condition> THEN <response> END 로 표현되는 규칙 중 하나를 선택하도록 되어 있음
- 규칙기반 시스템 구조

IF
	Condition1
THEN
	RESPONSE # weight
		Response1
	RESPONSE # weight
		Response2
END

IF
	Condition2
THEN
	RESPONSE # weight
		Response1
	RESPONSE # weight
		Response2
END

weight는 1에서 100사이의 정수이며 모든 Response의 Weight 합에서 해당되는 비율만큼의 확률로 Response가 이루어짐
또한 Response는 Action의 OR 조합으로 이루어짐
규칙기반 시스템 구조의 예

IF
	Class(LastAttackerOf(Myself().MAGE)
	HPGT(Myself.50)
THEN
	RESPONSE # 80
		Attack(LastAttackerOf(Myself).MELEE)
	RESPONSE # 40
		Help()
		RunAway()
END

위 예에서 자신을 공격한 적의 Class가 MAGE이고 자신의 건강(HP : Health Power)가 50 이하일 경우 80/(80+40)의 확률로 MELEE 방식으로 적을 공격(Attack)하거나 40/(80+40)의 확률로 도움(Help)을 요청하고 도피(RunAway?)하는 것을 나타냄
이는 원하는 상황에서의 캐릭터의 동작을 쉽게 표현할 수 있는 장점

RTS(Real-Time Strategy : 실시간 전략게임)의 사례
- RTS 장르의 대표적 게임인 AOK(Age of Kings : Ensemble Studio 사)는 인공지능 처리를 위해 스크립트 언어를 사용
- 앞서 살펴본 Infinity 엔진의 스크립트 언어와 유사하지만 다른 표현 방식을 사용
- AOK 인공지능 처리 스크립트 언어

(def_rule
(current-age == castle-age)
(building-type-count castle == 1)
=>
(set-goal GOTO_NEXT_AGE TRUE)
(chat-local-to-self "Trying to get to the Imperial Age*)
(set-goal CAN_ATTACKFALSE)
(disable-self)

(def_rule

(food-amount<=400)
(can-buy-commodity food)
(goal GOING_FOR_WONDER FALSE)
(goal GOTO_NEXT_AGE FALSE)
=>
(set-goal RESOURCE_STATE
RESOURCE_STATE_NEEDFOOD)
(chat-local-to-self *Need Food!*)

위 스크립트 언어에서 사용되는 예약어 중 goal은 게임의 전략 목표를 지정하는 boolean 형 변수값이며, 이를 지정하기 위해 set-goal이라는 예약어를 사용
위 스크립트 중 두 번째 규칙 정의에서 food의 양이 400보다 작거나 같을 경우 생필품으로 음식을 살 수 있으며 goal은 ONDER 상태로 가거나 다음 AGE로 가는 것을 FALSE로 처리하고 set-goal을 통해 “Need Food!” 메시지를 보내는 것을 나타낸 것

기타 장르
- 사실상 어떤 게임은 그 장르를 명확히 구분 지을 수 없음
- 그 대표적인 예로 B&W(Black and White)를 들 수 있음
- 이 게임에 등장하는 캐릭터는 에이전트 기능이 포함되어 있으며 이 에이전트는 어떠한 원인에 의해 특정한 행동을하도록 함
- 대부분의 RPG 게임에 등장하는 캐릭터가 이유 없이 주인공을 해치려 하는 것과 같은 무의미한 행동은 없어야 함
- 다음은 B&W의 에이전트가 갖고 있는 학습기능의 특징
  - 플레이어의 피드백으로부터 학습
  - 플레이어로부터 주어진 직접 명령을 학습
  - 다른 캐릭터로부터 학습
  - 외부의 반응으로부터 캐릭터 자체가 학습
- B&W에서는 믿음(Belief), 욕망(Desire), 의도(Intention)와의 관계를 설정하고 캐릭터의 계획된 행동을 얻음
- 또한 아키택쳐의 구현을 위해 동적인 결정트리를 사용
- 외부로부터의 반응에 따라 얻어지는 피드백을 보관하고 이러한 데이터를 바탕으로 결정트리를 게임 도중에 변경하는 방법을 사용하여 학습 기능을 구현

AI의 등장과 목적

AI의 적용 분야와 최적화 전략

AI 구현 기술

응용 사례

최신 기술의 전망