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

Igor Polyakov weiqiprogramming at gmail.com
Mon Feb 1 19:07:04 PST 2016


Have you heard of https://en.wikipedia.org/wiki/Graham's_number ? It is 
certainly far too large to write out the digits to, in fact the number 
of digits in that number is too large to write

On 2016-01-31 8:19, John Tromp wrote:
> 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 at computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go




More information about the Computer-go mailing list