space and games

June 5, 2006

Games with Graphs

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

This is a graph:

graph 1

This is another graph:

graph 2

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:

graph 1 (labeled)

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:

The graph for Go

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

linear 5

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.

So black lost. What could ve have done differently? How about this?

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:

Graph for Life

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.

Glider 0
Glider 1
Glider 2
Glider 3
Glider 4

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.

15 Comments »

  1. It seems Go and Life are equally amoral as “setting goals” for either game leaves the dynamics unchanged. The major difference is Go leaves the dynamics incomplete: the “board” must be coupled with a player-complex to determine its transitions.

    I can’t see how the differences between the games illuminates the fallacy of anthropomorphising the universe. Can you elaborate?

    (As an aside, it seems if black descends at 2 after the exchange B3 W4 we get the same result as black opening at 3. When formalising Go I like these http://brooklyngoclub.org/jc/rulesgo.html rules for reasons of simplicity in defining winning conditions.)

    Comment by Nick Hay — June 7, 2006 @ 9:22 pm

  2. I like this! A very concise way of putting it.

    Comment by EliezerYudkowsky — June 8, 2006 @ 7:56 pm

  3. Nick: In the actual universe, the players can perceive the description of Go, which includes a goal. So really the goal is not a rule of the game, but a label attached to the game. Go is not “closed” in the way that Life is, so labels matter.

    Life is closed, so whatever label we attach to it has no way of affecting the internal structure of Life. AFAICT, the universe appears to be closed, so in this way it is more like Life than Go.

    Alternatively, the rules of Go could specify precisely how the players think (e.g. minimax search). Then the goal could be passed as an argument to the players. It would be hard (ie, requires lots of complexity) to implement agents like this within the universe, at least if you wanted them to look like they belong in the universe and have comprehensible goals.

    (You’re right, black can open on either 2, 3, or 4 and still get a drawn game. The mathematical rules of Go are nice, but I prefer to allow suicide.)

    Comment by Peter de Blanc — June 8, 2006 @ 8:20 pm

  4. Nick: Also, I’m adding a link to your research blog.

    Comment by Peter de Blanc — June 8, 2006 @ 8:25 pm

  5. Hmm, there’s something I’m missing. Perhaps I’m splitting hairs.

    If we view things from the outside, as games implemented in our universe, both Life and Go can have goals. In Life the initial state can be chosen to implement a goal (e.g. maximise gliders, maximise alive cells) embedded in the description of the game. Just as the players in a Go game can be designed to implement a goal (e.g. to win, to lose, to have a game of even length, to maximise the number of alive groups). With Go there is a standard goal associated with it, but that doesn’t seem significant.

    Life maps much more nicely to the dynamical systems we see in physics: set the initial state (perhaps) and the dynamics’ll do the rest. With Go we have an incomplete system which doesn’t quite map so nicely. (Unless one considers the sequence of player moves, or the pair of players, as the initial state.)

    Viewing things from the inside, as universes themselves… Life works but Go doesn’t seem to. Typical Go players aren’t implemented as Go shapes. I can’t work out how to compare the two from this perspective.

    I don’t understand “the rules of Go could specify precisely how the players think” paragraph. What do you mean by passing a goal to a player? Are we implementing them in our universe, or a Go-universe? If we specify exactly how they think, what degrees of freedom are left?

    (Lack of suicide is my major gripe with the mathematical rules. Have likewise linked you.)

    Comment by Nick Hay — June 8, 2006 @ 9:45 pm

  6. Nitpick: the goal of Go is not to have more stones. The goal of Go is to have more territory. (And in the first example, White should have passed as soon as Black did – playing the center stone reduced White’s points, as it ate up a point of its own territory.)

    Other than that, nice write-up. :)

    Comment by Kaj Sotala — June 10, 2006 @ 11:52 am

  7. Nitpick: one can score by counting the number of stones on the board. This is equivalent to standard scoring (either by territory or area) except you are penalised for each separate live group you have. See http://senseis.xmp.net/?StoneScoring .

    Comment by Nick Hay — June 10, 2006 @ 2:44 pm

  8. Nitpick: Hmm, interesting. Okay. (That’s a nonstandard scoring method, though, so it might be good to note that in the main article.)

    Comment by Kaj Sotala — June 10, 2006 @ 5:39 pm

  9. I don’t think it’s nonstandard. :-)

    Comment by Peter de Blanc — June 11, 2006 @ 6:28 pm

  10. Nick: Of course, it really only makes sense to speak of agents, and not games (or universes), having goals. The point of this article was to show why it doesn’t make sense to think of the universe as having a goal.

    If we specify exactly how the players think, then there are no degrees of freedom left. That’s kinda the point. If we wanted to make rules of Go that determine the course of the game deterministically (as the rules of Life do), then we need to define exactly what the players do. One way to do that would be to say that the players use a minimax algorithm, and try to maximize their score as we defined it above. If you defined Go this way, then you could say that human Go players aren’t *really* playing Go, only approximating it.

    Comment by Peter de Blanc — June 11, 2006 @ 6:43 pm

  11. I don’t understand “the rules of Go could specify precisely how the players think” paragraph. What do you mean by passing a goal to a player? Are we implementing them in our universe, or a Go-universe? If we specify exactly how they think, what degrees of freedom are left?

    I think Nick means that, hypothetically, the rules of Go could include exact and deterministic rules governing how the players played the game, which would be anologous to the rules governing state transitions in Life, and this would make the two “games” quite similar.

    Comment by pdf23ds — June 15, 2006 @ 6:21 pm

  12. I see one significant difference between Go and Life as outlined here. You’ve set up Life on an infinite board, while Go has a finite territory. If Go also had an infinite board, then the win or end state, what you are calling the goal of the game, would become moot, that is unachievable.

    Can Go be played as a game with an infinite board? (By game, I mean something with an end state or win condition.)

    Comment by Carolyn L Burke — July 14, 2006 @ 8:48 am

  13. You might be able to play Go on an infinite board if the value of the board were finite. A stone placed on the origin might be worth one point, and the value of a stone would decrease as you went farther from the origin. When the value of the unplayed-on part of the board drops below the difference in score between the two players, you could end the game.

    Also, you can run Life on a finite grid. Usually this is done by connecting the left and right edges together, and connecting the top and bottom edges together, forming a torus, or doughnut shape.

    Comment by Peter de Blanc — July 14, 2006 @ 3:49 pm

  14. Very Interesting post! found via StumbleUpon.
    I would be honored to write an intelligent agent to play you in a game of Go on the surface of a buckyball.
    I know this is the web, but if you had givin a talk about this in person (say at UNC Charlotte for example) I would probably beg for your autograph

    Comment by Nathan — March 12, 2009 @ 11:12 pm

  15. You can certainly see your enthusiasm in the work you write. The world hopes for even more passionate writers like you who aren’t afraid to say how they believe. Always follow your heart.

    Comment by Mario Danish — November 22, 2011 @ 7:15 am

RSS feed for comments on this post.

Leave a comment

Powered by WordPress