BoardGameGeek News

To submit news, a designer diary, outrageous rumors, or other material, contact us at news@boardgamegeek.com.

Archive for Cameron Browne

Recommend
130 
 Thumb up
13.00
 tip
 Hide

AI Game Design: The Shibumi Challenge

Cameron Browne
Netherlands
Maastricht
Limburg
flag msg tools
designer
Check out Ludii: http://ludii.games
badge
Researcher in AI and automated game design.
Avatar
Microbadge: Zener Card - circleMicrobadge: Zener Card - crossMicrobadge: Zener Card - squareMicrobadge: Zener Card - starMicrobadge: Zener Card - waves
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".)

Board Game: Yavalath
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

Board Game: Primordial Soup
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

Family: Series: Shibumi
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:

Family: Series: Shibumi

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

Family: Series: Shibumi

Family: Series: Shibumi
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.

Family: Series: Shibumi
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
Twitter Facebook
44 Comments
Tue Jan 3, 2012 6:30 am
Post Rolls
  • [+] Dice rolls
Recommend
128 
 Thumb up
5.00
 tip
 Hide

Yavalath: On Evolutionary Game Design

Cameron Browne
Netherlands
Maastricht
Limburg
flag msg tools
designer
Check out Ludii: http://ludii.games
badge
Researcher in AI and automated game design.
Avatar
Microbadge: Zener Card - circleMicrobadge: Zener Card - crossMicrobadge: Zener Card - squareMicrobadge: Zener Card - starMicrobadge: Zener Card - waves
In November 2007, a new board game called Yavalath was invented. The rules of Yavalath are simple: Players take turns adding a piece of their colour to a hexagonal board and win by making four-in-a-row of their colour – but lose by making three-in-a-row beforehand.

From gallery of nestorgames
Fig. 1 – Yavalath puzzle: White to play and win.

Fig. 1 shows a Yavalath puzzle by way of example. What is White's only winning play? Hint: Consider what happens if Black is allowed to play at either cell marked X.

Yavalath has proven reasonably popular as its simple rules allow interesting and surprising situations to develop due to its innovative win with four but lose with three winning condition. But Yavalath is really set apart from the many other board games invented in 2007 by one remarkable fact: Yavalath was designed by a computer programme.

This computer programme, called Ludi, creates games by taking the rules of existing games and scrambling them into new combinations using genetic programming (GP) techniques of crossover and mutation. New games are tested through selfplay trials and assigned a quality score based on their estimated potential to interest human players, hence the complete process of design, testing and evaluation is entirely automated. Ludi creates a unique name for each evolved game using a Markovian process seeded with Tolkien-style words.

Ludi produced 1,389 new games over a four week run, of which it deemed 19 to be playable and of varying degrees of interest. It ranked Yavalath as the fourth best evolved game, while a group of human player testers found Yavalath to be the second most interesting of the evolved games. However, it was obvious from the moment the game arrived that Yavalath had a special quality about it, and it has since emerged as the clear favourite and now stands as a game in its own right. The game caught the attention of Néstor Romeral Andrés and was commercially published by nestorgames in 2009.

Board Game: Yavalath
The nestorgames edition

Rules

Yavalath is played on a hexagonal field of hexagons which is initially empty. The standard board size is five cells per side (Fig. 2).

From gallery of nestorgames
Fig. 2 – The Yavalath board.

Two players, White and Black, take turns adding a piece of their colour to an empty cell. A player wins by making four-in-a-row of their colour (or more) but loses by making three-in-a-row of their colour without also making 4-in-a-row (or more). If the board fills without either player winning or losing, then the game is a draw.

Swap Rule: White makes the first move, then Black has the choice of either swapping colours – effectively stealing the first move – or continuing with their move as usual. This discourages White from making an overly strong opening near the board centre.

Forcing Moves

The key tactical play in Yavalath is the forcing move, as shown in Fig. 3. White move 1 threatens to make a line of four white pieces next turn, hence Black is forced to play blocking move 2 to intervene. Unfortunately for Black, this forced blocking move completes a line of three black pieces to lose the game.

From gallery of nestorgames
Fig. 3 – A forcing move by White.

Games are typically won using sequences of such forcing moves to manipulate the opponent into disadvantageous and ultimately losing positions. Long sequences of forcing moves can be difficult to predict correctly, especially if forced replies by the opponent themselves trigger further forced replies from the mover, and so on. Hence players can plan ahead with some certainty but must be careful of any surprises that might lie in wait once a forced exchange is triggered.

Puzzle Solution

With this in mind, consider the simple puzzle introduced earlier (Fig. 4): White to play and win.

From gallery of nestorgames
Fig. 4 – White to play and win.

A Black move 1 at either cell X will force a losing reply 2 from White, as shown in Fig. 5. Hence Black must not be allowed to make either of these moves, and the only way to achieve this is for White to go on the offensive with forcing moves of their own.

From gallery of nestorgames
Fig. 5 – Black can force a win with either move X.

White has three forcing moves available to them, marked a, b and c in Fig. 4. A move 1 at either a or b would indeed force a reply 2 from Black as shown in Fig. 6, but each of these replies would in turn force a losing reply 3 from White. Such forcing moves that come back to hurt the mover are called rebounds (similar to the Go concept of "snap-backs").

From gallery of nestorgames
Fig. 6 – Forcing moves a and b lose for White.

The only non-losing choice available to White is therefore move 1 at c, as shown in Fig. 7. This move forces a harmless reply 2 from Black and sets up White for another forcing move 3 which forces another harmless reply 4. White can now play move 5 which forces Black to make losing move 6.

From gallery of nestorgames
Fig. 7 – Forcing move c is White's only winning play.

Strong Patterns

Triangular piece formations tend to form very strong patterns. For example, the small size-2 triangle shown in Fig. 8 allows White to launch a variety of winning attacks.

From gallery of nestorgames
Fig. 8 – The small size-2 triangle is a strong pattern.

Figures 9 and 10 show forced winning sequences by White both above the triangle's apex (9) and below its base (10). Given that both of these attacks can be applied in each of three rotations and two reflections, it is difficult for the opponent to block all possible attacks from the small triangle; all three sides of the triangle must be blocked. Players must therefore be wary of the opponent forming such patterns unless suitable precautions are taken.

From gallery of nestorgames
Fig. 9 – White can force a win above...

From gallery of nestorgames
Fig. 10 – ...and can force a win below.

Medium size-3 and large size-4 triangles (Figures 11 and 12) are also strong formations that allow forced wins, as shown. However, medium and large triangles are easier to block - it is usually sufficient to block one side - and hence do not present as much danger as small triangles.

From gallery of nestorgames
Fig. 11 – Medium size-3 triangles allow a forced win.

From gallery of nestorgames
Fig. 12. – Large size-4 triangles allow a forced win.

First Move Advantage

White has a huge (winning) advantage if allowed an unconstrained opening move. Fig. 13 shows how White can form a small triangle with their first three moves, which Black is helpless to defend against. This strong opening was first pointed out by Néstor Romeral Andrés in 2011.

From gallery of nestorgames
Fig. 13 – A strong (winning) opening for White.

Fig. 14 shows how it is possible to block a small triangle on all three sides with only three pieces. However, White can choose which way to orient the triangle with their third piece to avoid this situation; Black would have to catch White napping to achieve such a blockade.

From gallery of nestorgames
Fig. 14 – Black foils White.

The solution to this imbalance is the swap rule, which enables Black to swap colours in lieu of making their first move, which discourages White from making an overly strong opening move. This rule is used successfully to balance openings in a number of combinatorial games.

From gallery of nestorgames
Fig. 15 – Swappable openings.

Fig. 15 (left) shows opening moves that Black should swap. The large dots represent moves that should undoubtably be swapped, while the small dots represent moves that appear to be reasonably balanced. Opening moves in unmarked cells need not be swapped as their proximity to the board edge reduces the danger of the small triangle on that side. A general rule of thumb: Swap any opening move that is three or more cells away from the board edge.

Fig. 15 (right) shows the best opening moves for White. Opening moves along the board edge are too weak to consider, while openings one cell away from the edge (marked "1") are weak but plausible. Opening moves two cells away from the edge (marked "2") are stronger and reasonably balanced, and the opponent will not necessarily swap such a move.

Draws

Draws, although possible, are extremely rare. Players generally tend to make a fatal mistake due to the difficulty of correctly predicting forced sequences, or are forced into making a losing move as the number of available move choices dwindles in the end game.

From gallery of nestorgames
Fig. 16 – A indecisive fill pattern.

Fig. 16 shows a possible fill pattern that precludes a result, but which will not occur in standard play unless both players conspire for a draw.

Three-Player Yavalath

Yavalath works well as a three-player game. The standard two-player rules apply as specified by Ludi, with the following additions:

a) Any player to make three-in-a-row is removed from the game
(but not their pieces).
b) The mover must block the next player if possible.

Rule a) allows the game to continue when a player loses but a winner is not yet decided between the remaining two players. Rule b) removes a potential king-maker effect, which is the undesirable ability of a losing player to decide the outcome of a game. The move order is: White, Black, Grey.

For example, Fig. 17 shows a three-player game with Grey to move. Grey must move at a to block White, then White must move at b to block Black and hence lose the game. If rule b) were not in effect, then Grey would be free to choose between a White loss (or a Black win) with move a or a White win with any other move. Example by Stephen Tavener.

From gallery of nestorgames
Fig. 17 – Grey must block White at a.

The three-player version was devised as a natural extension of the two-player game shortly after its invention in 2007.

The Tournament

To celebrate the second anniversary of Yavalath's publication, we're running a tournament on igGamecenter. Please participate for a chance to win a copy of the game!

Cameron Browne
Computational Creativity Group
Imperial College London
Twitter Facebook
22 Comments
Tue Jun 7, 2011 6:30 am
Post Rolls
  • [+] Dice rolls