# space and games

## June 5, 2006

### Games with Graphs

Filed under: Graphs — Peter de Blanc @ 10:01 pm

This is a graph:

This is another graph:

A graph is a collection of vertices and edges. Each edge connects two vertices. Mathematically, we can define a graph as an ordered pair (V, E), where V is the set of vertices and E is a set of unordered pairs of vertices. For example:

This is the same as our first graph, except now the vertices are labeled.
Let’s call this graph G0 = (V0, E0), where:

V0 = {1, 2, 3, 4, 5, 6, 7}
E0 = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {4, 6}, {5, 6}, {5, 7}, {6, 7}}

You can play many fascinating games with graphs, such as Igo (囲碁), called Go in English.

You can play Go on any graph, although it is usually played on this one:

We will not be using this graph when discussing Go in the remainder of this article. For simplicity, we will use this graph:

G1 = (V1, E1), where
V1 = {1, 2, 3, 4, 5}
E1 = {{1, 2}, {2, 3}, {3, 4}, {4, 5}}

In a Go position, each vertex may be occupied by a black or white stone (or it may be empty). For example, position q2:

Within a Go position, two adjacent stones of the same color are connected. Furthermore, connectivity is transitive: if stones a and b are connected, and stones b and c are connected, then stones a and c are connected. A group consists of a stone and all the stones which are connected to it. For example, position q2 has two groups, each consisting of one stone. There are also two groups in this position, consisting of two black stones and one black stone:

The liberties of a group are the empty vertices adjacent to it. The left group has one liberty (vertex 3), and the right group also has one liberty (vertex 4). A group is called dead if it has no liberties.

A situation consists of two pieces of information: a Go position, and a turn color. A turn color may be either black or white. For example, the situation (q2, white):

White to play.

In Go, there are two players: black and white. On a player’s turn, ve may either place a stone of vis color on an empty vertex, or pass. After a stone is placed, the player removes all dead groups of the opposite color, and then removes all dead groups of vis own color. After any action, the turn color is reversed.

A game is a finite sequence of alternating situations and actions. Each action transforms the current situation into a new situation, which is added onto the game sequence. It is forbidden to place a stone which would result in a situation that has already occured in the game. If two consecutive actions are both passes, the game ends. The player with more stones wins. Here is a game of Go:

0:                       Black to play.

1: Black plays at 3.     White to play.

2: White plays at 4.     Black to play.

If black plays at 5, the white group (consisting of a single stone at 4) will have no liberties, so it will have to be removed from the board.

3: Black plays at 5.     White to play.

Black just captured the stone. Note that it would now be illegal for white to play at 4, because that would lead to a repetition of situation 2. It is forbidden to play a stone which would create a situation that has already occured in the game.

4: White plays at 2.     Black to play.

Black can capture this stone too:

5: Black plays at 1.     White to play.

6: White plays at 4.     Black to play.

Note that it would be illegal for black to play at 5, because that would lead to a repetition of situation 5.

7: Black passes.         White to play.

8: White plays at 2.     Black to play.

Now black has no legal moves. If ve placed a stone at 1, 3, or 5, that stone would immediately be removed, and this would lead right back to situation 8. It is forbidden to place a stone which would result in a situation that has already occured in the game, but it is not illegal to pass.

9: Black passes.         White to play.

10: White plays at 3.    Black to play.

11: Black passes.        White to play.

12: White passes.        Game over. White wins by 3 stones.

0:                       Black to play.

1: Black plays at 2.     White to play.

2: White plays at 4.     Black to play.

3: Black passes.         White to play.

4: White passes.         Game over. Draw.

These, then, are the rules of Go:

• Go is played on a graph. One player takes the black stones and the other player takes the white stones.
• Black and white stones may occupy vertices.
• Contiguous stones of the same color form groups.
• A group’s liberties are the empty vertices adjacent to it.
• A group with no liberties is dead.
• A situation consists of a position and a turn color.
• On a player’s turn, ve may either place a stone or pass. Then it becomes the other player’s turn.
• When a player places a stone, ve must then remove all dead groups of the other player’s color, and then remove all dead groups of vis own color.
• It is forbidden to place a stone which would result in a situation that has already occured in the game, but it is never illegal to pass.
• Conventionally, Go is played on a 19×19 grid. The initial situation has no stones on the grid, and black plays first.
• The player with more stones wins. If neither player has more stones, the game is a draw.

I will later refer to this last rule as the goal of Go.

Now I want to talk about another game. This game is called Life, and it was invented by John Horton Conway in 1970. You can read more about Life here. It may be more correct to call it a simulation instead of a game, but I will call it a game anyway.

Although Life may be played on any graph, it is normally played on this one:

This graph extends infinitely in all directions. The rules of life are as follows:

• In a game state, each vertex is either active or inactive.
• A game consists of a sequence of states. The initial state may be any state of your choosing.
• Given the current state, obtain the new state as follows:
• Set all vertices in the new state as inactive.
• If a vertex is active in the current state, and it has either two or three active neighbors, then activate it in the new state.
• If a vertex is inactive in the current state, and it has exactly three active neighbors, then activate it in the new state.

I’ll give you one example of an interesting pattern in Life. The active vertices are drawn with large circles, the inactive ones with small circles.

Note that the final pattern is the same as the initial pattern, except displaced up and to the left. This is called a glider.

Okay, we’ve looked at two games that can be played on graphs. I’d like you to imagine a graph as a universe, and the rules of Go and Life as possible laws of physics. Which one is more physics-like? Think about it for a minute, scroll down, and I’ll tell you my opinion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

I think that Life is much more physics-like than Go. Given any state in Life, the rules uniquely specify which state comes next. The rules of Go do not specify, even stochastically, how to obtain the next situation from the current situation – it all depends on the actions of the two entities called players, which are not specified by the rules of Go.

Life has been proven Turing Complete. That means, among other things, that you can build a mind in it. The thoughts and actions of that mind would be completely determined by the initial state and the rules of the game. No such feat is possible in Go.

Another difference is that Go has a goal and Life does not. Does physics have a goal – an objective morality that exists independently of any beings that live in the universe?

Consider that in Go, the players exist outside of the game. The actions of the players are not specified by the rules of Go, but when the players read the goal of the game, this influences their decisions. So it might make more sense to think of the goal not as a rule, but as an explanation to the players of what they might want to do with the rules.

What if we added a goal to life?

• The goal of Life is to make gliders.

It is pretty clear that this goal does not have any effect at all on the outcome of a game of life. In fact, no matter what goal we came up with, it would not affect what happens within the game, and any minds which exist within Life would have no way of perceiving this goal. Similarly, if physics possesses an objective morality, minds living within the universe would not be affected by it.

It is a common error, when one begins to think about morality, to suppose that the universe has a goal, and that human moral systems have already been influenced by it. Given this assumption, one might then infer that other minds could reason their way to a morality similar to that which we already possess. This is a mistake which is rooted in our species psychology. In our evolutionary past, we humans only had to deal with other humans, who shared many of our ideas about morality, so we could get away with thinking that these ideas were properties of the universe itself. They’re not.