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 network generates a score for each coordinate on the board in a given position, does

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

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.

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

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

[Computer-go] Alphago and solving Go

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 ___ Computer-go mailing list Computer-go@computer-go.org

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

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 typical variant of MCTS, it is technically correct. The reason it's technically correct uninteresting is because the bias introduced by a policy net is so extreme that it might

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

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

Re: [Computer-go] Alphago and solving Go

I understand why most people are saying that AlphaGo is not brute force, because it appears to be highly selective. But MCTS is a full width search. Read the AlphaGo papers, as one of the other respondents (rather sarcastically) suggested: AlphaGo will eventually search every move at every

Re: [Computer-go] Alphago and solving Go

If AlphaGo actually used hard (e.g. permanent) pruning, then it would not be brute force. But it doesn’t operate that way, so it is brute force. BTW, AlphaGo’s papers reports benefiting from search and RAVE. That suggests that hard pruning is a risky business. From: David Wu

Re: [Computer-go] Alphago and solving Go

Eventually exploring the entire tree is what I would call "mathematically sound", meaning that given enough time the algorithm is guaranteed to play optimally. I would reserve "brute force" for algorithms that simply search every possible variant exhaustively, like John Tromp's connect 4 program

Re: [Computer-go] Alphago and solving Go

Possibly you are answering a different question than the one posed? Possibly your interpretation is the one actually intended. I don’t know, and maybe you could be right about what was being asked. I do know the semantics of brute force, though, which you quoted below. Note that “brute

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:

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

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

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