Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism

[uurtamo .]

Not to beat a dead horse, but big numbers aren't inherently interesting to
describe.

There are integers bigger than any integer anyone has written down in any
form. This particular integer is large, but "consumable".

I guess I get tired of the "number of atoms in the observable universe"
comparison. Plenty of integers this size or larger can be dealt with in
other ways. (Think factoring).

steve


On Mon, Feb 1, 2016 at 2:11 AM, Olivier Teytaud 
wrote:

>
>> How do you know that an implicit expression (of length smaller than
>> 10^80) of the number does not exist? :)
>>
>
> I am pretty sure that such an implicit expression exists: it is << the
> number of etc etc >> (formalized for your favorite set of rules :-) ).
>
>
>
>
> --
> =
> Olivier Teytaud, INRIA TAO Research Fellow ---
> http://www.slideshare.net/teytaud
> "Please stop quoting me on internet."___ Albert Einstein
>
>
>
>
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism

[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).


It's hard to come up with a formal definition of "implicit expression"
which excludes the definition itself :-)  maybe something like a fast
algorithm for computing a given digit (this exists for pi
https://www.math.hmc.edu/funfacts/ffiles/20010.5.shtml ).

(Well, it's fun, but I would not spend days on this :-) )
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism

[Olivier Teytaud]

>
>
> How do you know that an implicit expression (of length smaller than 10^80)
> of the number does not exist? :)
>

I am pretty sure that such an implicit expression exists: it is << the
number of etc etc >> (formalized for your favorite set of rules :-) ).




-- 
=
Olivier Teytaud, INRIA TAO Research Fellow ---
http://www.slideshare.net/teytaud
"Please stop quoting me on internet."___ Albert Einstein
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism

[Robert Jasiek]

On 31.01.2016 17:19, John Tromp wrote:

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
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism

[Robert Jasiek]

On 31.01.2016 19:57, John Tromp wrote:

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
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

[Computer-go] AlphaGo and the Standard Mistake in Research and Journalism

[Robert Jasiek]

According to John Tromp et al at http://tromp.github.io/go/legal.html
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
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism

[John Tromp]

dear Robert,

> 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
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go