AI Game Design: The Shibumi Challenge

1. Summary

This article describes an upcoming experiment in automated game design, a new game system called the Shibumi set, and a contest called the Shibumi Challenge intended to produce a range of high quality base games for this experiment. The overall aim is to compare the dynamics of evolutionary versus Monte Carlo search methods for game design, and to gauge the usefulness of the computer as a creative collaborator in the game design process.

2. Background

In 2007 I ran an experiment in automated game design, in which a program called Ludi evolved the rules of existing games into new combinations and tested them for quality. This process produced a few interesting games, the best of which was Yavalath. (That story is summarized in the June 2011 BGG News post "Yavalath: On Evolutionary Game Design".)

Yavalath has been well received by players, and its novel mechanism of "win with 4-in-a-row but lose with 3-in-a-row" has inspired a number of subsequent game designs. It seems to have tapped into a new sub-genre of games which involve a tension between achieving condition X without achieving a subset of that condition X'. This raises some interesting questions:

• Did Ludi invent or simply discover Yavalath and its mechanism of rule subset tension?
• Was this a creative act?
• If so, should the mantle of "creator" lie with the program or the programmer?

I believe that the invention of Yavalath was an act of combinatorial creativity. Other designers might have provided the raw material in the form of the base rules, and I might have coded up the algorithms, but Ludi found the serendipitous combination of rules and more importantly recognised it as a good combination. If a human designer had achieved this result, it would certainly have been described as a creative act.

Ludi perhaps even mimicked the creative process of human game designers in the sense that it searched for interesting new combinations of known rules, as the invention of truly original rules and mechanisms is a rare thing. Puzzle designer Raf Peeters touches on this point in his blog entry "Inventing and Serendipity", in which he argues that serendipity (which he describes as the act of searching for something but finding something else) is central to the creative process in game/puzzle design.

Raf describes two requirements for serendipity to occur:

1. Active searching: The designer should not simply wait for inspiration to strike, but should immerse himself in ideas and look for harmonies between them.
2. Finding: The designer must recognise the potential in each new thing he finds.

This is exactly what Ludi did.

3. The Problem with Evolution

Ludi used an evolutionary approach for its active search, in which rule sets were bred, crossed over, and mutated. This eventually produced useful results, although some shortcomings of this method for game design became apparent.

The search seemed quite unfocussed. Evolution is at heart a random process, and there was no guarantee that the combination of rules that make up Yavalath was going to be tried, or ever would be tried again, no matter how long the program runs.

The search was not systematic. Ludi produced a game called Lammothm that was almost identical to the great connection game Gonnect except for one important detail: diagonal connections were allowed. This made Lammothm a mediocre game that barely made the cut and would be quickly forgotten by any player. One small mutation would transform this mediocre game into a truly excellent one, but there is no guarantee that this mutation would ever be tried.

Compounding this problem is the fact that rule sets are fragile, and generally any random change to a game's rules will break it. While one particular mutation would have transformed Lammothm into a much better game, almost any other mutation would have ruined it entirely. In computational terms, small incremental changes to a rule set will not necessarily result in a gradual climb up the local maximum. In biological terms, rule sets do not display the gradualism assumed in a neo-Darwinian approach and instead rely on saltations (large changes from one generation to the next) to make evolutionary progress.

4. Monte Carlo Game Design

Monte Carlo tree search (MCTS) might provide an alternative way to find optimal rule combinations that may address these shortcomings in the evolutionary approach. MCTS works by running a large number of random simulations and learning from each one in order to build a search tree that gets more accurate as more simulations are run. It has a natural mechanism for balancing exploration of the search space with exploitation of learnt knowledge, and a feedback mechanism in which continued simulation improves the tree, which in turn improves future simulations.

MCTS has two inherent qualities that make it attractive for game design:

1. Inherent local search: Whenever a new state is reached, the search does not progress beyond that state until all actions (mutations) have been tried upon it.
2. Inherent restarts: From time to time, the algorithm will naturally try less promising combinations of actions, until it is sure that they lack promise.

These two features mean that if any slight change will improve a game then it is more likely to be found, but that the search will still occasionally jump from the local maximum to visit other parts of the rule combination space. Further, MCTS can learn from previous simulations using a history heuristic so that combinations of rules that proved fruitful in previous contexts are more likely to be tried in future contexts. Heuristics based on this idea have allowed recent breakthroughs in computer Go that now see MCTS Go players challenging top human players.

5. Shibui Game Design

The ideal game system to test these ideas would be:

• Tightly constrained and with a small, clearly defined rule set.
• Simple enough that most of the rule combination space could be searched.
• Complex enough to provide a range of interesting games.
• Small enough that its board state would fit into a single integer (for efficient implementation).
• Novel enough that its search space was largely unexplored.

While I was looking for such a system, abstract gamer Tom Gilchrist mentioned a concept from Japanese aesthetics called shibui. Shibui objects balance simplicity with complexity; they may initially seem deceptively plain, but will reveal hidden depths and become more interesting the more time is spent with them.

The Western world has been gradually exposed to shibui through popular culture. Elizabeth Gordon described it as "the highest form of beauty" in a series of 1960 House Beautiful articles. It has since been described in Trevanian's novel Shibumi as "elegant simplicity" and "understated beauty", and in Michener's novel Iberia as "acerbic good taste", recalling the term's origins as a description of a sour but appealing taste. It is used by Matthew May as a philosophy for personal growth in his allegory The Shibumi Strategy.

There are obvious parallels between these principles and those of combinatorial game design, especially the notion of simplicity hiding depth, as exemplified by the old cliche "a minute to learn, a lifetime to master". A rule set that works harmoniously can produce a thing of both beauty and lasting enjoyment, reminiscent of John Holland's description of emergence as "much coming from little".

May also notices the parallels between shibui and elegance in creative design. The elegance of an object is often defined not by what it includes but by what it excludes, much as a game designer seeks to produce the simplest possible rule set for a given game. The apparent simplicity of a well-designed object is usually the result of much complexity and refinement in design that may go unnoticed by the end-user. These ideas resonate with most of the key aspects I was looking for in my experimental game system, and influenced the final design.

6. The Shibumi Set

After several months of deliberation and recovery from information overload after running around Spiel 2010 trying to see every small game system in existence in a single weekend, I finally decided on the system that is now called the Shibumi set and published by nestorgames. The term shibumi is a noun form of shibui used to describe particular instances.

The Shibumi set consists of a 4x4 square board and 16 balls in each of three colours:

The basic mechanisms are to place, move or remove balls on this board. Balls may be stacked on 2x2 platforms of other balls as follows:

Balls may also be removed to cause higher level balls that they support to drop and fill their place:

A completely filled board forms a 4x4 square pyramidal (SP4) packing. The 4x4 base allows a total of 4x4+3x3+2x2+1=30 potentially playable points. The state of each may be described by two bits:

00 = Empty
01 = White
10 = Black
11 = Red

Hence the entire board state may be described in 30 x 2 = 60 bits, or a single 64-bit long integer, as desired, with a few bits left over for storing the current mover and current winner (if any). More details can be found at http://www.mogal.ai/shibumi/.

The rule combination space of games playable with this set was almost entirely unexplored prior to its release in October 2011. The only known prior example was Pylos, which can be played with a Shibumi board and 15 white and 15 black balls, but otherwise there is a surprising lack of SP4 games. Note that 2D games that can be played with a subset of the equipment (such as Tic-Tac-Toe) are not counted as Shibumi games. Some related marble stacking games can be found in the Stacks of Spheres Geeklist; there aren't many.

While the equipment is extremely simple and the rule space quite small, it is still possible for interesting games to emerge, a couple of which are shown below. Moves can create 2x2 platforms that open up points that were not previously playable – the 16 physical board points imply an additional 14 potential ones – and removals can trigger changes in board state that can be surprisingly hard to predict. The human brain has trouble visualising abstract 3D manipulations, and that's what Shibumi games are all about!

The fact that higher level points do not become playable until the lower levels start to fill up constrains the branching factor (number of possible moves per turn), as the full 30 points are never playable at any given time. The average branching factor will be similar to that for a comparable 4x4 game in 2D while the state space complexity will be similar to that of a comparable 5x5 game in 2D, which tilts the apparent simplicity : actual complexity ratio even further towards shibusa.

6.1 Spline

Spline, by Néstor Romeral Andrés, is a prime example of shibui. Two players, White and Black, take turns placing a piece of their colour at any playable point. The game is won by the player who completes a line of their colour (orthogonal or diagonal) that spans the pyramid at any level. For example, the game shown has been won by White.

The rules are extremely simple and intuitive (players generally need to hear them only once), but the game can throw up some surprises and has a nice mathematical elegance in that every game must produce a winner before the last ball is placed. Spline shows how simple a rule set can be while still producing a non-trivial game. A variant called Spline+, which includes a drop mechanism, provides a deeper game at the expense of rule clarity.

6.2 Spargo

Spargo, by Cameron Browne, shows how deep Shibumi games can be. Spargo is a form of 3D Go played by two players, White and Black, who take turns placing a ball of their colour at any playable point that will have freedom after the move. (A ball has freedom if its visibly connected group is adjacent to an empty board hole.) Enemy groups without freedom are captured and removed, except that balls that support enemy balls at any level remain on the board as zombies. Passing is not allowed. The game ends when a player has no moves, and is won by the player with the most balls in play.

Zombie pieces are so called because they have been technically killed, but remain active in the game and can come back to bite you if you're not careful. For example, the position shown is a puzzle with White to play. White appears to be in a hopeless position; Black has a strong group with two eyes, dominates most of the board, and outnumbers White by more than 2:1. However, the fact that passing is not allowed and that all White pieces are zombies allows White to force a win from this position, which is most counterintuitive. The full proof of this solution can be found at http://www.cameronius.com/games/spargo/.

The Shibumi set is therefore a simple, constrained game system with a small set of well-defined rules that still allow the definition of interesting and non-trivial games. The rule combination space is small enough that a representative uniform coverage should be possible, but this space is still almost entirely unexplored. The set epitomises the notion of shibui and is ideal for the upcoming experiment in automated game design.

7. The Shibumi Challenge

Given this minimalist game system, the next step is to define a complete set of component rules in order to seed the automated searches. It would also be convenient to have a core set of Shibumi games created by human designers in order to provide a yardstick for what is possible within the system. The Shibumi Challenge was designed to address these needs.

The Shibumi Challenge is a game design contest currently being run by Cameron Browne and Stephen Tavener of the Computational Creativity Group at Imperial College London, and Spanish game publisher Néstor Romeral Andrés. Contestants are invited to submit the best (and most shibumi) games that they can devise for the system.

Response to the Challenge has been excellent so far, with over twenty new games already submitted at the halfway point. The Challenge continues until 31 January 2012 and is open to all comers. Once the deadline is reached, the entries will be judged by the Challenge organisers and prizes awarded to the three best and most shibumi games. The entries shall then be coded in software and used to seed parallel evolutionary and Monte Carlo searches for new Shibumi games in order to compare the dynamics of each search method for game design.

Note that this is not a Turing test! The intention is not to see whether computer-designed games can be passed off as human-designed ones, or whether an automated process can produce better games than humans. The intention is to see whether automated means can help human designers find good rule combinations that they might otherwise overlook, and act as creative collaborators in the game design process. I expect that similarly good results might arise from small tweaks to existing games as well as from quantum leaps to completely new rule combinations. If so, this will hopefully go some way to demonstrate the usefulness of machine learning approaches for automated playtesting and rule-tuning, to remove some of the combinatorial burden from the designer and reduce the occurrence of games being released with flaws that are easily detected and fixed.

Cameron Browne