Re: [computer-go] Simplified MC evaluator ¿explained?
The second explanation was no clearer to me. I'll try to criticize in more detail: 1. Uniform playouts, as used in practice, are not really uniform over all legal go moves. Generally, pass moves are excluded until necessary, and moves that fill eyelike points are excluded. So, I assume that when you use the word legal, you mean admissible within this sort of playout. 2. That variance depends on the length of the playout. It is difficult for me to make sense of this statement, simply because not all playouts from a given position have the same length. My best guess is that you are claiming that the longer a playout is, the more likely it is that its result differs from the result under correct play. However, I strongly doubt that this is true for all starting positions. (Imagine that the first player needs to prevent the second player from forming two eyes in a large group. After doing this, that group will eventually be captured, allowing playouts to continue longer by filling the intersections that it once occupied. Failing to kill this group may allow the playouts to complete much more quickly, but gives inaccurate results.) 2.5. The variance of the stochastic process is not to be mixed up with the distribution of the error of a repeated Bernoulli experiment! Perhaps I have mixed them up. Can you explain more clearly or precisely what the variance of the stochastic process is? Do you perhaps mean some measurement of variation across different starting points, rather than across different Bernoulli trials from the same starting position? Or, do you mean to distinguish the probability that a playout's outcome differs from the outcome under correct play, from the probability that a playout results in a win? (Although those are just two different Bernoulli experiments, right?) Or is there some subtlety that I have missed? 3. 'p is a biased towards 1/2 estimator of W'. Consider the game: o / \ o o / \ | 1 0 0 (1 is a win by the first player, and 0 is a loss.) There is a move that could allow the first player to win, if the second player does not respond to it correctly. This sounds like a realistic scenario for go. W = 1/3 p = 1/4 p is further from 1/2 than W. Does this game violate the condition that the number of legal moves for each side is balanced? (It is still not clear to me what this condition is that you are attempting to impose.) Or, was I supposed to calculate a statistic across multiple game trees where W=1/3, in order to interpret p as an estimator of W? 4. Even if we can compute W exactly, do we have any reason to think that its value is a good estimate of the minimax value of the game? Is it even a better estimate than p, which we can already estimate accurately? (Note that in the game tree above, it is not.) My offhand guess is that it would not be as good. Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
On 4/8/07, Don Dailey [EMAIL PROTECTED] wrote: These programs, in theory, will play perfect GO given enough time. ... and space. I doubt that your current programs would be capable of storing a large enough game tree to actually converge to the alpha-beta value. So in practice, it really would level out somewhere below optimal play, unless you also increase the memory usage, right? I think that it is still valid to present your chart as representing the lower portions of curves that do not do this, because you would presumably scale up the amount of memory used as well as the time, if you could. Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
On Mon, 2007-04-09 at 05:30 -0400, Weston Markham wrote: On 4/8/07, Don Dailey [EMAIL PROTECTED] wrote: These programs, in theory, will play perfect GO given enough time. ... and space. I doubt that your current programs would be capable of storing a large enough game tree to actually converge to the alpha-beta value. So in practice, it really would level out somewhere below optimal play, unless you also increase the memory usage, right? I think that it is still valid to present your chart as representing the lower portions of curves that do not do this, because you would presumably scale up the amount of memory used as well as the time, if you could. Weston Yes, you would need more time and memory. But the point is that as long as you can provide time and memory you will get improvement until perfect play is reached. But if it's true that heavy is increasing faster, that will proabably stop being the case MUCH sooner. They will both likely approach perfect play on a very similar slope (like a jet coming in for a landing) which means the distance beetween the two plot lines must start getting closer much sooner. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
Don, here is a question. Your curves plotted the playing level vs the computer speed. By computer speed you mean the number of MC simulations per node with all other factors fixed. Is this correct? If it is, it's legitimate for people to speculate that the curve could level off beyond some number of simulations per node. Actually this is an important question, because it relates to the nature of the MC simulation. Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Cc: computer-go@computer-go.org Sent: Mon, 9 Apr 2007 7:06 AM Subject: Re: [computer-go] The physics of Go playing strength. On Mon, 2007-04-09 at 05:30 -0400, Weston Markham wrote: On 4/8/07, Don Dailey [EMAIL PROTECTED] wrote: These programs, in theory, will play perfect GO given enough time. ... and space. I doubt that your current programs would be capable of storing a large enough game tree to actually converge to the alpha-beta value. So in practice, it really would level out somewhere below optimal play, unless you also increase the memory usage, right? I think that it is still valid to present your chart as representing the lower portions of curves that do not do this, because you would presumably scale up the amount of memory used as well as the time, if you could. Weston Yes, you would need more time and memory. But the point is that as long as you can provide time and memory you will get improvement until perfect play is reached. But if it's true that heavy is increasing faster, that will proabably stop being the case MUCH sooner. They will both likely approach perfect play on a very similar slope (like a jet coming in for a landing) which means the distance beetween the two plot lines must start getting closer much sooner. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
On Mon, 2007-04-09 at 14:46 +0100, Tom Cooper wrote: Perhaps it would be possible to infer how the lines would look as perfect play was approached from what the curves looked like for a smaller board size. I thought that too, but the studies on 5x5 and 7x7 break down very quickly. The problem is that the programs already play close to perfect on these board sizes. I can say that because on 7x7 using a fractional komi, either white wins most of the games or black, depending on how you set komi. - Don At 13:06 09/04/2007, Don wrote: On Mon, 2007-04-09 at 05:30 -0400, Weston Markham wrote: On 4/8/07, Don Dailey [EMAIL PROTECTED] wrote: These programs, in theory, will play perfect GO given enough time. ... and space. I doubt that your current programs would be capable of storing a large enough game tree to actually converge to the alpha-beta value. So in practice, it really would level out somewhere below optimal play, unless you also increase the memory usage, right? I think that it is still valid to present your chart as representing the lower portions of curves that do not do this, because you would presumably scale up the amount of memory used as well as the time, if you could. Weston Yes, you would need more time and memory. But the point is that as long as you can provide time and memory you will get improvement until perfect play is reached. But if it's true that heavy is increasing faster, that will proabably stop being the case MUCH sooner. They will both likely approach perfect play on a very similar slope (like a jet coming in for a landing) which means the distance beetween the two plot lines must start getting closer much sooner. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- This email has been verified as Virus free Virus Protection and more available at http://www.plus.net ___ 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] Noise reduction in alpha-beta search
I think following is a way to reduce the noise in alpha-beta search. Instead of using the evaluation values, use the cummulative evaluation values. That is the sum of the evaluation values of each node of the playing path under examination. Daniel Liu AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] LISP question (littlle bit off topic)
On Sun, Apr 08, 2007 at 10:18:10AM +0200, Chrilly wrote: Paper 1 in the list below states: Numbers were originally implemented in Lisp I as a list of atoms. and the Lisp 1.5 manual states: Arithmetic in Lisp 1.5 is new Could you give an example how the number 3 was implemented in Lisp-1 and how 2+1? I don't know, but from the description list of atoms, perhaps numbers were represented as linked lists of bits (using the facilities built in to support linked lists of anything). On Apr 7, 2007, at 12:54 PM, Chrilly wrote: Up to my knowledge the first Lisp Versions had no number system. The number n was represented as the list of numbers from 1 to n (which is also the mathematical/axiomatic definition of the natural numbers). But its not very practical. Can anyone provide me with a link how this was done. I am speaking some computer languages, but Lisp is not among them. I want to present the code in an article for the Austrian AI- Journal (as an example that mathematical elegance and practically usefull are 2 different things). Note how early this was in computer hardware development, and how it didn't take them long (in calendar years) to introduce more efficient representations of numbers. I think quite possibly it was not an instance of people choosing elegance at the expense of practicality, but an instance of practical people imposing very severe limitations on software features because of the hardware limitations of early machines. It wasn't all that far away (in calendar years) from the time when people programmed Chess on a 6x6 board, right? I doubt that that early 6x6 Chess program is good evidence that its computer programmers didn't care about playing Chess by standard rules... -- William Harold Newman [EMAIL PROTECTED] PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C Ubi saeva indignatio ulterius cor lacerare nequit. -- Jonathan Swift's epitaph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to MoGoBot and to StoneCrazy!
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Apr 9, 2007, at 19:36 , Nick Wedd wrote: I have written a short report on yesterday's bot tournament on KGS, it is at http://www.weddslist.com/kgs/past/25/index.html In the General Section you are referring to version 5 of HouseBot. That should be 0.5. BTW, thanks for organizing all the tournaments and the write-ups afterwards. Urban - -- http://bettong.net -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (Darwin) iD8DBQFGGm8HggNuVCIrEyURAvwFAJ0U87YtbFXwERqvIQQ2EOTS6c5nZwCeKH3q H9K/HohiRok7JU8BiBcrzis= =M3Uq -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: LISP question (littlle bit off topic)
I don't know, but from the description list of atoms, perhaps numbers were represented as linked lists of bits (using the facilities built in to support linked lists of anything). I don't believe that any non-toy version of lisp ever used anything as ineffecient as representing numbers as lists of bits. In early lisp implementations, all data are presumed to be pointers to structures. The address space (usually 16 or 18 bits in those days) was partitioned so that some range of addresses was used to represent integers, so for example pointers with values 0-255 represented integers from -128 to 127. Real pointers all had values greater thatn 255. Integers ouside of the small range were represented by real pointers to structures whose type and organization was determinable by inspection. To do arithmetic, you'd first check (and hope for) the reserved range of addresses, then interpret the data structure to retrieve the actual values of larger integers. Perform your arithmetic, then reverse the process (including allocating memory to represent results out of the small range). With no compiler at all, as was the case in the earliest systems, this was obviously horribly ineffecient. As compiler technology improved, it gradually became true that usual cases like multiplying two integers were only 10x or so less effecient than executing on the raw hardware. Really good compilers can now do better than that. .. then of course there were lisp machines, which put all the type checking in the hardware, so ordinary arithmetic ran at full hardware speed. Symbolics lisp machines had 44 bit word size, which represented 32 bit integers directly. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Absolute time in KGS robots
On Mon, 2007-04-09 at 17:36 +0100, Nick Wedd wrote: I have written a short report on yesterday's bot tournament on KGS, it is at http://www.weddslist.com/kgs/past/25/index.html From the writeup: CrazyStone has achieved an implausible 1k rating on KGS. Yes, very implausible. It has only played a handful of ranked 19x19 games. It won two games against a 2k on time in which CrazyStone was getting beaten badly. The time settings were 10 minutes absolute for each side. Absolute time games are bad, at least for humans. Why not have at least a 5 or 10 second byo-yomi for bot vs human games? -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: LISP question (littlle bit off topic)
.. then of course there were lisp machines (brain short circuits as sparks fly and magic smoke is released.) s. TV dinner still cooling? Check out Tonight's Picks on Yahoo! TV. http://tv.yahoo.com/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
Le lundi 9 avril 2007 14:06, Don Dailey a écrit : But the point is that as long as you can provide time and memory you will get improvement until perfect play is reached. Is there any proof that heavy player converge toward the same solution as the pure random playout ? With infinite resource, i agree that random playout will find the best move. But it seems that nothing is guaranted for heavy playout. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
On Tue, 2007-04-10 at 00:06 +0200, alain Baeckeroot wrote: Le lundi 9 avril 2007 14:06, Don Dailey a écrit : But the point is that as long as you can provide time and memory you will get improvement until perfect play is reached. Is there any proof that heavy player converge toward the same solution as the pure random playout ? I don't really know, but I suspect it converges as long as you score correctly at the end of the game. If you don't score correctly, then I suppose anything can happen. - Don With infinite resource, i agree that random playout will find the best move. But it seems that nothing is guaranted for heavy playout. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
On 4/10/07, alain Baeckeroot [EMAIL PROTECTED] wrote: Le lundi 9 avril 2007 14:06, Don Dailey a écrit: But the point is that as long as you can provide time and memory you will get improvement until perfect play is reached. Is there any proof that heavy player converge toward the same solution as the pure random playout ? With infinite resource, i agree that random playout will find the best move. But it seems that nothing is guaranted for heavy playout. With infinite resources the MC part won't have to make any move (heavy or light), so it does not matter. OC, this is all just theoretical throughout most of the game for any board of reasonable size. BTW pure random would fill it's own eyes... E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
With infinite resource, i agree that random playout will find the best move. But it seems that nothing is guaranteed for heavy playout. As Don pointed out before, the reason it converges to perfect play is because of the UCT part, not because of the playout part. If the playout part prunes some moves, nothing is guaranteed. I believe the point is that UCT never prunes moves. The playouts performed at UCT leaf nodes are just to give an estimate to help UCT decide which part of the tree to explore next. I.e. heavy vs. light playouts are like intelligent vs. random move ordering in alpha-beta. Darren -- Darren Cook http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary) http://dcook.org/work/ (About me and my work) http://dcook.org/work/charts/ (My flash charting demos) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
With a badly designed play-out algorithm you may have a horribly inefficent search - but it would eventually still find the best move in principle. - Don On Tue, 2007-04-10 at 09:16 +0900, Darren Cook wrote: With infinite resource, i agree that random playout will find the best move. But it seems that nothing is guaranteed for heavy playout. As Don pointed out before, the reason it converges to perfect play is because of the UCT part, not because of the playout part. If the playout part prunes some moves, nothing is guaranteed. I believe the point is that UCT never prunes moves. The playouts performed at UCT leaf nodes are just to give an estimate to help UCT decide which part of the tree to explore next. I.e. heavy vs. light playouts are like intelligent vs. random move ordering in alpha-beta. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] CGOS viewer update
I just updated the viewer again to version 0.31 I will not longer announce client updates unless they address a serious bug or problem or amazing new functionality Instead, I will give the latest version number on the CGOS webpage. In this case, there is probably no need to upgrade. The only difference is that it can take 1 or 2 optional arguments, the name of a server and a port number. This is to aid those behind a firewall and was done by request. cgosview ServerName PortNumber Of course if you leave the arguments off it defaults to cgos.boardspace.net 6867 - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Don Dailey wrote: (snip) In my opinion, the insight that Chrilly articulated was that all of sudden we are now all using some type of global search - the very idea was considered blasphemy just 2 or 3 years ago. That may be too strong a statement. It may have not been popular but many people consistently believed global search must be a big part of any strong playing program, myself included. Not searching using the same techniques as used for chess, but IMO certainly searching has not ever been altogether dismissed nor considered blasphemy. Look back at posts around 10 years ago (when I first joined the list) and probably since its inception and you'll find this to be true. I personally wrote about it on several occasions suggesting that to counter the evaluation problem the search needed to go very deep and even talked about sampling the tree. Other probability based searches have been studied and written about in academic papers and on this list as well. The crucial combination of techniques didn't bubble up, but not for lack of trying. But I have to admit that personally, I have many more ideas than time with a full time job. Over the last 10 years all I've really done is play around with various algorithms and ideas, study the game of go, collect and read a lot of published papers, and keep up on this list - occasionally posting. My wife still doesn't understand my putting this much time into it! ;-) This is the kind of thing that could consume a person. I don't know if particular ideas would pay off or not because I haven't been able to put in the proper time to focus. In spare time, on and off over the years I've only done a few experiments and algorithms mostly focused on partitioning, goal directed and hierarchical searching methods. This negligible computer-go work, some plans and a few ideas is the extent of my would-be program KatanaGo. Regardless, it has been great fun watching the progress of computer-go over the years and the current flurry of activity with MC/UCT is quite exciting! As I wrote in a post in early Feb of this year (paraphrasing from memory), I think the main reason MC/UCT works is because it goes deep (nearly always to the end) and tends to find paths with more favorable possibilities and more importantly avoid paths littered with problems. Though I'm still pretty amazed by how well it plays, but that's the power of the law of large numbers at work. Correct? As for the point that different paths may converge on similar methods, I agree that could be very plausible scenario, but there is a very long way to go yet... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
Erik van der Werf wrote: On 4/10/07, alain Baeckeroot [EMAIL PROTECTED] wrote: Le lundi 9 avril 2007 14:06, Don Dailey a écrit: But the point is that as long as you can provide time and memory you will get improvement until perfect play is reached. Is there any proof that heavy player converge toward the same solution as the pure random playout ? With infinite resource, i agree that random playout will find the best move. But it seems that nothing is guaranted for heavy playout. With infinite resources the MC part won't have to make any move (heavy or light), so it does not matter. OC, this is all just theoretical throughout most of the game for any board of reasonable size. BTW pure random would fill it's own eyes... The benefit that MC/UCT has is that it can be stopped any time and get a reasonable current selected move. The probability that it will find better moves tends to increase with more resources/playouts. But wouldn't a simple brute force search of the game tree be more efficient than MC/UCT at finding the certain best move, given the hypothetical hyper super computer we are talking about? So if ever this hyper computer exists with near infinite speed and resources we can just run a methodical brute force search and be done with it. Why would one bother running a googolplex random simulations to approach perfect play? So to be practical we have to find ways to improve the search beyond pure scalability like the MoGo developers are doing. Does this make sense? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
