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 Fhourstones does [very well, I may add].
But I do smell troll too, so I'll stop here. Enough feeding. Álvaro. On Sun, Aug 6, 2017 at 4:08 PM, Brian Sheppard via Computer-go < computer-go@computer-go.org> wrote: > 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 force” != unintelligent. Inevitably, every brute force > algorithm will incorporate intelligent heuristics. Consider the evolution > of minimax, for example, via alpha-beta, selective extensions, LMR, etc. > > > > > > > > *From:* Steven Clark [mailto:steven.p.cl...@gmail.com] > *Sent:* Sunday, August 6, 2017 2:52 PM > *To:* Brian Sheppard <sheppar...@aol.com> > *Cc:* computer-go <computer-go@computer-go.org> > > *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 network > generates a score for each coordinate on the board in a given position, > does not mean that all of those nodes will be expanded in any reasonable > scenario. > > > > On Sun, Aug 6, 2017 at 2:20 PM, Brian Sheppard <sheppar...@aol.com> wrote: > > 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 node. > > > > MCTS has the appearance of a selective search because time control > terminates search while the tree is still ragged. In fact, it will search > every continuation an infinite number of times. > > > > In order to have high performance, an MCTS implementation needs to search > best moves as early as possible 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 Sheppard <sheppar...@aol.com>; computer-go < > computer-go@computer-go.org> > *Subject:* 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 checking whether each candidate satisfies the problem's > statement." > > > > The whole point of the policy network is to avoid brute-force search, by > reducing the branching factor... > > > > On Sun, Aug 6, 2017 at 10:42 AM, Brian Sheppard via Computer-go < > computer-go@computer-go.org> wrote: > > 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. This > is estimated based on the win rate of top pros in head-to-head games. The > calculation starts by assuming that Go is a win at 6.5 komi for either > Black (more likely) or White, so a perfect player would win 100% for Black. > Actual championship caliber players win 51% to 52% for Black. In 9-dan play > overall, I think the rate is 53% to 54% for Black. Then you can estimate > how many errors each player has to make to bring about such a result. E.g., > If players made only one error on average, then Black would win the vast > majority of games, so they must make more errors. I came up with 12 errors > per game, but you can reasonably get other numbers based on your model. > > > > Best, > > Brian > > > > *From:* Computer-go [mailto:computer-go-boun...@computer-go.org] *On > Behalf Of *Cai Gengyang > *Sent:* Sunday, August 6, 2017 9:49 AM > *To:* computer-go@computer-go.org > *Subject:* [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 > http://computer-go.org/mailman/listinfo/computer-go > > > > > > _______________________________________________ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go >
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
