먼저, 절차적 콘텐츠의 생성을 유전 알고리즘을 이용해 연구한 논문 [8]이 있다. 게임에서 생성되는 몬스터의 주요 속성을 유전 알고리즘의 유전자로 구성하고, 사용자와 몬스터의 전투 시뮬레이션으로 유전자를 평가한다. 그 평가를 토대로 유전자들 교배하여 플레이어 적응형 몬스터를 생성한다.

본 논문의 인공신경망은 입력층, 은닉층, 출력층의 3가지 층과 각 층을 연결하는 시냅스 역할의 가중치 (weights)를 가지고 있다. 계산량을 줄여 유전 알고리즘 알고리즘을 구현하기 위해 가장 간단한 형태의 인공신경망을 구축한다. 입력층과 출력층은 노드 4개로 한 층씩 두고, 은닉층은 노드 10개, 20개, 10개로 세 층을 둔다.

게임에서 생성되는 몬스터의 주요 속성을 유전 알고리즘의 유전자로 구성하고, 사용자와 몬스터의 전투 시뮬레이션으로 유전자를 평가한다. 그 평가를 토대로 유전자들 교배하여 플레이어 적응형 몬스터를 생성한다. 비슷한 주제로 게임 몬스터 생성에 적합한 유전 알고리즘을 연구한 논문 [9]이 있는데, 기존 유전 알고리즘과 달리 상동염색체 구조를 갖도록 하였다.

따라서 이 팩맨 게임을 수행하는 데에 얼마나 적합한 지 알 수 있도록 설정해야 한다. 단순히 팩맨 게임의 결과인 포인트로 설정하지 않고, 게임의 가장 중요한 요소인 생존을 위해 유령 회피 횟수를 적합도로 선정했다. 팩맨이 진행하는 방향이 유령의 방향과 같으면 적합도는 감소하고, 유령의 방향과 다르면 적합도는 증가한다.

본 논문에서는 고성능의 팩맨 AI를 구현할 강화학습을 위하여 유전 알고리즘 뿐 아니라 다층 퍼셉트론 구조의 간단한 인공신경망을 활용하였다. 미로와 같은 팩맨 게임의 맵 구조상, 주어진 환경을 인식하고 판단을 내릴 알고리즘으로 인공신경망이 적합하였다.

본 논문에서는 연구 [14]와 달리 선택압의 설정 등에 집중하지 않고 유전 알고리즘과 인공신경망을 단순하게 결합하였다. 자연계에서 모방한 알고리즘들의 단순한 결합만으로 강화학습의 수준이 어느 정도 되는가를 확인하고 필요하면 향후 연구에서 역전파 알고리즘을 이용한 보완을 계획하기 위해서이다.

개발 언어로는 파이썬을 사용하였다. 본 논문에서는 연구의 실질적인 내용인 시뮬레이터 기능을 주로 서술한다.

본 논문에서는 팩맨 게임의 강화학습을 위하여 유전 알고리즘 뿐 아니라 다층 퍼셉트론 구조의 인공신경망 또한 활용한다. 미로와 같은 팩맨 게임의 맵 구조상, 주어진 환경을 인식하고 판단을 내릴 알고리즘이 필요하기 때문이다.

본 논문의 인공신경망은 입력층, 은닉층, 출력층의 3가지 층과 각 층을 연결하는 시냅스 역할의 가중치 (weights)를 가지고 있다. 계산량을 줄여 유전 알고리즘 알고리즘을 구현하기 위해 가장 간단한 형태의 인공신경망을 구축한다.

이는 심층학습에서 추론단계의 소비전력을 최적화시키는 문제와도 연관이 있다. 본 연구에서 사용된 인공신경망은 노드 10, 20, 10개의 은닉층과 노드 4개의 입력, 출력층으로 구성된 간단한 구조로서 복잡한 가중치를 가지는 깊은 인공신경망이 아니므로 추론단계에서 최적화된 유전 알고리즘 사용이 가능한 것이다.

또한 유전 알고리즘은 탐색공간이 매우 크거나 일반적인 해를 찾기 힘든 문제에서 뛰어난 성능을 발휘하며, 반드시 최적해가 필요한 경우가 아닐 때 유용하다 [7]. 본 연구에서는 이 유전자가 각각 팩맨 AI가 되어 게임을 반복하며 진행한다. 각 유전자가 마친 게임의 결과를 토대로 교연산과 변이 연산을 거치면 더 좋은 게임 결과를 이룰 수 있는 새로운 세대가 만들어지는 것이다.

그 평가를 토대로 유전자들 교배하여 플레이어 적응형 몬스터를 생성한다. 비슷한 주제로 게임 몬스터 생성에 적합한 유전 알고리즘을 연구한 논문 [9]이 있는데, 기존 유전 알고리즘과 달리 상동염색체 구조를 갖도록 하였다. 각 개체가 하나의 유전자를 갖는 것이 아닌 한 쌍의 대립 유전자를 지니게 하였고, 실험 결과 이러한 구조가 성능에 더 좋은 영향을 미치는 것으로 밝혀졌다.

팩맨 게임의 룰은 유령을 피하여 오래 생존하고 포인트를 먹어나가는 것이다. 이러한 게임 규칙에 따라 강화학습을 진행할 환경과 인식해야할 대상이 명확하여 간단한 인공지능을 설계해보기에 적합하므로 팩맨 게임을 선택하였다. 또한 인공신경망의 강화학습엔 일반적인 방식인 역전파 (Back propagation) 알고리즘이 있는데 본 연구에서는 인공신경망에 역전파 알고리즘을 적용하지 않은 단순한 다중 퍼셉트론 구조를 사용하여 유전 알고리즘과 결합하였을 때, 역전파 알고리즘만큼의 효율이 나오는지 알아보고 향후 연구를 계획할 수 있는 근거를 만들고자 하였다.

Evasion 컬럼이 적합도를 의미한다. 이렇게 한 세대에 유전자 번호가 0부터 15까지 존재하며, 세대가 지날수록 데이터가 어떻게 변하는지 분석했다.

강화학습 분야에는 상태공간의 문제, 캐릭터의 자동화 등의 문제가 있는데, 캐릭터의 자동화를 다룬 연구들은 서양보드 게임인 오델로, 틱택토 외에 슈팅게임 등을 다루고 있다. 이렇듯 게임 분야에서 활발하게 쓰이는 캐릭터의 자동화를 위한 강화학습을 본 논문에서는 고전 게임 팩맨에 적용하고자 한다.

이러한 게임 난이도 조절에 대해 유전 알고리즘을 이용해 연구한 논문 [10]이 있다. 테트리스 게임에 유전 알고리즘을 적용하여 게임 플레이 중 사용자의 성향과 게임 적응도를 분석하고 그에 맞도록 적당한 난이도를 제공한다.

강화학습이 가능한 팩맨 AI가 사람을 능가했는지 확인하기 위해 테스트 플레이어 10명의 게임 결과 데이터와 AI의 게임 결과 데이터를 비교, 분석하였다. 테스트 플레이어들은 최소 15번, 최대 22번의 게임을 진행하였으며 최대 점수와 평균 점수를 계산하여 AI와 비교하였다.

강화학습이 가능한 팩맨 AI가 사람을 능가했는지 확인하기 위해 테스트 플레이어 10명의 게임 결과 데이터와 AI의 게임 결과 데이터를 비교, 분석하였다. 테스트 플레이어들은 최소 15번, 최대 22번의 게임을 진행하였으며 최대 점수와 평균 점수를 계산하여 AI와 비교하였다.

강화학습을 위한 환경 인식과 그에 따른 판단을 내릴 인공신경망을 구현하였으므로, 인공신경망이 판단을 올바르게 할 수 있도록 학습을 시켜야한다. 그 방법으로 유전 알고리즘을 사용하였다. 이는 심층학습에서 추론단계의 소비전력을 최적화시키는 문제와도 연관이 있다.

인공신경망과 유전 알고리즘을 적용한 파라미터 설계 방법론을 연구한 논문 [12]에서는 기계학습 기반의 파라미터 설계 절차를 3단계로 구성하는데, 첫 번째로 인공신경망 구축에 필요한 데이터를 수집하고, 두 번째로 수집한 데이터를 기반으로 인공신경망을 구축한다. 마지막으로 최적의 공정조건을 도출하기 위해 유전 알고리즘을 적용한다. 이때 일반적인 문제에서는 적합도 함수로서 평균 및 산포의 반응함수를 사용하지만, 연구 [12]에서는 반응함수를 대신해 인공신경망을 사용한다.

팩맨 AI의 강화학습을 위해 유전 알고리즘과 인공신경망을 사용하여 구현한다. 한 세대의 개체군은 16이며, 각각의 유전자는 인공신경망으로 이뤄진다.

또한 유전 알고리즘의 핵심인 적합도를 설정함에 있어서 팩맨 게임의 점수인 포인트를 고려하지 않고, 게임의 가장 중요한 요소인 생존을 위해 유령을 회피한 횟수를 사용하여 시간에 구애받지 않고 높은 점수를 달성할 수 있게 하였다. 10여명의 플레이어로 테스트한 결과, 적합도 200이상을 달성한 팩맨 AI가 모든 참여자들보다 높은 평균 점수를 기록하는 것을 확인하였다. 또한 적합도 400 이상을 달성한 팩맨 AI는 유령으로 포위된 상황을 탈출함으로써 사람으로서는 불가능한 플레이를 보여주었다.

비슷한 주제로 게임 몬스터 생성에 적합한 유전 알고리즘을 연구한 논문 [9]이 있는데, 기존 유전 알고리즘과 달리 상동염색체 구조를 갖도록 하였다. 각 개체가 하나의 유전자를 갖는 것이 아닌 한 쌍의 대립 유전자를 지니게 하였고, 실험 결과 이러한 구조가 성능에 더 좋은 영향을 미치는 것으로 밝혀졌다.

미로와 같은 팩맨 게임의 맵 구조상, 주어진 환경을 인식하고 판단을 내릴 알고리즘으로 인공신경망이 적합하였다. 또한 유전 알고리즘의 핵심인 적합도를 설정함에 있어서 팩맨 게임의 점수인 포인트를 고려하지 않고, 게임의 가장 중요한 요소인 생존을 위해 유령을 회피한 횟수를 사용하여 시간에 구애받지 않고 높은 점수를 달성할 수 있게 하였다. 10여명의 플레이어로 테스트한 결과, 적합도 200이상을 달성한 팩맨 AI가 모든 참여자들보다 높은 평균 점수를 기록하는 것을 확인하였다.

10여명의 플레이어로 테스트한 결과, 적합도 200이상을 달성한 팩맨 AI가 모든 참여자들보다 높은 평균 점수를 기록하는 것을 확인하였다. 또한 적합도 400 이상을 달성한 팩맨 AI는 유령으로 포위된 상황을 탈출함으로써 사람으로서는 불가능한 플레이를 보여주었다.

본 논문에서는 고성능의 팩맨 AI를 구현할 강화학습을 위하여 유전 알고리즘 뿐 아니라 다층 퍼셉트론 구조의 간단한 인공신경망을 활용하였다. 미로와 같은 팩맨 게임의 맵 구조상, 주어진 환경을 인식하고 판단을 내릴 알고리즘으로 인공신경망이 적합하였다. 또한 유전 알고리즘의 핵심인 적합도를 설정함에 있어서 팩맨 게임의 점수인 포인트를 고려하지 않고, 게임의 가장 중요한 요소인 생존을 위해 유령을 회피한 횟수를 사용하여 시간에 구애받지 않고 높은 점수를 달성할 수 있게 하였다.

분석 결과, 그림 6과 같이 팩맨 AI의 최대 점수보다 더 높거나 비슷한 점수를 기록한 플레이어들이 몇몇 있었지만 대체로 플레이어들이 더 낮은 점수를 기록하였다. 그러나 최대 점수에서 AI와 플레이어의 확연한 차이는 눈에 띄지 않았다.

이와 비슷한 연구로 게임 환경에서 유전 알고리즘과 인공신경망을 이용한 경로탐색에 대한 연구 [13]이 있다. 이 연구에서는 유전 알고리즘과 인공신경망 두 가지 알고리즘을 각각 사용하여 실험했는데, 유전 알고리즘보다 인공신경망을 활용한 경우가 경로탐색 문제해결에 더 적합한 결과를 보여주었다. 본 논문에서 유전 알고리즘과 인공신경망을 결합한 연구를 진행하는데 참고하였다.

단순히 팩맨 게임의 결과인 포인트로 설정하지 않고, 게임의 가장 중요한 요소인 생존을 위해 유령 회피 횟수를 적합도로 선정했다. 팩맨이 진행하는 방향이 유령의 방향과 같으면 적합도는 감소하고, 유령의 방향과 다르면 적합도는 증가한다. 이렇게 설정한 적합도를 기준으로 상위 유전자를 4개 뽑는다.

그림 4와 그림 5를 보면 10세대 정도까지는 적합도와 함께 게임의 결과 값인 생존시간 및 총 점수가 증가하는 것을 볼 수 있으나, 40세대 정도까지 지역 최적점을 벗어나지 못하는 것을 확인할 수 있다. 하지만 40세대 중반쯤부터 적합한 변이가 일어나 지역 최적점을 돌파하고 높은 적합도와 게임결과 값을 달성하는 것을 확인할 수 있다.

그러나 인공신경망에 유전 알고리즘을 단순히 결합한 형태의 진화속도 자체는 예상보다 느렸고 지역 최적점 문제 등의 한계로 인해 기존 강화학습기법인 역전파 알고리즘보다 효율적인지는 의심스럽다. 그러므로 향후 연구에서는 각 세대의 신경망을 역전파 알고리즘으로 최적화시킨 뒤 이 신경망들을 유전 알고리즘으로 재차 선별하는 구조를 적용해 볼 필요가 있다.

본 논문에서는 연구 [14]와 달리 선택압의 설정 등에 집중하지 않고 유전 알고리즘과 인공신경망을 단순하게 결합하였다. 자연계에서 모방한 알고리즘들의 단순한 결합만으로 강화학습의 수준이 어느 정도 되는가를 확인하고 필요하면 향후 연구에서 역전파 알고리즘을 이용한 보완을 계획하기 위해서이다.