Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

number of 2*2 games

342 views
Skip to first unread message

John Tromp

unread,
Jun 24, 1999, 3:00:00 AM6/24/99
to
dear go/math friends,

After computing for a bit, I think I have determined the number of
games on 2*2 with positional superko as

386,356,909,593. ( = 3*4651*27689881)

That's over 4 times Bill Gates' net worth:-!
(see http://www.templetons.com/brad/billg.html)

Independent verification is most welcome.

Note that suicide is not an issue, as the only suicides possible
on 2*2 are of a single stone or of 4 stones, and thus already
prohibited by positional superko.

With situational superko, things become much hairier, as one then
has to count paths in a graph with 2*57 nodes, and each node may be
visited twice (once from a pass and once from a real move).

Also, suicide becomes an issue, as Robert Jasiek has pointed out.
In a position like

@ .
. @ ,

is a game where white suicides at A1 different from the game where
she suicides at B2? Should they both be considered a pass? I guess
not since passes are allowed to repeat a situation while moves are not.

In any case, it will be possible for black to suicide 4 stones and return
to the empty board with white to move...

I expect a 20+ digit number for situational superko, so if you even
have to spend 1 cycle on each game, it will take forever to compute.


regards,


%!PS % -John Tromp (http://www.cwi.nl/~tromp/)
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage

Robert Jasiek

unread,
Jun 24, 1999, 3:00:00 AM6/24/99
to
John Tromp wrote:
> After computing for a bit, I think I have determined the number of
> games on 2*2 with positional superko as
> 386,356,909,593. ( = 3*4651*27689881)

> Independent verification is most welcome.

If you provide reference to proof structure and source code, then
I might see whether a formal verification of your calculation can
be done within in reasonable time.

--
robert jasiek
http://www.snafu.de/~jasiek/rules.html


Eric Osman

unread,
Jun 25, 1999, 3:00:00 AM6/25/99
to

I'm truly astounded that the number of 2x2 go games can be in the
billions as you say.

How does it get that large ?

Robert Jasiek

unread,
Jun 26, 1999, 3:00:00 AM6/26/99
to

Please do a search at www.dejanews.com for
<2x2> AND <robert jasiek> AND <rec.games.go>.

A simple upper boundary is 4^3^4 = 5.84600655 * 10^48.
Please see the <Rules FAQ> for construction of this number.

Eric Osman

unread,
Jun 28, 1999, 3:00:00 AM6/28/99
to

> Please do a search at www.dejanews.com for
> <2x2> AND <robert jasiek> AND <rec.games.go>.
>

I just did and it only found the ABOVE !

Was I supposed to type the angle brackets as is ? (I copied-pasted from

the above actually.


Perhaps rather than sending me around, you could say just a few
sentences as to how
the number of 2x2 go games can be in the billions. Perhaps you're
counting trivial things like
if we each pass a billion times ? /Eric


Robert Jasiek

unread,
Jun 28, 1999, 3:00:00 AM6/28/99
to
Eric Osman wrote:
> > Please do a search at www.dejanews.com for
> > <2x2> AND <robert jasiek> AND <rec.games.go>.

> I just did and it only found the ABOVE !

What proves dejanews to have a very powerful search machine;
however, for years the number of my articles is shown as a
constant 2200, which must be dejanews' upper limit:)

> Was I supposed to type the angle brackets as is ?

You are supposed to recognize my meta-language as such and
interpret it properly:(

<> are meta-symbols enclosing search contents,
AND means to search for left and right sides,
titles shall be part of real titles,
names have to be entered as names,
newsgroups have to be entered as newsgroups,
IOW, you have to use some advanced search facility of the engine.

> Perhaps rather than sending me around, you could say just a few
> sentences as to how
> the number of 2x2 go games can be in the billions.

I have given you an upper bound 4^3^4, which is much greater than
billions, whichever semantics this word might have:) My other
smaller upper bounds for 2x2 are included below: they only give
numbers of cyclical choices, so numbers of games are a little
greater. For positional superko I gave 2^24 * 4^4 < 4.3 * 10^9
for the cyclical choices, so JT's result is not too unreasonable:)

--
robert jasiek
http://www.snafu.de/~jasiek/


Subject:
2x2 News
Date:
Mon, 15 Feb 1999 19:18:33 +0100
From:
Robert Jasiek <jas...@berlin.snafu.de>
Newsgroups:
rec.games.go


(problem: perfect 2x2 play, suicide/PSK/2-pass/area)

The compressed Taylor-graph has 48 situations,
64 plays, 40 passes.

The relevant situation classes for every colour are:

XX
.. (only relevant for other colour to move)

X.
.O (most complex with out-degree 3)

XX
O.

Only occuring in intervening situations:

X.
..

XX
X.

Currently, my graph looks like a child's painting, so
I cannot draw further conclusions yet:)

However, if I am not mistaken, the complexity of the
cyclical decisions is restricted to 2^40 * 3^8 < 10^16,
which is an improvement... A computer could have
trouble with it. Maybe more sophistication is possible.
Otherwise 2x2 might well be the smallest problem that
a human cannot solve!

I guess, 3x3 is easier...


Subject:
Re: 2x2 go AGAIN!
Date:
Fri, 26 Feb 1999 23:15:32 +0100
From:
Robert Jasiek <jas...@berlin.snafu.de>
Newsgroups:
rec.games.go
References:
1 , 2 , 3 , 4 , 5


Robert Jasiek wrote:
> The compressed Taylor-graph has 48 situations,
> 64 plays, 40 passes. The complexity of the cyclical decisions
> in the graph is restricted to 2^40 * 3^8 < 10^16.

This is a too rough estimate, which is valid for situational
superko. For positional superko, AFAICS, the number is a
little smaller: 2^24 * 4^4 < 4.3 * 10^9. [I have evaluated the
outdegrees of the positions in the Taylor-graph. Correct?] Now I
understand why Felix von Arnim was so confident while telling
me that he calculated perfect play with a program. So now we
have a structure for a proof and a myth that a proof has been
performed. I still wonder what perfect play under the given
rules is:)

--
robert jasiek


Subject:
Re: 2x2 go AGAIN!
Date:
Fri, 26 Feb 1999 22:37:01 +0100
From:
Robert Jasiek <jas...@berlin.snafu.de>
Newsgroups:
rec.games.go
References:
1 , 2 , 3 , 4


Scot McDermid wrote:
> >suicide, 2-pass game end, area scoring, positional superko.
[...]
> Okay... maybe I do not understand all of the rules you are talking about.

Surely you understand suicide, 2-pass game end, and area scoring.
Positional superko means: A board play may not recreate a position.

> On a 2x2 board [...]
> black plays (guess what) a corner!

You miss the possibility of a black pass.

> So the game could
> (1) end with black as the winner or
> (2) end in seki or

The game could end with one score of -4, -1, 0, 1, 4.

> (3) go on forever with no one ever winning.

With superko this is impossible.

> Show me how this is non-trivial.

One has to consider single moves that are passes. The following
speaks about consequences.

The compressed Taylor-graph has 48 situations,
64 plays, 40 passes. The complexity of the cyclical decisions
in the graph is restricted to 2^40 * 3^8 < 10^16. This is why
I call the problem non-trivial:) If you could further reduce
the graph, fine. However, until then we face the extraordinarily
high complexity of the problem.

Notes:

A _directed graph_ consists of nodes and arrows between them.

A _Taylor-graph_ is a graph where each node represents a position,
each arrow represents a move, and each arrow is in a cycle.

The term Taylor-graph has been introduced by me in 1997 for the
honour of Bill Taylor who appearently used the concept first.
Situations instead of positions can be used, so that the right to
move is distinguished. This is suitable here. A move is either a
play or a pass. A situation has its induced Taylor-graph due to the
rules; one just writes down all arrows of a game tree by using the
same node for the same position in a mapping and then cancelling all
arrows outside any cycle.

A Taylor-graph is _compressed_ if all nodes without branch are omitted
and if meaningless parallel arrows are contracted.

Meaningless parallel arrows do not occur here, however, several nodes
can be omitted.

***

I have attached a DOC file with the positions and the Taylor-graph.
A few remarks are included. The game is possibly supposed to start

.. X. X.
.. .. .O

You can try to follow the arrows in the Taylor-graph, mark visited
positions, and draw proper conclusions. Thereby you get a chance to
solve the problem first. You may also use a computer, if necessary.
Have fun!

0 new messages