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 <markgoldf...@comcast.net> 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
