Chapter 3. 오토마톤과 인공 생명 프로그램¶
이 문서는 한빛미디어에서 나온 처음 배우는 인공지능 을 공부하면서 정리한 것입니다.
| Authors: | Woong Jeong |
|---|
01 인공 생명 시뮬레이션¶
인공 생명이란?¶
생명의 가장 중요한 특징 [1] 은 자기복제 라고 할수 있습니다. 또한 자기복제 프로그램은 컴퓨터의 발달과 함께 존재해 왔습니다.
하지만 자기복제 프로그램을 생명이라고 할 수 있을지는 많은 의문이 있습니다. ‘인공 생명’에 조금이나마 가깝게 행동하려면 약간의 프로그램 스스로 ‘의지’나 ‘의사’를 표현할 수 있어야 할것입니다.
다르게 표현하자면, 기계가 ‘인공 생명’을 가지기 위해서는 “이 기계도 혹시 생명이 있는게 아닐까?”라는 의문을 갖게 해주는 무엇인가가 필요할 것입니다.
라이프 게임¶
라이프 게임 [2] 이란 생명체를 연상하게 하는 살아 움직이는 듯한 컴퓨터 게임을 말합니다. 바둑판에 원하는 돌을 놓고 미리 정해둔 법칙에 따라 전체 상태를 변화시켜가는 프로그램입니다.
라이프 게임은 시간이 지나며서 채워지는 부분이 매번 다르기 때문에 같은 패턴이 등장하는 일은 거의 없으며 특정 규칙을 따라 변화하게 됩니다.
라이프 게임은 실행할 수 있는 모든 계산을 칸을 채우거나 비우는 패턴으로 나타낼 수 있으므로 만능 튜링기계 로 알려저 있습니다.
라이프 게임 테스트 [3]
감염 시뮬레이션¶
라이프 게임의 확장형인 감염 시뮬레이션 모델은 한칸의 상태를 전염병에 걸린 사람의 상태로 설정 후 상태 변화를 표현한 것으로 볼 수 있습니다.
특히 건강한사람 (Susceptible) / 감염자 (Infected) / 항체 보유자 (Recovered)의 세 상태를 기반으로 둔 감염 시뮬레이션 모델을 SIR 모델 [4] 이라고 하고 일정한 규칙을 정하면 감염자 수 등에 대한 정보를 미분 방정식으로 나타낼 수 있다고 합니다. 이러한 모델은 감염에 대한 역학 조사의 연구에 이용할 수 있다고 하고, 특히나 잠복기에 있는 건강한 사람 (Exposed)의 상태를 추가한 모델을 SEIR모델이라고 하고 이 모델 또한 미분방정식으로 표현할 수 있다고 합니다.
02 유한 오토마톤¶
오토마톤¶
유한 오토마톤이란 외부 입력이나 이벤트가 발생할 때 유한한 패턴 내에서 상태를 변화시키는 모델을 가지는 기계 [5] 를 말합니다.
오토마톤은 시간의 경과 / 상태의 변화를 표현하고, 시간의 흐름에 따른 공간적 구조 변화를 연구하는 이론입니다. 앞서 언급한 라이프 게임과 같이 칸(셀)을 이용하면 셀 오토마톤 이라고 합니다.
유한 오토마톤의 동작은 다이어그램으로 나타낼 수 있는데 이처럼 원과 선을 연결한 형태의 그림을 상태 전이 다이어그램 이라고 합니다. 이 상태전이 다이어그램은 시작점과 종료점이 정해져 있으며, 종료점에 다 다라 끝난 상태를 접수 상태 (accept state) 라고 합니다.
유한 오토마톤에서 접수 상태 즉, 종료점에서 끝난 상태에서 실행 종료가 되지 않으면 오류 등이 발생한 비정상 상태를 나타냅니다.
오토마톤과 언어 이론¶
오토마톤의 기본적인 특징은 상태의 변화와 규칙 을 나타낼 수 있다는 것입니다.
이러한 특징은 언어의 구분 모델을 나타내는 데이도 이용할 수 있습니다. [6] 언어 이론에서는 문자들의 집합을 알파벳이라고 하고, 알파벳 중에서 문자의 중복을 허용한 상태를 문자열이라고 합니다.
예를 들면 유전자를 코딩하는 염기서열은 Σ = {A, T, G, C}, 단백질을 코딩하는 아미노산 서열은 Σ = {20가지 아미노산} 을 알파벳으로 하는 Σ를 이용한 문자열 입니다.
각종 프로그래밍 언어에서 많이 활용되고 있는 정규 표현식 또한 오토마톤으로 나타낼 수 있습니다.
03 마르코프 모델¶
마르코프 모델의 주요 개념¶
앞서 언급한 ‘유한 오토마톤’에서 오토마톤은 유한한 상태를 가지는 기계라고 하였습니다. 이때 상태의 변화를 러시아의 수학자 마르코프 가 제시한 모델로 표현한 것이 마르코프 모델입니다.
마르코프 모델의 주요 개념은 확률 과정 > 마르코프 과정 > 이산 상태 마르코프 과정 > 마르코프 연쇄 의 범위로 나타낼 수 있습니다.
마르코프 모델의 예¶
마르코프 모델은 상태에 따라 비용을 설정하고, 변화할때 비용을 더하여 누적비용을 추정하는 상황에 응용 할 수 있습니다. 대표적으로 광고의 열람 효과를 포함한 가치를 정상분포로 계산하는 것 등이 있습니다.
앞서 언급한 SEIR 모델을 마르코프 모델로 다룰 수 있습니다. 이 때 4 가지의 상태는 확률을 기반으로 하여 변화하게 됩니다.
04 상태 기반 에이전트¶
게임 AI¶
위에서 설명한 인공 생명 시뮬레이션을 게임 AI에 활요하게 되면, 게임의 등장 인물이나 필드의 구성요소 각각을 유한 오토마톤(유한 상태 기계)으로 설정해 인공지능을 구현할 수 있다.
엄밀히 말하여 2010년 이후의 인공지능에 유한 오토마톤 기반의 AI를 포함시키는 것은 논란의 여지가 있겠지만, 게임 AI는 사람을 대신하여 행동하는 프로그램으로써 인공지능 이해한다는 관점에서 알아야 할 점들을 소개합니다.
에이전트¶
게임에 존재하는 개별 상태 기계를 총괄하는 시스템 을 말합니다.
에이전트 는 다른 에이전트 와 상호작용 을 하면서 이용자인 플레이어 에게 정보와 자극을 제공합니다.
에이전트의 설계와 구축은 사람인 플레이어 와 게임 AI가 상호작용 할 수 있는 구조를 만드는데 큰 도움을 주게 됩니다.
여기서 말하는 에이전트는 소프트웨어(지능형) 에이전트 [7] 를 의미하는데, 지능형 에이전트는 자율성(autonomy) / 사회성(social ability) / 반응성(reaactivity) / 능동성(proactivity) / 시간연속성(temporal continuity) / 목표지향성(goal-orientedness) 의 6가지 특징을 지녀야 합니다.
에이전트는 동작하는 상태일 때가 많은데 이 경우를 이벤트라고 합니다. 이용자가 어떤 동작을 실행한 결과로 상태 기계에 변화가 일어나게 되는데 이러한 동작 상태 기반의 에이전트를 구동형 에이전트 [8] 라고 합니다.
보드게임¶
보드게임은 에이전트를 실제로 테스트 해보고 이용할 수 있는 대표적인 사례입니다.
가장 간단한 형태의 보드게임 모델로는 오델로(리버시) [9] 라는 바둑판에 돌을 놓는 게임이 있습니다. 오델로에서 컴퓨터 플레이어를 만들 때는 앞에서 명시한 셀 오토마톤의 사고방식을 도입합니다.
오델로는 기본적인 규칙에 따라 프로그래밍이 되어있고 이를 바탕으로 게임을 진행하게 됩니다.
보드게임의 게임 이론¶
게임을 진행하면서 모든 상태를 계산할 수 있으면 완전 정보 게임 이라고 하고, 체스/장기/바둑과 같은 게임이 이에 속합니다. 또한 2명이 대전하므로 우연에 의한 게임 진행상태가 정해지지 않기 때문에 상태를 예측할 수 있어서 2인 제로섬 유한 확정 완전 정보게임 이라고도 합니다.
게임 이론은 수리학적 영역뿐만 아니라 경제학 등의 분야에서도 이용이 되는데, 경제학적 측면에서의 불완전 정보 게임 으로는 죄수의 딜레마 [10] 가 있습니다. 이 죄수의 딜레마의 경우는 자신의 선택지와 상대방의 선택지가 모두 공개되어 있고 선택지 또한 공개되어 있어 완비 정보 게임 에 해당합니다.
복잡하게 구성된 에이전트 사용¶
심시티 같은 도시 건설 & 경영 시뮬레이션 게임 혹은 삼국지와 같은 전략/전투 시뮬레이션의 경우 또한 에이전트 기반으로 환경을 제어합니다.
심시티의 경우는 다수의 에이전트가 복잡하게 상호작용 하면서 시간을 중심으로 게임을 진행합니다. 도시의 구성 요소를 배치하는 경우, 필드의 셀이 총 4개의 층으로 구성됩니다.
Footnotes
| [1] | 생물과 무생물을 구별하는 가장 핵심적인 특징은 [ 자기증식능력 / 에너지변환능력 / 항상성유지능력 ]을 가지고 있어야 합니다. 위키피디아:생물 |
| [2] | 위키피디아:라이프게임 |
| [3] | 라이프 게임 테스트 |
| [4] | 질병관리본부:SIR모델 |
| [5] | 위키피디아:유한상태기계 |
| [6] | 위키피디아:형식언어 |
| [7] | 위키피디아:지능형에이전트 |
| [8] | CAIT:구동형에이전트 |
| [9] | 위키피디아:오델로(리버시) |
| [10] | 위키피디아:죄수의딜레마 |
| [11] | ``_ |
| [12] | ``_ |