Game AI

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 :
플레이어와 반대 방향으로 이동

•FSM도 표현해야할 상태수가 늘어나게 되면 몇가지 단점 •FSM이 나타낼 수 있는 상태 수는 어느 정도 제한적이지만 사실상 그 수에 대한 제한은 없기 때문에 복잡하고 많은 수의 상태 표현을 요구하는 경우 상태 다이어그램을 정리하기가 어렵고 상태 변화를 가능하게 하는 외부 자극 처리가 복잡해지게 됨
•게다가 FSM을 사용한 게임 혹은 게임내의 캐릭터는 그 행동의 예측이 쉬우며 그렇게 될 경우 게임의 재미가 떨어지고, 게임의 난이도를 높이기 위해 FSM을 새로 확장 구현해야하는 결과를 초래
•실제로 게임 개발 도중 FSM은 빈번하게 진화, 확장되거나 계층적 FSM으로 다시 설계

•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 THEN 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)와의 관계를 설정하고 캐릭터의 계획된 행동을 얻음
•또한 아키택쳐의 구현을 위해 동적인 결정트리를 사용
•외부로부터의 반응에 따라 얻어지는 피드백을 보관하고 이러한 데이터를 바탕으로 결정트리를 게임 도중에 변경하는 방법을 사용하여 학습 기능을 구현

최신 기술의 전망
•신경망(NN : Neural Network) •신경망은 인간의 신경세포 동작을 모방해서 외부 입력에 따른 결과를 출력하는 방법으로, 여러 입력에 적당한 가중치를 주어 얻어진 결과에 따라 행동을 결정하는 방법
•신경망은 위 그림에서와 같이 외부 입력을 입력단에 있는 퍼셉트론에서 받아 출력단에 있는 퍼셉트론에 적당한 가중치를 주어 전달하는 방식으로 진행되며 결과가 촉발되는 경우에 이를 사용하는 방식
•신경망은 완전한 하나의 연산 시스템
•이것은 충분한 노드와 선분만 주어진다면 그것들이 컴퓨터가 할 수 있는 어떠한 계산도 할 수 있다는 것
•신경망의 가장 중요하고 흥미로운 기능중의 하나는 망을 훈련받을 수 있고 자율적으로 학습
•그러나 자율적으로 학습할 경우 우리는 그것이 이용하고 있는 결과들을 검사할 방법이 없으며 이러한 유형의 망은 훈련받은 망보다 훨씬 더 느리게 학습
•게임에서의 신경망은 다음과 같은 경우에 이용 가능
•우리가 어떠한 상태에 이르면 개체는 에너지를 찾아 지금의 위치로부터 이동하게 하는 어떤 상태를 가지고 있다고 할 경우, 우리는 근처에 강한 적이 있을 때 에너지를 찾아 지금의 이동하기를 원할 것
•아니면 적당히 강한 적이 근처에 있고 나의 에너지가 적을 경우도 마찬가지 일 것
•이러한 경우는 아주 많이 존재 할 수 있으며 우리는 이것을 다른 기법을 이용하여 작성할 수 있지만 신경망을 이용하여 작성 가능
•신경망으로의 입력 값이 되는 입력 상태 값으로 가지고 있다가 촉발되었을 때 우리의 개체를 에너지를 향해 움직이게 할 수 있는 어떠한 결과 값을 가질 수 있음
•이 경우, 행동은 입력에 대한 수백만의 조합 중에서 나오게 됨
•충분한 요인들이 목표 상태를 이끈다면 그것은 촉발 할 것
•신경망을 사용하고자 하는 아이디어 및 연구는 많이 진행되고 있지만 그 진행 과정상 처리 속도가 느리며 앞서 제시하였던 방법보다 눈에 띄는 결과를 얻기 어렵기 때문에 아직은 연구 대상으로서 남아 있는 부분이 많음

•인공 생명 (AI-Life) •인공생명의 아이디어는 2001년부터 GDC(Game Developers Conference)에서 시도되고 있음을 알 수 있음
•이전의 여러 다른 인공지능 기법이 시도되었으나 성공하지 못한 것에 비해 인공생명 기술은 가능성이 있는 것으로 판정받고 있음
•Half-Life와 Unreal과 같은 게임에서 Flocking 이론을 사용하여 게임에 등장하는 몬스터의 움직임을 구현한 것으로 발표되고 있음
•Flocking 기법은 네가지의 간단한 규칙을 이용하여 실제 생물체와 유사한 결과를 얻어낼 수 있다는 장점을 가지고 있음 •분리(Separation) : 주변 보이드들과 충돌하지 않도록 방향을 돌림
•정렬(Alignment) : 주변 보이드들과 같은 방향을 가리키도록 함
•응집(Cohesion) : 주변 보이드들과의 평균 위치 쪽으로 방향을 돌림
•회피(Avoidance) : 주변의 장애물이나 적과 충돌하는 것을 피함

•크레이그 레이놀즈가 만든 보이드(Boid)는 새떼나 물고기떼, 또는 벌떼와 비슷한 집단 행동처럼 보이도록 1987년 SIGGRAPH에 제출된 논문에서 처음 등장한 기법
•각각의 보이드는 매 순간마다 자신의 주변을 다시 평가할 뿐, 무리에 대한 정보는 가지고 있지 않음
•무리의 보이드들은 어디로 가는지에 대해서 전혀 알지 못하지만, 모든 보이드들은 하나의 무리로서 움직이고, 장애물과 적들을 피하며, 다른 보이드들과 보조를 맞춰서 유동적으로 이동하게 됨

•인공 감정 (Artificial Emotion) •인공 감정 AE : 감정과 성격의 모방 •진짜 같은 환경을 구현하는 데 있어서 감정이 살아있는 캐릭터는 결정적인 역할
•특히 그 캐릭터가 실제로 정을 가지고 있는 사람들과 상호작용을 할 때에는 더욱 그렇다
•감정은 로봇같이 기계적인 행동과 살아있는 사람같은 행동의 차이를 가져오는 필수적인 요소
•전통적으로 애니메이터들은 이미 정해진 룰에 따른 행동을 어렵게 구현
•이러한 접근으로 각각 고유한 성격과 감정을 가진 자율적이고 인터액티브한 캐릭터를 만들어 내는 것은 불가능
•진정으로 인터액티브한 캐릭터는 인공 감정(AE) 이라고 부르는 것에 기반한 기술을 이용하여 자율적인 행동이 이루어지게 할 수있어야 함
•몇몇 작품을 제외하고는 현재의 게임 산업에서 유의미한 정도의 깊이를 지닌 자율적인 AE를 거의 찾아볼 수가 없음
•현재 게임 산업은 플레이어가 게임을 하는 과정에서 모든 것을 죽이거나 정복해야 하는 장르들이 압도적인 우세에 있음
•상대방은 감정이 거의 필요 없으며, 단지 어느 정도의 공포나 단순한 이동 패턴을 드러내는 공격만이 요구
•인터액티브 게임에서 감정은 사회적인 기능을 수행
•정서적인 반응은 우리가 만나게 될 캐릭터들을 실제같고 매력적이게 하기 위해 쓰임
•예를 들어, 만약 우리가 가상의 술집에 들어갔고, 술집 안에 있는 모든 캐릭터들이 분명한 성격을 가진다면, 그 장면은 매우 매력적이고 실제 같은 사회적인 상황이 연출 될 것
•만약 캐릭터들이 아무런 감정을 보이지 않는다면, 허구에 대한 우리의 몰입은 깨지게 되고, 우리는 우리만의 환상적인 세상이 아닌 컴퓨터로 생성된 가상의 세계에 있다는 것을 상기하게 될 것
•인공 감정의 결과로는 두 가지 •행동 •일반적인 범주에 속하며 캐릭터가 존재하는 상황의 맥락에 의존
•시뮬레이션의 행동 시스템에서 AE는 행동을 선택하고 (또는 선택하거나) 수정하기 위해 사용
•행동을 선택할 때, AE는 어떠한 행동이 캐릭터의 성격과 현재의 기분에 적합한 행동인지를 지시해 줌
•예를 들어 겁이 많은 캐릭터는 공격적인 행동은 전혀 하지 않으려고 하게 됨
•행동을 수정할 때 AE는 행동을 어떻게 이행하는지에 도움이 됨
•아주 내성적인 캐릭터라면 그러지 않겠지만, 사교적이고 외향적인 캐릭터라면 행동을 아주 적극적으로 표현할 것

•그러나 1차적인 AE의 사용은 손짓과 몸짓, 그리고 얼굴 표현 등의 활발한 제스처
•제스처 •우리의 감정을 바깥 세상에 알리는 하나의 방법
•제스처 없이 우리는 차갑고 단조롭고 감정이 없어 보일 것
•AE에 의한 제스처들은 우리의 캐릭터들의 성격과 정서에 직접적으로 연결되어 있고, 일정한 패턴을 따르기 마련
•이러한 몸동작(또는 Body Language)은 캐릭터의 행동에 또 다른 입체감을 주며, 독특한 성격을 가진 자율적인 캐릭터의 창조에 생기와 깊이를 불어넣어 줄 것

•유전자 알고리즘(Genetic Algorithm) •많은 게임 인공지능 담당자들은 유전자 이론의 가능성은 있으나, 아직은 게임에 사용할 수 없다는 생각지 지배적
•여러 유전자 관련 기법들은 다음과 같은 핵심 내용을 다룸 •첫 번째로는 표현형을 어떠한 압축적이고 간결한 ‘코드’들로 기술한다는 것 •즉, 체력(HP : Health Power), 마법력(MP : Magic Power), 속도, 크기, 모습 등등을 보통은 클래스나 구조체의 어떤 변수들로 저장하지만, 유전자 기법에서는 그것들을 어떠한 일련의 바이트 배열이나 숫자 배열로 표현
•또한 그 배열들을 적절히 복사, 교환, 변형(돌연변이)함으로써 새로운 표현형을 얻게 됨
•유전자 관련 기법들은 대부분 유전자 코드의 그러한 조작 방법에 기반

•두번째는 유전자들의 교환, 변형을 반복함으로써 개발자도 놀라게 할만한(즉 미리 구현되지 않은) 새로운 어떠한 특성이나 해법이 생겨난다는 점이 ‘진화’라는 관점에서 본 유전자 기법의 강점 •게임 프로그래밍에 유전자 기법을 도입할 때, 첫 번째 부분은 별 무리가 없으나, 두 번째 부분은 다음과 같은 이유로 문제가 발생
•학술적 측면의 유전자 알고리즘은 사용자와 상호 작용하는 실시간 애플리케이션을 만드는 것이 아니기 때문에 진화의 세대수가 그리 중요하지 않음
•따라서, 연구 목적의 GA에서는 수천 수만 세대가 지나서야 원하는 해답을 얻었다고 해도, 그것이 기존 알고리즘으로 해답을 얻는 것보다 효율적이기만 하면 됨
•그러나 게임에서는 그것이 불가능
•간단히 말하면, 어떤 몬스터의 진화를 뚜렷이 느낄 수 있으려면 게임을 엄청나게 반복해야 하는 문제점이 발생하기 때문
•그렇다면 ‘신의 손’을 개입시키거나 하는등의 진화를 촉진시키는 과정을 적용한다면 가능할까?
•이것은 GA의 원래 의도를 지키면서 진화를 촉진시키는 것은 매우 어려운 문제
•자칫 GA의 적용 보다는 그냥 시간이 지날 수록 HP나 공격력이 증가하는 것뿐일 수도 있게 되어 버리기 때문
•유전자 알고리즘의 원래 의미는 작은 알고리즘 조각(유전자)들이 서로 교배하면서 세대를 거듭하고, 그 과정 동안 효율적인 알고리즘은 살아남고 효율적이지 못한 알고리즘은 대가 끊기고, 그럼으로써 가장 효율적인 알고리즘이 ‘튀어 나오게’ 하는 것일 것
•이것을 게임에 적용시킨다면, 예를 들어 유전자는 빌드오더(Build Order : RTS에서의 빌딩 건설 순서로 봐도 무관)를 의미하고, 싸움에 이긴 빌드오더만이 대를 잇게 함으로써 효율적인 빌드오더를 찾는 것이 될 수도 있겠음
•그러나 얼마나 반복해야 뚜렷한 진화가 나타나는가 라는 문제를 해결하지 않는 한 게임 플레이에 적용하기란 한계가 있음
•그래서 유전자 알고리즘을 게임 플레이에 적용하기보다는 게임 개발 도중 게임의 밸런스를 조정하는데 적용하는 시도 있으나 큰 성과는 없는 것으로 알려지고 있음

•LOD(Level-Of-Detail) •LOD이라는 개념은 그래픽 이외의 분야에서도 많이 쓰이는 최적화 방법
•LOD는 3D 그래픽의 랜더링 관련 기술로서 현재 대부분의 게임 엔진들이 멀리 떨어져 있는 객체를 빠르게 랜더링하는데 사용되고 있음
•LOD의 개념은 생각보다 간단하여, 카메라로부터 멀리 떨어져 있는 객체는 다각형 수가 적은 모델을 사용(다각형의 수를 줄이는 등의 과정을 거쳐)하고, 객체가 카메라와 가까울수록 다각형 개수가 많은 모델을 사용한다는 것
•이는 게임의 시각적 품질을 유지하면서 랜더링 속도를 개선함으로써 게임 전체의 퍼포먼스를 향상시키는 결과를 얻을 수 있음
•최근 들어 이러한 개념을 AI 분야에서도 적용할 수 있다는 사실이 인식되고 있음
•AI를 위한 LOD 기법의 전략 •에이전트와 카메라나 플레이어와의 거리 또는 연관성에 따라 AI의 처리 빈도 변화
•연관성에 따라 에이전트 알고리즘의 복잡성의 변경
•여러 에이전트들의 개별적 특성이 플레이어에게 미치는 영향에 따른 알고리즘 선택

•결과적으로 플레이어의 주목을 끌지 못하는(화면상에 보이지 않거나 전혀 다른 세계에 있는 경우) 부분에 대한 부담을 줄여 작업을 최소화하는 것