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

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