The Number of Legal 19x19 Positions is...

[Robert Jasiek]

...solved by John Tromp et al here:

http://tromp.github.io/go/legal.html

I leave it to him to celebrate his result by explicitly stating the
number of 171 digits here, if he likes.

Congratulations!

This belongs to the problems of go theory for which the most research
time and effort must have been invested. I recall early talks about
the problem here during the late 1990s. Since then he has studied the
problem.

[rt]

Post by Robert Jasiek
http://tromp.github.io/go/legal.html
I leave it to him to celebrate his result by explicitly stating the
number of 171 digits here, if he likes.
Congratulations!
This belongs to the problems of go theory for which the most research
time and effort must have been invested. I recall early talks about
the problem here during the late 1990s. Since then he has studied the
problem.

That page states for a 2x2 board

"Few people believe that a tiny 2x2 Go board allows for more than a
few hundred games. Yet 2x2 games number not in the hundreds, nor in
the thousands, nor even in the millions. They number in the hundreds
of billions!"

whereas here I find

http://senseis.xmp.net/?PositionsAndGamesOn2x2

"On a 2x2 board, there are 3^4 = 81 possible positions:

Of these, there are 16 that have 4 stones and are illegal, and another
8 that have three stones and are illegal, which leaves 57 that are
legal. The illegal positions have been crossed out.

This gives an overal percentage of 70% for valid positions, on bigger
boards this percentage is much lower. "

57 and 81 are quite smaller than "hundreds of billions" ...

[Robert Jasiek]

games [...] They number in the hundreds of billions!
[...]
positions: [...] 57

Read again what you have cited.

[rt]

Post by Robert Jasiek

games [...] They number in the hundreds of billions!
[...]
positions: [...] 57

Read again what you have cited.

"Few people believe that a tiny 2x2 Go board allows for more than a
few hundred games. Yet 2x2 games number not in the hundreds, nor in
the thousands, nor even in the millions. They number in the hundreds
of billions!"

whereas here I find

http://senseis.xmp.net/?PositionsAndGamesOn2x2

"On a 2x2 board, there are 3^4 = 81 possible positions:

Of these, there are 16 that have 4 stones and are illegal, and another
8 that have three stones and are illegal, which leaves 57 that are
legal. The illegal positions have been crossed out.

This gives an overal percentage of 70% for valid positions, on bigger
boards this percentage is much lower. "

Ok, and?

[Robert Jasiek]

"positions" is something else than "games", so their numbers differ.

It is like putting three cards in front of you, label them Position 1,
Position 2, Position 3. Now find out in how many orders you can draw
the cards; this is your number of games. The more cards, the faster
the number of games explodes. Use your pocket calculator's factorial
key "!" for the cards metaphor.

[Jonas Klein]

Post by rt

Post by Robert Jasiek
http://tromp.github.io/go/legal.html
I leave it to him to celebrate his result by explicitly stating the
number of 171 digits here, if he likes.
Congratulations!
This belongs to the problems of go theory for which the most research
time and effort must have been invested. I recall early talks about
the problem here during the late 1990s. Since then he has studied the
problem.

That page states for a 2x2 board
"Few people believe that a tiny 2x2 Go board allows for more than a
few hundred games. Yet 2x2 games number not in the hundreds, nor in
the thousands, nor even in the millions. They number in the hundreds
of billions!"
whereas here I find
http://senseis.xmp.net/?PositionsAndGamesOn2x2
Of these, there are 16 that have 4 stones and are illegal, and another
8 that have three stones and are illegal, which leaves 57 that are
legal. The illegal positions have been crossed out.
This gives an overal percentage of 70% for valid positions, on bigger
boards this percentage is much lower. "
57 and 81 are quite smaller than "hundreds of billions" ...

Just in case you don't understand Robert's answer, the
number of possible POSITIONS is obviously much lower than
the number of possible GAMES.
There are many different ways to a certain position. All
paths lead to Rome. :-)

[Detlef Müller]

Post by rt

Post by Robert Jasiek
http://tromp.github.io/go/legal.html

[...]
[Games on the 2x2-Board]

Post by rt
"Few people believe that a tiny 2x2 Go board allows for more than a
few hundred games. Yet 2x2 games number not in the hundreds, nor in
the thousands, nor even in the millions. They number in the hundreds
of billions!"

Where the explicit Number 386356909593 ist given.

[...]

Post by rt
http://senseis.xmp.net/?PositionsAndGamesOn2x2
[...] , which leaves 57 that are legal.

furthermore the positions (o for white, # for black)

o .
. o

cannot be reached in a game without passing. Further
no Position with one single white Stone can be reached
(as the empty board is forbidden by superko).

Post by rt
57 and 81 are quite smaller than "hundreds of billions" ...

Well, the difference was pointet out, but the number
386356909593 of games seems astonishing big to me too,
as The Game-Tree has not too much branches.

Remove one field and we get the 1x3 - board, where I only
see the following 5 games (no passing, sit. superko):

... -> .#.
... -> #.. -> .o.
... -> #.. -> #.o -> ##. -> ..o -> .#.
... -> ..# -> .o.
... -> ..# -> o.# -> .## -> o.. -> .#.

I am tempted to write a back-tracking to convince
myself that there are really more than a view million games on
2x2 since 2^20 is a bit more than one million and most games
seem to end long before move 20 and 2 moves or even only 1 possible
move seem more often than 3 alternatives.

Greetings,
Detlef

[Robert Jasiek]

there are really more than a view million games on 2x2

Many years ago, I made a preliminary study on the number and it did
become quite large. The actual order of magnitude is in the range I
anticipated.

[Detlef Müller]

Post by Robert Jasiek

there are really more than a view million games on 2x2

Many years ago, I made a preliminary study on the number and it did
become quite large. The actual order of magnitude is in the range I
anticipated.

Ok, maybe i underestimate the length of the games ...
I wrote a program listing the Games starting at 1,1 with
length 7 Moves, until move 7.
There exist only 10 pathes, and only 4 of them without ending the
Game, the others ending with dead ends:
Positions are noted line-wise (first line, second line),
"|" means end of game, "-->" means game continues:

1 2 3 4 5 6 7 (Move Nr.)
#... #o.. #0#. .o.o #o.o .ooo|

.o#o oo.o ..#. -->

#..#|

#.o. ##o. ..oo #.oo .ooo|

.#oo o.oo .#.. -->

#..#|

#..o ##.o ..oo #.oo .ooo|

.#oo o.oo .#.. -->

#.#o .o.o #o.o .ooo|

.o#o oo.o ..#. -->

So after multiples of 7 moves there will be one single black stone
on the board and meanwhile there will be 6 dead end-branches at most
not even counting the loss of possibilities by super-ko.
We observe that the opposite position to the starting (here (1,1))
is not reachable.

Two pathes (with some dead ends) lead to each of the two possible
Positions 7 moves later.

#. .# ..
.. ---(7 moves)---> .. or #. (4 branches)

so in move 14 the only possible position is

..
.#
.. .#
and in move 21 only #. and .. are reached and 27 is an upper
Bound for the game-length.

I hope this far I am correct :)

greetings,
Detlef

[Detlef Müller]

Post by Detlef Müller

Post by Robert Jasiek

there are really more than a view million games on 2x2

Many years ago, I made a preliminary study on the number and it did
become quite large. The actual order of magnitude is in the range I
anticipated.

Ok, maybe i underestimate the length of the games ...

Failure in my following argumentation:
after 6 (not 7) moves positon

#.
..

changes to one of

.. .#
#. ..

so the key Numbers are 1, 7, 13, 19, 25.

my program never reaches move 25 and counts a
total of 178 games.

greetings,

Detlef

[Detlef Müller]

Post by Detlef Müller

there are really more than a view million games on 2x2

...

Post by Detlef Müller
my program never reaches move 25 and counts a
total of 178 games.

Btw: of course move 25 can never be reached, because this
is one of the positions with on single black stone - all of
them occured in the moves 1, 7, 13, 19.

I will append the 178 found games.

If anyone finds a Game not listed, let me know.

Notation is the output of the depth-first search, which means,
if a line starts with move number n it is the continuation
of the last occuring number n-1 above, example:
Line 3 starts with "9 o.## ..." so it branches from the move 8 in
the line 2.
Line 2 starts with 5 so it branches from move 4 in line 1.
Thus the Game in Line 3 completes to:
"1 #... 2 #o.. 3 #o#. 4 .o.o 5 .o#o 6 oo.o 7 ..#. 8 o.#.
9 o.## 10 oo.. 11 oo#." (End of Game because of super ko).

If the Tree is complete, there are 4*178 games on a 2x2-board.

Greetings,
Detlef

PS: Here are the Games:

1 #... 2 #o.. 3 #o#. 4 .o.o 5 #o.o 6 .ooo Game end.
5 .o#o 6 oo.o 7 ..#. 8 o.#. 9 .##. Game end.
9 o.## 10 oo.. 11 oo#. Game end.
11 oo.# 12 ooo. 13 ...# 14 o..# 15 o#.# 16 o.o. 17 o#o. 18 o.oo 19 .#..
20 o#.. 21 .##. Game end.
20 .#o. 21 ##o. 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .#o# Game end.
20 .#.o 21 ##.o 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .##. Game end.
17 o.o# Game end.
14 .o.# 15 #..# Game end.
15 .o## Game end.
14 ..o# 15 #..# Game end.
15 .#o# 16 o.o. 17 o#o. 18 o.oo 19 .#.. 20 o#.. 21 .##. Game end.
21 o#.# Game end.
20 .#o. 21 ##o. 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
20 .#.o 21 ##.o 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .##. Game end.
17 o.o# Game end.
8 .o#. 9 .o## 10 oo.. 11 oo#. Game end.
11 oo.# 12 ooo. 13 ...# 14 o..# 15 o#.# 16 o.o. 17 o#o. 18 o.oo 19 .#..
20 o#.. 21 .##. Game end.
20 .#o. 21 ##o. 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .#o# Game end.
20 .#.o 21 ##.o 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .##. Game end.
17 o.o# Game end.
15 o.## Game end.
14 .o.# 15 #..# Game end.
14 ..o# 15 #..# Game end.
15 .#o# 16 o.o. 17 o#o. 18 o.oo 19 .#.. 20 o#.. 21 .##. Game end.
21 o#.# Game end.
20 .#o. 21 ##o. 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
20 .#.o 21 ##.o 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .##. Game end.
17 o.o# Game end.
8 ..#o 9 #.#o Game end.
9 .##. Game end.
3 #..# Game end.
2 #.o. 3 ##o. 4 ..oo 5 #.oo 6 .ooo Game end.
5 .#oo 6 o.oo 7 .#.. 8 o#.. 9 .##. Game end.
9 o#.# 10 o.o. 11 o#o. Game end.
11 o.o# 12 ooo. 13 ...# 14 o..# 15 o.## 16 oo.. 17 oo#. 18 oo.o 19 ..#.
20 o.#. 21 .##. Game end.
20 .o#. 21 #o#. 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .o## Game end.
20 ..#o 21 #.#o 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .##. Game end.
17 oo.# Game end.
14 .o.# 15 #..# Game end.
15 .o## 16 oo.. 17 oo#. 18 oo.o 19 ..#. 20 o.#. 21 .##. Game end.
21 o.## Game end.
20 .o#. 21 #o#. 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
20 ..#o 21 #.#o 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .##. Game end.
17 oo.# Game end.
14 ..o# 15 #..# Game end.
15 .#o# Game end.
8 .#o. 9 .#o# 10 o.o. 11 o#o. Game end.
11 o.o# 12 ooo. 13 ...# 14 o..# 15 o#.# Game end.
15 o.## 16 oo.. 17 oo#. 18 oo.o 19 ..#. 20 o.#. 21 .##. Game end.
20 .o#. 21 #o#. 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .o## Game end.
20 ..#o 21 #.#o 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .##. Game end.
17 oo.# Game end.
14 .o.# 15 #..# Game end.
15 .o## 16 oo.. 17 oo#. 18 oo.o 19 ..#. 20 o.#. 21 .##. Game end.
21 o.## Game end.
20 .o#. 21 #o#. 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
20 ..#o 21 #.#o 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .##. Game end.
17 oo.# Game end.
14 ..o# 15 #..# Game end.
8 .#.o 9 ##.o Game end.
9 .##. Game end.
3 #..# Game end.
2 #..o 3 ##.o 4 ..oo 5 #.oo 6 .ooo Game end.
5 .#oo 6 o.oo 7 .#.. 8 o#.. 9 .##. Game end.
9 o#.# 10 o.o. 11 o#o. Game end.
11 o.o# 12 ooo. 13 ...# 14 o..# 15 o.## 16 oo.. 17 oo#. 18 oo.o 19 ..#.
20 o.#. 21 .##. Game end.
20 .o#. 21 #o#. 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .o## Game end.
20 ..#o 21 #.#o 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .##. Game end.
17 oo.# Game end.
14 .o.# 15 #..# Game end.
15 .o## 16 oo.. 17 oo#. 18 oo.o 19 ..#. 20 o.#. 21 .##. Game end.
21 o.## Game end.
20 .o#. 21 #o#. 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
20 ..#o 21 #.#o 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .##. Game end.
17 oo.# Game end.
14 ..o# 15 #..# Game end.
15 .#o# Game end.
8 .#o. 9 ##o. Game end.
9 .#o# 10 o.o. 11 o#o. Game end.
11 o.o# 12 ooo. 13 ...# 14 o..# 15 o#.# Game end.
15 o.## 16 oo.. 17 oo#. 18 oo.o 19 ..#. 20 o.#. 21 .##. Game end.
20 .o#. 21 #o#. 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .o## Game end.
20 ..#o 21 #.#o 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .##. Game end.
17 oo.# Game end.
14 .o.# 15 #..# Game end.
15 .o## 16 oo.. 17 oo#. 18 oo.o 19 ..#. 20 o.#. 21 .##. Game end.
21 o.## Game end.
20 .o#. 21 #o#. 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
20 ..#o 21 #.#o 22 .o.o 23 #o.o 24 .ooo Game end.
23 .o#o Game end.
21 .##. Game end.
17 oo.# Game end.
14 ..o# 15 #..# Game end.
8 .#.o 9 .##. Game end.
3 #.#o 4 .o.o 5 #o.o 6 .ooo Game end.
5 .o#o 6 oo.o 7 ..#. 8 o.#. 9 .##. Game end.
9 o.## 10 oo.. 11 oo#. Game end.
11 oo.# 12 ooo. 13 ...# 14 o..# 15 o#.# 16 o.o. 17 o#o. 18 o.oo 19 .#..
20 o#.. 21 .##. Game end.
20 .#o. 21 ##o. 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .#o# Game end.
20 .#.o 21 ##.o 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .##. Game end.
17 o.o# Game end.
14 .o.# 15 #..# Game end.
15 .o## Game end.
14 ..o# 15 #..# Game end.
15 .#o# 16 o.o. 17 o#o. 18 o.oo 19 .#.. 20 o#.. 21 .##. Game end.
21 o#.# Game end.
20 .#o. 21 ##o. 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
20 .#.o 21 ##.o 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .##. Game end.
17 o.o# Game end.
8 .o#. 9 #o#. Game end.
9 .o## 10 oo.. 11 oo#. Game end.
11 oo.# 12 ooo. 13 ...# 14 o..# 15 o#.# 16 o.o. 17 o#o. 18 o.oo 19 .#..
20 o#.. 21 .##. Game end.
20 .#o. 21 ##o. 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .#o# Game end.
20 .#.o 21 ##.o 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .##. Game end.
17 o.o# Game end.
15 o.## Game end.
14 .o.# 15 #..# Game end.
14 ..o# 15 #..# Game end.
15 .#o# 16 o.o. 17 o#o. 18 o.oo 19 .#.. 20 o#.. 21 .##. Game end.
21 o#.# Game end.
20 .#o. 21 ##o. 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
20 .#.o 21 ##.o 22 ..oo 23 #.oo 24 .ooo Game end.
23 .#oo Game end.
21 .##. Game end.
17 o.o# Game end.
8 ..#o 9 .##. Game end.
178

[Robert Jasiek]

I lack time to check your study, but maybe it helps to point out what
John Tromp writes today on the mailing-list computer go under area
scoring, positional superko:

"Finding the maximum length of a Go game, if we measure length
by number of (non-pass) moves, is equivalent to finding the longest
simple path in the game graph.

For 2x2 this can easily be brute forced, and one finds a maximum
length of 48 moves (so a single game can visit at most 49 of the 57
legal positions)."

Now, introduce (single) passes.

[Detlef Müller]

Post by Robert Jasiek
I lack time to check your study,

np (don't feel urged to anwer me).
The given output is rather ugly, I convinced python to
create a nice tree, its a 70k pdf-file (big, but manageable).

Post by Robert Jasiek
but maybe it helps to point out what
John Tromp writes today on the mailing-list computer go under area
"Finding the maximum length of a Go game, if we measure length
by number of (non-pass) moves, is equivalent to finding the longest
simple path in the game graph.
For 2x2 this can easily be brute forced, and one finds a maximum
length of 48 moves (so a single game can visit at most 49 of the 57
legal positions)."

Well - this is not possible when no passes are allowed at all,
because every 6 moves there is one single black Stone on the
board (and there are obviously only 4 such positions).
As my time is limited too, I better will not join to another
mailing-list ... theese investigations are interesting, but
not very lucrative :)

Post by Robert Jasiek
Now, introduce (single) passes.

I guess then the tree "explodes". Without passing, some positions
(i.e. one single white stone or 3 black stones) dont appear.

So with passing allowed:

- more reachable nodes

- more moves per node (passing allowed is equivalent to add both,
black and white continuations to each position). (Important)

- longer Games (very important).

maybe some time I will play around with this ...

greetings
Detlef

[Bill]

Post by Robert Jasiek
I lack time to check your study, but maybe it helps to point out what
John Tromp writes today on the mailing-list computer go under area
"Finding the maximum length of a Go game, if we measure length
by number of (non-pass) moves, is equivalent to finding the longest
simple path in the game graph.

Do you mean "simple path" as in math, meaning no intersecting points (or
vertices?)?

Post by Robert Jasiek
For 2x2 this can easily be brute forced, and one finds a maximum
length of 48 moves (so a single game can visit at most 49 of the 57
legal positions)."
Now, introduce (single) passes.

[Bill]

Post by Bill

Post by Robert Jasiek
I lack time to check your study, but maybe it helps to point out what
John Tromp writes today on the mailing-list computer go under area
"Finding the maximum length of a Go game, if we measure length
by number of (non-pass) moves, is equivalent to finding the longest
simple path in the game graph.

Do you mean "simple path" as in math, meaning no intersecting points
(or vertices?)?

I see now that you wrote "game graph". It that is really what you mean,
then it doesn't say anything (!)

Post by Bill

Post by Robert Jasiek
For 2x2 this can easily be brute forced, and one finds a maximum
length of 48 moves (so a single game can visit at most 49 of the 57
legal positions)."
Now, introduce (single) passes.

[Robert Jasiek]

Post by Bill

the longest simple path in the game graph.

Do you mean "simple path" as in math, meaning no intersecting points (or
vertices?)?

We mean a path in a game (tree) graph. Inform yourself about graph
theory, game trees and abstract data structures.

[Bill]

Post by Robert Jasiek

Post by Bill

the longest simple path in the game graph.

Do you mean "simple path" as in math, meaning no intersecting points (or
vertices?)?

We mean a path in a game (tree) graph. Inform yourself about graph
theory, game trees and abstract data structures.

You didn't say "tree" the first time, and I didn't understand what you
meant. Other than that, your description of the length of a game
appears a triviality. Please try to say something interesting.

[Rainer Rosenthal]

Post by Bill
appears a triviality. Please try to say something interesting.

Well, these days people tend to be not so nice, especially in newsgroups.
Wish you a pleasant day.

Rainer

[Bill]

Post by Rainer Rosenthal

Post by Bill
appears a triviality. Please try to say something interesting.

Well, these days people tend to be not so nice, especially in newsgroups.
Wish you a pleasant day.

Yes. The arrogance is tough to take.. Thank you.

Bill

Post by Rainer Rosenthal
Rainer

[Robert Jasiek]

Post by Bill
the length of a game
appears a triviality. Please try to say something interesting.

State the "trivial" maximal length of the game and provide the
"trivial" proof, please:) Of course, the description of what is being
wanted is trivial. Solving the problem is the difficulty.

[rt]

Positions vs games does not resolve this.

Taking a look at

http://senseis.xmp.net/?PositionsAndGamesOn2x2

81 positions.

By simple rotation one set of positions becomes identical to another.

It also looks like positions just repeat without end, seki...?

http://senseis.xmp.net/?2x2Board


BTW, cards are a poor analog for the go board.