Zero-player Games

Katie Steckles

You might enjoy playing games with a friend, or a group of friends. The good news is that even if you don’t have any friends, or even if you don’t exist yourself, you can still play mathematical games. Zero-player games are ones which have no sentient players, and the rules of the game are such that it can proceed without input from any human. 

There are a few different ways in which a game can have zero players – and not all of them require you to build a functioning game-playing robot before you start.

Cellular automata

Cellular automata are mathematically determined systems which are based on cells – conventionally arranged in a grid, but automata can also be defined in more or fewer than two dimensions. The idea is that for each cell, there are a given number of states it can be in (usually indicated by the colour of the cell), and a fixed rule about how the state of each cell changes with time.

Such systems can be thought of as games, in the sense that changes happen to the cells sequentially and can be seen as taking turns. The rules of the game being specified, it can run without any input from a player, since what happens at each stage is determined by the rules. The classic example of a cellular automaton is John Conway’s Game of Life.

Invented in 1970, the Game of Life involves a two-dimensional grid in which cells can either be black or white (in the game, the two states are known as ‘alive’ and ‘dead’) and at each time step, whether a cell is going to be alive or dead for the next time step is determined by how many of its eight immediate neighbours are currently alive. The standard rules are given as:

  1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overpopulation.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. 

Given this simple set of rules, and a plain black and white grid, some surprisingly interesting structures arise. Study of this game has largely been devoted to finding sets of cells which, if the game is started with exactly those cells alive, it will continue in particular ways. For example, structures have been found which are stable – they don’t change; others which form a loop of two or three states which repeat indefinitely unless disturbed; and even structures which evolve in such a way that they destroy themselves while producing a copy of themselves one square further across – by which means they move slowly across the grid. Some examples are shown here.

In fact, it’s been shown that within the Game of Life you can construct systems which can be used to perform any calculation that can be written down as an algorithm – known as Turing complete.

There are plenty of other examples of cellular automata – all possible 1-dimensional automata with two possible states have been enumerated by Stephen Wolfram. These consist of a single row of cells, whose states determine the states of cells in the next row, producing a pattern which can be so beautiful that people will put it on a train station.

Other automata are defined in different ways – for example, Langton’s Ant is an example of an automata which is defined using an ant character on the grid, which moves around changing the states of the cells as it goes according to fixed rules.

No players, no waiting

Another way to make a game zero-player is to teach a computer how to play it. Ever since computers came into widespread use, people have been trying to teach them how to play games – it’s an interesting programming challenge, and while some games are simple to model, others take huge amounts of computation power.

EDSAC (the Electronic Delay Storage Automatic Calculator) was an early computer which was taught to play noughts and crosses in 1952 – called OXO, the output from the game was displayed on a cathode ray tube, and the input was via a rotary telephone dial! It was widely thought of as the first computer game. Since then, almost all simple games have been modelled and studied using algorithms, and people have also had a go at the more complex ones too.

Chess computers were a huge focus of artificial intelligence development in the 1980s and 90s, since it’s a game which has a simple specified set of rules and objectives, but whose complexity becomes very large very quickly. The number of possible moves in any given situation can be quite large, and checking all the many avenues of possible moves for yourself and your opponent through to the end of the game is too much even for a computer. This forces people writing chess computer algorithms to think about other ways to optimise their strategy – thinking a few moves ahead, and assuming your opponent will choose good moves.

Chess computers surpassed humans in the 1990s – when Deep Blue famously played and beat chess grandmaster Gary Kasparov – but for other, more complex games, like the ancient Japanese game of Go, the number of possibilities is too big even for advanced computers. It was only in 2015 when computers employing machine learning were able to first beat a human at the game. AlphaGo, developed by DeepMind, was trained to play the game partly by playing against itself repeatedly, until it had seen enough possible strategies to learn how to play well. Truly a zero-player game!

Playing against mathematics

There’s one other way in which games can be considered to be zero-player – and there’s a good chance that you’ve played a zero-player games yourself. Many games are considered ‘solved’ – that is, they’re simple enough that they have been fully analysed and all possible strategies are known. One example is noughts and crosses – there are only 31,896 possible game states, and many optimal strategies are known. So if both players are playing optimally, their moves are effectively chosen for them – so there’s not really any input from human players.

Some zero-player games can really feel like you’re actually playing them, when in fact you aren’t. Snakes and ladders is a nice example of this – you take it in turns to roll a die and move your piece, and if you happen to land on a snake or a ladder, you’ll go to a different part of the board. But in a game like this, literally all your movements are determined by the roll of the dice. Maybe you feel like you have some influence on the results of the dice roll – but if it’s a truly fair dice, it shouldn’t be possible, and any throw is equally probable.

So if you’re playing snakes and ladders, you’re not really putting much in. In fact, I’m playing snakes and ladders right now, and have been for a few years – some friends and I wrote a program which rolls a dice and moves us around on an imaginary board, which plays about 1000 games a week and emails us to let us know who’s winning. I’m currently in the lead!

Der Beitrag Zero-player Games erschien zuerst auf Heidelberg Laureate Forum.