Evolutionary learning and search-based content generation in computer games

Modern computer games achieved an impressive level of realism featuring advanced 3D graphics and sophisticated physics engine able to simulate complex game environments. However, the increasing complexity of the game environment poses many challenges for developing the Artificial Intelligence which controls the non-player characters. In many games, the non-player characters show very simple and predictable behaviors which are not able to evolve over time or to adapt to the user's gameplay. Another problem, caused from the complexity of the game environment, is the generation of a large quantity of game content, e.g., levels, maps, racing tracks, etc. In most complex computers games, the content generation can require the work of several designers and can last even for months. Thus, there is the necessity of techniques that can automate or support some aspects of the game development process. In this context, Computational Intelligence can be a valid approach to deal with some of the issues in computer games. Computational Intelligence is a field of the Artificial Intelligence which includes techniques and mathematical models which are inspired by nature, such as Evolutionary Algorithms and Neural Networks. In the recent years, the number of scientific works involving Computational Intelligence and Game is quickly growing and suggests that this is a promising research direction. In this thesis, we focus on the application of Computational Intelligence, and in particular Evolutionary Algorithms, to computer games. In the first part, we investigate different learning paradigms which can support the development of non-player characters. In particular, we investigate on-line learning, i.e., a learning process applied during the game to generate sophisticated non-player characters that can evolve over time. In the second part, we focus on game content generation. We investigate several representations and different approaches for evaluating the game content. In our experimental analysis we take into account different computer games: racing games, shooters and platform games. The results show that all the proposed methods are promising and Computational Intelligence represents an effective approach to support the game development process.

I videogiochi di ultima generazione hanno raggiunto notevoli livelli di realismo. Questo risultato è stato possibile grazie agli elevati progressi ottenuti nella realizzazione di motori grafici tridimensionali e simulatori della fisica sempre più sofisticati che permettono di rappresentare degli ambienti di gioco con un elevato grado di complessità. Tuttavia, la crescente complessità degli ambienti di gioco ha reso sempre più difficile la programmazione dell'intelligenza artificiale dei giocatori controllati dal computer, spesso indicati come non-player characters (NPCs). Da una parte vi è la necessità di avere tecniche in grado di automatizzare lo sviluppo dei comportamenti di gioco dei non-player characters. Dall'altra si rendono necessari dei meccanismi per realizzare non-player characters più sofisticati, in grado di apprendere dall'esperienza ed adattarsi a nuove condizioni di gioco. Un altra problematica, relativa alla crescente complessità degli ambienti di gioco, riguarda la generazione del contenuto di gioco. Per contenuto si intendono tutti quegli elementi che non fanno strettamente parte del motore di gioco, ma ne estendono la giocabilità e la durata: per esempio i livelli di gioco, le mappe, le armi, i personaggi, le piste da corsa, ecc. Nei videogiochi più complessi, la generazione delle mappe di gioco è una attività costosa che può richiedere diversi mesi di lavoro. Da qui la necessità di avere degli strumenti in grado di automatizzare parzialmente o totalmente la generazione del contenuto di gioco. In questo contesto, la Computational Intelligence può rappresentare un approccio interessante per affrontare alcune delle problematiche presenti nell'ambito dei videogiochi. La Computational Intelligence è un area di ricerca dell'Intelligenza Artificiale, che comprende tecniche e modelli matematici ispirati alla natura, come Algoritmi Evolutivi, Reti Neurali e Apprendimento per Rinforzo. Negli ultimi anni, la Computational Intelligence è stata applicati ai giochi e a i videogiochi in molti lavori di ricerca. Il numero di pubblicazioni scientifiche e i risultati ottenuti in questo ambito suggeriscono che l'applicazione della Computational Intelligence nei videogiochi rappresenta una direzione di ricerca promettente. In questa tesi ci proponiamo di affrontare alcune problematiche presenti nell'ambito dei videogiochi, usando tecniche di Computational Intelligence ed in particolare Algoritmi Evolutivi. Prenderemo in esame due problematiche dei videogiochi moderni: l'apprendimento dei comportamenti di gioco dei non-player characters e la generazione del contenuto di gioco. Per quanto riguarda l'apprendimento, verranno studiati due aspetti: da una parte tecniche per automatizzare l'apprendimento dei comportamenti di gioco; dall'altra tecniche per creare dei non-player characters sofisticati in grado di apprendere on-line, cioè durante il gioco stesso. Per quanto riguarda la generazione del contenuto di gioco studieremo diversi approcci: generazione basata su cifre di merito teoriche e generazione basata sulle preferenze dell'utente. I vari approcci verranno studiati in videogiochi che richiedono contenuto di gioco molto diverso tra loro: piste per un gioco di guida, mappe per uno sparatutto in prima persona e livelli per un gioco platform. I risultati ottenuti mostrano che gli approcci proposti hanno un buon potenziale e che la Computational Intelligence rappresenta una metodologia efficace per supportare diversi aspetti dello sviluppo di videogiochi.