Procedural Content Metageneration via Program Search and Continual Abstraction Discovery

Matthew Siper; Ahmed Khalifa; Julian Togelius

Source-linked AI summary

Procedural Content Metageneration via Program Search and Continual Abstraction Discovery

Matthew Siper, Ahmed Khalifa, Julian Togelius

arXiv:2608.17947v12026년 8월 18일cs.AIcs.LGcs.NE

TL;DR

Procedural content metageneration은 개별 레벨이 아니라 generator를 탐색해 게임별 generator를 만드는 데 드는 높은 비용을 자동화하려 한다. 이 논문은 LLM 기반 evolutionary program search 중 검증된 primitive를 추출하고 재사용하는 Continual Abstraction Discovery를 제안하며, 고정 helper API의 유무와 관계없이 네 게임 도메인에서 mean final best fitness가 더 높음을 보인다.

문제
Procedural content metageneration에는 재사용 가능한 search primitive가 필요하다. raw-code search는 유용한 routine을 반복해서 재생성할 수 있지만, 고정 helper API는 vocabulary를 확장할 수 없기 때문이다.
방법
Continual Abstraction Discovery는 evolutionary program search 중 high-fitness program에서 utility를 추출하고 검증한 뒤, run별 helper module에서 재사용한다.
결과
CAD는 run이 빈 helper function 또는 expert helper function으로 시작하는지와 관계없이 Sokoban, Zelda, Dangerous Dave, Lode Runner 전반에서 mean final best fitness를 높인다.
시사점 및 한계
학습된 library는 이후 program에 채택되며 validation, reachability, structural utility를 반복해서 복원한다. 이는 searchable program vocabulary의 adaptation을 뒷받침한다.
시사점 및 한계
이 접근법은 상당한 compute cost를 수반한다. 일반적인 50-generation run은 수백만 token과 수 시간의 wall-clock time을 사용한다.

Abstract

from arXiv · show

Large language models can generate executable programs, which makes it possible to search directly over procedural content generators rather than individual levels. We study this approach in Sokoban, Zelda, Dangerous Dave, and Lode Runner. Each run evolves complete Python generators through language-model mutation and crossover. We introduce Continual Abstraction Discovery, or CAD, which extracts reusable primitives from high-fitness programs into a run-specific helper module. A 2x2 experiment crosses CAD with access to a fixed hand-written domain API. The completed data set contains 160 complete runs, with at least ten 50-generation runs in every cell. CAD raises mean final best fitness in all eight domain and API comparisons. Across all CAD runs, learned libraries are adopted by most later programs and repeatedly rediscover validation, reachability, and structural utilities. These results support that discovering reusable primitives improves evolutionary program search for content generators.

I. 서론

이 논문은 개별 산출물이 아니라 실행 가능한 game generator를 탐색하는 문제로 procedural content metageneration을 정식화하고, LLM 기반 evolutionary program search를 사용한다. 또한 탐색 중 재사용 가능한 utility를 학습하는 Continual Abstraction Discovery (CAD)를 제안하고, 네 game domain에서 CAD를 고정 helper API와 비교 평가한다.

동기: Procedural content metageneration은 개별 산출물이 아니라 generator 자체를 탐색함으로써, 맞춤형 game-specific generator에 필요한 engineering과 반복 평가 문제를 다룬다.기존 접근법으로는 evolutionary computation, machine learning, reinforcement learning이 있으며, 많은 방법이 불투명한 representation을 생성한다.
접근법: LLM 기반 evolutionary search는 후보 program을 실행하고, 생성된 level을 평가하며, 그 feedback을 사용해 이후 mutation과 crossover를 유도한다.실행 가능한 source code는 compile하고 test할 수 있으며, designer가 수정하고 search system 밖에서도 재사용할 수 있다.
문제와 해법: Raw-code search는 유용한 routine을 독립적으로 재현할 수 있지만, hand-written helper API는 재사용 가능한 operation을 노출하는 대신 search 중 vocabulary를 확장할 수 없다.CAD는 run 중 실행 가능한 primitive 집합을 늘릴 수 있도록 허용해 이 한계를 해결한다.
기여: CAD는 고 fitness program에서 발견한 helper function을 추출하고, 검증하고, 재사용함으로써 evolutionary generator search를 개선한다.학습된 utility는 run별 helper module에 저장되며, program을 안전하게 refactor할 수 있을 때 사용된다.
실험 설계: 주요 연구는 CAD와 고정 expert helper API에 대한 access를 교차해, search 중 reusable vocabulary access와 vocabulary discovery를 분리한다.이 연구는 160개의 완료된 run에 걸친 2 × 2 design으로 구성된다.
결과: Sokoban, Zelda, Dangerous Dave, Lode Runner 전반에서 Positive CAD effects가 나타나며, 학습된 library의 growth, adoption, primitive도 분석한다.평가는 실행 가능한 Python-level generator를 사용하고 네 game domain 모두에서 효과를 보고한다.

II. 관련 연구

선행 연구는 게임 콘텐츠 생성을 위해 계산적, 학습 기반, 진화적 접근법을 폭넓게 다뤘지만, 특화된 constructive 또는 black-box generator는 재사용성과 해석 가능성을 제한한다. LLM 기반 레벨 생성은 여전히 성능이 엇갈리고 공간적·구조적 제약 처리에 어려움을 겪으며, 이는 CAD를 검색 시점의 abstraction mechanism으로 도입할 동기를 제공한다.

계산적 게임 콘텐츠 생성: Evolutionary computation, constraint satisfaction, supervised learning, reinforcement learning 은 모두 게임 콘텐츠 생성에 적용되어 왔지만, constructive generator 는 대체로 특정 게임에 종속되어 재사용하기 어렵다.이 부분은 다양한 생성 패러다임을 살펴보고, 기존 게임 생성기의 특화가 한계임을 지적한다.
LLM의 한계: LLM은 보장된 경로와 문·열쇠 수의 일치 같은 공간적·구조적 레벨 제약을 처리하는 데 어려움을 겪으며, 이는 취약한 공간 추론 능력,, [18]을 반영한다.이러한 실패에는 플레이어를 정확히 한 명으로 유지하고 문과 열쇠의 수를 같게 만드는 일이 포함된다.
진화적 프로그램 합성: fitness-guided evolutionary loop 내부의 LLM code generation은 genetic programming, 과 연결되며, 여기서 LLM은 mutation and crossover를 수행한다.구현 방식은 알려져 있지 않더라도 원하는 동작을 fitness function으로 지정할 수 있을 때 이 접근법이 유용하다.
Continual abstraction discovery: Voyager의 Minecraft library [24]와 같은 agent skill library와 달리, CAD는 고성능 generator에서 helper function을 지속적으로 추출하고 진행 중인 검색에서 사용할 수 있는 primitive를 변경한다.따라서 CAD는 해결된 task나 수동으로 노출된 skill의 기록이 아니라 검색 시점의 representation mechanism이다.
PCG의 표현: Machine-learning PCG는 일반적으로 불투명한 neural 또는 black-box generator를 학습하는 반면, evolutionary approach는 더 높은 수준의 인간 해석과 편집을 지원하는 symbolic generator를 학습할 수 있다,.이 대조는 CAD를 black-box representation만이 아니라 프로그램 수준의 구조를 유지하려는 연구 흐름 속에 위치시킨다.

III. 방법 … C. 평가 및 적합도

이 방법은 archive 기반 LLM mutation과 crossover를 통해 완전한 실행 가능 Python generator를 진화시키며, 각 candidate를 validity, quality, diversity 측면에서 평가한다. Robustness pipeline과 run 수준의 reflection memory가 신뢰성 있는 반복 search를 지원한다.

A. Program Representation: 각 candidate는 고정된 generate(context_dict) interface를 갖춘 완전한 Python program으로, uniform compilation, execution, inspection, evaluation을 가능하게 한다.Program은 grid dimensions와 initial level을 입력받은 뒤 tile grid를 반환하며, local functions, constants, layout routines를 유지한다.
A. Program Representation: 모든 run은 하나의 minimal seed program에서 시작하며, archive는 성공적으로 평가된 모든 individual을 보존한다.Seed는 tile constants와 generation logic가 없는 blank 또는 copied initial grid를 포함한다.
B. Evolutionary Search: 각 generation은 fitness-proportional probability로 archive에서 parent를 sampling하며, individual이 두 개 이상 존재할 때 probability 0.25로 crossover를 사용한다.정규화 전에 fitness 값에 10^-6의 하한을 적용하며, 실패한 crossover 시도는 mutation으로 대체된다.
B. Evolutionary Search: LLM은 parent programs, domain information, run memory, fixed generator contract를 사용해 mutation과 crossover를 수행한다.Mutation은 강한 behavioral edit를 요청하는 반면, crossover는 호환 가능한 mechanisms를 하나의 executable program으로 결합한다.
B. Evolutionary Search: 모든 candidate는 compilation과 smoke testing을 거치며, error-conditioned correction attempts를 수행하고 유효한 candidate가 나오지 않으면 zero fitness를 할당한다.Program은 다섯 smoke tests 중 최소 세 개를 통과해야 하며, 각 mutation 또는 crossover cycle은 최대 네 번 시도되고 failure types는 별도로 기록된다.
B. Evolutionary Search: 각 generation 후 LLM reflection call은 이후 search를 위해 run별 memory에 changes, outcomes, global lessons를 기록한다.이후 mutation 및 crossover prompts에는 각 parent의 원시 evaluation feedback 대신 누적된 global lessons가 전달된다.
C. Evaluation and Fitness: Fitness는 30 executions에 걸친 validity, benchmark quality, pairwise diversity의 평균이며, PCG Benchmark functions를 사용하고 crash 또는 validation failure에는 zero를 할당한다.용어 V, Q, D는 [0, 1]에 속하며, fitness는 3(V + Q + D)로 정의된다.

D. Continual Abstraction Discovery · IV. 실험 설계 · A. 도메인

이 연구는 고 fitness 프로그램에서 검증된 utility function을 지속적으로 추출하고, quality, diversity, 그리고 2초 실행 제한을 적용해 네 개의 타일 기반 PCG Benchmark 도메인에서 generator를 평가한다.

D. Continual Abstraction Discovery: generation 8 및 그 이후 매 5 generation마다, 시스템은 run 내부 프로그램 중 75th fitness percentile 이상인 프로그램에서 재사용 가능한 utility를 추출한다.제안된 각 function은 compile되고 smoke test를 통과해야 하며, refactoring 전에 최대 두 번의 compile correction이 허용된다.
D. Continual Abstraction Discovery: 승인된 refactoring은 재평가되고 archive entry가 업데이트되며, 추출된 function은 evolution 중 system library를 통해 사용할 수 있게 된다.ten-generation warmup 이후에도 success rate가 30% 미만으로 유지되면 refactoring을 비활성화한다.
IV. 실험 설계: 실험에서는 PCG Benchmark의 네 개 타일 기반 도메인을 평가한다.도메인은 Sokoban, Zelda, Dangerous Dave, Lode Runner다.
A. 도메인: Sokoban은 플레이어가 상자를 지정된 target location으로 미는 5x5 level을 사용한다.이 도메인은 일본 퍼즐 게임으로 설명된다.
A. 도메인: Zelda는 플레이어가 key를 획득하고 monster에게 죽지 않은 채 exit에 도달해야 하는 7x11 dungeon-crawler level을 사용한다.이 도메인은 원작 The Legend of Zelda game의 dungeon room에서 영감을 받았다.
A. 도메인: Dangerous Dave는 플레이어가 key를 획득하고 spike에 죽지 않은 채 goal에 도달해야 하는 7x11 platformer level을 사용한다.이 도메인은 동명의 game을 기반으로 한다.
A. 도메인: Lode Runner는 플레이어가 jump하지 않고 enemy를 피하면서 모든 gold를 수집해야 하는 11x16 puzzle-platformer level을 사용한다.Navigation에는 walking, digging, ladder, rope가 사용되며, quality와 diversity는 A∗ solver를 포함한 framework output에 의존한다. 각 generator call은 2초로 제한된다.

B. 요인 조건 · C. LLM 및 실행 구성

이 연구는 나머지 검색 파이프라인을 고정한 채 CAD와 손으로 설계한 Expert API를 helper function의 원천으로 검증하는 요인 설계를 사용한다. 모든 run은 지정된 generation 설정과 문서화된 계산 비용에 따라 GLM 5.2를 사용한다.

B. 요인 조건: 주요 연구는 CAD와 Expert API 접근을 교차시킨 네 가지 실험으로 구성되며, helper function의 유용성을 검증한다.CAD는 LLM이 program을 추상화하고 helper function을 생성하도록 한다.
B. 요인 조건: CAD는 검색 중 LLM이 program을 추상화하고 재사용 가능한 helper function을 생성하도록 한다.이 조건은 section III-D에 기술된 abstraction procedure를 따른다.
B. 요인 조건: Expert API는 entity normalization, reachability, repair, domain-specific structural operation을 위한 손으로 설계한 primitive를 제공한다.예시로 connect_floors_with_ladder와 ensure_one_player가 있다.
B. 요인 조건: Expert API는 helper function을 제공하는 것만으로 충분한지, 아니면 CAD가 여전히 필요한지를 검증한다.모든 실험은 동일한 minimal seed, evolutionary search, reflection memory, correction pipeline, evaluation setting을 사용한다.
C. LLM 및 실행 구성: 모든 language-model call은 GLM 5.2를 사용하며, mutation에는 temperature 0.2를, correction과 refactoring에는 0.1을 사용한다.이 설정은 실험의 language-model 및 execution configuration을 정의한다.
C. LLM 및 실행 구성: 평균적인 50-generation run은 약 9.5 million input tokens와 2.6 million output tokens를 사용하고, 비용은 약 $25이며, 약 2.5시간이 걸렸다.각 run은 generation statistics, program source, evaluation analysis, prompt, valid rendered level, evolution tree, reflection memory, CAD helper-module snapshot을 저장한다.

V. 결과 · A. 도메인 간 탐색 성능 · B. 학습 라이브러리의 성장과 도입

CAD는 네 도메인 모두에서 종점 탐색 성능을 향상시키며, 정확한 양측 sign-test 결과는 p = 0.008이다. 학습 라이브러리는 초기에 확장되고 도메인 전반에서 안정화되며, 이후 프로그램 대부분에 도입되는 동시에 Base 조건에서 최적 프로그램의 길이를 줄인다.

A. 도메인 간 탐색 성능: 고정 API에서는 Lode Runner가 CAD와 no-CAD 간 차이가 가장 크고, Base 대조에서는 Lode Runner의 차이가 작으며 Sokoban에서는 더 크다.
A. 도메인 간 탐색 성능: 사전 정의된 API가 API 없이 시작하는 경우보다 성능이 높은 도메인은 Zelda뿐이며, 저자들은 이를 문제의 단순성으로 설명한다.
A. 도메인 간 탐색 성능: 대표 레벨은 CAD를 사용할 때 시각적 다양성이 더 낮게 나타나며, 특히 Dangerous Dave에서 그러하다. 이는 해당 다양성 지표가 시각적 외관이 아니라 플레이어 해법의 궤적을 추적하기 때문이다.그림의 이미지는 출력 구조를 보여주며, 플레이 가능성은 benchmark 실행을 통해 평가된다.
B. 학습 라이브러리의 성장과 도입: 학습 라이브러리는 초기 추출 사이클 동안 급격히 확장된 뒤 네 도메인 모두에서 안정화된다.
B. 학습 라이브러리의 성장과 도입: 도우미 사용이 시작된 후, 이후 대부분의 세대에서 도입률은 약 80%를 웃돌며, 프로그램은 평균적으로 15에서 20회의 도우미 호출을 수행한다.
B. 학습 라이브러리의 성장과 도입: Base 조건에서 CAD는 최적 프로그램의 평균 길이를 대략 370줄에서 대략 296줄로 줄인다.
A. 도메인 간 탐색 성능: CAD는 모든 도메인에서 양의 종점 차이를 만들며, 모든 실험이 CAD에 유리하고 정확한 양측 sign-test 결과는 p = 0.008이다.고정 API에서 가장 큰 차이는 Lode Runner에서 나타나며, 이곳에서는 CAD가 계속 개선되는 반면 no-CAD는 더 일찍 정체된다.

C. 반복 추상화 발견 … B. 표현 적응으로서의 CAD

네 게임 모두에서 CAD는 평균 fitness를 향상시키며, expert API를 사용하는 Lode Runner에서 효과가 가장 크다. CAD는 재사용 가능한 generator 연산의 반복적으로 나타나는 핵심을 발견하는 동시에 각 run에 맞춰 library와 표현을 적응시킨다.

C. 반복 추상화 발견: CAD는 validation, reachability, structural operation을 반복적으로 발견하는 동시에 run별 utility의 긴 꼬리도 생성한다.in_bounds와 Entity Count Normalization은 각각 28개 CAD run에 나타나며, Ensure One Player와 Grounded Empty Cells는 24개에 나타난다.
C. 반복 추상화 발견: CAD는 난이도를 높이는 primitive를 추상화하여 생성된 level을 적응시키며, 여기에는 gold 옆이나 solution path 주변에 enemy를 배치하는 것이 포함된다.Figure 5는 Lode Runner에서 gold 옆에 enemy를 배치하는 primitive와 Zelda의 player-key-door critical path에서 떨어진 곳에 enemy를 배치하는 primitive도 보여준다.
A. Cross-Domain Evidence: CAD는 네 domain 모두에서 평균 fitness를 향상시키며, expert API를 사용할 수 있을 때 Lode Runner에서 효과가 가장 크다. 다른 세 API 비교에서도 p < 0.05 검정 없이 CAD가 우세하다.domain-specific callable routine이 이미 제공되는 경우에도 run별로 학습된 vocabulary가 best fitness를 향상시킨다.
B. 표현 적응으로서의 CAD: 학습된 helper vocabulary는 후속 program에 채택되며 entity normalization, player placement, reachability, connectivity, structural construction을 반복적으로 처리한다.CAD는 Python을 실행 substrate로 유지하면서 후속 variation call에서 사용할 수 있는 operation을 바꾼다.
B. 표현 적응으로서의 CAD: 학습된 library는 하나의 고정된 library로 수렴하기보다 반복되는 핵심과 domain 및 history에 따라 형성된 utility를 결합한다.이러한 반복 핵심과 꼬리 구조는 tile-based generator search 전반에서 CAD가 적응하는 특징으로 기술된다.
B. 표현 적응으로서의 CAD: CAD는 best Base program을 더 짧게 만드는 반면, 고정 API는 이미 compact한 source library를 생성한다.Figure 4는 CAD 유무에 따른 Base 및 API prompting의 best-solution line count를 비교한다.
VI. Discussion: 더 짧은 program이 본질적으로 더 우수하다는 근거는 제시되지 않는다. 대신 재사용 가능한 callable vocabulary가 generator에서 logic을 덜어내어 후속 수정과 보존을 쉽게 할 가능성이 있다.이 해석은 program length만이 아니라 expressiveness와 maintainability에 관한 것이다.

C. 실용적 시사점 및 한계 · VII. 결론

이 연구는 Continual Abstraction Discovery가 네 가지 procedural-content 도메인 전반에서 evolutionary program search를 개선하지만, 실제 활용은 평가 공백, 상당한 compute 비용, 그리고 분리되지 않은 pipeline 구성요소로 제약된다는 점을 보인다.

C. 실용적 시사점 및 한계: 해결 가능성, benchmark 품질, diversity만으로는 visual style, pacing, novelty, designer intent를 완전히 포착할 수 없다.benchmark에 원하는 미적 또는 경험적 목표가 포함되지 않은 경우에도 human review는 여전히 중요하다.
C. 실용적 시사점 및 한계: 일반적인 50-generation run은 near-frontier-model token을 수백만 개 사용하고 wall-clock time으로 수 시간이 걸리며, CAD는 extraction, correction, refactoring call을 추가한다.향후 연구에서는 fitness 향상을 token 사용량 및 wall-clock cost와 함께 평가해야 한다.
C. 실용적 시사점 및 한계: CAD는 complete pipeline으로 평가되므로 helper extraction, module correction, source refactoring에는 별도의 ablation이 없다.Mechanism trace는 growth, adoption, program-size change를 보여주지만 각 구성요소의 인과적 기여를 분리하지는 못한다.
C. 실용적 시사점 및 한계: 향후 연구에서는 더 긴 budget, 다른 language model, non-tile content, cross-run library transfer, 그리고 discovered helper에 대한 designer editing을 검증해야 한다.이러한 방향은 discovered abstraction의 generality와 human control을 모두 다룬다.
VII. 결론: Continual Abstraction Discovery는 Sokoban, Zelda, Dangerous Dave, Lode Runner 전반에서 empty 또는 expert helper library를 사용할 때 mean final best fitness를 높인다.각 domain은 10회 run에 걸쳐 평가된다.
VII. 결론: Learned library는 성장하고 후속 program에 채택되며, validation, reachability, structural utility를 반복적으로 복원한다.이 결과는 procedural content metageneration에서 CAD가 searchable program vocabulary를 적응시키는 mechanism이라는 점을 뒷받침한다.

부록

부록은 진화적 변이, 오류 수정, 메모리 성찰, CAD helper-module 유지 관리를 뒷받침하는 프롬프트와 런타임 조건을 정리한다. 이 프롬프트는 search loop 전반에서 프로그램 계약, 피드백, 재사용 가능한 유틸리티, 복구 절차를 지정한다.

Mutation: mutation prompt는 generate(context_dict) contract, 도메인 제약, run memory, helper API, mutation strength, parent-program input을 정의한다.Fig. 6에 제시되어 있다.
Variation and correction: Crossover는 두 parent program을 하나의 complete child로 결합하며, correction prompt는 compilation 또는 smoke testing에 실패한 output을 복구한다.archive에 최소 두 agent가 있을 때 ∼25% probability로 crossover가 발생하며, correction은 최대 세 번의 retry를 허용한다.
Memory Reflection: Memory reflection은 매 generation 후 실행되어 structured generation observation을 기록하고, 이후 variation call을 위한 global learning을 갱신한다.memory에는 parent와 child의 fitness, evaluation feedback, failure, learned lesson, code structure가 포함된다.
CL Helper Extraction: CAD는 generation 8부터 매 five generation마다 generation window 내 high-fitness program 하나당 한 번의 call을 사용해 재사용 가능한 domain utility를 추출한다.이 extraction prompt는 CL condition에만 적용되며, fitness 상위 quartile의 program을 대상으로 한다.
CAD helper maintenance: CAD는 또한 실패한 helper module을 correction하고, generator가 tested helper를 호출하도록 refactor하며, 누락된 imported function을 위한 scaffold를 생성한다.이 recovery 및 maintenance prompt는 CL condition에만 적용된다. helper가 존재할 때 refactoring은 mutation 또는 crossover 후 25% probability로 수행된다.