RE: Re: [computer-go] computer Go article in The Economist
Dear all, In the Economist, two Hungarian guys are mentioned. Do you guys know who they are? Do they have a website? Thank you in advance! Yours truly, Tae-Hyung ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re: [computer-go] computer Go article in The Economist
Hello, I think that they are the authors of the UCT algorithm, so L. Kocsis and C. Szepesvari. Regards, Sylvain 2007/1/30, tk424 [EMAIL PROTECTED]: Dear all, In the Economist, two Hungarian guys are mentioned. Do you guys know who they are? Do they have a website? Thank you in advance! Yours truly, Tae-Hyung ___ 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] computer Go article in The Economist
In message [EMAIL PROTECTED], Sylvain Gelly [EMAIL PROTECTED] writes Hello, I think that they are the authors of the UCT algorithm, so L. Kocsis and C. Szepesvari. and their paper is at http://zaphod.aml.sztaki.hu/papers/ecml06.pdf Nick Regards, Sylvain 2007/1/30, tk424 [EMAIL PROTECTED] : Dear all, In the Economist, two Hungarian guys are mentioned. Do you guys know who they are? Do they have a website? Thank you in advance! Yours truly, Tae-Hyung ___ 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/ -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] IEEE Computer article
Found a recent article on computer Go in the IEEE Computer journal. pdf here: http://csdl2.computer.org/comp/mags/ex/2007/01/x1005.pdf The author is Jan Krikke. title The Challenge of Go Terry McIntyre [EMAIL PROTECTED] The fish are biting. Get more visitors on your site using Yahoo! Search Marketing. http://searchmarketing.yahoo.com/arp/sponsoredsearch_v2.php___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Computer article
That was a well written article. Too often you see articles written with cliches copied from other sources but this one was refreshing - although written in laymen terms. - Don On Tue, 2007-01-30 at 06:28 -0800, terry mcintyre wrote: Found a recent article on computer Go in the IEEE Computer journal. pdf here: http://csdl2.computer.org/comp/mags/ex/2007/01/x1005.pdf The author is Jan Krikke. title The Challenge of Go Terry McIntyre [EMAIL PROTECTED] __ Food fight? Enjoy some healthy debate in the Yahoo! Answers Food Drink QA. ___ 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] Is skill transitive? No.
On Mon, 2007-01-29 at 23:17 -0600, Matt Gokey wrote: 1. Game playing skill is a function of time. 2. Memory (or knowledge) can proxy for time - saving enormous amounts of time in many cases. 3. Technique is a function of knowledge and how it's organized - which translates to a big time savings indirectly. This is really the ability to apply knowledge. 4. Because these various aspects of game playing ability can be mixed and matched, you are sure to get very interesting intransitives. (snip) I agree this is quite reasonable and very well said. The intransitive nature of ratings for players in complex games is evident. Much of what you are describing accurately reflects my understanding and explains in another way what I was trying to express earlier. Let me take this reasoning a little further. Rating systems - yes they are one dimensional whereas reality strength is very much multi-dimensional. Ratings are not perfect, but do pretty good job especially for widely disparate ratings which rarely exhibit intransitivity. Where widely disparate could be defined as whatever rating difference is needed to achieve a, let's say, 99% win rate between the higher and lower rated player. It would be interesting if it would be possible to construct a 2 dimensional model statistically. A 2 dimensional system would not be a perfect fit either, but would simply be a better approximation.So in some way a players strength could be expressed by 2 numbers instead of 1, and the 2 numbers together would predict your chances of beating another (2 dim) player more accurately that a 1 dimension system could. And of course you could extend this. But I don't have a clue how one would construct such a system or if it's even possible - but it seems like more information should be better than less. #1 - I completely agree with this; it is only the curve that is different and in question for each type of player and individual player. #2 #3 - These are exactly what I was referring to and especially I think apply in Go to a significantly greater extent than many other games. This is primarily because there is no relatively simple and reliable evaluation method in conjunction with the huge branching factors and deep play. Other games mentioned such as Chess, Checkers, Armimaa, Othello for example have simpler evaluations that work. #4 - I completely agree. Now with regard to #2 and #3, if these can be substitutes for enormous amounts of time, which usually must be learned over whole games and real experience (this is what I understand as 'enormous amounts of time'), doesn't this support my position? When you say 'enormous amounts of time' are you talking about a few doublings of thinking time over one move or more like weeks or months of practice and experience and study, etc.? With humans, a few days of studying a position probably leads directly to becoming a better player with permanent benefits. However, I would prefer to isolate this from the picture. An inflexible but scalable program might improve with thinking time, but it doesn't benefit permanently. In other words, it won't help the program play the next game better. (But I will conjecture that a properly designed god program probably would be picking up skill every time it makes a move.) I believe that in principal you play a complete game better on the average with more thinking time and this scales naturally. Of course I went to great lengths to make the point that even in a human lifetime you don't have very many doublings to work with (that allow you to play a single game) so you cannot expect to be able to play pro level if you not just a few stones away already.And I believe that this is even worse because of the scaling properties of different algorithms, including the various human algorithms (where stronger players have a different playing algorithm in some sense of the word.)It's even stronger with computer go (and even computer chess it's true.) In computer chess, programs that run faster tend to be significantly stronger than other programs, but they seem to improve a bit less against humans. I believe there is a mathematical way to model this. I have considered trying to build a pseudo game simulation where I could specify all these factors to get a better feel for this.It wouldn't be a real game, but it would have some number of moves, a probability of making an error and a variable to determine the seriousness of the error and perhaps I could divide game playing skill into 100 different categories, so that you could abstractly create players with different degrees of skill in different areas of the game (perhaps phases of the game for instance.)A purely mathematical system where I could create intransitives and run matches etc. Perhaps some insights could be gained here. The scalability experiment you
Re: [computer-go] Is skill transitive? No.
On 29, Jan 2007, at 9:17 PM, Matt Gokey wrote: I wrote: In computer-go where there are so many wildly different techniques being used, some scalable to some degree or another and some not, it doesn't make sense to make generalizations. Whether a specific program's scalability results in any improvements (linear or otherwise) with time-doubling depends entirely on the algorithms and techniques in use. Of course we all know many computer-go programs don't scale extremely well. MC Go (and variants) scale fairly well but probably need a lot more knowledge and probably other methods built into them to become good as MoGo is showing. But this doesn't really say anything about human play. In fact, since Go would not succumb to standard game-search techniques, most computer-go programs used fairly simplistic models, pattern matching, combined with some reading - roughly attempting to emulate certain aspects of human play. So I thought of another way to express some of what I was thinking. Humans play kind of like GNU Go only lots better and can think beyond what they've learned and learn as they play. GNU Go can't get dramatically better by thinking longer, only modestly better. Instead GNU Go must learn (i.e. be programmed with knowledge/ techniques - #2 and #3) to get that much better (no offense to the GNU Go team). Matt, I think your statements, particularly the ones above, are the most accurate. Not that Don is wrong, just that I think he is over- focused upon methods that do scale better. First, as a human player I very definitely feel that I can improve a few specific moves somewhat with perhaps one doubling of my time, but after that my mind just fills up and I cannot get any better by myself, even if I recognize and understand immediately when a stronger player shows me a better move. But on my own, after a few minutes I just am not going to find anything new. Second, with respect to computer algorithms (and I know that the primary thrust of your argument was NOT directed towards computer Go) I think that SlugGo shows rather well that some algorithms do not scale well. SlugGo gives GNU Go about 72 times as much thinking, and while it could be argued that some of our heuristics and evaluation functions sometimes lead us to make worse moves, in a statistical sense when SlugGo decides to make a move that GNU Go considered to have a lower value, it is often correct that it is a better move (even if rarely the best from the view of a good human). SlugGo is at best 2 stones stronger than GNU Go against a third opponent. Don's curve does hold much better when SlugGo plays GNU Go, where we have seen that we can get SlugGo to beat GNU Go with 7 handicap stones with enough lookahead time. Cheers, David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is skill transitive? No.
From: David Doshay [EMAIL PROTECTED] I think that SlugGo shows rather well that some algorithms do not scale well. SlugGo gives GNU Go about 72 times as much thinking, and while it could be argued that some of our heuristics and evaluation functions sometimes lead us to make worse moves, in a statistical sense when SlugGo decides to make a move that GNU Go considered to have a lower value, it is often correct that it is a better move (even if rarely the best from the view of a good human). SlugGo is at best 2 stones stronger than GNU Go against a third opponent. Don's curve does hold much better when SlugGo plays GNU Go, where we have seen that we can get SlugGo to beat GNU Go with 7 handicap stones with enough lookahead time. --- my comment: This is why, much as I appreciate the value of the scalability study now being done, in which I am participating, it will be even more valuable to run a study against a variety of opponents. Of course that is easier said than done, alas. There are some efforts, such as the Home SETI search, which make it easier to recruit people to volunteer spare computer cycles. It will take a good bit of effort to set things up, but once done, the process seems to be fairly automatic. Cheap talk? Check out Yahoo! Messenger's low PC-to-Phone call rates. http://voice.yahoo.com___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is skill transitive? No.
On Tue, 2007-01-30 at 10:16 -0800, David Doshay wrote: Second, with respect to computer algorithms (and I know that the primary thrust of your argument was NOT directed towards computer Go) I think that SlugGo shows rather well that some algorithms do not scale well. SlugGo gives GNU Go about 72 times as much thinking, and while it could be argued that some of our heuristics and evaluation functions sometimes lead us to make worse moves, in a statistical sense when SlugGo decides to make a move that GNU Go considered to have a lower value, it is often correct that it is a better move (even if rarely the best from the view of a good human). SlugGo is at best 2 stones stronger than GNU Go against a third opponent. Don's curve does hold much better when SlugGo plays GNU Go, where we have seen that we can get SlugGo to beat GNU Go with 7 handicap stones with enough lookahead time. But my understanding is that SlugGo is like Botnoid, it improves to a point but isn't truly scalable. A truly selective program cannot be scalable unless it is selective in an admissible way. I think SlugGo is a true selective search program right? Computer chess programs are called selective, but they are really what I call progressively full width. They prune more aggressively near leaf nodes but as they iterate to deeper levels, those same nodes start looking more like root nodes than leaf nodes and get more and more consideration.If any of these pruned moves turns out to be best, it is guaranteed to be eventually discovered. Thus it's scalable. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is skill transitive? No.
I have been thinking lately in terms of building a turn based server than logs in, grabs a set of positions to process, your program processes them off-line, you log back in and report your moves. This sounds real simple, but if you think about the problems involved you realize there are some issues with scheduling that have to be solved. But I think you don't need a time limit - all games are pending and if a program retires there is no foul. (However, for scheduling purposes I think you have to void a game after some period of time - 1 to 4 weeks perhaps.) But beyond this, it's a very simple thing. A client could be provided that handles all the details in a very convenient and simple way. - Don On Tue, 2007-01-30 at 10:52 -0800, David Doshay wrote: It seems it would not be that hard to set up cgos-like environments where participants offer up more than one version of their program: some play quickly, and some are allowed to take longer. ELO levels can be set for some to correspond to mean values obtained on the normal cgos. Cheers, David On 30, Jan 2007, at 10:33 AM, terry mcintyre wrote: This is why, much as I appreciate the value of the scalability study now being done, in which I am participating, it will be even more valuable to run a study against a variety of opponents. Of course that is easier said than done, alas. ___ 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] Re: Scaling monte carlo up to 19x19
Here's an idea for scaling up, which should result in only factor of 10 slower speed. To scale from 9x9 to 19x19, subdivide the board into four, overlapping 10x10 boards. Run a standard 9x9 monte carlo up to the 90% full stage on each of the four boards, then run a full board monte on the whole board remaining. Treat the ovelapping stripes as edges in a slightly more sophisticated way than usual, becuase you might be connecting to liberties by playing in the stripe. To avoid artifacts caused by the location of the overlaps: the number of zones, and the location of the stripes, is also subject to randomization. It might be interesting to try this on a 9x9 board using a 5x5 zone to begin with. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is skill transitive? No.
On Tue, 2007-01-30 at 14:31 -0500, Don Dailey wrote: A truly selective program cannot be scalable unless it is selective in an admissible way. I think SlugGo is a true selective search program right? You can determine if you program is truly scalable with a thought experiment: Would this program play perfect chess given enough time? Botnoid is not scalable, but it does improve rapidly up to a point of severely diminishing returns. But even if there were such a think as an googleplex computer, Botnoid would not play any better than it does as AnchorMan on CGOS. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Scaling monte carlo up to 19x19
At 02:59 PM 1/30/2007, [EMAIL PROTECTED] wrote: I'm having difficulty picturing this, so I'll start with the most basic questions. Do you mean Monte Carlo by itself or Monte Carlo combined with tree search (e.g. UCT)? The idea isn't more than lightly toasted (less than half baked), but the kernal is turn the full board search into set of searches on much smaller boards, using the overlapping strips as boundary conditions, then do some unifying final step to pick the move. Do you mean partition the larger board for the course of each playout (randomizing zones from one to the next) or in some other sense? I imagine you'd want to randomizing the set of zones in the course of the search. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scaling monte carlo up to 19x19
I have an idea in the back of my mind that is an extreme version of this: Divide the board into 361 separate local searches, then use information from these to guide a global search. The local searches would be done on the full board, but would only search for strategies that will capture or defend individual intersections. I suspect that this first phase could potentially benefit from parallelization for a significant portion of the game. Eventually this parallelism will break down because there will only be a limited number of local battles, and the eventual status of points that are in the same chain will almost always be the same. Any practical program would need to deal with this gracefully, of course, rather than duplicate its effort many times. Also, I only have a vague idea of how to take advantage of the information gained from the local searches, when performing the global search. Weston On 1/30/07, Dave Dyer [EMAIL PROTECTED] wrote: The idea isn't more than lightly toasted (less than half baked), but the kernal is turn the full board search into set of searches on much smaller boards, using the overlapping strips as boundary conditions, then do some unifying final step to pick the move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scaling monte carlo up to 19x19
I believe this to be a good idea, but I couldn't get around some minor problems. Essentially, because the local searches are coupled to one another, it ends up exploding as you consider this coupling (scaling to larger regions). You then have to trade accuracy or have more computing power than I have access to... There are cases though where you can find local solutions that are independent in some sense from the rest of the board and the program I am working on now does that. I'm sure someone smarter than me will be able to figure out a better way though. There are certain times when this technique is highly useful. For a simple example, imagine a board with two walls down the middle bordering on each other. In some sense, as long as both those walls live, there are 2 subgames taking place. This type of situation is where I see your approach as being the most useful. Just my thoughts. - Nick On 1/30/07, Weston Markham [EMAIL PROTECTED] wrote: I have an idea in the back of my mind that is an extreme version of this: Divide the board into 361 separate local searches, then use information from these to guide a global search. The local searches would be done on the full board, but would only search for strategies that will capture or defend individual intersections. I suspect that this first phase could potentially benefit from parallelization for a significant portion of the game. Eventually this parallelism will break down because there will only be a limited number of local battles, and the eventual status of points that are in the same chain will almost always be the same. Any practical program would need to deal with this gracefully, of course, rather than duplicate its effort many times. Also, I only have a vague idea of how to take advantage of the information gained from the local searches, when performing the global search. Weston On 1/30/07, Dave Dyer [EMAIL PROTECTED] wrote: The idea isn't more than lightly toasted (less than half baked), but the kernal is turn the full board search into set of searches on much smaller boards, using the overlapping strips as boundary conditions, then do some unifying final step to pick the move. ___ 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/
