Re: [Computer-go] Alphago and solving Go

> Shouldnt that number at most be 722^#positions? Since adding a black or a > white stone is something fundamentally different? The upper bound of 361^L(19,19) games is from Theorem 7 on page 31 of http://tromp.github.io/go/gostate.pdf, where you will find a proof. As the paragraph preceding that

Re: [Computer-go] Alphago and solving Go

On 09.08.2017 20:50, John Tromp wrote: The number of games is at most 361^#positions. This misses passes, rules distinguishing situations etc. and infinite sequences under some rulesets. -- robert jasiek ___ Computer-go mailing list Computer-go@com

Re: [Computer-go] Alphago and solving Go

Why do you think that there is a 3 in the denominator? On Aug 9, 2017 2:29 PM, "Marc Landgraf" wrote: > I don't mind your terminology, in fact I feel like it is a good way to > distinguish the two different things. It is just that I considiered one > thing wrongly used instead of the other for t

Re: [Computer-go] Alphago and solving Go

It's trivial, dude. On Aug 9, 2017 8:35 AM, "Marc Landgraf" wrote: > 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 comp

Re: [Computer-go] Alphago and solving Go

I don't mind your terminology, in fact I feel like it is a good way to distinguish the two different things. It is just that I considiered one thing wrongly used instead of the other for the discussion here. But if we go with the link you are suggesting here: Shouldnt that number at most be 722^#p

Re: [Computer-go] Alphago and solving Go

> And what is the connection between the number of "positions" and the number > of games The number of games is at most 361^#positions. > or even solving games? In the game trees we do not care about > positions, but about situations. We care about lots of things, including intersections, stones

Re: [Computer-go] Alphago and solving Go

And what is the connection between the number of "positions" and the number of games or even solving games? In the game trees we do not care about positions, but about situations. For the game tree it indeed matters whos turn it is, which moves are legal, and if super-ko rules are used which positi

Re: [Computer-go] Alphago and solving Go

> Under which ruleset is the 3^(n*n) a trivial upper bound for the number of > legal positions? Under all rulesets. > Unless we talk about simply the visual aspect Yes, we do. > but then this has > absolutely nothing to do with the discussion abour solving games. If you want the notion of "pos

Re: [Computer-go] Alphago and solving Go

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 abo

Re: [Computer-go] Alphago and solving Go

361! seems like an attempt to estimate an upper bound on the number of games where nothing is captured. On Wed, Aug 9, 2017 at 2:34 PM, Gunnar Farnebäck wrote: > Except 361! (~10^768) couldn't plausibly be an estimate of the number of > legal positions, since ignoring the rules in that case give

Re: [Computer-go] Alphago and solving Go

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

Re: [Computer-go] Alphago and solving Go

On Mon, Aug 7, 2017 at 12:52 PM, Darren Cook wrote: > > https://en.wikipedia.org/wiki/Brute-force_search explains it as > > "systematically enumerating all possible candidates for the > > solution". > > > > There is nothing systematic about the pseudo random variation > > selection in MCTS; > > M

Re: [Computer-go] Alphago and solving Go

> https://en.wikipedia.org/wiki/Brute-force_search explains it as > "systematically enumerating all possible candidates for the > solution". > > There is nothing systematic about the pseudo random variation > selection in MCTS; More semantics, but as it is pseudo-random, isn't that systematic?

Re: [Computer-go] Alphago and solving Go

BTW, if anyone is wondering about the "roughly" part, 361! = 1.438 * 10^768 while L19 = 2.081681994 * 10^170. On Sun, Aug 06, 2017 at 07:14:42PM -0700, David Doshay wrote: > Yes, that zeroth order number (the one you get to without any thinking about > how the game’s rules affect the calculatio

Re: [Computer-go] Alphago and solving Go

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

Re: [Computer-go] Alphago and solving Go

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

Re: [Computer-go] Alphago and solving Go

> *Sent:* Sunday, August 6, 2017 2:52 PM > *To:* Brian Sheppard > *Cc:* computer-go > > *Subject:* Re: [Computer-go] Alphago and solving Go > > > > This is semantics. Yes, in the limit of infinite time, it is brute-force. > Meanwhile, in the real world, AlphaGo cho

Re: [Computer-go] Alphago and solving Go

> There is a definition of “brute force” on Wikipedia. https://en.wikipedia.org/wiki/Brute-force_search explains it as "systematically enumerating all possible candidates for the solution". There is nothing systematic about the pseudo random variation selection in MCTS; it may not even have suffi

Re: [Computer-go] Alphago and solving Go

an Sheppard *Cc:* computer-go *Subject:* Re: [Computer-go] Alphago and solving Go This is semantics. Yes, in the limit of infinite time, it is brute-force. Meanwhile, in the real world, AlphaGo chooses to balance its finite time budget between depth & width. The mere fact that the CNN policy

Re: [Computer-go] Alphago and solving Go

PM To: Brian Sheppard Cc: computer-go Subject: Re: [Computer-go] Alphago and solving Go This is semantics. Yes, in the limit of infinite time, it is brute-force. Meanwhile, in the real world, AlphaGo chooses to balance its finite time budget between depth & width. The mere fact that the

Re: [Computer-go] Alphago and solving Go

Aren't you a little bit too old now to be troling this list? On Sun, Aug 6, 2017 at 3:49 PM, Cai Gengyang wrote: > Is Alphago brute force search? > Is it possible to solve Go for 19x19 ? > And what does perfect play in Go look like? > How far are current top pros from perfect play? > > Gengyang

Re: [Computer-go] Alphago and solving Go

[mailto:lightvec...@gmail.com] Sent: Sunday, August 6, 2017 2:54 PM To: Brian Sheppard ; computer-go@computer-go.org Cc: Steven Clark Subject: Re: [Computer-go] Alphago and solving Go Saying in an unqualified way that AlphaGo is brute force is wrong in the spirit of the question. Assuming AlphaGo uses a

Re: [Computer-go] Alphago and solving Go

There is a definition of “brute force” on Wikipedia. Seems to me that MCTS fits. Deep Blue fits. From: Álvaro Begué [mailto:alvaro.be...@gmail.com] Sent: Sunday, August 6, 2017 2:56 PM To: Brian Sheppard ; computer-go Subject: Re: [Computer-go] Alphago and solving Go It was already a

Re: [Computer-go] Alphago and solving Go

om:* Steven Clark [mailto:steven.p.cl...@gmail.com] > *Sent:* Sunday, August 6, 2017 1:14 PM > *To:* Brian Sheppard ; computer-go < > computer-go@computer-go.org> > *Subject:* Re: [Computer-go] Alphago and solving Go > > > > Why do you say AlphaGo is brute-force? Brute fo

Re: [Computer-go] Alphago and solving Go

in each node. It is in this respect that > AlphaGo truly excels. (AlphaGo also excels at whole board evaluation, but > that is a separate topic.) > > > > > > *From:* Steven Clark [mailto:steven.p.cl...@gmail.com] > *Sent:* Sunday, August 6, 2017 1:14 PM > *To:* Brian Sh

Re: [Computer-go] Alphago and solving Go

whole board evaluation, but > that is a separate topic.) > > > > > > *From:* Steven Clark [mailto:steven.p.cl...@gmail.com] > *Sent:* Sunday, August 6, 2017 1:14 PM > *To:* Brian Sheppard ; computer-go < > computer-go@computer-go.org> > *Subject:* Re: [Com

Re: [Computer-go] Alphago and solving Go

: [Computer-go] Alphago and solving Go Why do you say AlphaGo is brute-force? Brute force is defined as: "In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique that consists of systematically enumeratin

Re: [Computer-go] Alphago and solving Go

Why do you say AlphaGo is brute-force? Brute force is defined as: "In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique that consists of *systematically enumerating all possible candidates* for the solution and ch

Re: [Computer-go] Alphago and solving Go

Yes, AlphaGo is brute force. No it is impossible to solve Go. Perfect play looks a lot like AlphaGo in that you would not be able to tell the difference. But I think that AlphaGo still has 0% win rate against perfect play. My own best guess is that top humans make about 12 errors per game. T

Re: [Computer-go] Alphago and solving Go

Actually, a better Go-God for handicap games would probably be one that ignores score margin as long as it's behind and simply maximizes the entropy measure for the lowest-entropy proof tree that proves that Black is winning. (And only counts the entropy for the black moves, not the white moves in

Re: [Computer-go] Alphago and solving Go

*Is Alphago **brute **force search? * No, simply because there are way to many possibilities in the game, roughly (19x19)! Alphago tries to consider the game like the human do: it evaluates the board from only a limited set of moves, based on its "instinct". This instinct is generated from d

Re: [Computer-go] Alphago and solving Go

* A little but not really. * No, and as far as we can tell, never. Even 7x7 is not rigorously solved. * Unknown. * Against Go-God (plays move that maximizes score margin, breaking ties by some measure of the entropy needed to build the proof tree relative to a human-pro-level policy net), I guess u

Re: [Computer-go] Alphago and solving Go

No (have you read any of the papers about it?) No We don't know We don't know (pros used to claim they were 2-3 stones away from God, but AlphaGo might have encouraged them to be a bit more humble) On Sun, Aug 6, 2017 at 9:49 AM, Cai Gengyang wrote: > Is Alphago brute force search? > Is it possi

Re: [Computer-go] Alphago and solving Go

No, it is not possible to solve go on a 19x19 board. The closest we have is 5x5, I believe. We have a pretty good idea what optimal play looks like on 7x7. The difficulty of finding optimal play on large boards is unfathomable. Álvaro. On Sun, Aug 6, 2017 at 10:06 AM Cai Gengyang wrote: > Is A