On Fri, Jun 3, 2011 at 3:30 AM, Scott Christensen <[email protected]>wrote:
> Doesn't the simple mathematics of why go is difficult make the 'faster > hardware' topic a small issue? At the starting move there is on the > scale of 361! = (roughly 10 ^ 300 ?) possible combinations having a > very simple algorithm with a hardware improvement of 10 ^ 9 can't > possibly outperform an algorithm with even minimal intelligent tree > pruning? > > The issue is that a program on 2x faster hardware clearly outperforms. If you can easily get 2x by pruning a couple of moves then congratulations, you have a much stronger program now. Now take that same program and run it on 2x faster hardware and you have another big improvement. Simple mathematics. Why don't you ask the MCTS authors if it's simple to double the speed and see what they say? Don > > On Fri, Jun 3, 2011 at 6:18 AM, <[email protected]> wrote: > > Send Computer-go mailing list submissions to > > [email protected] > > > > To subscribe or unsubscribe via the World Wide Web, visit > > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > > or, via email, send a message with subject or body 'help' to > > [email protected] > > > > You can reach the person managing the list at > > [email protected] > > > > When replying, please edit your Subject line so it is more specific > > than "Re: Contents of Computer-go digest..." > > > > > > Today's Topics: > > > > 1. Direct DX11 and graphics cards for cheaper simulation > > hardware? (Jacques Basald?a) > > 2. Re: Direct DX11 and graphics cards for cheaper simulation > > hardware? (Don Dailey) > > 3. [Computer-go ]Congratulations to Zen! (Nick Wedd) > > 4. Re: [Computer-go ]Congratulations to Zen! (Andy) > > 5. Re: [Computer-go ]Congratulations to Zen! (Michael Williams) > > > > > > ---------------------------------------------------------------------- > > > > Message: 1 > > Date: Thu, 02 Jun 2011 20:48:16 +0100 > > From: Jacques Basald?a <[email protected]> > > To: [email protected] > > Subject: [Computer-go] Direct DX11 and graphics cards for cheaper > > simulation hardware? > > Message-ID: <4DE7E <[email protected]>[email protected]> > > Content-Type: text/plain; charset=us-ascii; format=flowed > > > > Don Dailey wrote: > > > > > Are you trying to say that heavy playouts are better? > > > Who is going to argue with that? I agree completely. > > > Are you trying to make the point that there are very simple > > > to understand positions that computers cannot easily solve? > > > I agree with that. Are you trying to say that heavy playouts > > > can solve many types of common positions orders or magnitude > > > faster than light playouts? I agree with that. > > > Are you trying to say uniformly random playouts suck? > > > I agree with that. > > > > I do not pretend to argue. Just to clarify ideas and read what > > others have to say. And of course I agree on all that. > > > > In self play all MCTS programs scale. Everybody agrees and it > > has been tested empirically. Intuitively: If we admit that 2000 > > sims is better than 1000, since nodes in the tree are trees > > themselves, it is clear that no matter how many million > > simulations we play, there will always be nodes with 1000 visits > > and they would be better evaluated if they had 2000. The entire > > tree relies on the correct evaluation at the nodes so the entire > > tree benefits of more sims. > > > > A different question is: Can a really weak program, say vanilla > > MCTS with uniform random playouts, just no eye filling (no RAVE, > > no progressive widening) reach the strength of, say Aya, with 2500 > > sims (KGS 4 kyu) in 19x19 ? > > > > The answer is: > > > > Theoretically: Yes. > > In practice: No. Not with a trillion sims per move. > > > > You probably don't disagree since that is implicit in "heavy > > playouts can solve many types of common positions orders > > or magnitude faster than light playouts". > > > > Note that this question is equivalent to: Would the current > > version of Zen become a pro just with hardware evolution? > > > > > > Jacques. > > > > > > > > ------------------------------ > > > > Message: 2 > > Date: Thu, 2 Jun 2011 16:57:51 -0400 > > From: Don Dailey <[email protected]> > > To: [email protected] > > Subject: Re: [Computer-go] Direct DX11 and graphics cards for cheaper > > simulation hardware? > > Message-ID: <[email protected]> > > Content-Type: text/plain; charset="iso-8859-1" > > > > On Thu, Jun 2, 2011 at 3:48 PM, Jacques Basald?a <[email protected]> > wrote: > > > >> Don Dailey wrote: > >> > >> > Are you trying to say that heavy playouts are better? > >> > Who is going to argue with that? I agree completely. > >> > Are you trying to make the point that there are very simple > >> > to understand positions that computers cannot easily solve? > >> > I agree with that. Are you trying to say that heavy playouts > >> > can solve many types of common positions orders or magnitude > >> > faster than light playouts? I agree with that. > >> > Are you trying to say uniformly random playouts suck? > >> > I agree with that. > >> > >> I do not pretend to argue. Just to clarify ideas and read what > >> others have to say. And of course I agree on all that. > >> > > > > I'm not really directing this to any specific individual, sorry it came > > across that way. > > > > > > > >> In self play all MCTS programs scale. Everybody agrees and it > >> has been tested empirically. Intuitively: If we admit that 2000 > >> sims is better than 1000, since nodes in the tree are trees > >> themselves, it is clear that no matter how many million > >> simulations we play, there will always be nodes with 1000 visits > >> and they would be better evaluated if they had 2000. The entire > >> tree relies on the correct evaluation at the nodes so the entire > >> tree benefits of more sims. > >> > >> A different question is: Can a really weak program, say vanilla > >> MCTS with uniform random playouts, just no eye filling (no RAVE, > >> no progressive widening) reach the strength of, say Aya, with 2500 > >> sims (KGS 4 kyu) in 19x19 ? > >> > > > > That's not an interesting question. You can just run a program like > this > > and get your answer as you have mostly specified the level and the > > algorithm. I don't know the answer, but 4 kyu seems pretty strong to > me > > for a program that only uses uniform random playouts and no tricks. > > > > > >> The answer is: > >> > >> Theoretically: Yes. > >> In practice: No. Not with a trillion sims per move. > >> > > > > Uniformly random sims will often send the program down an incorrect > pathway, > > but the program eventually discovers it's error (assuming there is SOME > > exploration) and will find better moves. A trillion sims is a LOT of > sims > > and I believe it is enough to get above 4 kyu, which is not a very high > > level. But I don't really have a good way of estimating this level. > > > > I do believe that with the quality of the sims there has to be some > > adjustment to the tree search algorithms. If the sims are horrible you > > cannot depend on them as much to direct the shape of the tree and visa > > versa. So I would say that if such a program is allowed to be > properly > > tuned and gets to do a whopping trillion playouts per move, it's going > to > > be stronger than 4 kyu. I believe that even an alpha/beta search > > (perhaps like Aya was) is doing a trillion nodes per move, it is going > to > > play a good game. > > > > To be sure, you would still be able to find some simple position that it > > screws up big time. But isn't that also true of the 3 and 4 Dan > programs > > we now have? So why can't we have a 4 kyu program that plays stupid > > moves too? > > > > > > > >> > >> You probably don't disagree since that is implicit in "heavy > >> playouts can solve many types of common positions orders > >> or magnitude faster than light playouts". > >> > > > > Heavy playouts is like turbo charging the program. The difference > between > > a uniform simulation and heavy playouts is not just enormous, but grows > with > > each doubling. In practical terms, you cannot have a strong program > > without heavy playouts and in 10 years the majority of progress will be > with > > the playouts, not the search. The quality of the software (if it's > > like in chess) will grow at least as fast and probably faster in GO as > the > > hardware. Of course if we are seeing the limits of Moores law, that is > > even more true, but I don't think we are (they said that 10 years ago, > > didn't they?) > > > > > >> > >> Note that this question is equivalent to: Would the current > >> version of Zen become a pro just with hardware evolution? > >> > > > > When you ask questions like this you open things up to confusion and > > argument because you didn't ask a well formed question. You did not > > specify a time period or any kind of rate of hardware evolution. Are > you > > just asking for a prognostication? > > > > With infinite hardware evolution (assuming it will always reach some > > arbitrary speed if you wait enough years or centuries) then the answer > is > > yes. But at some point the limits of physics must rear it's ugly head > > and the hardware progress with be much slower. So it's not possible to > give > > any kind of estimate that is attached to reality. > > > > I can only guess about this, but I think we are going to be surprised by > > how much a 100x faster computer gives us. If you had asked this exact > > question 35 years ago with respect to computer chess, most reasonable > > people would have said that having a computer 10,000 times faster would > > probably only give you a hundred to two additional ELO. I'm not joking, > > this is how it was. This happens because when we see a really big > > problem, we imagine that it's even bigger than what it is. It was > very > > common back then to show people problems from real games that no computer > > imaginable would ever be able to solve. And yet now they are solved > > trivially. I don't mean to be disparaging, but it shows how stupid and > > naive and shortsighted we all tend to be at times. > > > > The Zen question won't happen because the software (in my opinion) will > > evolve much faster than the hardware. But they will both be very > > important. We will get a pro playing Go program decades sooner if we > > don't wait for hardware to run Zen on, but instead we make constant > > advances. > > > > Don > > > > > > > > > >> > >> Jacques. > >> > >> _______________________________________________ > >> Computer-go mailing list > >> [email protected] > >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >> > > -------------- next part -------------- > > An HTML attachment was scrubbed... > > URL: < > http://dvandva.org/pipermail/computer-go/attachments/20110602/efb664e5/attachment-0001.html > > > > > > ------------------------------ > > > > Message: 3 > > Date: Thu, 02 Jun 2011 22:17:29 +0100 > > From: Nick Wedd <[email protected]> > > To: [email protected] > > Subject: [Computer-go] [Computer-go ]Congratulations to Zen! > > Message-ID: <[email protected]> > > Content-Type: text/plain; charset=ISO-8859-1; format=flowed > > > > Congratulations to Zen19S, winner of last week's slow bot tournamwent, > > four wins ahead of its nearest rival! > > > > My report is at http://www.weddslist.com/kgs/past/S11.2/index.html > > As usual, I will welcome your comments and corrections. > > > > Nick > > -- > > Nick Wedd > > [email protected] > > > > > > ------------------------------ > > > > Message: 4 > > Date: Thu, 2 Jun 2011 16:48:37 -0500 > > From: Andy <[email protected]> > > To: Nick Wedd <[email protected]>, [email protected] > > Subject: Re: [Computer-go] [Computer-go ]Congratulations to Zen! > > Message-ID: <[email protected]> > > Content-Type: text/plain; charset="iso-8859-1" > > > > "Also in round 9, there was an interesting game between AyaMC and > > ManyFaces1, involving a semeai at the lower left sideof the board, as > shown > > to the right. If move 215 had been answered by a move at 218 (or one > point > > below, at A7), the result would have been seki. Move 216 is a blunder, > > allowing Black to kill with 217. White 218 achieves nothing." > > > > I think at that point white can't do anything: > > http://eidogo.com/#HFxgu5j:0,1,0 > > > > It is a big-eye kills small-eye situation. > > > > > > > > On Thu, Jun 2, 2011 at 4:17 PM, Nick Wedd <[email protected]> wrote: > > > >> Congratulations to Zen19S, winner of last week's slow bot tournamwent, > four > >> wins ahead of its nearest rival! > >> > >> My report is at http://www.weddslist.com/kgs/past/S11.2/index.html > >> As usual, I will welcome your comments and corrections. > >> > >> Nick > >> -- > >> Nick Wedd > >> [email protected] > >> _______________________________________________ > >> Computer-go mailing list > >> [email protected] > >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >> > > -------------- next part -------------- > > An HTML attachment was scrubbed... > > URL: < > http://dvandva.org/pipermail/computer-go/attachments/20110602/227bee15/attachment-0001.html > > > > > > ------------------------------ > > > > Message: 5 > > Date: Thu, 2 Jun 2011 18:18:00 -0400 > > From: Michael Williams <[email protected]> > > To: [email protected] > > Subject: Re: [Computer-go] [Computer-go ]Congratulations to Zen! > > Message-ID: <[email protected]> > > Content-Type: text/plain; charset="iso-8859-1" > > > > Why doesn't CrazyStone compete? I'm guessing Remi does not have the > time. > > Perhaps one of his trusted students could run it. > > > > > > > > On Thu, Jun 2, 2011 at 5:48 PM, Andy <[email protected]> wrote: > > > >> "Also in round 9, there was an interesting game between AyaMC and > >> ManyFaces1, involving a semeai at the lower left sideof the board, as > shown > >> to the right. If move 215 had been answered by a move at 218 (or one > point > >> below, at A7), the result would have been seki. Move 216 is a blunder, > >> allowing Black to kill with 217. White 218 achieves nothing." > >> > >> I think at that point white can't do anything: > >> http://eidogo.com/#HFxgu5j:0,1,0 > >> > >> It is a big-eye kills small-eye situation. > >> > >> > >> > >> On Thu, Jun 2, 2011 at 4:17 PM, Nick Wedd <[email protected]> wrote: > >> > >>> Congratulations to Zen19S, winner of last week's slow bot tournamwent, > >>> four wins ahead of its nearest rival! > >>> > >>> My report is at http://www.weddslist.com/kgs/past/S11.2/index.html > >>> As usual, I will welcome your comments and corrections. > >>> > >>> Nick > >>> -- > >>> Nick Wedd > >>> [email protected] > >>> _______________________________________________ > >>> Computer-go mailing list > >>> [email protected] > >>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >>> > >> > >> > >> _______________________________________________ > >> Computer-go mailing list > >> [email protected] > >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > >> > > -------------- next part -------------- > > An HTML attachment was scrubbed... > > URL: < > http://dvandva.org/pipermail/computer-go/attachments/20110602/8c41e8f9/attachment.html > > > > > > ------------------------------ > > > > _______________________________________________ > > Computer-go mailing list > > [email protected] > > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > > > > End of Computer-go Digest, Vol 17, Issue 11 > > ******************************************* > > > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
