1) TITLE Evolutionary Game Design -------------------------------------------------------------------------- 2) AUTHOR Cameron Browne Computational Creativity Group Department of Computing Imperial College London 180 Queens Gate South Kensington London, SW7 2AZ, UK -------------------------------------------------------------------------- 3) CORRESPONDING AUTHOR Cameron Browne -------------------------------------------------------------------------- 4) ABSTRACT This submission concerns Ludi, a software system able to evolve, play and evaluate new board games. Ludi invented a number of games in 2007, two of which were commercially published in 2009, but the real impact of these games - and the system itself - has only become fully manifest over the last year as the games reach a broader audience, are played more, and are studied in greater depth. This submission is based on publications over the last twelve months that analyse this impact, notably the book "Evolutionary Game Design" [1]. Particular attention is made to Yavalath, the best game evolved by Ludi and the main result of the project. Ludi works by representing games as rule trees in the form of symbolic expressions, and evolving these into new rule sets using standard genetic programming operators. The resulting rule sets are exercised through a number of self-play trials between AI agents. A "playability filter" catches those with serious flaws - culling about 98% of evolved individuals - then the survivors are judged for quality according to a number of functional and aesthetic criteria, previously correlated with scores by human players. The critical part of this process is getting the computer to recognise games likely to interest human players. Only tentative steps had been taken in this direction prior to Ludi, and it was generally thought that automating the entire game design process to the level of human design was not feasible, until Ludi did so. In this entry, I argue not only that the results produced by Ludi are human competitive (Yavalath has been commercially published and ranked in the top #100 abstract board games ever invented), but that the system captures several game design principles used by human designers, has inspired human designers, and that the software even taught its (human) author a thing or two about game design. -------------------------------------------------------------------------- 5) CRITERIA SATISFIED BY THE WORK C, D, F -------------------------------------------------------------------------- 6) RATIONALE This work satisfies the criteria listed above for the following reasons. Some allowances must be made for the unusual nature of the domain; game design produces "artistic" rather than "scientific" results, although Ludi demonstrates how these may still be empirically measured. C) "The result is equal to or better than a result that was placed into a database or archive of results maintained by an internationally recognized panel of scientific experts." There is no "internationally recognised panel of scientific experts" for game design. However, an expert source of peer review is provided by the BoardGameGeek (BGG) community, which is the world's largest and most active international community of board game players and designers, with over 400,000 members and 45,000 games in its database [5]. Its membership includes many of the world's best game designers and players, and its peer voting mechanism for rating database entries is hidden from casual users, which encourages educated assessments. Games submitted to BGG must pass a review and moderation process before being added to the database. Yavalath was added to the BGG database in the "Abstract Games" category immediately following its creation. It achieved a high ranking of #99 in this category (out of more than 4,300 games), placing it in the top 2.5% of abstract board games ever invented, according to the BGG community. D) "The result is publishable in its own right as a new scientific result — independent of the fact that the result was mechanically created." Two of the games created by Ludi have been commercially published under contract to Spanish publisher nestorgames: Yavalath and Ndengrod (published under the name Pentalath) [6],[7]. Yavalath was the first game published by nestorgames, whose catalogue has now grown to over 80 games in three years. To commemorate the importance of Yavalath, which remains a flagship product, nestorgames will be releasing a special Yavalath Deluxe edition worth over $200 on their third anniversary (14 July, 2012) [6]. nestorgames do not hide the fact that these games were computer-generated. This is stated clearly as a marketing feature, and does not appear to concern players. F) "The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered." Yavalath was one of more than 200 "Abstract Strategy" games invented in 2007, and the only one invented by a computer. Only seven of these games are rated more highly than Yavalath on the BGG database, placing it in the top 4% of abstract board games invented that year. CLOSE MISSES A) Criterion A (patentability) is not claimed. Yavalath and Pentalath (nee Ndengrod) have both been copyrighted and commercially published, and could theoretically be patented or trademarked. However, the simplicity of the equipment, and the difficulty and cost of enforcing such patents/trademarks within the industry, would not make this worthwhile for most board game publishers. G) Criterion G (solution to a problem of indisputable difficulty in its field) is not claimed. Although game design is a problem of indisputable difficulty in its field, it would be too strong to claim that Ludi "solves" this problem; rather, it demonstrates the discovery of solutions at least as good as those of human counterparts. There is no single "best" game, or game design process. In 1992 Barney Pell [8] observed: "If we could develop a program which, upon consideration of a particular game, declared the game to be uninteresting, this would seem to be a true sign of intelligence! So when this becomes an issue, we will know that the field has certainly matured." Pell's observation remained unrealised for 15 years, until Ludi not only demonstrated how a program could detect uninteresting games, but could go a step further to automatically create and identify new and interesting games, using an evolutionary approach. -------------------------------------------------------------------------- 7) CITATIONS This submission is based on the following book: [1] C. Browne (2011) Evolutionary Game Design, Springer, Berlin, ISBN 978-1-4471-2178-7. Sample chapter: http://www.cameronius.com/research/evo-game-design/07-yavalath.pdf Related support material: [2] C. Browne (2012) "Yavalath: Sample Chapter from 'Evolutionary Game Design'", ICGA Journal, 35:2 (to appear - reprint of chapter linked above). [3] A. Boumanza (2012) "Cameron Browne: Evolutionary Game Design", Genetic Programming and Evolvable Machines, 13:3, 407-9, http://www.springerlink.com/content/7p0680w770hn2314/ (review of Springer book). [4] C. Browne (2012) "Go Without Ko on Hexagonal Grids", ICGA Journal, 35:1, 37-40. Additional references: [5] S. Alden (2000) BoardGameGeek, http://www.boardgamegeek.com. [6] N. Romeral Andres (2012) "Yavalath Deluxe", http://www.nestorgames.com/#yavalathdeluxe_detail.html. [7] N. Romeral Andres (2012) "Pentalath", http://www.nestorgames.com/#pentalath_detail.html. [8] B. Pell (1992) "METAGAME in symmetric Chess-like games," Heuristic Programming in Artificial Intelligence 3, eds. H. Van den Kerik and L. Allis, Ellis Horwood, Chichester. -------------------------------------------------------------------------- 8) STATEMENT OF PRIZE ALLOCATION Any prize money, if any, is to be claimed by the single author. -------------------------------------------------------------------------- 9) WHY THE JUDGES SHOULD CONSIDER THIS ENTRY In his 2012 review of "Evolutionary Game Design", Boumanza [3] asks: "How can computers create interesting games? What makes a game interesting and how can a machine decide if a game is of interest to human players?" These are the questions asked by almost anyone who encounters the Ludi project. Game design is such a "human" craft, and players' assessment of games so intuitive, that even experts could not see how game quality could be measured mathematically in a reliable way. The main contribution of Ludi is to demonstrate how this can be achieved automatically at a human-competitive level. Boumanza concludes by describing the book as "a valuable contribution to evolutionary computation and more generally to artificial intelligence" [3]. Jaap van den Herik, Editor-in-Chief of the International Computer Games Association (ICGA), recently asked to publish a sample chapter of "Evolutionary Game Design" in an upcoming issue of the ICGA Journal [2]. This indicates the significance of the Ludi project to the broader game research community. COMPUTATIONAL CREATIVITY Game design has (until now) been very much a creative human endeavour. The main criteria used in the field of Computational Creativity to decide whether a system exhibits signs of creativity include: 1. QUALITY: Yavalath has been successfully published, and is enjoyed by players. It was ranked the #99 abstract board game on the BGG database, placing it in the top 2.5% of abstract board games ever invented. 2. TYPICALITY: The rules of Yavalath are simple: win with 4 in-a-row but lose with 3-in-a-row beforehand. It is a typical abstract board game, and more specifically a typical N-in-a-Row game. This makes the rules familiar to anyone who has previously played Tic Tac Toe, and means that new players can pick up the game easily. 3. NOVELTY: Yavalath subverts the familiar N-in-a-Row genre with its novel twist of "win with 4 but lose with 3", which allows an interesting forced move mechanism that revitalises this genre. This mechanism has not previously been described in the literature, which is remarkable given that N-in-a-Row is one of the most fundamental game rules that has been studied by game designers for centuries. One close precedent is the game Renju, in which players strive to make 5-in-a-row on a square board, while one is constrained from making various patterns with their pieces. However, Yavalath's rules are simpler and more direct, and they are distinct games. As soon as Yavalath was announced, game designer Dieter Stein stated that he had previously worked on a similar idea for a game tentatively titled "Quarti", but that he had not found a rule set that worked and had never released it. Ludi succeeded where a human designer had not. Stein quipped that he had invented Quarti with "my _human_ brain", as if Ludi's automated search gave it an unfair advantage. Ludi displays signs of creativity, produces results at least as good as those of human counterparts, and in at least one case succeeded where an experienced human designer had failed. INSPIRATION Another indication of the creativity of a system is the extent to which it inspires and influences others. Ludi achieved this with the invention of Yavalath. The simple "win with 4 but lose with 3" goal has since been abstracted to the more general concept "N but not sub(N)" and applied to other game types: 1. Form a group of size N but not size N-1. 2. Connect N sides but but not N-1 sides. Ludi has directly inspired the invention of a number of new games by human designers, including: Tritt, Cross, Tailath, Morro, Coffee and Epsilon. These constitute a new sub-genre of "N but not sub(N)" games. GAME DESIGN PRINCIPLES Some of the games generated by Ludi display fundamental principles of good game design used by human designers, albeit unintentionally; none of these principles were programmed into Ludi, they emerged as a by-product of the evolutionary search: 1. RULE TENSION: The inclusion of rules that create strategic conflict against other rules is a common mechanism for increasing tension in a game, as players must carefully weigh the benefits of a given move with any detrimental side-effects. Yavalath's "win with 4 but lose with 3" rule is an obvious manifestation of this principle, as lines of a certain length are infinitely beneficial while lines of a different length are fatal; players cannot simply strive to make the longest line each turn. 2. NOVELTY WITH TYPICALITY: Players generally prefer games with familiar rules and short learning curves, but will quickly become bored with games that do not offer something new. Achieving both of these competing goals is one of the greatest challenges faced by game designers, but Ludi did exactly that with Yavalath. The fact that the winning and losing conditions both use the same (N-in-a-row) basis also means that players need to process less information to understand the rules, maximising the game's clarity. When new players are shown Yavalath they tend to pick up the basic idea immediately, but soon reach two "Aha!" moments; one when they realise that the opponent can be forced to block, and the other when they realise that such forcing moves can be used to manoeuvre the opponent into a losing position. For this reason, Yavalath is the first game that Nestor Romeral Andres (owner of nestorgames) teaches from his catalogue to new players at any board game convention or exhibition; new players can start playing it immediately, are surprised by the hidden twist, then will re-play it addictively to explore it more fully. nestorgames also ran an online "Yavalathon" tournament in June 2011 that attracted 32 players from a dozen countries, who played the game against each other for a week. Romeral Andres points out that new players are typically surprised when it is revealed that Yavalath was designed by computer, and that they would have expected a computer-generated game to be more complex and difficult to play. Ludi can create games that players would not guess are by a non-human designer. 3. EFFICIENCY: In order to keep rule sets as simple as possible, it is preferable (and more elegant) to handle degenerate cases through the geometry of the equipment rather than the addition of special-case rules. Ludi captured this principle by using tilings other than the 4-connected square grid for the two games it invented with Go-like surround capture. Games such as Go that involve surround capture on the 4-connected square grid require an additional ko rule - stating that a move cannot repeat the board position of the previous turn - to avoid infinite cycles of play [4]. Ndengrod, the evolved game ranked #1 by both Ludi and human play testers and also published by nestorgames (under the name Pentalath [7]), involves surround capture on the hexagonal grid. An investigation into why this game works so well without a ko rule inspired the publication of [4]. Ludi had benefitted from a fundamental geometric property unfamiliar to its (human) author. In addition, Ndengrod was initially remapped (by humans) from its original trapezoidal board to the same hexagonal board used by Yavalath, so that both games could be published as a set. However, it has recently been found that Ndengrod plays better on its original trapezoidal board, as the presence of acute corners allows a wider variety of tactical play. Ludi's original design was better than subsequent modifications by human designers [8]. In summary, Ludi has: - Generated new and interesting games that compete with the best games by human designers. - Found a working design for a type of game that an experienced human designer could not. - Inspired the invention of new games by human designers. - Initiated a new sub-genre of "N but not sub(N)" games. - Yielded insights into games that have surprised its (human) users.