Re: [computer-go] early results
I would highly recommend that you do your testing against a different Go engine. Self-play is a weak indicator. Cheers, David On 26, Jan 2007, at 5:39 PM, Don Dailey wrote: Here are some early results on the scalability study. Basically, level 2 beats level 1 83.6 percent of the time. level 4 beats level 2 90.0 percent of the time. Where a level is number of play-outs divided by 1024 Approximately 300 ELO between levels. I fixed level 1 to have an ELO of zero. Of course these numbers are still rough as there has only be a few games played between players so far. - Don gameswin% score Match Up -- -- - -- 55 16.4% 159.0 0001 0002 55 83.6% 202.0 0002 0001 30 10.0% 153.2 0002 0004 30 90.0% 207.8 0004 0002 Rating Win perc Tot Gms Ave Time Player --- --- -- 589.190.000 30 396.5 0004 269.157.647 85 225.3 0002 0.016.364 55 120.7 0001 Black wins: 37 43.5 % White wins: 48 56.5 % ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] early results
Here are some early results on the scalability study. Basically, level 2 beats level 1 83.6 percent of the time. level 4 beats level 2 90.0 percent of the time. Where a level is number of play-outs divided by 1024 Approximately 300 ELO between levels. I fixed level 1 to have an ELO of zero. Of course these numbers are still rough as there has only be a few games played between players so far. - Don gameswin% score Match Up -- -- - -- 55 16.4% 159.0 0001 0002 55 83.6% 202.0 0002 0001 30 10.0% 153.2 0002 0004 30 90.0% 207.8 0004 0002 Rating Win perc Tot Gms Ave Time Player --- --- -- 589.190.000 30 396.5 0004 269.157.647 85 225.3 0002 0.016.364 55 120.7 0001 Black wins: 37 43.5 % White wins: 48 56.5 % ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A ponder only engine
On Fri, 2007-01-26 at 15:57 -0600, Nick Apperson wrote: > So I was thinking. I wonder if anyone has written a go engine that > can play using only the time that it takes their opponent to think. > It seems some of your monte carlo programs would be able to do this > decently well. Has anyone tried to see how much it hurts the ranking > of a program? I would estimate that it would lose only 600 ELO = > around 3 doublings of thinking time. That is assuming the engine > spends on *proper average 1/8 the time it has trying the move that the > opponent picked. Proper average I am defining to be: e^(mean(ln(time > spent))). So essentially, the expected ELO of the move picked. Any > thoughts or data? Lazarus uses the opponents time to think. It does this by assuming that the opponent will play the next move in the principal variation. The prediction accuracy is fairly high on CGOS but I don't have exact numbers. Another idea is to start searching as soon as you make a move, as if you were the opponent. When the opponent finally plays a move, you then can discard the root node and all the siblings of the move the opponent chose. Unfortunately, this doesn't buy that much time except at nodes where the moves are obvious and forced. I came to the conclusion that it's better to just predict the opponents move, play it and then start thinking right away, and if the opponent doesn't do what you predicted you have lost nothing (but neither have you gained anything.) But when you predict correctly you get the full benefit of his time. Right now, Lazarus uses the opponents time to think, but that doesn't change the amount of time it thinks on it's own time. I think this is wrong and it's just a detail I have not yet implemented. I think the proper behavior is to have a fixed "goal time" for the move and play the move as soon as the opponent moves if you have already met that goal time, otherwise continue to think until you've met the goal time. So you might get instant response, or just fairly quick response but if you predict correctly it will always be at least a little benefit. This should be combined with even more aggressive up front time loading (where you spend a lot more time on early moves.) This should be done whether you think on the opponents time or not. Lazarus does save the tree from each search - so there is at least a minor benefit even if you don't predict the opponents move correctly you get to use any nodes that you have generated although this usually doesn't amount to much. So it never resets the tree completely, it just continues to splice forward. - Don > - Nick > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] A ponder only engine
So I was thinking. I wonder if anyone has written a go engine that can play using only the time that it takes their opponent to think. It seems some of your monte carlo programs would be able to do this decently well. Has anyone tried to see how much it hurts the ranking of a program? I would estimate that it would lose only 600 ELO = around 3 doublings of thinking time. That is assuming the engine spends on *proper average 1/8 the time it has trying the move that the opponent picked. Proper average I am defining to be: e^(mean(ln(time spent))). So essentially, the expected ELO of the move picked. Any thoughts or data? - Nick ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: computer-go Digest, Vol 30, Issue 26
Arend Bayer wrote: > . . without ever believing anything that some of the strong go players > (some a lot stronger than me) have to say. Please, don't think that. I am sure there is more people in this list who, like myself, do not think computer go will "do it" through global search only. The opinion of strong go players is always welcome and read with extra attention. I think there is a qualitative difference between go and chess, even if mathematically they both belong to the same class of games and many proved conclusions apply to both. The difference is: Chess is "feasible" by global search and go (19x19) isn't and will probably be "un-feasible" for a long time. (I use feasible and "do it" = "program beats the best human on Earth") I don't want to disregard the talented people who, like Chrilly, did a great job on chess, but the fact that "global search chess" was feasible may have slowed down the development of "intelligent computer chess", o call it "humanlike computer chess" if you prefer. I.e. a program that can _reason_ about a position instead of examining millions of nodes with a by-itself poor evaluation function. I see the fact that "global search go" is not feasible as *good news*. Because we cannot beat the best human by "global search" we are forced to find out something better. I agree with Don in all he states in this thread, but that applies to global search. If a go program playing at move 150 has fully searched the 20 only local games in the board (18 of which did not change since move 148) and _understands_ : a. territorial values of them b. territorial interactions between them c. conditional relations between them d. threat/win sequence that makes optimal use of sente e. ko-threat stock management related with foreseeable kos And from a + b + c + . . . + j + k + l decides its best move, ... what can it do with extra time ? Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 19:54 +, ivan dubois wrote: > Isn't UCT equivalent to Alpha-beta with some cleaver pruning rules ? Both UCT and Alpha-beta are mini-max searches, but UCT is a best first style search and they are substantially different. UCT doesn't prune any branches, it just visits some branches much less than others. alpha beta actually prunes whole trees without any further consideration but only when it is safe (fully admissible) to do so. - Don > - Message d'origine > De : Don Dailey <[EMAIL PROTECTED]> > À : computer-go > Envoyé le : Vendredi, 26 Janvier 2007, 19h51mn 10s > Objet : Re: Re : [computer-go] an idea... computer go program's rank vs time > > > >Part of my procrastination is that I'm not sure how to make UCT > >scale to a large number of CPU's.I am an expert in scaling > >alpha/beta to a large numbers of processors (I did this with Socrates > >on 1836 processors a few years ago) but it's different with UCT > >which is inherently serial. > > - Don > > > > > > > ___ > Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! > Profitez des connaissances, des opinions et des expériences des internautes > sur Yahoo! Questions/Réponses > http://fr.answers.yahoo.com > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 14:47 -0500, Chris Fant wrote: > I personally would love to see more experimental results and less > feelings and intuitions on this list. I agree. I will post my data as I go. Just for reference, this is the the Lazarus program that is currently rated at 1807 on CGOS but running 19x19 games. Current results: Rating Win perc Tot Gms Ave Time Player --- --- -- 1600.075.0004 234.8 0002(1024 playouts) 1400.025.0004 117.5 0001(2048 playouts) Black wins:1 25.0 % White wins:3 75.0 % - Don > > On 1/26/07, Don Dailey <[EMAIL PROTECTED]> wrote: > > On Fri, 2007-01-26 at 11:32 -0800, terry mcintyre wrote: > > > > > > - Original Message From: Don Dailey <[EMAIL PROTECTED]> > > > > > > > > May I ask the range of "number of playouts" tested? > > > > > > I'm still curious about this question? > > > > I think I started at 64 play-outs, and kept doubling the number > > of play-outs to some large number where it took an hour to play > > a single game. > > > > I don't currently have the data, but I am willing to reproduce > > the experiment. Other MC guys can verify it. I'll set it up > > on a slow computer I have free and I'll start at 64 simulations > > on a 19x19 board.I'll play 200 games in pairs, 64 vs 128, > > 128 vs 256, etc. > > > > - Don > > > > > > > > > > Part of my procrastination [ about using 72 processors ] is that > > > > I'm not sure how to make UCT scale to a large number of CPU's. > > > > I am an expert in scaling alpha/beta to a large numbers of > > > > processors (I did this with Socrates on 1836 processors a few > > > > years ago) but it's different with UCT which is inherently serial. > > > > > > > > > I surely appreciate the difficulties in adapting algorithms to > > > multiple processors - I may be rusty, but some years ago I > > > worked on Neuralware and multiple transputers, 860s, and > > > so forth. It gets a little hairy! > > > > > > Hasn't Mogo been parallelized to 4 processors? Can this be > > > extended to larger numbers? > > > > > > Due to the problems with heat dissipation at higher clock cycles, > > > we'll probably be working with large numbers of processors per > > > chip in the future, rather than Terahertz uniprocessors. > > > > > > > > > > > > > > > __ > > > Any questions? Get answers on any topic at Yahoo! Answers. Try it now. > > > ___ > > > computer-go mailing list > > > computer-go@computer-go.org > > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > ___ > > computer-go mailing list > > computer-go@computer-go.org > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] C++ GTP class wrappers
Hey all, don't know if any of you are intereseted, but I am giveing out my GTP wrappers written in C++. I hope to improve them and add more features with time. http://www.nicholasapperson.com/go/computer Any feedback is always welcome. - Nick ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 14:43 -0500, Don Dailey wrote: > I don't currently have the data, but I am willing to reproduce > the experiment. Other MC guys can verify it. I'll set it up > on a slow computer I have free and I'll start at 64 simulations > on a 19x19 board.I'll play 200 games in pairs, 64 vs 128, > 128 vs 256, etc. Ok, I am starting the new study and will report the results after each 200 game match starting at 1k simulations. The way my program works is that level 1 does 1024 simulations, and each new level adds 1024 simulations, so I have to start at 1024 instead of 64. 1024 will be pretty weak but I'll keep building up as I go. Maybe I will get someone to help me with other computers. I have an autotester than manages the games and utilities that report statistics on the results. This is my UCT program, not my older Botnoid series. Two games have already been played and the score is tied, level 1 vs level 2 (1024 sims vs 2048 sims.) - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] an idea... computer go program's rank vs time
Isn't UCT equivalent to Alpha-beta with some cleaver pruning rules ? - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Vendredi, 26 Janvier 2007, 19h51mn 10s Objet : Re: Re : [computer-go] an idea... computer go program's rank vs time >Part of my procrastination is that I'm not sure how to make UCT >scale to a large number of CPU's.I am an expert in scaling >alpha/beta to a large numbers of processors (I did this with Socrates >on 1836 processors a few years ago) but it's different with UCT >which is inherently serial. - Don ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
I personally would love to see more experimental results and less feelings and intuitions on this list. On 1/26/07, Don Dailey <[EMAIL PROTECTED]> wrote: On Fri, 2007-01-26 at 11:32 -0800, terry mcintyre wrote: > > - Original Message From: Don Dailey <[EMAIL PROTECTED]> > > > > May I ask the range of "number of playouts" tested? > > I'm still curious about this question? I think I started at 64 play-outs, and kept doubling the number of play-outs to some large number where it took an hour to play a single game. I don't currently have the data, but I am willing to reproduce the experiment. Other MC guys can verify it. I'll set it up on a slow computer I have free and I'll start at 64 simulations on a 19x19 board.I'll play 200 games in pairs, 64 vs 128, 128 vs 256, etc. - Don > > Part of my procrastination [ about using 72 processors ] is that > > I'm not sure how to make UCT scale to a large number of CPU's. > > I am an expert in scaling alpha/beta to a large numbers of > > processors (I did this with Socrates on 1836 processors a few > > years ago) but it's different with UCT which is inherently serial. > > > I surely appreciate the difficulties in adapting algorithms to > multiple processors - I may be rusty, but some years ago I > worked on Neuralware and multiple transputers, 860s, and > so forth. It gets a little hairy! > > Hasn't Mogo been parallelized to 4 processors? Can this be > extended to larger numbers? > > Due to the problems with heat dissipation at higher clock cycles, > we'll probably be working with large numbers of processors per > chip in the future, rather than Terahertz uniprocessors. > > > > > __ > Any questions? Get answers on any topic at Yahoo! Answers. Try it now. > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 11:32 -0800, terry mcintyre wrote: > > - Original Message From: Don Dailey <[EMAIL PROTECTED]> > > > > May I ask the range of "number of playouts" tested? > > I'm still curious about this question? I think I started at 64 play-outs, and kept doubling the number of play-outs to some large number where it took an hour to play a single game. I don't currently have the data, but I am willing to reproduce the experiment. Other MC guys can verify it. I'll set it up on a slow computer I have free and I'll start at 64 simulations on a 19x19 board.I'll play 200 games in pairs, 64 vs 128, 128 vs 256, etc. - Don > > Part of my procrastination [ about using 72 processors ] is that > > I'm not sure how to make UCT scale to a large number of CPU's. > > I am an expert in scaling alpha/beta to a large numbers of > > processors (I did this with Socrates on 1836 processors a few > > years ago) but it's different with UCT which is inherently serial. > > > I surely appreciate the difficulties in adapting algorithms to > multiple processors - I may be rusty, but some years ago I > worked on Neuralware and multiple transputers, 860s, and > so forth. It gets a little hairy! > > Hasn't Mogo been parallelized to 4 processors? Can this be > extended to larger numbers? > > Due to the problems with heat dissipation at higher clock cycles, > we'll probably be working with large numbers of processors per > chip in the future, rather than Terahertz uniprocessors. > > > > > __ > Any questions? Get answers on any topic at Yahoo! Answers. Try it now. > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
- Original Message From: Don Dailey <[EMAIL PROTECTED]> > > May I ask the range of "number of playouts" tested? I'm still curious about this question? > Part of my procrastination [ about using 72 processors ] is that > I'm not sure how to make UCT scale to a large number of CPU's. > I am an expert in scaling alpha/beta to a large numbers of > processors (I did this with Socrates on 1836 processors a few > years ago) but it's different with UCT which is inherently serial. I surely appreciate the difficulties in adapting algorithms to multiple processors - I may be rusty, but some years ago I worked on Neuralware and multiple transputers, 860s, and so forth. It gets a little hairy! Hasn't Mogo been parallelized to 4 processors? Can this be extended to larger numbers? Due to the problems with heat dissipation at higher clock cycles, we'll probably be working with large numbers of processors per chip in the future, rather than Terahertz uniprocessors. Have a burning question? Go to www.Answers.yahoo.com and get answers from real people who know.___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : Re : [computer-go] an idea... computer go program's rank vs time
I see what you are saying. Yes, I agree with you that the strength of these programs will decrease exponentially as board sizes increase. By the way, I haven't been offended by any of these messages and I hope I haven't offended anyone either. This is a very interesting conversation to me and I welcome your thoughts and even if I sound too strong I mean no disrespect to anyone. - Don On Fri, 2007-01-26 at 19:05 +, ivan dubois wrote: > You missunderstood my point. However, I admit it was not clear. What i wanted > to say is this : > Given a fixed amount of time, strength of monte-carlo algorithm will decrease > exponentialy when boardsize increases. > It does not mean that monte-carlo does not scale well with time on 19*19. > Of course, it all depends on the referential you use to measure strength. By > the way, it is not a critisism towards UCT : actualy I do think monte-carlo > is the key to build realy strong programs. > I just wanted to state that scaling with computation-time is not the only > thing that matters. Scaling with board size matters too. > It was not another criticism towards you opinion either. > > - Message d'origine > De : Don Dailey <[EMAIL PROTECTED]> > À : computer-go > Envoyé le : Vendredi, 26 Janvier 2007, 19h05mn 40s > Objet : Re: Re : [computer-go] an idea... computer go program's rank vs time > > > On Fri, 2007-01-26 at 13:38 +, ivan dubois wrote: > > However, if you take for example a computer programm that does > > straight UCT (global UCT, with no sub-areas), then i believe it can > > not scale well when board size increases. Because the branching would > > factor increase proportinaly to the size of the board, and therefore > > the computation time for an equivalent search deapth will increase > > exponentialy. > > Any thoughts ? > > This can be tested directly. In my own experiments 19x19 improves very > rapidly in UCT with each doubling of the number of play-outs. > > Of course someone will say, "yes, but that won't continue" and I will > have no way to refute their intuition. > > I am presenting real evidence that it scales at least as far as I > can test, and nobody has presented any evidence whatsoever to the > contrary other than gut feelings. > > - Don > > > > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > > > ___ > Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! > Profitez des connaissances, des opinions et des expériences des internautes > sur Yahoo! Questions/Réponses > http://fr.answers.yahoo.com > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] GTK client OSX and Windows
Does anyone here have experience with the GTK user interface library for Windows or for OSX ? - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] an idea... computer go program's rank vs time
You missunderstood my point. However, I admit it was not clear. What i wanted to say is this : Given a fixed amount of time, strength of monte-carlo algorithm will decrease exponentialy when boardsize increases. It does not mean that monte-carlo does not scale well with time on 19*19. Of course, it all depends on the referential you use to measure strength. By the way, it is not a critisism towards UCT : actualy I do think monte-carlo is the key to build realy strong programs. I just wanted to state that scaling with computation-time is not the only thing that matters. Scaling with board size matters too. It was not another criticism towards you opinion either. - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Vendredi, 26 Janvier 2007, 19h05mn 40s Objet : Re: Re : [computer-go] an idea... computer go program's rank vs time On Fri, 2007-01-26 at 13:38 +, ivan dubois wrote: > However, if you take for example a computer programm that does > straight UCT (global UCT, with no sub-areas), then i believe it can > not scale well when board size increases. Because the branching would > factor increase proportinaly to the size of the board, and therefore > the computation time for an equivalent search deapth will increase > exponentialy. > Any thoughts ? This can be tested directly. In my own experiments 19x19 improves very rapidly in UCT with each doubling of the number of play-outs. Of course someone will say, "yes, but that won't continue" and I will have no way to refute their intuition. I am presenting real evidence that it scales at least as far as I can test, and nobody has presented any evidence whatsoever to the contrary other than gut feelings. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 10:22 -0800, terry mcintyre wrote: > > - Original Message From: Don Dailey <[EMAIL PROTECTED]> > > >This can be tested directly. In my own experiments 19x19 > > improves very rapidly in UCT with each doubling of the > > number of play-outs. > > May I ask the range of "number of playouts" tested? > > > Have you considered taking up David Doshay's offer and running > some multi-computer simulations? With 72 processors whirling > away for a month or so, one could have a lot of interesting data. Yes, David agreed to let me use his system several weeks ago but I have procrastinated due to many other projects and my work schedule not to mention the time I have wasted posting on this group. Part of my procrastination is that I'm not sure how to make UCT scale to a large number of CPU's.I am an expert in scaling alpha/beta to a large numbers of processors (I did this with Socrates on 1836 processors a few years ago) but it's different with UCT which is inherently serial. I am also considering doing a public huge UCT scalability study with 19x19 go. My idea is for several programs to set their program up to a "fixed" level (n play-outs) and set up a CGOS server with really long time controls.But I want to just get a normal 19x19 server running first. > Btw, how are your experiments with D coming along? Is it becoming > competitive, performance-wise, with C or C++? D is a lovely language but the current compilers generate code that is too slow for my taste.I think this situation will improve in the future and I will keep my eye on D. There is no reason I am aware of that D cannot run as fast as C. - Don > > > __ > We won't tell. Get more on shows you hate to love > (and love to hate): Yahoo! TV's Guilty Pleasures list. > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
- Original Message From: Don Dailey <[EMAIL PROTECTED]> >This can be tested directly. In my own experiments 19x19 > improves very rapidly in UCT with each doubling of the > number of play-outs. May I ask the range of "number of playouts" tested? Have you considered taking up David Doshay's offer and running some multi-computer simulations? With 72 processors whirling away for a month or so, one could have a lot of interesting data. Btw, how are your experiments with D coming along? Is it becoming competitive, performance-wise, with C or C++? It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 13:38 +, ivan dubois wrote: > However, if you take for example a computer programm that does > straight UCT (global UCT, with no sub-areas), then i believe it can > not scale well when board size increases. Because the branching would > factor increase proportinaly to the size of the board, and therefore > the computation time for an equivalent search deapth will increase > exponentialy. > Any thoughts ? This can be tested directly. In my own experiments 19x19 improves very rapidly in UCT with each doubling of the number of play-outs. Of course someone will say, "yes, but that won't continue" and I will have no way to refute their intuition. I am presenting real evidence that it scales at least as far as I can test, and nobody has presented any evidence whatsoever to the contrary other than gut feelings. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
I second Mark Boon's comment. On 1/26/07, Mark Boon <[EMAIL PROTECTED]> wrote: Am I the only one who got tired of this rather pointless discussion a hundred messages ago? I also can't help feeling that the tone of the discussion tends to get such that it can easily be mistaken for lack of respect for each other. Can we get back to more mundane issues, like how MC scales to 13x13 and possibly later to 19x19? Or what other ways we could use connection-machine like hardware? Anything, really. Just a thought. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] an idea... computer go program's rank vs time
Hello. Just my grain of salt : I think it is relevant to consider strength as a a function of time AND board size. I have the feeling that, for humans, board size doesnt matter very much, whereas for computers, depending on the algorithm they use, it can be an extremely important factor. The reason would be that human are very good at breaking the board, mentaly, into mostly unrelated areas. However, if you take for example a computer programm that does straight UCT (global UCT, with no sub-areas), then i believe it can not scale well when board size increases. Because the branching would factor increase proportinaly to the size of the board, and therefore the computation time for an equivalent search deapth will increase exponentialy. Any thoughts ? - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : Nick Apperson <[EMAIL PROTECTED]> Cc : computer-go Envoyé le : Vendredi, 26 Janvier 2007, 14h10mn 08s Objet : Re: [computer-go] an idea... computer go program's rank vs time On Fri, 2007-01-26 at 02:41 -0600, Nick Apperson wrote: > I am not trying to say that you don't know what you are talking about, > but how are you so sure that we must be on the linear part of the > curve? Based on what you said, I estimate your ideal (non empirical) > formula to be something like the following: > > S = P * (1 - e^-kt) > > where S is skill level and P is perfect play and k is some constant > specific to the game. In fact this is an ideal formula that should > apply given the reasonable assumption that the chance of reading one > unit of skill is proportional to the amount of time taken and the > amount left to be seen. This makes sense assuming a very specific > distribution of the difficulties of different items that can be seen. > That distrobution would have to have all units capable of being seen > as equally likely to be seen. I think this could be a good > theoretical model. > > > Anyway, I would like to see you make more specific claims with formula > and justifications for them. Vague statements about linear > relationships that taper off and how we are clearly not anywhere near > the top help nobody. You seem to know a lot about this. I would > appreciate it if you would share your reasoning. You seem pretty > skeptical of intuition. So, what is the reason you believe these > things about go? Here is why I feel as I do and where I think the burden of proof is: All computer games of perfect information that I am aware of follow this curve. Chess, checkers, Armimaa, Othello, Go and others. So it seems to have nothing to do with the branching factor of the game. This curve is shown to also be true (even more-so) in HUMAN play, at least in Chess and anywhere from a fraction of a second per move to postal chess. >From a perfectly logical point of view, what is the most reasonable conclusion to come to about this? Furthermore, I have anecdotal evidence (which you should always be skeptical of but I present nonetheless) that strong human players are not good judges in these matters because their ego's are involved. In Chess, there were some more humble players who understood the curve right away but they were the minority. In short, strong players will generally take the point of view that their game is not subject to mere computation, but to skill which only they possess. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
On Fri, 2007-01-26 at 02:41 -0600, Nick Apperson wrote: > I am not trying to say that you don't know what you are talking about, > but how are you so sure that we must be on the linear part of the > curve? Based on what you said, I estimate your ideal (non empirical) > formula to be something like the following: > > S = P * (1 - e^-kt) > > where S is skill level and P is perfect play and k is some constant > specific to the game. In fact this is an ideal formula that should > apply given the reasonable assumption that the chance of reading one > unit of skill is proportional to the amount of time taken and the > amount left to be seen. This makes sense assuming a very specific > distribution of the difficulties of different items that can be seen. > That distrobution would have to have all units capable of being seen > as equally likely to be seen. I think this could be a good > theoretical model. > > > Anyway, I would like to see you make more specific claims with formula > and justifications for them. Vague statements about linear > relationships that taper off and how we are clearly not anywhere near > the top help nobody. You seem to know a lot about this. I would > appreciate it if you would share your reasoning. You seem pretty > skeptical of intuition. So, what is the reason you believe these > things about go? Here is why I feel as I do and where I think the burden of proof is: All computer games of perfect information that I am aware of follow this curve. Chess, checkers, Armimaa, Othello, Go and others. So it seems to have nothing to do with the branching factor of the game. This curve is shown to also be true (even more-so) in HUMAN play, at least in Chess and anywhere from a fraction of a second per move to postal chess. >From a perfectly logical point of view, what is the most reasonable conclusion to come to about this? Furthermore, I have anecdotal evidence (which you should always be skeptical of but I present nonetheless) that strong human players are not good judges in these matters because their ego's are involved. In Chess, there were some more humble players who understood the curve right away but they were the minority. In short, strong players will generally take the point of view that their game is not subject to mere computation, but to skill which only they possess. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
here's my attempt to talk about how a 9x9 algorithm should be expected to scale on a bigger board, and what limits we can expect to have on perfect algorithms. i'm kind've trying to bridge the divide here. maybe it's silly. hopefully the experts can correct me. saying that doubling computer time won't result in a constant increase in skill at any particular task is another way of saying that there is a good exponential approximation to the effort function E(s) over some particular range (say, the early skill levels), but that after some point the effort function function will increase *more quickly* than the exponential approximation. (here E(s) is the effort for a particular algorithm to play at least as well as skill level "s".) one somewhat muddying fact is that both chess and go should belong to EXPTIME. this means that to find a winning move for a fixed board position at a fixed boardsize n will require O(2^p(n)) steps, where p is a polynomial in n. to play either game "perfectly" such that the algorithm would apply to a 19x19 board, or a 9x9 board, or a 13x13 board, or an NxN board would imply that you had constructed an algorithm with at least such a running time. Lets imagine that 9x9 go has been effectively* solved by some algorithm that we all love, called algorithm X. applying algorithm X unchanged to boardsize 13x13, we will find that it takes: 2^(p(13)) / 2^(p(9)) times longer to find "the best move" for a given board position. taking the log base 2 of this we find that the difference in the doubling constants between the different boardsizes is: p(13) - p(9) if the polynomial in question is linear, then we will still observe the same doubling phenomenon for a 13x13 board as we would have on a 9x9 board. if the polynomial in question is anything other than linear, we won't, although depending upon the coefficients involved in this term and smaller terms, it may be well-approximated, again, through some number of skill levels. mitigating factors: *effectively solved is my hand-waving way of not dealing with the fact that solving the game and winning against opponents of some fixed skill level are not the same problem. what this additionally means is that any algorithm with enough _encoded knowledge_ that applies to a fixed boardsize can play arbitrarily well (note that this neatly captures the case of a pure lookup table solution). so we have two competing ideas: one is that if i double the thinking time for my existing algorithm that works quite well at size 9 and get linear improvement, what will happen to the improvement for that unmodified algorithm on a larger board? the answer is that it will definitely get better, although it may no longer gain the same amount of strength with each doubling of cpu time, or for as far across the skill level range. the other idea is that if i encode enough knowledge about details that apply to one particular boardsize into my algorithm, i can reduce its running time by an arbitrary amount. an example would be a joseki library for 19x19 boards that wouldn't have existed (or even made sense) in the same form in the code of a 9x9 program. so anyone looking for an analytic solution that will perfectly solve go needs to cope with the fact that if it works great (in the running-time sense) for a 9x9 board, it might work quite a bit less well for a 13x13 board, and significantly less well for a 19x19 board. with no knowledge about the size of the _coefficients_ of the terms in the complexity function, the possibility still exists that for the board sizes in question, the complexity is dominated by terms much smaller than 2^p(n), and so all boardsizes and skill levels are easily approximated with the 'doubling technique' until n is large. s. Get your own web address. Have a HUGE year through Yahoo! Small Business. http://smallbusiness.yahoo.com/domains/?p=BESTDEAL ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Am I the only one who got tired of this rather pointless discussion a hundred messages ago? I also can't help feeling that the tone of the discussion tends to get such that it can easily be mistaken for lack of respect for each other. Can we get back to more mundane issues, like how MC scales to 13x13 and possibly later to 19x19? Or what other ways we could use connection-machine like hardware? Anything, really. Just a thought. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote: On Thu, 2007-01-25 at 20:16 -0600, Matt Gokey wrote: > Don Dailey wrote: > > You are still missing the point. > I can say the same of you. > > I merely am raising a question about the assertion that doubling of > _human_ thinking time results in _linear_ improvements. I am not > claiming that there is no improvement - never have. I am not claiming > that every turn must produce better results to improve overall play - > never have. However I am trying to explain a rationale for the > possibility that improvements may not be linear based on the nature of Go. It's possible, but I think my curve (it is a curve, it gradually tapers off as you get closer to perfection which is an obvious limit) holds in all non-trivial games of perfect information. The curve may have a different shape or slope but it's there. It's already easy to produce in computer go despite a reluctance by many (not you of course) to admit it. My sense is that many on this group want to believe that we just happen to be at the top of the curve but that it immediately falls off. There is no rational reason to believe that other than superstition. I am not trying to say that you don't know what you are talking about, but how are you so sure that we must be on the linear part of the curve? Based on what you said, I estimate your ideal (non empirical) formula to be something like the following: S = P * (1 - e^-kt) where S is skill level and P is perfect play and k is some constant specific to the game. In fact this is an ideal formula that should apply given the reasonable assumption that the chance of reading one unit of skill is proportional to the amount of time taken and the amount left to be seen. This makes sense assuming a very specific distribution of the difficulties of different items that can be seen. That distrobution would have to have all units capable of being seen as equally likely to be seen. I think this could be a good theoretical model. Anyway, I would like to see you make more specific claims with formula and justifications for them. Vague statements about linear relationships that taper off and how we are clearly not anywhere near the top help nobody. You seem to know a lot about this. I would appreciate it if you would share your reasoning. You seem pretty skeptical of intuition. So, what is the reason you believe these things about go? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
