Yavalath: On Evolutionary Game Design

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.

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.

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).

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.

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.

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.

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").

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.

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.

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.

Fig. 9 – White can force a win above...

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.

Fig. 11 – Medium size-3 triangles allow a forced win.

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.

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.

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.

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.

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.

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