Junsu Park

Passion

9 minute read

PCGRL 논문링크

Keyword

논문에 나오는 키워드 정리

  • OpenAI Gym : OpenAI에서 제공하는 Gym이라는 오픈소스 파이썬 라이브러리로 강화학습 알고리즘을 개발하고 비교할 수 있게 해주는 툴킷이다.
  • Markov Decision Process : 강화학습이 푸는 문제들의 대부분은 MDP로 표현되며, 의사결정 과정을 모델링하는 수학적인 틀을 제공한다
    • discount factor : reward 조절 관련 요소
  • search based PCG, Method : 논문링크 / Togelius et al. 2011
  • PCG : Procedural Content Generation
  • supervised sequence
  • Markov Chain
  • LSTM
  • Q-Learning


1. Abstract

2. Introduction

강화 학습으로 레벨 생성을 공식화 하는 것이 목표이다.
=> observation space, Action space, reward schemes(보상 체계)를 공식화하여 RL이 사용 가능하게 하는 것이 목표이다.

PCG에 대한 강화 학습 접근 방식은 기존 방식들에 비해 비교해봤을 때 몇 가지 잠재적인 장점이 있다.

  • Serach Based PCG와 비교했을 때
    • 머신러닝 접근 방식은 훈련 후 요청 시 검색(search)이 필요하지 않기 때문에 훨씬 빠르게 새로운 level을 생성할 수 있다.
    • PCGRL에서도 시간소비가 소요되는건 마찬가지만, infrence 하는 시간 소비 부분을 training하는 소비 부분으로 옮긴다. (search Based PCG에는 학습단계가 존재하지 않고, PCGRL에서 긴 학습 단계가 필요하다.)
  • 지도 학습(Summervile et al. 2018)과 비교했을 때 가장 큰 장점은 훈련 데이터가 필요하지 않다는 것이다.
  • 또 다른 장점은 훈련된 정책의 증분 특성(incremental nature)으로 인해 콘텐츠가 인간 사용자와 함께 생성되는 PCG에 대한 interactive 및 mixed-initiative 접근 방식에 더 적합하다는 것이다. (Yannakakis, Liapis, and Alexopoulos 2014)


2차원 level에 초점을 맞춤

  • Sokoban
  • Zelda의 전설

강화 학습 문제로 게임 레벨의 세 가지 다른 표현(representation)을 공식화 한다.

  • narrow representation
  • turtle representation
  • wide represention

보상 체계(reward schemes) 및 에피소드길이에 관해 올바른 선택이 주어지긴 하지만 세 가지 representation 모두 세 게임 시나리오에서 성공할 수 있는 것을 발견했다.

3. Background

Procedural level generation 연구는 최근 기계 학습의 발전 이후 더 많은 기계 학습 기술들을 통합하기 시작했다. (Jain et al. 2016; Volz et al. 2018)

image

그러나 강화 학습(RL)은 비디오 게임에서 성공한 후에도 PCG에 거의 적용되지 않았습니다(Mnih et al. 2015). 아마도 레벨 생성 프로세스를 RL 문제로 구성하는 방법이 불분명하기 때문일 수 있습니다.

한 가지 해결책은 콘텐츠 생성을 반복적인 프로세스로 구성하는 것입니다. 여기서 각 단계에서 에이전트는 Guzdial, Liao, and Riedl(2018)의 작업 아이디어와 유사하게 콘텐츠의 작은 부분을 수정하려고 합니다. 여러 연구자들이 Markov Chains(Snodgrass and Ontan~on 2014) 및’ LSTM(Summerville 및 Mateas 2016)과 같은 supervised sequence 학습 방법을 사용하여 플랫포머 level을 구축하기 위한 반복 생성 아이디어를 탐구했습니다.

순차적인 관점에서 level generation을 보면 에이전트가 현재 레벨을 개선하기 위해 작고 반복적인 변경을 수행하는 MDP(Markov Decision Process)로 공식화할 수 있습니다. 예를 들어, McDonald (2019)는 3D 빌딩 생성 프로세스를 MDP로 공식화합니다. 그것들은 상태 공간(state space)을 여러 직육면체의 위치로 정의하는 반면, 작업 공간(action space)은 데카르트 축을 따라 이러한 직육면체의 움직임에 해당합니다. 그들은 (직육면체 사이의 교차를 최소화하면서 접촉하게 만드는) 행동에 대해 보상합니다. 그들은 어떤 학습도 하지 않습니다. 대신 그들은 즉각적인 보상을 최대화하기 위해 다음 행동을 선택하는 greedy agent를 사용합니다.

Earle(2019)는 A2C(Mnih et al. 2016)를 사용하여 프랙탈 신경망을 훈련하여 SimCity(Will Wright, 1989)를 재생합니다. 이 작업이 PCG에 RL을 사용하는 아이디어를 다루지는 않지만 훈련된 모델이 게임 레벨을 구성할 수 있는 도시를 설계하기 때문에 PCGRL을 향한 단계로 볼 수 있습니다. 게임 콘텐츠를 직접 생성하기 위해 RL을 사용한 유일한 작업은 Chen et al. (2018) 및 Guzdial et al. (2019). Chen et al.의 작업에서 Q-Learning(Watkins and Dayan 1992)은 검색 기반 방법을 능가하는 deck-building system을 훈련하는 데 사용됩니다. Guzdial et al.의 작업에서 그들은 능동 학습을 사용하여 훈련된 모델을 사용자 선택에 맞게 업데이트하는 Super Mario Bros(Nintendo, 1985)의 레벨을 설계하기 위한 혼합 이니셔티브 도구(mixed initiative tool)를 제안했습니다. 이 논문은 모델을 처음부터 훈련하기 위해 RL을 사용하지 않았지만 시스템은 사용자 선택에 성공적으로 적응했습니다.

4. PCGRL 프레임워크

PCGRL 프레임워크는 전체 콘텐츠를 한 번에 생성하는 대신 PCG 프로세스를 반복 작업으로 캐스트합니다. 따라서 콘텐츠 생성을 MDP로 보고 각 단계에서 에이전트는 관찰과 보상을 받은 다음 조치로 응답합니다. 이 작업에서는 레벨 생성 작업만 살펴보겠지만 여기에서 논의할 모든 내용은 다른 유형의 콘텐츠 생성에도 적용될 수 있습니다.

반복적인 콘텐츠 생성이라는 아이디어를 실현하기 위해 무작위 타일로 채워진 레벨에서 시작합니다. 각 단계에서 에이전트는 레벨을 약간 변경할 수 있습니다(예: 타일 하나). 이 변경 사항은 레벨의 목표를 위한 target과 관련하여 시스템에서 판단 될 것입니다. 그리고 보상을 할당합니다. 보상은 그 작은 변화가 에이전트를 목표 상태에 얼마나 더 가깝게 했는지 반영해야 합니다. 예를 들어: PacMan(NAMCO, 1980) 레벨을 생성하는 경우 목표 중 하나는 플레이어를 한 명만 두는 것입니다. 플레이어가 없을 때 플레이어를 추가하는 변경은 긍정적인 변경이고 그렇지 않은 경우에는 마이너스입니다. 시스템은 또한 생성 프로세스의 정지 지점을 결정해야 합니다(영원히 걸리지 않도록 반복 횟수 제한).

모든 게임에서 프레임워크를 쉽게 구현할 수 있도록 세 부분으로 나누고 생성 프로세스에서 게임 관련 정보를 분리합니다. 이러한 부분은 Problem 모듈, Representation 모듈 및 Change Percentage입니다.

  • Problem 모듈은 목표(goal), 보상 기능(reward function) 등과 같은 생성된 level에 대한 정보를 저장합니다.
  • Representation 모듈은 현재 level을 에이전트에 대해 실행 가능한 Observation state로 변환하는 역할을 합니다.
  • Change Percentage은 에이전트가 에피소드가 진행되는 동안 콘텐츠에 영향을 줄 수 있는 변경될 수 있는 횟수를 제한하여 콘텐츠를 너무 많이 변경하는 것을 방지합니다.

그림 1(콘텐츠 생성을 위한 PCGRL 시스템 아케텍처)은 PCGRL 에이전트-환경 루프를 보여줍니다. 에이전트는 현재 상태(St)를 관찰하고 이를 기반으로 액션(at)을 Representation 모듈로 보내고, 이는 다시 상태(St)를 다음 상태(St+1)로 변환합니다. 이 두 가지 상태(St 및 St+1)는 모두 problem 모듈로 보내지며 맵 품질에 대한 변경의 영향을 평가하고 새 보상(rt+1)을 반환합니다. 이 새로운 보상과 새로운 상태(St+1)는 에이전트로 돌아가고 루프는 계속됩니다. 루프가 맵을 많이 변경하는 경우 종료 신호(et+1)를 전송하여 일찍 종료될 수 있습니다.

훈련 후 이러한 에이전트는 Generator로 사용됩니다. 고정된 step(단계) 횟수 동안 무작위로 초기화된 맵을 반복합니다. stemp마다 약간 개선하거나 완전히 변형합니다.

Problem

Problem 모듈은 현재 생성 작업에 대한 모든 정보를 제공하는 역할을 합니다. 예를 들어: Super Mario Bros(Nintendo, 1985) 레벨을 생성하려고 하면 Problem 모듈은 level size, 레벨에 나타날 수 있는 객체 타입 등을 지원합니다. 이 모듈은 두 가지 기능을 제공합니다.

image

  • 첫 번째 기능은 특정 에이전트 작업 후 생성된 콘텐츠의 품질 변화를 평가합니다. 예를 들어, 에이전트가 게임 레벨에서 개체를 제거하면 문제 모듈은 레벨 품질의 결과적인 변화를 평가하고 에이전트가 학습하는 데 사용할 수 있는 보상 값을 반환합니다.
  • 두 번째 기능은 목표에 도달한 시점을 결정하여 생성 프로세스를 종료합니다. 예를 들어 집 layout을 생성하는 경우 특정 수의 방이 생성된 후 생성을 종료할 수 있습니다. 우리는 generator를 배우고 단일 레벨을 찾지 않기 때문에 가능한 많은 레벨로 이어지는 문제에 대한 목표를 정의하는 것이 중요합니다. 예를 들어: 10x10 미로의 목표 함수(goal function)가 경로 길이가 54(이러한 지도의 두 타일 사이에서 가능한 가장 긴 경로)인 레벨을 갖는 것이라면 모델은 이러한 지도만 생성하는 방법을 학습합니다. 디자이너가 단일 레벨을 찾고자 한다면 이것은 괜찮지만, 이를 위한 많은 최적화 기술이 있으며 여기서는 여러 개의 개별 레벨을 생성하는 방법을 배우는 데 중점을 둡니다.

Representation

콘텐츠 생성을 MDP로 모델링하려면 state space(상태 공간), action space(동작 공간) 및 transition function(전환 기능)을 정의해야 합니다. Representation 모듈은 이 변환을 담당합니다. 그 역할은 문제를 초기화하고 현재 상태를 유지하며 에이전트의 조치에 따라 state(상태)를 수정하는 것입니다.

단순화를 위해 생성된 레벨을 정수의 2D 배열로 표현합니다. 여기서 배열의 위치는 레벨의 위치에 해당하고 값은 해당 위치의 객체 유형을 정의합니다. 예를 들어: 그림 2는 2D 배열로 Sokoban(Thinking Rabbit, 1982) level과 해당하는 level을 보여줍니다. 이 제약(constraint)으로 인해 Bhaumik et al.의 작업에서 사용된 것과 동일한 representation을 쉽게 채택할 수 있습니다. (2019) 트리 검색 알고리즘을 사용하여 레벨 생성에 대해. 그 작업에서 그들은 다음과 같은 표현을 정의했습니다.

  • Narrow : 문제를 나타내는 가장 간단한 방법입니다. 각 단계에서 에이전트에게 현재 상태와 위치가 제공되는 셀룰러 오토마타(Wolfram 1983)에서 영감을 받았습니다. 그런 다음 해당 위치에서 변경할 수 있습니다. Observation space는 현재 상태(2D 정수 배열)와 수정 위치(2D 배열의 x 및 y 인덱스)로 정의됩니다. Action space는 작업 없음(현재 위치 건너뛰기) 또는 타일 변경 작업으로 정의됩니다.(0에서 n -1 사이의 값, 여기서 n은 problem 모듈에서 제공하는 타일 타입의 수 (타일 변경을 할 때 변경하게 될 타일의 종류))

  • turtle : 로고(Bolt and Newman 1967)와 같은 거북이 그래픽 언어에서 영감을 얻었습니다. 여기서 각 단계에서 에이전트는 길을 따라 이동하고 특정 타일을 수정할 수 있습니다. Observation space는 현재 상태(2D 정수 배열)와 현재 에이전트 위치(2D 배열의 x 및 y 인덱스)로 표시됩니다. Action space는 다음과 같이 정의됩니다: 이동 행동(에이전트를 위, 아래, 왼쪽 또는 오른쪽으로 이동) 또는 타일 변경 동작(0에서 n -1 사이의 값, 여기서 n은 숫자임)

image [figure3 이미지] Location data is being transformed as an image translation (위치 데이터를 이미지로 변환 중입니다.)

  • Wide : SimCity 플레이에 대한 Earle의 작업(2019)과 유사합니다. 각 단계에서 에이전트는 위치와 타일 유형을 완전히 제어할 수 있습니다. Observation space는 현재 상태(2D 정수 배열)입니다. Action space는 영향을 받는 위치(레벨의 x 및 y 위치) 및 타일 변경 작업(0에서 n-1 사이의 값, 여기서 n은 문제 모듈에서 제공하는 타일 유형의 수)으로 정의됩니다.

각 Representation은 에이전트의 고유한 클래스에 해당합니다. Narrow presentation이 있는 것들은 미리 결정된 빌드 위치 시퀀스에 종속됩니다. Turtle presentation이 있는 것들은 현재 위치에 대한 지역 제어를 갖지만 마지막 위치에 대해서만 상대적입니다. Wide presentation이이 있는 사람들(those?)은 모든 권한을 가집니다. 또한 하이브리드 표현(예: 에이전트가 주어진 위치 주변의 작은 영역을 수정할 수 있는 narrow와 wide를 섞어서)을 개발하거나 작업 계획을 수정할 수 있습니다(예: 타일 한 개 대신 여러 개의 타일 변경).

Change Percentage

Change percentage(변경 비율)는 에이전트가 레벨의 전체 크기에 대한 백분율로 변경할 수 있는 타일 수를 정의하는 중요한 매개변수입니다. 에이전트가 모든 타일을 변경할 수 없도록 훈련 중 에피소드의 길이를 제한합니다. discount factor와 유사하게 생각할 수 있습니다. 에이전트가 얼마나 탐욕스러워야 하는지를 정의합니다. 예를 들어, 비율이 작으면 에이전트가 맵을 아주 조금만 변경할 수 있다는 의미이므로 에이전트는 더 높은 단기 보상을 얻기 위해 더 greedy action을 배우게 됩니다. 반면에 비율이 높으면 에이전트가 맵을 최대한 변경할 수 있으므로 에이전트는 문제에 대한 욕심이 덜하고 최적의 솔루션을 학습하게 됩니다.

더 greedy한 에이전트가 optimal한 에이전트보다 선호되는 이유가 궁금할 수 있습니다. 항상 최적의 레벨을 만드는 에이전트는 initial random level layout을 신경 쓰지 않습니다. 이는 완전한 정보가 주어지면 에이전트가 single optimal solution으로 수렴한다는 것을 의미합니다. 우리는 입력 수준을 입력에서 영감을 받은 새로운 레벨로 변환할 수 있는 디자이너 역할을 하는 에이전트를 원하기 때문에 이것은 목표가 아닙니다. 이에 대한 여러 가지 가능한 솔루션이 있습니다. 우리는 에이전트 작업을 제한하는 접근 방식을 사용하여 가장 직접적인 접근 방식이므로 환경에 최소한의 변경을 가하도록 하기로 결정했습니다.

=> 최적의 솔루션을 뽑아 내게되면, 여러 레벨디자인을 볼 수 없다.

Experiments

image [figure4 이미지] The Success percentage of generating levels from random a initial state with respect to the change percentage. (Chage percentage에 대한 임의의 초기 상태에서 레벨 생성 성공 확률입니다.)

우리의 PCGRL 프레임워크1는 OpenAI Gym(Brockman et al. 2016) 인터페이스로 구현되어 기존 에이전트와 호환됩니다. 우리는 세 가지 고유한 Representation(Narrow, Turtle, Wide)과 Problem(Binary, Zelda 및 Sokoban)을 사용하여 프레임워크를 테스트합니다. 모든 문제에 대해 reward function은 문제의 목표에 도달하는 데 도움이 되는 행동을 선호하고 문제에서 멀어지는 사람(에이전트?)들을 처벌합니다. 목표에 도달하면 문제가 종료됩니다.

  • Binary : 가장 쉬운 작업입니다. 목표는 지도의 두 지점 사이의 가장 긴 최단 경로가 최소 X(실험에서 X = 20)개의 타일만큼 증가하고 모든 빈 공간이 연결되도록 솔리드 및 빈 공간의 2D 맵을 수정하는 것입니다.

  • Zelda: 목표는 GVGAI 프레임워크(Perez et al. 2019)에 대한 The Legend of Zelda(Nintendo, 1986)의 던전 시스템 포트인 Zelda의 2D 레벨을 수정하는 것입니다. 게임의 목표는 플레이어를 이동시켜 열쇠를 잡은 다음 움직이는 적에게 죽임을 당하는 것을 피하면서 문에 도달하는 것입니다. 따라서 레벨에는 정확히 1명의 플레이어, 1개의 문 및 1개의 키(다른 게임 개체)가 있어야 하며 플레이어는 키에 도달한 다음 최소한 X 단계로 문에 도달할 수 있어야 합니다(X = 16으로 설정). 적은 플레이어와 너무 가깝게 생성될 수 없습니다(실험에서는 3타일 이상 떨어져 있음).

  • Sokoban : 목표는 일본 퍼즐 게임인 Sokoban(Thinking Rabbit, 1982)을 위한 2D 레벨을 생성하는 것입니다. 여기에서 플레이어는 모든 상자를 벽에 걸리지 않도록 하면서 특정 목표 위치를 향해 모든 상자를 밀어야 합니다. 따라서 레벨에는 정확히 1명의 플레이어와 동일한 수의 상자와 목표가 있어야 하며, 모두 플레이어가 도달할 수 있습니다. 이 경우 Sokoban 솔버(제한된 깊이(약 5000개 노드)를 갖는 트리 검색 알고리즘(BFS 및 A*))를 사용하여 레벨이 최소한 X 단계(X = 18로 설정)로 풀릴 수 있는지 확인합니다.

자가진단

  1. 저자가 뭘 해내고 싶어했는가?
    • RL을 사용한 Level 절차적 생성
  2. 이 연구의 접근에서 중요한 요소는 무엇인가?
    • RL로 표현하기 위해선 MDP로 표현되어야 하는데, 그 표현을 만들어주는 방법이 narrow, turtle, wide이다.
    • 그리고 최적의 해를 찾는 것이 아닌, 여러 레벨디자인의 영감을 떠올릴 수 있도록 인간과 협업가능한 에이전트를 만드는 것이 목표이다.
  3. 당신(논문독자)은 스스로 이 논문을 이용할 수 있는가?
    • 아직 아니다. 오픈 소스를 받아서 응용할 수 없다.
    • 이제 살짝 할 수 있을 것 같기도..?
  4. 당신이 참고하고 싶은 다른 레퍼런스에는 어떤 것이 있는가?

You may also enjoy

조건부 확률

less than 1 minute read

조건부 확률 사건 A,B가 표본공간 S의 두 부분집합이며, 사건 A가 일어났다는 조건 하에 사건 B가 일어날 확률을 사건 A가 일어났을 때 사건 B의 조건부 확률이라 한다. 이는 기호로 다음과 같이 표현한다. \[ P(B|A) = \frac{P(A \cap B)}{P(A)} \]