10 views

Skip to first unread message

Jun 5, 2003, 1:57:59 AM6/5/03

to

I've made a program which simulates "random go game",

by tweaking my Monte Carlo code of Ising model.

http://www.geocities.co.jp/SiliconValley-SanJose/9606/src/go-mc.tgz

It is for UNIX/X11. You can compile it by executing the script "go-mc/mk".

by tweaking my Monte Carlo code of Ising model.

http://www.geocities.co.jp/SiliconValley-SanJose/9606/src/go-mc.tgz

It is for UNIX/X11. You can compile it by executing the script "go-mc/mk".

The rule of Go is nicely summarized in John Baez's

"This Week's Finds in Mathematical Physics (Week 142)"

http://math.ucr.edu/home/baez/week142.html

In my simulation, the following rule is omitted for simplicity:

"First, you are not allowed to put a stone someplace where it will immediately

die, *unless* doing so immediately kills one or more of the other player's

stones - in which case their stones die, and yours lives."

By running the code, you can observe occurrence of large

"avalanches" in which a large cluster dies. It is reminiscent of

the "sand pile" model which shows self-organized criticality:

When a last grain of sand is added and the critical gradient is

exceeded, a large scale avalanche occurs.

As a result of these avalanches, the configuration becomes

very irregular shaped as shown below:

http://www.geocities.co.jp/SiliconValley-SanJose/9606/img/go2.gif

These avalanches occur when a stone is placed at the last vacant grid

inside the cluster. If you forbid these "suicidal" moves, an equilibrium

is reached. The following figure shows a resulting configuration:

http://www.geocities.co.jp/SiliconValley-SanJose/9606/img/go1.gif

You can observe that there is a typical size of clusters.

The following figure shows variance of "block spin", namely

(number of white - number of black) in a cell of LxL size,

normalized by variance of uncorrelated case (=LxL), plotted against

various L:

16 ++-------+--------+-------+--------+--------+-------+A

+ + + + + + +

14 ++ A ++

| AAA |

| A A A|

12 ++ AA A A A AA ++

| A A A A AA A |

10 ++ A AAA A AAA A A A A ++

| A A A A A AA |

| A A A A |

8 ++ AAA A A ++

| A |

6 ++ A ++

| A |

| A |

4 ++ A ++

| |

2 ++ A ++

| A |

+ + + + + + +

0 ++-------+--------+-------+--------+--------+-------++

0 10 20 30 40 50 60

It can be seen that it saturates at around L=20, indicating that

the typical linear size of clusters is around 20. This result is

striking if you remember that the game of go is played on a 19X19 grids board.

This finiteness of cluster size is partly because that the critical

concentration of site-percolation on a square lattice is approximately

58%, slightly above 50%.

If you played Go game on a cubic lattice, the critical concentration of

site-percolation is around 30%, so the domain of each player "percolates".

The resulting configuration will be two intersecting large clusters

with huge genus number, which seems less attractive than the 2D case.

--

Mitsuhiro Itakura, Tokyo, Japan

http://arXiv.org/find/cond-mat/1/au:+Itakura_M/0/1/0/all/0/1

Jun 6, 2003, 2:41:40 AM6/6/03

to

Mitsuhiro Itakura wrote:

> I've made a program which simulates "random go game",

> by tweaking my Monte Carlo code of Ising model.

> http://www.geocities.co.jp/SiliconValley-SanJose/9606/src/go-mc.tgz

> It is for UNIX/X11. You can compile it by executing the script "go-mc/mk".

> I've made a program which simulates "random go game",

> by tweaking my Monte Carlo code of Ising model.

> http://www.geocities.co.jp/SiliconValley-SanJose/9606/src/go-mc.tgz

> It is for UNIX/X11. You can compile it by executing the script "go-mc/mk".

This is an interesting process. Even looking at the time history of a

single point, no finite size board gives the same behavior as an infinite

board.

On an infinite board each point changes color infinitely many times

(prove?), but I don't think there is a equilibrium distribution of waiting

times. The changes become infinitely clustered, and the clusters get

infinitely rare. A fractal hierarchy with no top level.

I think 2 dimensions is special for Go. In 1D the it takes a constant

number (2) of stones to kill a group, so the behavior should converge to a

simple (statistical) equilibrium fairly quickly.

In 3D it is easier to "connect" and harder to "cut". There will be infinite

groups of both colors, which can never die. Eventually empty spaces become

infinitely rare, but stones almost never die, so a given region becomes static.

> In my simulation, the following rule is omitted for simplicity:

> "First, you are not allowed to put a stone someplace where it will immediately

> die, *unless* doing so immediately kills one or more of the other player's

> stones - in which case their stones die, and yours lives."

I don't think your (disabled) implementation of that rule is correct. It

appears to forbid moves in which the connected component of vacant points

connects to points of only one color (i.e. only moves into "disputed

territory" are allowed). The correct rule is that the point not be

connected to a vacant point by stones of the player's color, unless at

least one adjacent stone of the other color is not connected to any other

vacant point.

Perhaps, after disabling the rule you tried a different rule?

It is true that, with the normal rule, a static equilibrium is reached.

Once a group gets two eyes it can never be removed, so eventually all the

legal moves are used up.

Ralph Hartley

Jun 8, 2003, 2:43:54 AM6/8/03

to

Ralph Hartley <har...@aic.nrl.navy.mil> wrote

> Mitsuhiro Itakura wrote:

> > In my simulation, the following rule is omitted for simplicity:

> > [...]

> Mitsuhiro Itakura wrote:

> > In my simulation, the following rule is omitted for simplicity:

As I understand it he allows suicide, as eg. in the SST Go ruleset.

This is in contrast to the the japanese Go rules.

> It is true that, with the normal rule, a static equilibrium is reached.

No, not true. A purely random player eventually fills in his own eyes,

killing unconditionally alive groups.

Volker

Jun 8, 2003, 2:44:04 AM6/8/03

to

Ralph Hartley wrote:

> It is true that, with the normal rule, a static equilibrium is reached.

> Once a group gets two eyes it can never be removed, so eventually all the

> legal moves are used up.

> It is true that, with the normal rule, a static equilibrium is reached.

> Once a group gets two eyes it can never be removed, so eventually all the

> legal moves are used up.

Oops! In the real game, a group with two eyes can never be removed, but

with random players they can. The owner can fill one of the eyes himself.

Ralph Hartley

Jun 16, 2003, 5:37:50 PM6/16/03

to

Ralph Hartley <har...@aic.nrl.navy.mil> wrote in message news:<3EDF6DFB...@aic.nrl.navy.mil>...

> On an infinite board each point changes color infinitely many times

> (prove?), but I don't think there is a equilibrium distribution of waiting

> times. The changes become infinitely clustered, and the clusters get

> infinitely rare. A fractal hierarchy with no top level.

Probably the fractal shape is characterized by a non-trivial

Hausdorff exponent. But I couldn't measure it because

the system is not equilibriated and I can't take the time average.

> I don't think your (disabled) implementation of that rule is correct. It

> appears to forbid moves in which the connected component of vacant points

> connects to points of only one color (i.e. only moves into "disputed

> territory" are allowed). The correct rule is that the point not be

> connected to a vacant point by stones of the player's color, unless at

> least one adjacent stone of the other color is not connected to any other

> vacant point.

>

> Perhaps, after disabling the rule you tried a different rule?

Well, to tell the truth, I made this program to understand the rules

of Go myself :-) I'm not a player of Go.

I knew the rules but I wasn't sure whether

the territory is well defined, and wanted to see what happens

when a territory is formed inside the opponent's territory, etc.

I'll code the correct rule after understanding the rule and

the basic strategy completely.

--

Mitsuhiro Itakura, Tokyo, Japan

http://arXiv.org/find/cond-mat/1/au:+Itakura_M/0/1/0/all/0/1

[spelling enhanced by s.p.r moderator]

Jun 19, 2003, 3:26:25 AM6/19/03

to Mitsuhiro Itakura

Mitsuhiro Itakura wrote:

> Probably the fractal shape is characterized by a non-trivial

> Hausdorff exponent. But I couldn't measure it because

> the system is not equilibriated and I can't take the time average.

On an infinite board there isn't even a well defined equilibrium, and time

averages may diverge, so it is tricky.

> Well, to tell the truth, I made this program to understand the rules

> of Go myself :-) I'm not a player of Go.

> I knew the rules but I wasn't sure whether

> the territory is well defined, and wanted to see what happens

> when a territory is formed inside the opponent's territory, etc.

> I'll code the correct rule after understanding the rule and

> the basic strategy completely.

I took the liberty of playing with your program a bit. My version is at:

http://www.aic.nrl.navy.mil/~hartley/go.tar.gz

It has an option to implement the suicide rule (which has no qualitative

effect).

It permits multiple players (which appears to lower the fractal dimension).

I was interested in what would happen in 3D with more players. With two

players they would both build an infinite group, but with more players

connections are harder to make.

It turns out that *all* the players make (incipient) infinite groups (after

some losses), so 3D is boring even with many (at least up to 8) players.

The topology of the board was changed to a torus to eliminate edge effects.

Also, it runs much faster.

Ralph Hartley

Jun 26, 2003, 2:43:18 PM6/26/03

to

Ralph Hartley <har...@aic.nrl.navy.mil> wrote in message

news:<3EEF300...@aic.nrl.navy.mil>...> I took the liberty of playing with your program a bit. My version is at:

>

> http://www.aic.nrl.navy.mil/~hartley/go.tar.gz

>

> It has an option to implement the suicide rule (which has no qualitative

> effect).

Thank you very much for cleaning my messy code.

> It permits multiple players (which appears to lower the fractal

> dimension).

>

> I was interested in what would happen in 3D with more players. With two

> players they would both build an infinite group, but with more players

> connections are harder to make.

>

> It turns out that *all* the players make (incipient) infinite groups

> (after some losses), so 3D is boring even with many (at least up to

> 8) players.

I added a code which forbid placing a stone on one's own "eye".

/************************/

int an_eye(int p, unsigned char my_color) {

int j,q;

unsigned char s0 = spin[p];

if (s0) return(0);

for (j=0;j<NBDSIZE;j++) {

q = nbr(p,j);

if (spin[q] != my_color) return(0);

}

return 1;

}

Then an equilibrium is reached, except some blinking dots

which is "Kou".

Since the percolation threshold of cubic lattice is approximately 0.3,

4 players seems to be a modest number in 3D.

But in the actual game, the mini-max theory breaks down owing to

cooperation/alliance/betrayal between players, so I don't have

a slightest idea what it will be like when actually played.

> The topology of the board was changed to a torus to eliminate edge

> effects. Also, it runs much faster.

Fast indeed! It's called "screw boundary condition" in my field,

since the torus is slightly twisted when each end is connected.

--

Mitsuhiro Itakura, Tokyo m-it...@geocities.no-spam.co.jp

http://arXiv.org/find/cond-mat/1/au:+Itakura_M/0/1/0/all/0/1

Jun 27, 2003, 1:17:17 PM6/27/03

to smi1...@innerx.com, har...@aic.nrl.navy.mil, i...@zangband.org, i...@turin.koma.jaeri.go.jp, volker...@physik.hu-berlin.de

My main comment is that a cubic lattice might not be the most natural

higher-dimensional generalization of the 2-D Go board, and that

diamond-type lattices (actually technically maybe not lattices, but,

as Conway and Sloane say, a 3-D diamond configuration is a packing

rather than a lattice, but often I abuse language and call it a

lattice anyway) may be the most natural generalization, particularly

since in dimensions 1, 2, 4, and 8 they are related to the "integral"

(again an abuse of language) versions of division algebras.

higher-dimensional generalization of the 2-D Go board, and that

diamond-type lattices (actually technically maybe not lattices, but,

as Conway and Sloane say, a 3-D diamond configuration is a packing

rather than a lattice, but often I abuse language and call it a

lattice anyway) may be the most natural generalization, particularly

since in dimensions 1, 2, 4, and 8 they are related to the "integral"

(again an abuse of language) versions of division algebras.

Here are some pictures by Ishihama Yoshiaki of some 3-D Go "boards"

http://www.asahi-net.or.jp/~hq8y-ishm/3dgo/3dgo.html

and a web page with links to some (Macintosh) 3-D Go programs

http://www.asahi-net.or.jp/~hq8y-ishm/game.html

and here is a web page about diamond Go

http://www.nrinstruments.demon.co.uk/diamond/diamintro.html

and here is a page with a .exe type 3-D Go program

http://www.nrinstruments.demon.co.uk/diamond/diamprog.html

I would like to see, but have not seen, 4-D and 8-D programs

with hyperdiamond boards, since I think they may be related

to generalized Feynman checkerboards and spin networks.

One more comment is that I prefer the Chinese name Wei-Qi,

but I realize that the Japanese term Go is more prevalent

in Euro/American circles (and Japan). (In Korea, it is Baduk.)

Tony 27 June 2003

Jul 14, 2003, 5:01:57 PM7/14/03

to sci-physic...@moderators.isc.org

Tony Smith wrote:

> My main comment is that a cubic lattice might not be the most natural

> higher-dimensional generalization of the 2-D Go board, and that

Be that as it may, I wouldn't expect the qualatative behavior of random go

to change. Critical phenomena tend to have "universal" properties that

depend on the dimension but not on local details.

Also, I have now tried it. The Diamond board doesn't make much difference.

Ralph Hartley

Jul 31, 2003, 2:58:44 AM7/31/03

to sci-physic...@moderators.isc.org

Ralph Hartley <har...@aic.nrl.navy.mil> wrote in message news:<bdvco2$798$1...@ra.nrl.navy.mil>...

Actually, diamond lattice can be regarded as a 3D version

of honeycomb lattice, in a sense that it has the smallest

coordination number (=D+1) among D-dimensional lattices.

Thus the sparsity of links may make visualization easy

and lower the percolation threshold (easy to cut,

difficult to connect).

BTW I tried 10-players case in 3D, forbidding suicidal move

and found that the resulting territories of all the players

"percolate" and have a volume about L^3/10, which is

far below the percolation threshold ~0.3*L^3. This indicates

that the percolation threshold is irrelevant in 3D.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu