SOC of "Go game"
Mitsuhiro Itakura
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
Ralph Hartley
> 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
Volker Braun
> 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
Ralph Hartley
> 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
Mitsuhiro Itakura
> 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]
Ralph Hartley
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
Mitsuhiro Itakura
> 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
Tony Smith
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
Ralph Hartley
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
Mitsuhiro Itakura
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.