Een creatieve computer?
Artificiële intelligentie is voor veel mensen niet langer een fantasie. Computers hebben de laatste jaren hun kracht bewezen aan de hand van verschillende verbazingwekkende toepassingen (denk onder meer aan AlphaGo, deepfakes en autonome voertuigen). Veel vertrouwen is er, zelfs bij AI-onderzoekers, echter niet in computationele creativiteit, de studie naar machines die in staat zijn tot creatief gedrag. Enerzijds is het ontzettend moeilijk om een definitie op creativiteit te plakken. Het wordt juist vaak gezien als unieke vorm van menselijke uitdrukking. Anderzijds zijn er (nog) geen systemen die overtuigend creatief zijn.
Stijl leren uit voorbeelden
Een essentieel onderdeel van menselijke creativiteit betreft het leren van nieuwe kennis, onder andere in de vorm van technieken, concepten of stijlen, en deze te combineren in een origineel werk. Een schilder zal bijvoorbeeld inspiratie halen uit andere kunst en deze kennis kunnen verderzetten in zijn eigen werk. Een belangrijk onderdeel in een creatieve computer zou op dezelfde manier uit voorbeelden kunnen bijleren om deze informatie op creatieve manier te gebruiken.
Nauw verwant aan computationele creativiteit is procedurele generatie, of het automatisch genereren van objecten met behulp van algoritmen. Het creëren van een nieuw object is namelijk een typisch creatieve actie dat in het geval van procedurele generatie door een computerprogramma wordt uitgevoerd. Procedurele generatie algoritmes werden niet ontwikkeld met het doel van computationele creativiteit voor ogen. In de videogame industrie wordt procedurele generatie gebruikt om, in de plaats van elk onderdeel van een spel met de hand te ontwikkelen, efficiënt en goedkoop enorm veel objecten te kunnen genereren. Het is een brede techniek dat modellen van bomen, karakters, missies, muziek en zelfs volledige spellen kan genereren. De algoritmes die het generatieproces bepalen moeten wel met de hand worden opgesteld. Indien je huizen in een bepaalde stijl wil genereren moet je eerst handmatig de regels van deze stijl bepalen. Hoe ingewikkelder de objecten die je wil genereren, hoe ingewikkelder dit proces.
Kunnen we procedurele generatie verbeteren door automatisch regels voor stijl te leren, terwijl we een stapje dichter bij computationele creativiteit zetten?
Deze thesis onderzocht een techniek om de stijl te leren van driedimensionale gebouwen in de vorm van regels tussen geometrische vormen. De gebouwen worden opgedeeld in een aantal vormen die stijlelementen voorstellen. Vervolgens zoekt het systeem regels tussen deze stijlelementen. Door deze regels uit te voeren kan de computer originele gebouwen genereren in een gelijkaardige stijl als het voorbeeld. Het systeem laat ook toe meerdere voorbeelden te gebruiken met als resultaat een combinatie van stijlen.
Figuur 1: Twee voorbeelden worden verdeeld in kleinere stijlelementen. Regels tussen deze elementen laten ons toe nieuwe gebouwen te genereren met een combinatie van de stijl van beide voorbeelden.
Automatisch stijlelementen vinden
We werken met voorbeelden in de vorm van Minecraft gebouwen, omdat ze bestaan uit eenvoudige kubusvormige blokken van gelijke grootte. Deze blokken bestaan elk uit een materiaal zoals hout of glas. Eerst en vooral willen we de voorbeelden opdelen in groepen samenhangende blokken, die we vormen noemen, die een deel van de stijl voorstellen. Deze opdeling wordt uitgevoerd door een iteratief algoritme dat start met één vorm voor elke blok in het voorbeeld. In elke stap voert het algoritme een merge of een split uit dat de groep vormen zal verbeteren. Een merge voegt twee vormen, en de blokken waaruit ze bestaan, samen in één, terwijl een split één vorm splitst in twee nieuwe vormen. Wat is echter een betere vorm, of een betere groep vormen?
Figuur 2: Visualisatie van een merge en een split operatie.
We merken op dat de meeste stijlelementen bestaan uit een klein aantal materialen. Zo bestaat een raam meestal enkel uit glas en een raamkozijn in één materiaal. We zorgen er dus voor dat het algoritme op zoek gaat naar vormen die bestaan uit zo weinig mogelijk materialen. Anderzijds willen we niet dat elke vorm uit maar één materiaal bestaat. Daarom geven we het algoritme een tweede doel, namelijk het voorbeeld voorstellen met zo weinig mogelijk vormen. Het algoritme zal een balans zoeken tussen deze twee doelstellingen en uiteindelijk voor elk voorbeeld een kleine groep simpele vormen kunnen vinden.
Het generatieproces
Met de ontdekte vormen kunnen we regels opstellen voor de stijl van het voorbeeld. Deze regels stellen de relaties tussen de vormen voor. Indien twee vormen elkaar aanraken in het voorbeeld creëren we een regel waarbij beide vormen elkaar kunnen produceren. Indien één van deze vormen aanwezig is in het gebouw dat gegenereerd wordt, zal het uitvoeren van deze regel de tweede vorm in het gebouw plaatsen. Bovendien beschrijven de regels waar vormen geplaatst moeten worden aan de hand van de relaties tussen vormen in het voorbeeld.
Deze regels laten ons op de volgende manier toe nieuwe gebouwen in dezelfde stijl als het voorbeeld te genereren. Beginnend van één enkele vorm, voeren we steeds een regel uit dat een nieuwe vorm in het gebouw plaatst op een geschikte plaats. Dit proces kunnen we op elk moment stopzetten met als resultaat een gebouw met vaak ontbrekende en onnodige vormen. Na een automatische bewerkingsstap krijgen we een gebouw in dezelfde stijl als de voorbeelden.
Figuur 3: Een voorbeeld, een gebouw in dezelfde stijl als het voorbeeld voor de bewerkingsstap en een finaal origineel gebouw.
Vooruitzichten
Onze methode werkt: het is mogelijk om regels te leren voor de stijl van één of meerdere gebouwen en originele gebouwen in een gelijkaardige stijl te genereren. Automatisch stijlen leren nabootsen is een belangrijke ontwikkeling voor procedurele generatie. Het algoritme heeft echter een aantal tekortkomingen die op meerdere manieren verbeterd kunnen worden. Bovendien is er nood aan algemene methodes die regels kunnen leren voor verschillende soorten objecten.
Hier spreken we natuurlijk nog niet van computationele creativiteit, maar met verder onderzoek zouden dit soort algoritmes, die nieuwe concepten leren uit voorbeelden, een belangrijke basis kunnen vormen voor creatieve computersystemen.
Bibliografie
[1] E. Aarts, E. H. Aarts, and J. K. Lenstra. Local search in combinatorial optimization. Princeton University Press, 2003.
[2] R. Adams and L. Bischof. Seeded region growing. IEEE Transactions on pattern
analysis and machine intelligence, 16(6):641–647, 1994.
[3] T. Adams and Z. Adams. Dwarf Fortress. Bay 12 Games, 2006.
[4] D. G. Aliaga, P. A. Rosen, and D. R. Bekins. Style grammars for interactive
visualization of architecture. IEEE transactions on visualization and computer
graphics, 13(4):786–797, 2007.
[5] P. Ammanabrolu, W. Broniec, A. Mueller, J. Paul, and M. O. Riedl. Toward automated quest generation in text-adventure games. arXiv preprint
arXiv:1909.06283, 2019.
[6] B. Beneš, O. Št’ava, R. Měch, and G. Miller. Guided procedural modeling. In
Computer graphics forum, volume 30, pages 325–334. Wiley Online Library,
2011.
[7] M. A. Boden. The creative mind: Myths and mechanisms (second edition).
Routledge, 2004.
[8] M. Bokeloh, M. Wand, and H.-P. Seidel. A connection between partial symmetry
and inverse procedural modeling. In ACM SIGGRAPH 2010 papers, pages 1–10.
2010.
[9] I. BoussaïD, J. Lepagnot, and P. Siarry. A survey on optimization metaheuristics.
Information sciences, 237:82–117, 2013.
[10] D. Braben and I. Bell. Elite. Acornsoft, Firebird and Imagineer, 1984.
[11] C. B. Browne. Automatic generation and evaluation of recombination games.
PhD thesis, Queensland University of Technology, 2008.
[12] N. Chomsky. Three models for the description of language. IRE Transactions
on Information Theory, 2(3):113–124, Sep. 1956.
[13] S. Colton. Creativity versus the perception of creativity in computational
systems. In AAAI spring symposium: creative intelligent systems, volume 8,
2008.
[14] S. Colton, G. A. Wiggins, et al. Computational creativity: The final frontier?
In Ecai, volume 12, pages 21–26. Montpelier, 2012.
[15] M. Cook and S. Colton. Multi-faceted evolution of simple arcade games. In
2011 IEEE Conference on Computational Intelligence and Games (CIG’11),
pages 289–296. IEEE, 2011.
[16] S. Dahlskog and J. Togelius. Patterns and procedural content generation:
revisiting mario in world 1 level 1. In Proceedings of the First Workshop on
Design Patterns in Games, page 1. ACM, 2012.
[17] S. Dahlskog and J. Togelius. Procedural content generation using patterns
as objectives. In European Conference on the Applications of Evolutionary
Computation, pages 325–336. Springer, 2014.
[18] S. Dahlskog, J. Togelius, and M. J. Nelson. Linear levels through n-grams. In
Proceedings of the 18th International Academic MindTrek Conference: Media
Business, Management, Content & Services, pages 200–206. ACM, 2014.
[19] K. David Rio Vierra and all other contributors. MCEdit. 2010-2015.
[20] F. Doshi-Velez and B. Kim. Towards a rigorous science of interpretable machine
learning. arXiv preprint arXiv:1702.08608, 2017.
[21] A. A. Efros and T. K. Leung. Texture synthesis by non-parametric sampling.
In Proceedings of the seventh IEEE international conference on computer vision,
volume 2, pages 1033–1038. IEEE, 1999.
[22] A. Emilien, A. Bernhardt, A. Peytavie, M.-P. Cani, and E. Galin. Procedural
generation of villages on arbitrary terrains. The Visual Computer, 28(6-8):809–
818, 2012.
[23] B. Entertainment. Diablo. Blizzard Entertainment, 1996-2017.
[24] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair,
A. Courville, and Y. Bengio. Generative adversarial nets. In Advances in neural
information processing systems, pages 2672–2680, 2014.
[25] J. A. Hall, B. Williams, and C. J. Headleand. Artificial folklore for simulated
religions. In 2017 International Conference on Cyberworlds (CW), pages 229–232,
Sep. 2017.
[26] M. Hendrikx, S. Meijer, J. Van Der Velden, and A. Iosup. Procedural content
generation for games: A survey. ACM Transactions on Multimedia Computing,
Communications, and Applications (TOMM), 9(1):1, 2013.
[27] S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation,
9(8):1735–1780, 1997.
[28] Y. Hu, J. Dorsey, and H. Rushmeier. A novel framework for inverse procedural
texture modeling. ACM Transactions on Graphics (TOG), 38(6):1–14, 2019.
[29] R. Jain, A. Isaksen, C. Holmgård, and J. Togelius. Autoencoders for level
generation, repair, and recognition. In Proceedings of the ICCC Workshop on
Computational Creativity and Games, 2016.
[30] G. Kelly and H. McCabe. Citygen: An interactive system for procedural city
generation. In Fifth International Conference on Game Design and Technology,
pages 8–16, 2007.
[31] A. Khalifa, M. C. Green, D. Perez-Liebana, and J. Togelius. General video game
rule generation. In 2017 IEEE Conference on Computational Intelligence and
Games (CIG), pages 170–177. IEEE, 2017.
[32] D. P. Kingma and M. Welling. Auto-encoding variational bayes. arXiv preprint
arXiv:1312.6114, 2013.
[33] J. Knutzen. Generating climbing plants using l-systems. Chalmers University of
Technology, 2009.
[34] H. Koning and J. Eizenberg. The language of the prairie: Frank lloyd wright’s
prairie houses. Environment and planning B: planning and design, 8(3):295–323,
1981.
[35] B. Kybartas and C. Verbrugge. Analysis of regen as a graph-rewriting system
for quest generation. IEEE Transactions on Computational Intelligence and AI
in Games, 6(2):228–242, 2013.
[36] A. Liapis, G. N. Yannakakis, and J. Togelius. Computational game creativity.
In ICCC, pages 46–53. Citeseer, 2014.
[37] A. Lindenmayer. Mathematical models for cellular interactions in development
i. filaments with one-sided inputs. Journal of theoretical biology, 18(3):280–299,
1968.
[38] M.-Y. Liu, O. Tuzel, S. Ramalingam, and R. Chellappa. Entropy rate superpixel
segmentation. In CVPR 2011, pages 2097–2104. IEEE, 2011.
[39] A. A. Markov. Extension of the limit theorems of probability theory to a sum of
variables connected in a chain. Dynamic probabilistic systems, 1:552–577, 1971.
[40] A. Martinovic and L. Van Gool. Bayesian grammar learning for inverse procedural modeling. In Proceedings of the IEEE Conference on Computer Vision
and Pattern Recognition, pages 201–208, 2013.
[41] M. Mateas and A. Stern. Facade. Procedural Arts, 2005.
[42] P. Merrell. Example-based model synthesis. In Proceedings of the 2007 symposium on Interactive 3D graphics and games, pages 105–112, 2007.
[43] P. Merrell and D. Manocha. Continuous model synthesis. In ACM SIGGRAPH
Asia 2008 papers, pages 1–7. 2008.
[44] P. Merrell and D. Manocha. Model synthesis: A general procedural modeling
algorithm. IEEE transactions on visualization and computer graphics, 17(6):715–
728, 2010.
[45] K. E. Merrick, A. Isaacs, M. Barlow, and N. Gu. A shape grammar approach
to computational creativity and procedural content generation in massively
multiplayer online role playing games. Entertainment Computing, 4(2):115–130,
2013.
[46] N. J. Mitra, M. Wand, H. Zhang, D. Cohen-Or, V. Kim, and Q.-X. Huang.
Structure-aware shape processing. In ACM SIGGRAPH 2014 Courses, pages
1–21. 2014.
[47] D. C. Moffat and M. Kelly. An investigation into people’s bias against computational creativity in music composition. Assessment, 13(11), 2006.
[48] Mojang. Minecraft. Mojang, 2011.
[49] P. Müller, P. Wonka, S. Haegler, A. Ulmer, and L. Van Gool. Procedural
modeling of buildings. In ACM SIGGRAPH 2006 Papers, pages 614–623. 2006.
[50] P. Müller, G. Zeng, P. Wonka, and L. Van Gool. Image-based procedural
modeling of facades. In ACM Transactions on Graphics (TOG), volume 26,
page 85. ACM, 2007.
[51] G. Nierhaus. Algorithmic composition: paradigms of automated music generation.
Springer Science & Business Media, 2009.
[52] Nintendo. Super Mario Bros. Nintendo, 1985.
[53] Y. I. H. Parish and P. Müller. Procedural modeling of cities. In Proceedings of
the 28th Annual Conference on Computer Graphics and Interactive Techniques,
SIGGRAPH ’01, pages 301–308, New York, NY, USA, 2001. ACM.
[54] P. Prusinkiewicz and A. Lindenmayer. The algorithmic beauty of plants. Springer
Science & Business Media, 1990.
[55] T. Roden and I. Parberry. From artistry to automation: A structured methodology for procedural content creation. In International Conference on Entertainment Computing, pages 151–156. Springer, 2004.
[56] L. Rokach and O. Maimon. Clustering methods. In Data mining and knowledge
discovery handbook, pages 321–352. Springer, 2005.
[57] N. Shaker, J. Togelius, and M. J. Nelson. Procedural content generation in
games. Springer, 2016.
[58] A. Shamir. A survey on mesh segmentation techniques. In Computer graphics
forum, volume 27, pages 1539–1556. Wiley Online Library, 2008.
[59] C. E. Shannon. Prediction and entropy of printed english. Bell system technical
journal, 30(1):50–64, 1951.
[60] R. M. Smelik, T. Tutenel, R. Bidarra, and B. Benes. A survey on procedural
modelling for virtual worlds. In Computer Graphics Forum, volume 33, pages
31–50. Wiley Online Library, 2014.
[61] A. R. Smith. Plants, fractals, and formal languages. In Proceedings of the
11th Annual Conference on Computer Graphics and Interactive Techniques,
SIGGRAPH ’84, pages 1–10, New York, NY, USA, 1984. ACM.
[62] S. Snodgrass and S. Ontanón. Generating maps using markov chains. In Ninth
Artificial Intelligence and Interactive Digital Entertainment Conference, 2013.
[63] G. Software. Borderlands. 2K Games, 2009-2019.
[64] N. Sorenson and P. Pasquier. Towards a generic framework for automated video
game level creation. In European conference on the applications of evolutionary
computation, pages 131–140. Springer, 2010.
[65] F. Sportelli, G. Toto, and G. Vessio. A probabilistic grammar for procedural
content generation. 07 2014.
[66] O. Št’ava, B. Beneš, R. Měch, D. G. Aliaga, and P. Krištof. Inverse procedural
modeling by automatic generation of l-systems. In Computer Graphics Forum,
volume 29, pages 665–674. Wiley Online Library, 2010.
[67] G. Stiny. Introduction to shape and shape grammars. Environment and planning
B: planning and design, 7(3):343–351, 1980.
[68] G. Stiny. Spatial relations and grammars. Environment and Planning B:
Planning and Design, 9(1):113–114, 1982.
[69] G. Stiny and W. J. Mitchell. The palladian grammar. Environment and planning
B: Planning and design, 5(1):5–18, 1978.
[70] A. Stolcke and S. Omohundro. Inducing probabilistic grammars by bayesian
model merging. In International Colloquium on Grammatical Inference, pages
106–118. Springer, 1994.
[71] A. Summerville and M. Mateas. Super mario as a string: Platformer level
generation via lstms. arXiv preprint arXiv:1603.00930, 2016.
[72] A. Summerville, S. Snodgrass, M. Guzdial, C. Holmgård, A. K. Hoover, A. Isaksen, A. Nealen, and J. Togelius. Procedural content generation via machine
learning (pcgml). IEEE Transactions on Games, 10(3):257–270, 2018.
[73] J. O. Talton, Y. Lou, S. Lesser, J. Duke, R. Měch, and V. Koltun. Metropolis
procedural modeling. ACM Transactions on Graphics (TOG), 30(2):1–14, 2011.
[74] O. Teboul, I. Kokkinos, L. Simon, P. Koutsourakis, and N. Paragios. Parsing
facades with shape grammars and reinforcement learning. IEEE transactions
on pattern analysis and machine intelligence, 35(7):1744–1756, 2012.
[75] J. Togelius, A. J. Champandard, P. L. Lanzi, M. Mateas, A. Paiva, M. Preuss,
and K. O. Stanley. Procedural content generation: Goals, challenges and
actionable steps. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013.
[76] J. Togelius, E. Kastbjerg, D. Schedl, and G. N. Yannakakis. What is procedural
content generation?: Mario on the borderline. In Proceedings of the 2nd international workshop on procedural content generation in games, page 3. ACM,
2011.
[77] J. Togelius and J. Schmidhuber. An experiment in automatic game design.
In 2008 IEEE Symposium On Computational Intelligence and Games, pages
111–118. IEEE, 2008.
[78] J. Togelius, G. N. Yannakakis, K. O. Stanley, and C. Browne. Search-based
procedural content generation: A taxonomy and survey. IEEE Transactions on
Computational Intelligence and AI in Games, 3(3):172–186, 2011.
[79] H. Toivonen and O. Gross. Data mining and machine learning in computational creativity. Wiley Interdisciplinary Reviews: Data Mining and Knowledge
Discovery, 5(6):265–275, 2015.
[80] M. Toy, G. Wichman, K. Arnold, and J. Lane. Rogue. Epyx, 1980.
[81] L.-Y. Wei, S. Lefebvre, V. Kwatra, and G. Turk. State of the art in example-based
texture synthesis. 2009.
[82] P. Wonka, M. Wimmer, F. Sillion, and W. Ribarsky. Instant architecture,
volume 22. ACM, 2003.
[83] F. Wu, D.-M. Yan, W. Dong, X. Zhang, and P. Wonka. Inverse procedural
modeling of facade layouts. arXiv preprint arXiv:1308.0419, 2013.
[84] G. N. Yannakakis and J. Togelius. Artificial intelligence and games, volume 2.
Springer, 2018.
