[Computer-go] AlphaGo and the Standard Mistake in Research and Journalism
Robert Jasiek
the number of legal 19x19 go positions is
P19 =
2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935
P19 ~ 2.081681994 * 10^170
***
The number G19 of legal games under a given go ruleset is unknown. We
only know lower bounds and the following upper bound, where N = 19x19
= 361 is the number of intersections on the board: For positional
superko (prohibition of recreation of the same position after
completion of a move on the board), no passes, and no resignation, the
number of possible games is smaller than N^P19 because P19 also
restricts the maximal number of moves per game and there are at most N
possible intersections per move. So approximately the upper bound for
the number of legal games under the mentioned rules is
G19 < 361^(2.081681994 * 10^170)
Note that, changing the ko rules from positional superko to Japanese /
Korean / Chinese style no-result ko rules, we get an infinite number
of legal games with equivalence classes for as many different games as
under positional superko. (For the sake of simplicity, let us ignore
the impact of passes and resignations as technicalities for now.)
***
Citation from my rec.games.go Rules FAQ: "Extremely modest estimates
look like 10^N, which is based on an assumption of 10 reasonable
intersections per move. A popular estimate for 19x19 go is 10^761,
which must have originated from a typo and should be 10^361, if at
all... These types of estimates are so popular because humans cannot
even imagine the suggested number of atoms in the universe, 10^80. For
comparison, 3^361 is ca. 10^172."
In the AlphaGo research paper
https://storage.googleapis.com/deepmind-data/assets/papers/deepmind-mastering-go.pdf
the number of possible go games is estimated as approximately b^d,
where b is the breadth (number of available intersections per move)
and d is the depth (length of a game as its number of moves) and
stated as approximately 250^150 by referencing to an earlier research
article.
This number is not completely meaningless: it is somehow related to
empirical data. Even so, the number would be wrong because practically
occurring games have been reported to last up to ca. 450 moves.
Supposing 250 would be a reasonable average number of available
intersections, we would get 250^450. I.e., already by correcting a
minor mistake in the referenced number, we get a more meaningful
number that already is astronomically larger than the stated 250^150.
If we pretend the 250 in 250^450 to be reasonably correct, this more
correct empirical number serves as an empirical lower bound.
***
Therefore, under the made assumptions (such as permitting an empirical
estimate for the lower bound), we know that the number G19 of legal go
games is
250^450 < G19 < 361^(2.081681994 * 10^170).
***
In various go blog messages and media articles, the same kinds of
wrong (by astronomic factors too small) numbers are circulated for
"the" complexity of go: 10^361, 10^170, 10^171, 250^150.
The AlphaGo research paper, go players feeding journalists with
information and journalists make the same mistake: they copy or cite
without understanding the meaning of a particular number.
The worst example has been a popular science journal's statement that
ca. 10^170 would be the number of possible go games (when confusing it
with the extremely smaller number of possible go positions). This
leads us to types of complexities. There are the complexity of the
number of legal positions, the complexity of the number of legal games
(which is the actual complexity of go as a game because great
applicable shorthands to a solution of perfect play are unknown) and
the computational complexity of the generalised game on boards with N
intersections (but go as a game is played on the 19x19 board with its
fixed N = 361).
--
robert jasiek
_______________________________________________
Computer-go mailing list
Compu...@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
John Tromp
> The number G19 of legal games under a given go ruleset is unknown.
It will never be known since there's not enough space in the known
universe to write it down. We're talking about a number with over
10^100 digits.
> For positional
> superko (prohibition of recreation of the same position after
> completion of a move on the board), no passes, and no resignation, the
> number of possible games is smaller than N^P19
The no-pass restriction makes this rather uninteresting.
But actually, the same bound applies to games with passes,
stated as Theorem 7 in our paper.
Besides this upper bound, I can think of only two other numbers
that are well defined and interesting, namely
1) the size of the smallest search tree that proves the perfect komi.
and
2) same but for a full-width tree
These are called the decision complexity and game tree complexity on
https://en.wikipedia.org/wiki/Game_complexity#Decision_complexity
It is reasonable to expect the perfect komi does not depend on games
of more than 361 moves. Even with some ko fights, the ko recaptures
are likely bounded by the number of unplayed points.
The branching factor will be high though; let's put it at at most 200
on (geometric) average.
Then we estimate the decision complexity to be upper bounded by
200^181 and the game tree complexity by 200^361.
regards,
-John
Robert Jasiek
> It will never be known since there's not enough space in the known
> universe to write it down. We're talking about a number with over
> 10^100 digits.
How do you know that an implicit expression (of length smaller than
10^80) of the number does not exist? :)
> [interesting stuff deleted]
> It is reasonable to expect the perfect komi does not depend on games
> of more than 361 moves.
I do not think we may make such a premature claim.
> Even with some ko fights, the ko recaptures
> are likely bounded by the number of unplayed points.
From experience as go players, yes. But... I have seen too many
surprising sequences and sacrifices to be sure.
> Then we estimate the decision complexity to be upper bounded by
> 200^181 and the game tree complexity by 200^361.
I won't believe such until proven:)
--
robert jasiek
John Tromp
>> It will never be known since there's not enough space in the known
>> universe to write it down. We're talking about a number with over
>> 10^100 digits.
>
> How do you know that an implicit expression (of length smaller than 10^80)
> of the number does not exist? :)
Of course an implicit one exists. One can write a program to compute it,
and declare that's the number, in a highly compressed form:-)
>> It is reasonable to expect the perfect komi does not depend on games
>> of more than 361 moves.
>
> I do not think we may make such a premature claim.
I didn't say I'm sure; I only said it's reasonable, as in I would bet
evenly on it.
Presumably ou think chances are better than even that it doesn't
depend on games of more than 450 moves, and worse than even that it
only depends on games of at most 300 moves. What is your best estimate
of
point where where chances are even?
>> Even with some ko fights, the ko recaptures
>> are likely bounded by the number of unplayed points.
>
> From experience as go players, yes. But... I have seen too many surprising
> sequences and sacrifices to be sure.
>
>> Then we estimate the decision complexity to be upper bounded by
>> 200^181 and the game tree complexity by 200^361.
>
> I won't believe such until proven:)
This is not about proving. This is about what numbers the press could use
that are not too arbitrary.
regards,
-John
Robert Jasiek
> What is your best estimate of point where where chances are even?
I do not know.
> what numbers the press could use that are not too arbitrary.
- The number P of legal positions.
- An empirical average number I of available intersections for the next
move, where I needs to be determined before exposed to the press.
- The maximal number N of available intersections for the next move.
- An empirical average number X of moves in not resigned games, where X
needs to be determined before exposed to the press.
- The maximal number ca. 450 of moves in a practically occurring game
[excluding neutral intersections, area scoring removals and virtual pass
fights].
- The maximal number ca. P of moves in theory.
- The number of legal games is unknown. An explanation that at every
move, all currently available, legal intersections must be considered
and the upper bound is ca. N^P.
For the yellow press: "The number of 10^80 atoms in the universe is much
smaller than the number 2 * 10^170 of possible positions, which is very
much smaller than the uncountable number of possible different games."
--
robert jasiek
David Ongaro
> On 31 Jan 2016, at 16:05, Robert Jasiek <jas...@snafu.de> wrote:
>
> For the yellow press: "The number of 10^80 atoms in the universe is much smaller than the number 2 * 10^170 of possible positions, which is very much smaller than the uncountable number of possible different games."
"much smaller" is a much too weak word. And the point of such comparisons is that the press wants to avoid stating exponentials (which nobody can "relate" to). But I agree with Tromp, that a comparison with the number of atoms of the universe is just ridiculous. I'm just astounded that a smart guy like Demis Hasabbis thinks it's a good comparison and reiterates it all the time. Maybe saying "Even if we replace every atom in our universe with a copy of our universe the resulting number of atoms would still be less than the number of Go positions" would be appropriate.
Olivier Teytaud
How do you know that an implicit expression (of length smaller than 10^80) of the number does not exist? :)
--
=========================================================
Olivier Teytaud, INRIA TAO Research Fellow --- http://www.slideshare.net/teytaud
Robert Jasiek
> I am pretty sure that such an implicit expression exists: it is << the
> number of etc etc....
We do not speak of just the definition of what kind of number to find,
but of the construction of finding the number (or already of a
compression of its explicit digits). BTW, I think that there is much
more storage in the universe than atoms: think of Boltzmann states and
quantum states.
Olivier Teytaud
I am pretty sure that such an implicit expression exists: it is << the
number of etc etc....
We do not speak of just the definition of what kind of number to find, but of the construction of finding the number (or already of a compression of its explicit digits).
Igor Polyakov
certainly far too large to write out the digits to, in fact the number
of digits in that number is too large to write
