Re: [Computer-go] Number of Go positions computed at last (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)
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)
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 Goldfainwrote: > 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)
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