[Computer-go] Alphago and solving Go

Marc Landgraf mahrgell87 at gmail.com
Wed Aug 9 07:40:58 PDT 2017


Under which ruleset is the 3^(n*n) a trivial upper bound for the number of
legal positions?
I'm sure there are rulesets, under which this bonds holds, but I doubt that
this can be considered trivial.

Under the in computer go more common rulesets this upper bound is simply
wrong. Unless we talk about simply the visual aspect, but then this has
absolutely nothing to do with the discussion abour solving games.

2017-08-09 14:34 GMT+02:00 Gunnar Farnebäck <gunnar at lysator.liu.se>:

> Except 361! (~10^768) couldn't plausibly be an estimate of the number of
> legal positions, since ignoring the rules in that case gives the trivial
> upper bound of 3^361 (~10^172).
>
> More likely it is a very, very bad attempt at estimating the number of
> games. Even with the extremely unsharp bound given in
> https://tromp.github.io/go/gostate.pdf
>
> 10^(10^48) < number of games < 10^(10^171)
>
> the 361! estimate comes nowhere close to that interval.
>
> /Gunnar
>
> On 08/07/2017 04:14 AM, David Doshay wrote:
>
>> Yes, that zeroth order number (the one you get to without any thinking
>> about how the game’s rules affect the calculation) is outdated since early
>> last year when this result gave us the exact number of legal board
>> positions:
>>
>> https://tromp.github.io/go/legal.html
>>
>> So, a complete game tree for 19x19 Go would contain about 2.08 * 10^170
>> unique nodes (see the paper for all 171 digits) but some number of
>> duplicates of those nodes for the different paths to each legal position.
>>
>> In an unfortunate bit of timing, it seems that many people missed this
>> result because of the Alpha Go news.
>>
>> Cheers,
>> David G Doshay
>>
>> ddoshay at mac.com <mailto:ddoshay at mac.com>
>>
>>
>>
>>
>>
>> On 6, Aug 2017, at 3:17 PM, Gunnar Farnebäck <gunnar at lysator.liu.se
>>> <mailto:gunnar at lysator.liu.se>> wrote:
>>>
>>> On 08/06/2017 04:39 PM, Vincent Richard wrote:
>>>
>>>> No, simply because there are way to many possibilities in the game,
>>>> roughly (19x19)!
>>>>
>>>
>>> Can we lay this particular number to rest? Not that "possibilities in
>>> the game" is very well defined (what does it even mean?) but the number of
>>> permutations of 19x19 points has no meaningful connection to the game of go
>>> at all, not even "roughly".
>>>
>>> /Gunnar
>>> _______________________________________________
>>> Computer-go mailing list
>>> Computer-go at computer-go.org <mailto:Computer-go at computer-go.org>
>>> http://computer-go.org/mailman/listinfo/computer-go
>>>
>>
>>
>>
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>>
>>
> _______________________________________________
> Computer-go mailing list
> Computer-go at computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20170809/89467298/attachment.html>


More information about the Computer-go mailing list