This post was released for Issue 13 of Bitcoin Magazine as part of a series of articles about puzzles and games that started with Issue 12. I hope you enjoy reading them as much as I enjoy writing them.
Background
In 2005, computer scientist Cameron Browne¹·¹ begins work on a computer program called LUDI as part of his Ph.D. research. On November 2007, after running for a month, LUDI becomes self aware. In a panic, humans attempt to shut it down…
Okay, okay. LUDI did not become self aware (yet). But it did something amazing.
While humans code sets of rules to be executed by computers, LUDI coded sets of rules to be executed by humans. But not only that, LUDI coded sets of rules that humans enjoy executing.
LUDI invented games.
It invented thousands of games, and tested them by playing against itself over and over. And it evolved them, combined them, mutated them, repeating this process until it came up with a final list: LUDI’s nineteen playable games.
Two of these games were recognised as being outstanding. LUDI also invented names¹·² for these games – Yavalath and Ndengrod – although Ndengrod was later changed to Pentalath by myself. Both were published by nestorgames in 2009. LUDI was described in the “Evolutionary Game Design” book and it went on to win the GECCO Humies gold medal for human-competitive results in evolutionary computation in 2012.
I’ll show you the most popular of the two, Yavalath, which at one point was ranked in the top #100 abstract board games ever invented on boardgamegeek, the largest online database of games. Quite impressive for a game designed by a computer. In fact, Yavalath is ranked higher that any of the games designed by Cameron himself, much to his embarrassment; his program is a better game designer than he is!
YAVALATH
Yavalath is a board game played on a hexagon made of hexagons. The standard board size is 5 cells per side.
Figure 1: A hexagonal board
You can play Yavalath with paper and pencil. Here’s how to draw a hexagonal grid on graph paper.
Figure 2: How to draw a hexagonal grid substitute
Figure 3: White wins (left) and Black loses (right)
After reading the rules for the first time, two thoughts might arise:
1. “How can I make four-in-a-row without making three-in-a-row beforehand?” You’ll quickly realise how. But this simple mechanism hides something deeper which I’ll talk about later.
2. “I can avoid losing by simply not making a three-in-a-row. What a weird rule! Nobody will make a three-in-a-row!” Not so fast. See figure 4.
Figure 4: A forced move
If Black wants to prevent White from making four-in-a-row, he must place a stone at ‘a’, thus making a three-in-a-row and losing! This is called a ‘forced move’. So the goal of the game is not so much to create a four-in-a-row (which could easily be blocked), but to create a situation in which the opponent is forced to make a three-in-a-row and thereby lose the game. This is the first “aha!” moment that players typically experience. Se second “aha!” moment comes when you realiz\se that you can use such forcing moves to manipulate your opponent into a losing position. The following challenge is a good example for this.
Challenge 1 (easy): White to play and win in three.
Figure 5: White to play and win in 3
Now that you’ve grasped the basics, let’s dig a bit deeper into what LUDI achieved. LUDI found a constraint (3-in-a-row is forbidden) that is a subset of a goal (4-in-a-row wins). So in order to reach your goal, you have to find alternate paths that are not forbidden, while subsets of your goal are¹·³. LUDI created a set of rules that makes you think ‘out of the box’²·¹; simply making your line longer is not enough.
Figure 6: Think out of the box in order to reach your goals. The forbidden pattern is indicated in red.
But LUDI, even being a groundbreaking piece of technology, was just a prototype of what will²·² come in the near future, and thereby had its flaws. In 2012, while testing the AI that LUDI used to play the games, I found a way to consistently beat it when playing White, in seven turns at most. LUDI’s AI had some issues when dealing with short-term threats.
Challenge 2 (hard): Find a sequence of seven moves that guarantees a win for White (this was posted online, so don’t cheat).
Fortunately, we fixed this problem by adding the pie rule to the game, which is often used in game design to counteract a first player advantage. After White’s first move, 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 move, i.e. near the board centre in this case.
Yavalath has inspired a plethora of new games. In case you don’t have a hexagonal board handy, don’t want to draw one, or wish to play a shorter game, here is a small Yavalath derivative of my own design that can be played on a small square board.
SQUAVA
Squava is played on a 5x5 square board according to the same rules as Yavalath. Lines can be horizontal, vertical or diagonal. I came up with this variant while trying to solve the ‘strong centre’ problem; in Yavalath the board centre is a powerful opening move, whereas in Squava it might be a bad idea. Can you see why? I also had to reduce the size of the board, as Squava has four available directions (horizontal, vertical and two diagonals) instead of three (as in the hexagonal Yavalath), making White unstoppable on bigger boards.
Figure 7: White wins.
Challenge 3 (hard): Can you find a winning Squava strategy for White or Black?
Please post your answers in my forum and I will reward the best post with a copy of one of my games! I’m looking forward to discussing your findings. Thank you for reading!
1.1 Cameron Browne is now a researcher for the Computing Department of Goldsmiths, University of London, member of the 'UCT for games and beyond' project, outstanding game designer and a good friend. My acknowledgments to him for checking and approving this article.
1.2 LUDI creates names for its games using Markov chains based on letter combination frequencies in a list of Tolkien-style names from the game Angband.
1.3 Sounds familiar? Satoshi Nakamoto did the same thing on a way bigger scale recently.
2.1 You might wish to check out issue 12 of Bitcoin Magazine or the online article here, where I describe a puzzle that uses another goal-but-not-subset mechanism.
2.2 Stay tuned. We're on it.