Angry Birds meet EAs at EVO* 2019

Last 24 of April we presented the work «Free Form Evolution for Angry Birds Level Generation» at EVOApplications 2019 (EvoGAMES) a conference part of EVO* 2019, held in Leipzig (Germany).

The abstract of the work is:

This paper presents an original approach for building structures that are stable under gravity for the physics-based puzzle game Angry Birds, with the ultimate objective of creating fun and aesthetically pleasing Angry Birds levels with the minimum number of constraints. This approach consists of a search-based procedural level generation method that uses evolutionary algorithms. In order to evaluate the stability of the levels, they are executed in an adaptation of an open source version of the game called Science Birds. In the same way, an open source evolutionary computation framework has been implemented to fit the requirements of the problem. The main challenge has been to design a fitness function that, first, avoids if possible the actual execution of the simulator, which is time consuming, and, then, to take into account the different ways in which a structure is not structurally sound and consider them in different ways to provide a smooth landscape that eventually achieves that soundness. Different representations and operators have been considered and studied. In order to test the method four experiments have been carried out, obtaining a variety of stable structures, which is the first path for the generation of levels that are aesthetically pleasing as well as playable.

@amorag did a short presentation and later ‘defended’ a poster during the reception act. The presentation is a description of the poster:

Actually the poster was selected as the second best of the conference by the attendants. :D

Those interested can found the paper at Springer web: https://link.springer.com/chapter/10.1007/978-3-030-16692-2_9

Enjoy it… and cite us! ;D

[Paper] My life as a sim: evolving unique and engaging life stories using virtual worlds

Our latest publication My life as a sim: evolving unique and engaging life stories using virtual worlds, using our framework MADE (created by @rubenhek), has been published in the ALIFE 2014 conference. The abstract:

Stories are not only painfully weaved by crafty writers in the solitude of their studios; they also have to be produced massively for non-player characters in the video game industry or tailored to particular tastes in personalized stories. However, the creation of fictional stories is a very complex task that usually implies a creative process where the author has to combine characters, conflicts and backstories to create an engaging narrative. This work describes a general methodology to generate cohesive and coherent backstories where desired archetypes (universally accepted literary symbols) can emerge in complex stochastic systems. This methodology supports the modeling and parametrization of the agents, the environment where they will live and the desired literary setting. The use of a Genetic Algorithm (GA) is proposed to establish the parameter configuration that will lead to backstories that best fit the setting. Information extracted from a simulation can then be used to create the literary work. To demonstrate the adequacy of the methodology, we perform an implementation using a specific multi-agent system and evaluate the results, testing with three different literary settings.

Check out the presentation by @jjmerelo at http://jj.github.io/alife14-made/#/home. You can download the proceedings of the conference (CC license), or download the paper draft.

More information is available on the project page.

Paper «Testing the Differences of Using RGB and HSV Histograms During Evolution in Evolutionary Art» in ECTA

This week we are presenting the paper «Testing the Differences of Using RGB and HSV Histograms During Evolution in Evolutionary Art» in the Evolutionary Computation Theory and Applications.

This is the work we developed in the Hackathon of the Spanish Free Software Contest of the University of Granada with the help of several students of our university (who are also authors!).

In this work we have added Processing to our OSGiLiath (service oriented architecture for evolutionary algorithms) framework to generate images from individual representations to work with generative art. The fitness is the equality to a predefined image. HSV, RGB and a combination of both have been used.

The abstract:

This paper compares the use of RGB and HSV histograms during the execution of an Evolutionary Algorithm. This algorithm generates abstract images that try to match the histograms of a target image. Three different fitness functions have been used to compare: the differences between the individual with the RGB histogram of the test image, the HSV histogram, and an average of the two histograms at the same time. Results show that the HSV fitness also increases the similarities of the RGB (and therefore, the average) more than the other two measures.

And here is the poster:

Unreal Expert Bots at IWANN 2013

Last week there was held IWANN 2013 at Tenerife, an international conference mainly devoted to researches inside the neural networks scope. In it, Antonio Fernández Leiva, Raúl Lara and Me organized the Special Session on Artificial Intelligence and Games.

There were five works in the session, one of them «Designing and Evolving an Unreal Tournament— 2004 Expert Bot«.

It describes the designing and improvement, through off-line (not during the game) evolution, of an autonomous agent (or bot) for playing the game Unreal Tournament 2004. This was created by means of a finite state machine which models the expert behaviour of a human player in 1 vs 1 deathmatch mode, following the rules of the international competition.

Then, the bot was improved by means of a Genetic Algorithm, yielding an agent that is, in turn a very hard opponent for the medium-level human player and which can (easily) beat the default bots in the game, even in the maximum difficulty level.

The presentation can be seen at:

Moreover, you can watch one example of the evolution in the following video:

Finally, the Unreal Expert and Genetic bot’s source code are available at https://github.com/franaisa/ExpertAgent

Enjoy them. ;)

Pervasive evolutionary algorithms on mobile devices

Last week I received the paper aceptance notification for the DCAI conference in Salamanca. This time we are going to present a distributed algorithm framework for mobile devices using Bluetooth. Ok, today I am quite lazy (today, and all the days, actually), so I think the best idea is to copy the abstract.

Abstract. This work presents a Java framework which allows to implement easily connectivity applications via Bluetooth. Nowadays it is difficult to program Bluetooth devices, so it is necessary to use a high-level Application Programming Interface (API) to make easy the creation of applications in Java ME and Java SE platforms, the most extended ones. As a solution we show the development of a distributed computing environment using a layered, client-server, and event-based with asynchronous communication architecture. In addition we solve two well-known evolutionary computation problems (the Traveler Salesman Problem and the Wave Function Problem), as an example of use.

The most interesting thing is that we have used real mobiles in order to execute the experiments, with all associated problems. It is difficult to find a compatible mobile phone with a Bluetooth stack that works properly. Even is not easy communicate two phones of the same fabricant but different model! But finally we managed to start the experiment, as you can see in the next photo.

Two Nokias executing our distributed algorithm. Photo by DraXus.

You can download the draft from here.

Automatic Generation of XSLT Stylesheets Using Evolutionary Algorithms

Finally I’m going to be present in the Mankind History after my first publication in an international conference! It just a poster, but it’s still quite cool. It was presented in the GECCO’08 Conference, in  Atlanta, where some intrepid GeNeura members drank a lot  of Coca-Cola, even the (suspicious) beer flavoured Coca-Cola.

Here is the abstract:

This paper introduces a procedure based on genetic programming to evolve XSLT programs (usually called stylesheets or logicsheets). XSLT is a general purpose, document-oriented functional language, generally used to transform XML documents or, in general, solve any problem that can be coded as an XML document. The proposed solution uses a tree representation for the stylesheets as well as diverse specific operators in order to obtain, in the studied cases and a reasonable time, a XSLT stylesheet that performs the transformation.

You can download the draft from here, or the poster from here. The poster is orange, perfect for these summer days ;)

Now I am preparing my suitcase in order to go to the PPSN conference in Dortmund, where I will present an improvement of this algorithm.

Pablo

Friday Paper Seminar: BEA (Bacterial Evolutionary Algorithm)

Today in our Friday Thursday Paper Seminar we’ve been discussing the paper «Fuzzy System Parameters Discovery by Bacterial Evolutionary Algorithm» of Norberto Eiji Nawa and Takeshi Furuhashi.

It’s a very interesting paper because introduces a bioinspired algorithm based in bacteria (as the title says, obviously), and its application to fuzzy system. The main improvement from the previous algorithm of the authors the Pseudo-Bacterial Evolutionary Algorithm is the fact of using the transduction, the way that the bacterias interchanges information between themselves. But let’s begin from the beginning.

Every individual of the population is a bacteria whose chromosome is the parameters of a fuzzy system. This chromosome has low epistasis, that is, the chromosoma have weak interrelationships between parts so it is possible to perform optimization in parts. So in each generation every bacteria have a local improvement called bacterial mutation, cloning the bacteria and improving every part but taking care of the global fitness, so the best clone is chosen.

The second operator presented is the Gene Transfer Operation. Instead crossover, the best bacterias sends information to the worst bacterias adding or overwriting parts of the chromosome.

After explain the algorithm the authors performs several experiments to compare other algorithms and this one. I’m not expert in Fuzzy Systems, so probably I’ll be wrong, but I can see that the while the BEA has lower error rates evaluating train set, it also has higher error rates in test set, and the fuzzy system obtained has more (and not used) fuzzy rules. I think this is not a good improvement, but the idea of bacterial mutation and gene transfer is quite interesting in other problems, as we can see in more papers that refers this one.

So, that’s all! Until next week!

Pablo (aka Fergu)