This post was released for Issue 14 of Bitcoin Magazine as part of a series of articles about puzzles and games that started with Issue 12.
This is a short story about how one of my favourite game designs came to life. I hope you enjoy reading it as much as I enjoyed my journey. You can play the game with paper and pencil.
BACKGROUND
Part of my work at the Computing Department of Imperial College London consists in providing real world applications for their findings in Artificial Intelligence research. Such research is focused in developing efficient searching algorithms in order to attack large decision trees.
And what is a decision tree? Suppose a Tic-Tac-Toe game with free opening (playing on the centre square on the first turn is not mandatory). I have 9 possible first moves (I have to decide which one to play). On your turn, you have 8 possible responses for my first move (you have to decide which one you play). Then I have 7 responses on my turn, and so on. If we draw a diagram with all possible moves, it will look like the following figure. Notice the tree structure that is generated. Every node of the tree, where a branch splits into several other branches, is a decision point.
Figure 1: The Tic-Tac-Toe tree (condensed).
Finding the best move in a given turn is a problem. These algorithms try to solve it.
The decision tree for Tic-Tac-Toe is quite small. But the trees for games like Chess or GO are gigantic (the number of different possible games of GO is larger than the number of particles in the universe). When coding an Artificial Intelligence algorithm for playing these types of games, we have to assume that browsing the whole tree is impossible. So we use algorithms that find optimal solutions without searching the whole tree (the best possible solution in a given time), even if they’re not the best moves overall.
The most advanced algorithm uses a very smart mechanism to achieve this. It tests promising moves by playing thousands of game simulations for those moves. This process is called exploitation, and it converges to a solution (optimal or not) over time. But at the same time, it tests other moves just in case it’s missed a potentially better one. This is called exploration, and it diverges from the possible solutions already being tested, in order to find another ones. The algorithm perfectly balances both processes with outstanding results¹·¹.
I’m not a computer scientist, so it took me a bit to understand this mechanism by just reading the code. But being a teacher myself, I know that the best way to understand something, is trying to reword it so you can teach it to a kid. So I took what initially looked like a complex algorithm, and turned it into a simple diagram.
Figure 2: The T-shaped diagram.
This ‘T-shaped’ diagram shows how the algorithm balances both convergent (arrow pointing down) and divergent processes (two-headed arrow on top).
After coming up with this diagram, I realized that this resembles how humans try to solve problems. We use several areas of expertise to attack them (divergent thinking) and at the same time we exploit the most promising ones (convergent thinking). And we do this for every stone we find in our path. Moreover, the more we balance both ways of thinking, the more efficient we became in solving the problem.
SOLVING A PROBLEM: GAME CREATION
When I create games, I’m in fact trying to solve a problem: to design a good game¹·². But when I’m designing a game, I’m not aware of the design process itself. I’m just focused on the game.
That day in 2012, with all this in mind, I was willing to create a tile-laying game¹·³. After spending several weeks trying to exploit a handful of mechanics and components without success, I became self aware of the creative process that I was executing, and realized that something was missing. I was too focused on the exploitation part of the process, while ignoring the exploration part.
As I mentioned above, exploration relates to divergent thinking. In 1967 in order to measure Divergent Thinking, J.P. Guilford developed the Alternative Uses Test. It gives you two minutes to think of as many uses as possible for an everyday object like a chair, a spoon, or a paper clip as you can. A regular person can think of up to 15 different uses for the given object. The more creative you are, the more uses you are likely to think of. But the population group that gives the highest score for the test is… kids!
So I decided to plug a bit of divergence on my design process by asking for help to the most divergent person I’ve ever met: my daughter. She was four at that time.
- Sweetheart, would you like to design a game with daddy?
- Yes, daddy.
- Great! How do you want it to be?
- Look, daddy. We place a sheep here, a wolf here, and a dog in the middle, so the wolf doesn't eat the sheep. The wolves want to eat the sheep, but the sheep escape from the wolves and the dogs bark the wolves to scare them so they don't eat sheep.
- !!!
I drew the tile in 5 minutes with some cliparts:
Picture 3: The tile.
… and two days later the game was finished!
SHEEP, DOGS AND WOLVES
Two players (Sheep and Wolf) share a common pool of 23 rectangular tiles like the one in figure 3. Instead of using tiles, you can play with paper and pencil (see below). The ‘sheep’ player must save as many sheep as possible (by placing dogs next to wolves, but keeping the sheep away from them), and the ‘wolf’ player must eat as many sheep as possible (by placing wolves next to sheep but not next to dogs). The game takes place over two rounds. In the first round, one player plays as the sheep, the other as the wolves. In the second round, the roles reverse. Whoever saves more sheep playing the ‘sheep’ role wins the game.
You’ll need a graph paper, a regular pencil and a colour pencil (red, for example).
White circles will represent sheep, red circles will represent dogs and black circles will represent wolves. Draw a tile according to the figure.
Figure 4: Game setup.
Starting with the ‘sheep’ player, players take turns drawing a tile (sheep-dog-wolf²·¹) in any orientation and direction (not diagonal), and touching at least one already drawn tile (corners don’t count as ‘touching’).
Figure 5: Example of game state after Sheep’s first move. Notice how the new tile has been placed vertically pointing upwards.
The game ends when each player has taken 11 turns²·². To get the ‘sheep’ score, do the following, in order:
- Draw an ‘X’ on each and every wolf that has at least 2 adjacent dogs (corners don’t count). These wolves are ‘scared’ of the dogs and won’t eat sheep²·³.
- Draw an ‘X’ on each and every sheep that is adjacent at least to one wolf that is not scared of the dogs. These sheep have been eaten by the wolves.
- Count the remaining sheep (the ones with no X’s on them), which are ‘safe’. This is the ‘sheep’ score.
Figure 6: Example of endgame. Sheep scores 11 points.
THE CHALLENGES
Challenge 1: Find the best move for the wolf player.
Figure 7: Challenge 1.
Challenge 2: Find the best move for the sheep player.
Figure 8: Challenge 2.
Challenge 3: How many tiles can you fit into a 7x7 grid so that no 2 dogs are placed next to each other (touching) and the ‘sheep’ score is maximum?
Please post your answers in my forum:
http://nestorgames.freeforums.org/bitcoin-magazine-puzzles-f16.html
... 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!
You might also enjoy my previous posts:
-----------------------------------------------------------------------------------
1.1 It uses the mechanism for all moves of all game simulations of every move, through an iterative process.
1.2 I’m not saying that I’ve solved it yet, I just say that I’m trying!
1.3 A tile-laying game is a game where players take turns placing tiles on the playing surface. A popular example is Dominoes.
2.1 You cannot alter the order of the 3 animals. The dog has to be always in the middle. This is, Dog-Sheep-Wolf is forbidden, for example.
2.2 You can play more or less turns upon agreement.
2.3 The X’s may be drawn during play (to add some clarity).