This is cool, I've been thinking of how this could be applied to turn based games, for example RPG combat. I have read about commercial "balancing" tools but never about a wholly computer generated system.
Usually the most intriguing part of any genetic-algorithm type optimization is the fitness function. In your case, what makes a good or fun game?
From the first paper it looks like you tried to achieve steady forward progress (in terms of power ups and "reachability"). Did you consider any alternative fitness functions?
Fitness is easily the trickiest part of both projects so far. We're using co-operative co-evolution so elements of the game design are evaluated separately as well as together. For the Metroidvania, the key bit of the FF is "the play should have to collect all the powerups, in a mostly total order, to reach the exit". What this does is create segmented levels that have 'stages' which you access through powerup collection.
For the arcade games it was a lot more general. We did a lot of very rough heuristics like "maps shouldn't be too cluttered", "you should have to explore most of the screen to win" and things like that. I want to go back to arcade games becuase it's a much harder problem to design games without genre staples.
Hey, I'm the guy behind ANGELINA - glad you like the project! The New Scientist game is available to play on that link, near the bottom of the article. You can also check out older games (less impressive than the one we made for NS!) over on the project site: www.gamesbyangelina.org/games
