Re: [Computer-go] Number of Go positions computed at last (John Tromp)

[John Tromp]

dear Mark,

> Well, although Dr. Tromp seems rather modest about this result, I haven't
> heard of anyone else doing similarly interesting work on the theoretical
> foundations of the game.

There is a lot of other interesting research beyond counting things.
Just to name a few there's rule explorations, where Robert Jasiek
has done a lot of work, and the theory of evaluating Go positions,
endgames, kos, etc. in the setting of Combinatorial Game Theory,
where Elwyn Berlekamp is a name that comes to mind. Apologies for
leaving out countless others who have made valuable contributions.

> 1. So, as you go up the chart, what is the percentage of all possible
> positions that are legal?

The asymptotics of legal positions is derived in our paper (under some
conjecture) as

L(m,n) ~ 0.850639925845714538 * 0.96553505933837387^{m+n} *
2.97573419204335724938^{m*n}

So the legal probability grows as that divided by 3^{m*n}, or

Prob_legal(m,n) ~ 0.850639925845714538 * 0.96553505933837387^{m+n}
*0.99191139734778574979 ^{m*n}

> And isn't that an interesting sequence?  Perhaps more intuitively useful
> to a go-programmer  than the raw numbers themselves?

No; to a programmer that much precision is not interesting.
And to those for whom a lot of precision is interesting, the exact number
of legal positions is more natural than the probability.

>  Does this set of ratios make any
> intuitive sense to you
> ... or should I rephrase that as -- can you rationalize these results of
> the ratios?

Yes, the constant 2.97573419204335724938 is the effective freedom
per point under the legality constraint. That's why we call it the
"base of liberties".

> 2. One of the most frustrating things about writing a program to play go is
> that the rules are
> a bit blurry.  Far too blurry to really satisfy a computer programmer.
> I think some of the
> work you've done over the years is in creating a rigorous and computable
> set of rules.
> Is this correct, or have I heard wrong on this count?  Do you have a set
> of rules that
> could be profitably used for the basis of a go-playing program, that you
> like today?
> Is there a link to such a rule set somewhere?

Obviously I'm inclined to direct you to my personal Go page at

http://tromp.github.io/go.html

which states the Logical rules that I developed with Bill Taylor.

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions computed at last (John Tromp)

[Mark Goldfain]

Well, although Dr. Tromp seems rather modest about this result, I haven't
heard of anyone else doing similarly interesting work on the theoretical
foundations of the game.  This set of results is fascinating and newsworthy.
Congratulations on carrying this out, all the way up to 19x19 !

I have a couple of questions, if these comments are being seen by Dr. Tromp.

1. So, as you go up the chart, what is the percentage of all possible 
positions that are legal?
Isn't that a trivially-quick corollary from your results?  [ (Tromp 
result) / (3 **(n*n)) ]
And isn't that an interesting sequence?  Perhaps more intuitively 
useful to a go-programmer
than the raw numbers themselves?  Does this set of ratios make any 
intuitive sense to you
... or should I rephrase that as -- can you rationalize these 
results of the ratios?


2. One of the most frustrating things about writing a program to play go 
is that the rules are
a bit blurry.  Far too blurry to really satisfy a computer 
programmer.  I think some of the
work you've done over the years is in creating a rigorous and 
computable set of rules.
Is this correct, or have I heard wrong on this count?  Do you have 
a set of rules that
could be profitably used for the basis of a go-playing program, 
that you like today?

Is there a link to such a rule set somewhere?

Thanks,
-- Mark Goldfain

___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions computed at last (John Tromp)

[Olivier Teytaud]

Hi;
maybe, for the rules, you would like the Chinese rules,
and in particular the
"TROMP-TAYLOR CONCISE RULES OF GO"
at https://www.cs.cmu.edu/~wjh/go/tmp/rules/TrompTaylor.html

If you like maths, you might check Robson's result, which shows that with
Japanese rules the game is Exptime-hard (exptime-completeness depends on
the exact formalization of Japanese rules, which are too blurry...) (see at
the end of this message).

The complexity for Chinese rules is somewhere between Pspace and Expspace
(this was discussed earlier in this mailing list, I guess... sorry for not
remembering who pointed out first that the common belief that Go with
Chinese rules is in Exptime has never been formally proved and is in fact
not trivial).

Interestingy, for Japanese rules, even for a subset of positions for which
Robson's result is applied, the decidability of phantom-Go (in the sense:
is there a move with winning probability >= 50% ?) is not proved (the
undecidability is not proved, also :-) ); and for Chinese rules, the
decidability is obvious, but the upper complexity bounds are just
huge.

=
Nb: Robson's paper is discussed here
https://docs.google.com/document/d/1Oq4Vk4oEDZQEbB3hql8nCDUK69pmyJrG0rs9LvsG_WM/edit;
I have scanned the original report and, as Michael agrees for it, I will
put this on the web soon (for the moment only rare people have access to
the document in paper format :-) ).









On Mon, Jan 25, 2016 at 9:11 AM, Mark Goldfain 
wrote:

> Well, although Dr. Tromp seems rather modest about this result, I haven't
> heard of anyone else doing similarly interesting work on the theoretical
> foundations of the game.  This set of results is fascinating and
> newsworthy.
> Congratulations on carrying this out, all the way up to 19x19 !
>
> I have a couple of questions, if these comments are being seen by Dr.
> Tromp.
>
> 1. So, as you go up the chart, what is the percentage of all possible
> positions that are legal?
> Isn't that a trivially-quick corollary from your results?  [ (Tromp
> result) / (3 **(n*n)) ]
> And isn't that an interesting sequence?  Perhaps more intuitively
> useful to a go-programmer
> than the raw numbers themselves?  Does this set of ratios make any
> intuitive sense to you
> ... or should I rephrase that as -- can you rationalize these results
> of the ratios?
>
> 2. One of the most frustrating things about writing a program to play go
> is that the rules are
> a bit blurry.  Far too blurry to really satisfy a computer
> programmer.  I think some of the
> work you've done over the years is in creating a rigorous and
> computable set of rules.
> Is this correct, or have I heard wrong on this count?  Do you have a
> set of rules that
> could be profitably used for the basis of a go-playing program, that
> you like today?
> Is there a link to such a rule set somewhere?
>
> Thanks,
> -- Mark Goldfain
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go




-- 
=
Olivier Teytaud, olivier.teyt...@inria.fr, TAO, LRI, UMR 8623(CNRS - Univ.
Paris-Sud),
bat 490 Univ. Paris-Sud F-91405 Orsay Cedex France
http://www.slideshare.net/teytaud
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Number of Go positions computed at last (John Tromp)

[Robert Jasiek]

On 25.01.2016 09:11, Mark Goldfain wrote:

I haven't heard of anyone else doing similarly interesting work on the 
theoretical
foundations of the game.


Sorry, but this is your fault. Where Tromp excels is Go combinatorics, a 
field that does not equate the more general "the theoretical foundations 
of the game". For the latter (and excluding computer go research), there 
have been a few researchers with more contributions, even if you permit 
formal theory only and exclude more general math research (e.g. by John 
Conway) also applicable to go.


> One of the most frustrating things about writing a program to play go
> is that the rules are a bit blurry.

You say so after having read my commentaries?
http://home.snafu.de/jasiek/rules.html

On 25.01.2016 10:15, Olivier Teytaud wrote:
> the Chinese rules

Please do not confuse the flawed Chinese Rules
http://home.snafu.de/jasiek/c2002.pdf
http://home.snafu.de/jasiek/c2002com.pdf

with the flawless Area Scoring in general.

--
robert jasiek
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go