Re: [computer-go] Former Deep Blue Research working on Go
Absolutelu _great_ link, raises my go rank I hope. thanks. Do they exist? I have watched many hilarious youtube stuff, but no clue to search go stuff, great. t. harri - Original Message - From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Saturday, October 13, 2007 2:31 AM Subject: Re: [computer-go] Former Deep Blue Research working on Go How do I find the ones narrated in English? Do they exist? The closest I could find was this one which is almost unwatchable. http://www.youtube.com/watch?v=uArhCnJu7LM On 10/12/07, Ray Tayek [EMAIL PROTECTED] wrote: At 07:36 AM 10/12/2007, you wrote: Chris Fant wrote: Ho can I find Go vids on youtube? Searching for go obviously does nothing. Atari was also a good keyword here. There it is: http://www.youtube.com/watch?v=qt1FvPxmmfE searching for: go baduk weiqi returns a bunch. --- vice-chair http://ocjug.org/ ___ 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: [computer-go] Former Deep Blue Research working on Go
that just kills me every time i see the expression on yasuhiro's (?) face. losing the 5 stones is one thing, losing the second eye is brutal. s. - Original Message From: Tapani Raiko [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Friday, October 12, 2007 10:36:01 AM Subject: Re: [computer-go] Former Deep Blue Research working on Go Chris Fant wrote: Ho can I find Go vids on youtube? Searching for go obviously does nothing. Atari was also a good keyword here. There it is: http://www.youtube.com/watch?v=qt1FvPxmmfE -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out. http://answers.yahoo.com/dir/?link=listsid=396545433 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Or weiqi. Peter Drake http://www.lclark.edu/~drake/ On Oct 12, 2007, at 7:29 AM, steve uurtamo wrote: try baduk! s. - Original Message From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Friday, October 12, 2007 10:04:23 AM Subject: Re: [computer-go] Former Deep Blue Research working on Go Ho can I find Go vids on youtube? Searching for go obviously does nothing. On 10/12/07, steve uurtamo [EMAIL PROTECTED] wrote: Hi Steve, So this doesn't get too lengthy I'll remove the stuff I'm not responding to. no problem. But why would it suddenly go log at some point nearby? This is the same superstition people had in computer chess for decades! Everyone had this gut feeling based on nothing whatsoever. well, every continuous function is well-approximated by a linear function at a small enough scale, right? so we should expect to see linearity over a reasonably small range. if we don't know the function and don't have datapoints from anywhere other than the beginning of the function, we can't really say much about datapoints at the end of the function, much less guess the function itself. having sparse datapoints from all over the function would give more information than having really detailed datapoints at the easy end of the function. unfortunately, it's really difficult to get datapoints further down the function. so i'm not sure that we can extrapolate from one end of the function to the other. that's all. in a physics experiment you sample from all over the range where you think that your fitting function is appropriate. it would be unreasonable to sample from one end and make claims about the other end. the number of doublings is relevant here as well -- the valid human ELO range in chess is quite a bit smaller than the same for go. we can obtain datapoints from all over the chess ELO range. we don't have the same for go. What DID happen is that there were always some hills the computer couldn't climb over and there still are, but it had nothing to do with their improvement rate.Your fallacy is that you believe the landscape is relatively smooth, but with some monster unscaleable hill just out of sight. The truth is there are many different hills of all different sizes. Each improvement will enable the program to climb over one or two it couldn't before. That's really how you should be thinking of this. There is no wall around the corner. that's a good point -- any incremental gain in strength may be by having the ability to solve a completely different class of subproblems (described in a completely different way) in the game than the ones that humans try to solve. I think professional play is a long way off too. But I also believe this is romanticized too much. As I gradually became better at chess I learned that a lot of concepts were just barely out of reach and not really that big a deal. With just a little extra understanding a profound move becomes rather simple but if you don't understand it it seems like magic. Great players have a LOT of these and we look at their games and imagine them to be gods. it's true that people are quite falliable -- i think that someone recently posted on the list (with youtube video) an example of a big group being in atari in a professional game and one of the two players not noticing. this is the kind of error that would simply be impossible for any program that can count liberties. s. _ ___ Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos more. http://mobile.yahoo.com/go?refer=1GNXIC ___ 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/ __ __ Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out. http://answers.yahoo.com/dir/?link=listsid=396545433 ___ 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] Former Deep Blue Research working on Go
Chris Fant wrote: Ho can I find Go vids on youtube? Searching for go obviously does nothing. Atari was also a good keyword here. There it is: http://www.youtube.com/watch?v=qt1FvPxmmfE -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Hi Steve, So this doesn't get too lengthy I'll remove the stuff I'm not responding to. no problem. But why would it suddenly go log at some point nearby? This is the same superstition people had in computer chess for decades! Everyone had this gut feeling based on nothing whatsoever. well, every continuous function is well-approximated by a linear function at a small enough scale, right? so we should expect to see linearity over a reasonably small range. if we don't know the function and don't have datapoints from anywhere other than the beginning of the function, we can't really say much about datapoints at the end of the function, much less guess the function itself. having sparse datapoints from all over the function would give more information than having really detailed datapoints at the easy end of the function. unfortunately, it's really difficult to get datapoints further down the function. so i'm not sure that we can extrapolate from one end of the function to the other. that's all. in a physics experiment you sample from all over the range where you think that your fitting function is appropriate. it would be unreasonable to sample from one end and make claims about the other end. the number of doublings is relevant here as well -- the valid human ELO range in chess is quite a bit smaller than the same for go. we can obtain datapoints from all over the chess ELO range. we don't have the same for go. What DID happen is that there were always some hills the computer couldn't climb over and there still are, but it had nothing to do with their improvement rate.Your fallacy is that you believe the landscape is relatively smooth, but with some monster unscaleable hill just out of sight. The truth is there are many different hills of all different sizes. Each improvement will enable the program to climb over one or two it couldn't before. That's really how you should be thinking of this. There is no wall around the corner. that's a good point -- any incremental gain in strength may be by having the ability to solve a completely different class of subproblems (described in a completely different way) in the game than the ones that humans try to solve. I think professional play is a long way off too. But I also believe this is romanticized too much. As I gradually became better at chess I learned that a lot of concepts were just barely out of reach and not really that big a deal. With just a little extra understanding a profound move becomes rather simple but if you don't understand it it seems like magic. Great players have a LOT of these and we look at their games and imagine them to be gods. it's true that people are quite falliable -- i think that someone recently posted on the list (with youtube video) an example of a big group being in atari in a professional game and one of the two players not noticing. this is the kind of error that would simply be impossible for any program that can count liberties. s. Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos more. http://mobile.yahoo.com/go?refer=1GNXIC ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
try baduk! s. - Original Message From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Friday, October 12, 2007 10:04:23 AM Subject: Re: [computer-go] Former Deep Blue Research working on Go Ho can I find Go vids on youtube? Searching for go obviously does nothing. On 10/12/07, steve uurtamo [EMAIL PROTECTED] wrote: Hi Steve, So this doesn't get too lengthy I'll remove the stuff I'm not responding to. no problem. But why would it suddenly go log at some point nearby? This is the same superstition people had in computer chess for decades! Everyone had this gut feeling based on nothing whatsoever. well, every continuous function is well-approximated by a linear function at a small enough scale, right? so we should expect to see linearity over a reasonably small range. if we don't know the function and don't have datapoints from anywhere other than the beginning of the function, we can't really say much about datapoints at the end of the function, much less guess the function itself. having sparse datapoints from all over the function would give more information than having really detailed datapoints at the easy end of the function. unfortunately, it's really difficult to get datapoints further down the function. so i'm not sure that we can extrapolate from one end of the function to the other. that's all. in a physics experiment you sample from all over the range where you think that your fitting function is appropriate. it would be unreasonable to sample from one end and make claims about the other end. the number of doublings is relevant here as well -- the valid human ELO range in chess is quite a bit smaller than the same for go. we can obtain datapoints from all over the chess ELO range. we don't have the same for go. What DID happen is that there were always some hills the computer couldn't climb over and there still are, but it had nothing to do with their improvement rate.Your fallacy is that you believe the landscape is relatively smooth, but with some monster unscaleable hill just out of sight. The truth is there are many different hills of all different sizes. Each improvement will enable the program to climb over one or two it couldn't before. That's really how you should be thinking of this. There is no wall around the corner. that's a good point -- any incremental gain in strength may be by having the ability to solve a completely different class of subproblems (described in a completely different way) in the game than the ones that humans try to solve. I think professional play is a long way off too. But I also believe this is romanticized too much. As I gradually became better at chess I learned that a lot of concepts were just barely out of reach and not really that big a deal. With just a little extra understanding a profound move becomes rather simple but if you don't understand it it seems like magic. Great players have a LOT of these and we look at their games and imagine them to be gods. it's true that people are quite falliable -- i think that someone recently posted on the list (with youtube video) an example of a big group being in atari in a professional game and one of the two players not noticing. this is the kind of error that would simply be impossible for any program that can count liberties. s. Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos more. http://mobile.yahoo.com/go?refer=1GNXIC ___ 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/ Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out. http://answers.yahoo.com/dir/?link=listsid=396545433 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
At 07:36 AM 10/12/2007, you wrote: Chris Fant wrote: Ho can I find Go vids on youtube? Searching for go obviously does nothing. Atari was also a good keyword here. There it is: http://www.youtube.com/watch?v=qt1FvPxmmfE searching for: go baduk weiqi returns a bunch. --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
How do I find the ones narrated in English? Do they exist? The closest I could find was this one which is almost unwatchable. http://www.youtube.com/watch?v=uArhCnJu7LM On 10/12/07, Ray Tayek [EMAIL PROTECTED] wrote: At 07:36 AM 10/12/2007, you wrote: Chris Fant wrote: Ho can I find Go vids on youtube? Searching for go obviously does nothing. Atari was also a good keyword here. There it is: http://www.youtube.com/watch?v=qt1FvPxmmfE searching for: go baduk weiqi returns a bunch. --- vice-chair http://ocjug.org/ ___ 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] Former Deep Blue Research working on Go
At 04:31 PM 10/12/2007, you wrote: How do I find the ones narrated in English? not sure, i just found these things/ Do they exist? yes The closest I could find was this one which is almost unwatchable. http://www.youtube.com/watch?v=uArhCnJu7LM all of the ones by her that i have seen are in english. searching for: Guo Juan gives a few hundred! here is a new guy: http://www.youtube.com/watch?v=zFImtHxZrEw i found searching on: go baduk weichi. On 10/12/07, Ray Tayek [EMAIL PROTECTED] wrote: At 07:36 AM 10/12/2007, you wrote: Chris Fant wrote: Ho can I find Go vids on youtube? Searching for go obviously does nothing. Atari was also a good keyword here. There it is: http://www.youtube.com/watch?v=qt1FvPxmmfE searching for: go baduk weiqi returns a bunch. --- vice-chair http://ocjug.org/ ___ 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/ --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
i think that it's an accurate statement. it certainly hasn't already played such a role, and there is no evidence that it will or can. s. - Original Message From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, October 10, 2007 9:15:18 PM Subject: Re: [computer-go] Former Deep Blue Research working on Go I'm just now reading the article. Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. The author loses credibility with this statement. On 10/10/07, Ray Tayek [EMAIL PROTECTED] wrote: At 02:33 PM 10/7/2007, you wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244 --- vice-chair http://ocjug.org/ ___ 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/ Catch up on fall's hot new shows on Yahoo! TV. Watch previews, get listings, and more! http://tv.yahoo.com/collections/3658 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
In your own paper you say: At the 19x19 level, Monte Carlo programs are now at the level of the strongest traditional programs. [https://webdisk.lclark.edu/drake/publications/GAMEON-07-drake.pdf] And MC programs are more scalable that traditional programs. That seems like some evidence that it can or will. Especially given that the current techniques are still so young. On 10/11/07, steve uurtamo [EMAIL PROTECTED] wrote: i think that it's an accurate statement. it certainly hasn't already played such a role, and there is no evidence that it will or can. s. - Original Message From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, October 10, 2007 9:15:18 PM Subject: Re: [computer-go] Former Deep Blue Research working on Go I'm just now reading the article. Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. The author loses credibility with this statement. On 10/10/07, Ray Tayek [EMAIL PROTECTED] wrote: At 02:33 PM 10/7/2007, you wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244 --- vice-chair http://ocjug.org/ ___ 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/ Catch up on fall's hot new shows on Yahoo! TV. Watch previews, get listings, and more! http://tv.yahoo.com/collections/3658 ___ 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] Former Deep Blue Research working on Go
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Let's cut to the chase and the real issue: Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. This statement is more about the feasibility of Monte Carlo techniques on the 19x19 board than it is about beating the top human player. The author wants to design an alpha/beta brute force searcher on big hardware because he thinks IT WILL play a significant role and Monte Carlo WILL NOT. Since we don't know if this will every happen in our life-times a more interesting question in my opinion is this: Will programs having a significant Monte Carlo component (perhaps UCT) be able to dominate program NOT having a significant Monte Carlo component in the near future? That's really what we are talking about. I can only guess, but right now I have a strong hunch that the basic Mogo approach is the best way forward. I know a way we can try to answer that question right away - I will post about it in a minute. - - Don steve uurtamo wrote: i think that it's an accurate statement. it certainly hasn't already played such a role, and there is no evidence that it will or can. s. - Original Message From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, October 10, 2007 9:15:18 PM Subject: Re: [computer-go] Former Deep Blue Research working on Go I'm just now reading the article. Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. The author loses credibility with this statement. On 10/10/07, Ray Tayek [EMAIL PROTECTED] wrote: At 02:33 PM 10/7/2007, you wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244 --- vice-chair http://ocjug.org/ ___ 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/ Catch up on fall's hot new shows on Yahoo! TV. Watch previews, get listings, and more! http://tv.yahoo.com/collections/3658 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHDjA+DsOllbwnSikRAmNbAJ4yF2eeGHUJHGb+0ZuwerxVOP423wCg5FQ+ 9WZ3ZLDZxW5NN/4ncCkjOCE= =P1DI -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
On 10/9/07, Andrés Domínguez [EMAIL PROTECTED] wrote: 2007/10/9, Eric Boesch [EMAIL PROTECTED]: Naive null move is unhelpful because throughout much of a go game, almost every move is better than passing, I think this is not the point of null move. Null move is if pass is good enough to an alpha cut, then will be a _better_ move. It is not important if pass is the worse move, is important that there is a better (=) move than pass (not zugzwang). Then you bet searching not so deep. Sorry, that was sloppy writing in several places. I was not trying to argue why null-move pruning (NMP) would give the wrong answer, but why, even if NMP performs as intended and horizon effects don't spoil its evaluation, it might not prune many moves. The hope is to prune variations that are bad and lopsided enough that starting at some point, one side loses the equivalent of a whole move compared to, er, more or less, correct play by both sides, right? The fraction of variations that fit that description will increase with the depth of the tree and the variability of move quality. The depth and variability are both likely to be lower in global go search than in global chess search. (As for local go search, as I already explained, I think that even if NMP is effective when compared with bare-bones alpha-beta, it is still less effective than other approaches like lambda search.) If all moves except pass for both players are better than nothing, then if NMP works as intended, no moves will be pruned in the first two plies of the search (it takes at least two moves by the same player to fall a full move behind). If an average move is more than two-thirds as valuable as the best move -- which is usually true in go for, very roughly, the first 20 moves of a typical 19x19 game -- you'll have to go six levels deep before you see many NMP cutoffs (even if white's sequence is below average and cumulatively a move worse than best, it may not lose a full move to black's imperfect responses, so only a minority of 6-ply sequences will be eligible, and then you have to consider how many of those sequences would be cut off by alpha-beta anyhow -- I would assume the sequences that NMP might prune would be cut off by ordinary alpha-beta at a greater rate than more balanced sequences would be). You won't see NMP cutoffs at the bottom of the tree, either, because it's too late to prune then. If NMP doesn't prune much near the root or the deepest nodes, and the tree is not very deep because the branching factor and static evaluation cost are high enough that there isn't time to search very deeply, then NMP isn't doing much, period. I think that is at least part of what has limited the benefits of null move pruning for full-breadth global search in go. Selective global search allows deeper searches, but a good selector should prune away most of the sequences NMP might otherwise have caught. None of this is an argument that NMP would be literally useless, just that it's unlikely to lead to a dramatic strength improvement. Even in chess, Chrilly Donninger said NMP was good for, what, 100 Elo points? The only alpha-beta tweak that can add 400 Elo to a chess program on its own is transposition tables, and everybody already has those. That makes it difficult to understand why non-go-programmers are sometimes so willing to believe that just souping up an alpha-beta search could turn today's top go programs, which I would say are at about the go equivalent of class B at 19x19, into the go equivalent of grandmasters. A simple-but-fast full-breadth alpha-beta go solver would have even further to go to reach grandmaster level, because it would need to reach the level of being competitive with the top tier of extant programs first (which no such program currently is). Either way, in terms of performance measured in human terms, the jump from the state of the art to world-champion-caliber play would be a far bigger leap beyond the state of the art than Deep Thought and Deep Blue ever made. (The leap to dan level, if gaining just two stones can be called that, surely requires only throwing a little more hardware at existing programs.) Okay, enough of that. If people aren't persuaded by other programmers' experience trying to map computer chess methods to computer go in a straightforward way, then they're not likely to be convinced by my hand-waving arguments either. [Regarding programmers' experience: when a top chess programmer (Chrilly) and a successful go programmer (Peter Woitke) collaborated on a chess-style go program, the result fell -- at last report, anyhow -- about 600 Elo points short of the top tier of programs at 9x9, and presumably much farther short at real go. (The 600 figure is derived from Chrilly's claims of a 60% success record against GnuGo, and GnuGo's placement nearly 700 Elo points behind Mogo on CGOS -- 9x9 is not GnuGo's long suit.) That should dispel any residual hopes that applying state-of-the-art chess-search
Re: [computer-go] Former Deep Blue Research working on Go
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Several points: Null move is usually applied to a beta cutoff - but of course this is mostly semantics. In the literature if you can pass (play the null move) and still get a beta cutoff then you are in a fruitless line of play because your opponent has the power to avoid this line of play. Null move is pointless without a depth reduction, otherwise it just adds 1 extra node to this level in many cases. When I played around with null move it only hurt the program some - because it does reduced the tree significantly which partially compensates for the reduced quality of the tree.That gives some hope that it's not totally stupid but it would need some bolstering somehow. Null move is nothing more than a test. If there is some other way to estimate an upper or lower bound on the score, it could be used the same way that null move is. Alpha Beta pruning hasn't been explored to it's full potential in computer GO. Translating a chess program to go by itself is not going to work but in my experience there is some pretty strong evidence that you can be a lot more sloppy about selectivity in Go.For instance you can throw out a lot of moves without it killing the search completely. In chess you have to be paranoid about which move you can throw out. The secret is that you don't throw out any move permanently, unless you can prove admissibility.You taper the search. Perhaps with patterns you can eliminate most of the moves NEAR the leaf nodes, but at some point you have to reintroduce them.Null move is a recursive mechanism to re-introduce moves but we probably need something else in GO. One thing is clear - if alpha beta is to be workable it has to be extremely liberal about pruning moves. - - Don Eric Boesch wrote: On 10/9/07, Andrés Domínguez [EMAIL PROTECTED] wrote: 2007/10/9, Eric Boesch [EMAIL PROTECTED]: Naive null move is unhelpful because throughout much of a go game, almost every move is better than passing, I think this is not the point of null move. Null move is if pass is good enough to an alpha cut, then will be a _better_ move. It is not important if pass is the worse move, is important that there is a better (=) move than pass (not zugzwang). Then you bet searching not so deep. Sorry, that was sloppy writing in several places. I was not trying to argue why null-move pruning (NMP) would give the wrong answer, but why, even if NMP performs as intended and horizon effects don't spoil its evaluation, it might not prune many moves. The hope is to prune variations that are bad and lopsided enough that starting at some point, one side loses the equivalent of a whole move compared to, er, more or less, correct play by both sides, right? The fraction of variations that fit that description will increase with the depth of the tree and the variability of move quality. The depth and variability are both likely to be lower in global go search than in global chess search. (As for local go search, as I already explained, I think that even if NMP is effective when compared with bare-bones alpha-beta, it is still less effective than other approaches like lambda search.) If all moves except pass for both players are better than nothing, then if NMP works as intended, no moves will be pruned in the first two plies of the search (it takes at least two moves by the same player to fall a full move behind). If an average move is more than two-thirds as valuable as the best move -- which is usually true in go for, very roughly, the first 20 moves of a typical 19x19 game -- you'll have to go six levels deep before you see many NMP cutoffs (even if white's sequence is below average and cumulatively a move worse than best, it may not lose a full move to black's imperfect responses, so only a minority of 6-ply sequences will be eligible, and then you have to consider how many of those sequences would be cut off by alpha-beta anyhow -- I would assume the sequences that NMP might prune would be cut off by ordinary alpha-beta at a greater rate than more balanced sequences would be). You won't see NMP cutoffs at the bottom of the tree, either, because it's too late to prune then. If NMP doesn't prune much near the root or the deepest nodes, and the tree is not very deep because the branching factor and static evaluation cost are high enough that there isn't time to search very deeply, then NMP isn't doing much, period. I think that is at least part of what has limited the benefits of null move pruning for full-breadth global search in go. Selective global search allows deeper searches, but a good selector should prune away most of the sequences NMP might otherwise have caught. None of this is an argument that NMP would be literally useless, just that it's unlikely to lead to a dramatic strength improvement. Even in chess, Chrilly Donninger said NMP was good for, what, 100 Elo points? The
Re: [computer-go] Former Deep Blue Research working on Go
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Good common sense answer. I agree that this could be settled. I'll go ahead and help Chris Fant set up a the server which he will administer. Meanwhile, can you experiment with the 9x9 server just to see if you can get it working on CGOS?You can use any anonymous name. - - Don David Fotland wrote: It's because strong players play strong moves, and the program has knowledge about the strong moves. When Mogo plays an unconventional move, Many Faces has less knowledge, and is more likely to do something really stupid. People are more able to respond well to odd moves. 9x9 is a different case, since mogo plays nearly perfectly once the opening is done, unless there is a rare tactic that falls outside the uct tree so the monte carlo doesn't see it. In 19x19 middle games, mogo is still relying on the monte carlo playouts rather than the uct tree, so it is more sensitive to tactics. I've watched it play 19x19, and it plays greedy for territory while leaving many weaknesses. A human will focus on the weaknesses and find some deep tactics to exploit them. Many Faces won't do this since it expects the opponent to play the honest move and not leave this kind of weakness. But the only way to settle this is to do some experiments. I could certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and we also have them play for ratings against people on kgs, it would settle it. David -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHDnfuDsOllbwnSikRAjIxAKDMtn/IC7ybKC40Gc73k93y5zkOxACg4qoT JOZy56ZHYDPqyno9XMqLhuk= =9Kou -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 I thought Monte Carlo plays and thinks MORE like human players. That might make them easier to beat, I don't know. Playing like a human doesn't imply they are harder to beat. I have heard people complain that they couldn't beat the early chess programs BECAUSE they didn't play normal moves. You would know more than me because you are much stronger. But you claim they are better against the more human knowledge based programs for the reason I stated, that they play strange moves. But why should that not help against humans who play more human like? You are basically saying there is a great deal of in-transitivity between humans, monte carlo players, and knowledge based players. I don't believe there is that much. For instance when Mogo dominated at 9x9 it was found that it is also quite strong against humans (compared to other kinds of programs.) I know the argument that I will hear - 19x19 isn't 9x9. I believe in Occams razor - whichever program proves to be stronger in head to head is probably stronger against other opponents - at least that is the simple conclusion and the burden of proof should go to the one claiming otherwise. I don't have any problem with you being right - but you are claiming something that is contrary to the simplest explanation. - - Don David Fotland wrote: I would not agree with this statement. I think it is likely that the current Monte Carlo programs can get good results agaisnt traditional programs, but I don't think they are as strong against people. Certainly they don't play in a human style. One of the resons they do well against knowledge based programs is that they play strange moves (at 19x19). I think people are more able to exploit the way the programs play. I do agree that since monte carlo is scalable, these programs will improve much faster than traditional programs. David -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Chris Fant Sent: Thursday, October 11, 2007 5:24 AM To: computer-go Subject: Re: [computer-go] Former Deep Blue Research working on Go In your own paper you say: At the 19x19 level, Monte Carlo programs are now at the level of the strongest traditional programs. [https://webdisk.lclark.edu/drake/publications/GAMEON-07-drake.pdf] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHDnNYDsOllbwnSikRAtYJAJ9AtB5QlGYZl7YIPI8nPTMW1AW0cACgg3Ly ryaPGSKLsPRhyAu3KedBxEk= =zXh0 -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Former Deep Blue Research working on Go
I already have experimented with the 9x9 server with an anonymous name :) The results have aged off the server, but I think it had a rating between 1750 and 1850. So I had working GTP code about 8 months ago. I'll give it a try today on 9x9 to see if it still works. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Don Dailey Sent: Thursday, October 11, 2007 12:22 PM To: computer-go Subject: Re: [computer-go] Former Deep Blue Research working on Go -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Good common sense answer. I agree that this could be settled. I'll go ahead and help Chris Fant set up a the server which he will administer. Meanwhile, can you experiment with the 9x9 server just to see if you can get it working on CGOS?You can use any anonymous name. - - Don David Fotland wrote: It's because strong players play strong moves, and the program has knowledge about the strong moves. When Mogo plays an unconventional move, Many Faces has less knowledge, and is more likely to do something really stupid. People are more able to respond well to odd moves. 9x9 is a different case, since mogo plays nearly perfectly once the opening is done, unless there is a rare tactic that falls outside the uct tree so the monte carlo doesn't see it. In 19x19 middle games, mogo is still relying on the monte carlo playouts rather than the uct tree, so it is more sensitive to tactics. I've watched it play 19x19, and it plays greedy for territory while leaving many weaknesses. A human will focus on the weaknesses and find some deep tactics to exploit them. Many Faces won't do this since it expects the opponent to play the honest move and not leave this kind of weakness. But the only way to settle this is to do some experiments. I could certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and we also have them play for ratings against people on kgs, it would settle it. David -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHDnfuDsOllbwnSikRAjIxAKDMtn/IC7ybKC40Gc73k93y5zkOxACg4qoT JOZy56ZHYDPqyno9XMqLhuk= =9Kou -END PGP SIGNATURE- ___ 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] Former Deep Blue Research working on Go
Can we also count on Steenvreter for this 19x19 smack-down? You out there, Erik? On 10/11/07, Eric Boesch [EMAIL PROTECTED] wrote: On 10/11/07, David Fotland [EMAIL PROTECTED] wrote: But the only way to settle this is to do some experiments. I could certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and we also have them play for ratings against people on kgs, it would settle it. Mogobot1 and mogobot2 are rated 2k and 3k, respectively, on KGS. CrazyStone is rated 2k. All of these numbers are with moderate time controls (not the 15 minute sudden death time controls that became a subject of controversy). There was also KCConGui, running KCC Igo, that played for a while on KGS. I don't know whether it was an official bot, or whether its departure had anything to do with its lopsided losing record against CrazyStone. The KCConGui page notes that KCC Igo won the Gifu Challenge four years in a row, most recently against sparse competition, but the best claim to the computer go throne belongs to Steenvreter, for edging out Mogo and CrazyStone in the stronger ICGA tournament. ___ 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] Former Deep Blue Research working on Go
On Oct 11, 2007, at 1:49 PM, Eric Boesch wrote: On 10/11/07, David Fotland [EMAIL PROTECTED] wrote: But the only way to settle this is to do some experiments. I could certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and we also have them play for ratings against people on kgs, it would settle it. Mogobot1 and mogobot2 are rated 2k and 3k, respectively, on KGS. CrazyStone is rated 2k. All of these numbers are with moderate time controls (not the 15 minute sudden death time controls that became a subject of controversy). There was also KCConGui, running KCC Igo, that played for a while on KGS. I don't know whether it was an official bot, or whether its departure had anything to do with its lopsided losing record against CrazyStone. The KCConGui page notes that KCC Igo won the Gifu Challenge four years in a row, most recently against sparse competition, but the best claim to the computer go throne belongs to Steenvreter, for edging out Mogo and CrazyStone in the stronger ICGA tournament. I thought Steenvreter only played 9x9 Go. The 19x19 ICGA tournament winners were MoGo, CrazyStone, and GnuGo in that order. Ian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Yes I'm here :-) Sorry to have to disappoint you though, I have not yet found enough time to work on 19x19. For now the throne rightfully belongs to Mogo. Erik On 10/11/07, Chris Fant [EMAIL PROTECTED] wrote: Can we also count on Steenvreter for this 19x19 smack-down? You out there, Erik? On 10/11/07, Eric Boesch [EMAIL PROTECTED] wrote: On 10/11/07, David Fotland [EMAIL PROTECTED] wrote: But the only way to settle this is to do some experiments. I could certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and we also have them play for ratings against people on kgs, it would settle it. Mogobot1 and mogobot2 are rated 2k and 3k, respectively, on KGS. CrazyStone is rated 2k. All of these numbers are with moderate time controls (not the 15 minute sudden death time controls that became a subject of controversy). There was also KCConGui, running KCC Igo, that played for a while on KGS. I don't know whether it was an official bot, or whether its departure had anything to do with its lopsided losing record against CrazyStone. The KCConGui page notes that KCC Igo won the Gifu Challenge four years in a row, most recently against sparse competition, but the best claim to the computer go throne belongs to Steenvreter, for edging out Mogo and CrazyStone in the stronger ICGA tournament. ___ 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: [computer-go] Former Deep Blue Research working on Go
Then they are stronger than many face against people. I think Many Faces would be around 4k to 6k. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Eric Boesch Sent: Thursday, October 11, 2007 1:50 PM To: computer-go Subject: Re: [computer-go] Former Deep Blue Research working on Go On 10/11/07, David Fotland [EMAIL PROTECTED] wrote: But the only way to settle this is to do some experiments. I could certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and we also have them play for ratings against people on kgs, it would settle it. Mogobot1 and mogobot2 are rated 2k and 3k, respectively, on KGS. CrazyStone is rated 2k. All of these numbers are with moderate time controls (not the 15 minute sudden death time controls that became a subject of controversy). There was also KCConGui, running KCC Igo, that played for a while on KGS. I don't know whether it was an official bot, or whether its departure had anything to do with its lopsided losing record against CrazyStone. The KCConGui page notes that KCC Igo won the Gifu Challenge four years in a row, most recently against sparse competition, but the best claim to the computer go throne belongs to Steenvreter, for edging out Mogo and CrazyStone in the stronger ICGA tournament. ___ 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] Former Deep Blue Research working on Go
Someone already did: Stone eater. On 10/11/07, terry mcintyre [EMAIL PROTECTED] wrote: Erik, It would be great to see Steenvreter on the 9x9 cgos server. BTW, can you translate Steenvreter for us English speakers? Thanks! From: Erik van der Werf [EMAIL PROTECTED] Yes I'm here :-) Sorry to have to disappoint you though, I have not yet found enough time to work on 19x19. For now the throne rightfully belongs to Mogo. Erik Looking for a deal? Find great prices on flights and hotels with Yahoo! FareChase. ___ 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] Former Deep Blue Research working on Go
On Thu, 2007-10-11 at 18:37 -0400, Chris Fant wrote: Someone already did: Stone eater. On 10/11/07, terry mcintyre [EMAIL PROTECTED] wrote: Erik, It would be great to see Steenvreter on the 9x9 cgos server. BTW, can you translate Steenvreter for us English speakers? Thanks! Eater is a bit too weak, IMHO. Stone gobbler or stone muncher seems more appropriate. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
I think that there's an apples/oranges thing going on here. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. i agree with this statement. And MC programs are more scalable that traditional programs. That seems like some evidence that it can or will. Especially given that the current techniques are still so young. i do not agree with this statement. top the best human players in a 19x19 game is quite a bit different than at the level of the strongest traditional programs. at the level of, or near the level of, or slightly better than just means (perhaps) that the wheel has been re-invented. it could mean more than that, but there surely doesn't seem to be much evidence for that at this point. scalable doesn't mean linear, and it also doesn't give an asymptotic growth function or a constant. if anyone anywhere could give a good estimate for how many cpus it would take, with any particular algorithm, to beat a professional player, and if the number were feasible, there's no reason not to start building such a machine. s. Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out. http://answers.yahoo.com/dir/?link=listsid=396545433 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Hi Steve, So this doesn't get too lengthy I'll remove the stuff I'm not responding to. I think this statement is more or less true. Didn't you see the scalability data for 19x19? In fact didn't you help me produce it? we tested some very low ELO ranges. speculating about how that scales up to the upper stratosphere of ELO is pretty difficult for me. it wasn't straight enough for me to believe that it doesn't go log at some point nearby and start to cripple the doubling of cpu advantage. But why would it suddenly go log at some point nearby? This is the same superstition people had in computer chess for decades! Everyone had this gut feeling based on nothing whatsoever. in the sense that 19x19 is still brutally difficult, and that these methods haven't improved the state of the art by more than a stone or two, if that. so we should definitely not extrapolate, or expect them to perform, any better than we already have evidence for. What do you consider evidence? If every doubling so far has yielded the same approximate improvement then I would say the evidence is pretty good that the next one will.I guess you believe there is no evidence the next one will? i agree that on smaller boards UCT-type programs are superior. without trying too hard to sound like an apologist/traditionalist, i will mention that boardsize isn't merely a scaling factor in this problem. things change in a fundamental way inbetween 9x9 and 19x19 that direct search can't recognize. (this is essentially what monte carlo methods are doing, as they are somewhat carefully sampling from the move distribution). I'm sure some will believe this observed scalability is short lived but I know of no reason to believe that other than superstition. i hate to do this, but i'll give you an analogy that i think is relevant. if you crawl at 1/2 mph across the desert for 7 years, encounter a tiny hill, and manage to scale it, you may say to yourself that you've made a massive accomplishment. and you have. but it doesn't imply, entail, or otherwise suggest that all future obstacles will be of similar size. honestly, 9x9 doesn't even leave *room* for some of the important problems that are critical on a 19x19 board. those problems don't exist on a small board because it's a full-on tactical fight from the get-go. this is a different kind of problem than being willing to trade 40% of the board for a 51% likelihood of getting 41% of the board in exchange. 9x9 is about getting a 100% likelihood of winning as soon as possible. Everyone likes to romanticize this fact. Of course there are a lot of differences but that has nothing to do with how scalable the problem is. All you are really saying is that it's more difficult and complicated - that is totally unrelated to scalability. These conceptual hills are not barriers, they are hills. These same barriers were imagined to exist in computer chess too. Many masters criticized the nature of search and said computers would never be able to do long term planning and this was certain to create a sudden standstill and it was just around the corner always. But it never happened. What DID happen is that there were always some hills the computer couldn't climb over and there still are, but it had nothing to do with their improvement rate.Your fallacy is that you believe the landscape is relatively smooth, but with some monster unscaleable hill just out of sight. The truth is there are many different hills of all different sizes. Each improvement will enable the program to climb over one or two it couldn't before. That's really how you should be thinking of this. There is no wall around the corner. That's why I believe a super hardware gizmo could easily be built that would be in the DAN range somewhere at 19x19, at least low Dan.I'm not so bold as to predict that it will be at top human levels any time soon though. i think that we're likely in agreement here. crazy hardware could get you into the 1 dan range, but professional play is way, way out of bounds at this point. to see why i think this, watch a 7d game on kgs and listen to the 1d kibitz. note how ridiculously out-of-touch they are with the game that is going on in front of them. pro play is yet another magnitude or two of out of touch from amateur play. I think professional play is a long way off too. But I also believe this is romanticized too much. As I gradually became better at chess I learned that a lot of concepts were just barely out of reach and not really that big a deal. With just a little extra understanding a profound move becomes rather simple but if you don't understand it it seems like magic. Great players have a LOT of these and we look at their games and imagine them to be gods. - - Don s.
Re: [computer-go] Former Deep Blue Research working on Go
terry mcintyre wrote: IIRC, a few Microsoft researchers did some interesting work with SVMs and the prediction of pro-level moves. I've always wondered whether that could be integrated with UCT to narrow the search tree. Hi, This is what I do in Crazy Stone: http://remi.coulom.free.fr/Amsterdam2007/ Mango does something similar, too. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Andrés Domínguez wrote: 2007/10/10, Don Dailey [EMAIL PROTECTED]: Andrés, You are right about null move of course. The assumption that other moves are = to the value of a pass is much stronger in GO than in Chess, yet ironically it's not as effective in Go. That was what i was trying to say. Pass is one of the worst moves (except final) is good for null-move on Go. Of course you have reduced depth, probably bad with alpha-beta with a bad evaluation function, but looks interesting with UCT reducing the number of simulations and increasing the % value. I don't use UCT, so I haven't tried it. Andrés Hi, UCT does no alpha-beta pruning, so null-move pruning cannot be used. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Rémi Coulom wrote: Andrés Domínguez wrote: 2007/10/10, Don Dailey [EMAIL PROTECTED]: Andrés, You are right about null move of course. The assumption that other moves are = to the value of a pass is much stronger in GO than in Chess, yet ironically it's not as effective in Go. That was what i was trying to say. Pass is one of the worst moves (except final) is good for null-move on Go. Of course you have reduced depth, probably bad with alpha-beta with a bad evaluation function, but looks interesting with UCT reducing the number of simulations and increasing the % value. I don't use UCT, so I haven't tried it. Andrés Hi, UCT does no alpha-beta pruning, so null-move pruning cannot be used. Rémi Hi again, I did not read your reply carefuly before answering, sorry. I still don't believe your approach could work. You would waste a lot of simulations searching a bad move, and it would be extremely difficult to determine how much the % value should be increased. In alpha-beta tree search, you only need to determine that one move is better than another, regardless of the difference in value. In UCT, it is very important to also determine how much better one move is. I cannot see any reasonable approach to determine how much the null move is worse than the others. Depending on very subtle details of the position, it could be a lot or very little. Regarding the question of null move in Go, I remember that some programmers who tried it in alpha-beta programs did not manage to make it work (Peter MacKenzie comes to mind, maybe others). As Don wrote, the main problem of null move is the depth reduction. It hides long-term threats that the evaluation function might not be able to evaluate. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
As Don wrote, the main problem of null move is the depth reduction. It hides long-term threats that the evaluation function might not be able to evaluate. even with a very good evaluation function, i would think that another problem (this is likely just restating what you and others have already said) is that your opponent can quite readily often crush you if you pass, even if he plays what would otherwise be a fairly substandard move. the sheer advantage of having sente for free can be huge. at the beginning of the game it's an entire handicap stone, and near the endgame it can mean several new ko threats. in the middle game it means winning any reasonable liberty race, turning many reasonable kills into sekis, blocking any ladder, etc. so it wouldn't, generally, ever generate any cutoffs, and yet you'd be checking it with every move for effectively no reason. there is a related concept that go players actually do use, and it has to do with reordering a set of moves that have been played to see if it changes the position. tewari analysis -- this is probably more useful than null-move pruning, as it should be able to make a relatively weak evaluation function act stronger. s. Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos more. http://mobile.yahoo.com/go?refer=1GNXIC ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
On 10/10/07, Don Dailey [EMAIL PROTECTED] wrote: In GO, threats tend to be very indirect and distant, at least from the point of view of a naive search algorithm and this is a real killer to the idea - my feeling is that null move in GO is not workable. I have the same feeling. Some years ago in Magog I did quite a lot of experiments with tricks like (recursive) null move pruning. Although it provided significant reductions in the search tree it consistently made the program play weaker. The only trick that (almost) seemed to work was Multi-Cut. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Quoting Rémi Coulom [EMAIL PROTECTED]: Regarding the question of null move in Go, I remember that some programmers who tried it in alpha-beta programs did not manage to make it work (Peter MacKenzie comes to mind, maybe others). As Don wrote, the main problem of null move is the depth reduction. It hides long-term threats that the evaluation function might not be able to evaluate. I used null-moves in my old program Viking which used alpha-beta with lazy MC-Evaluation. It worked in the sense that it searched deeper, but I never observed an increase in playing strength. This might of course mean that the implementation was buggy or could be improved somehow. -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
At 02:33 PM 10/7/2007, you wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244 --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
I'm just now reading the article. Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. The author loses credibility with this statement. On 10/10/07, Ray Tayek [EMAIL PROTECTED] wrote: At 02:33 PM 10/7/2007, you wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244 --- vice-chair http://ocjug.org/ ___ 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] Former Deep Blue Research working on Go
Of no particular importance I suppose, but did any one else get the impression after looking at the picture (and the way he is holding the stone) that he is not a regular go player? Chris Fant wrote: I'm just now reading the article. Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. The author loses credibility with this statement. On 10/10/07, Ray Tayek [EMAIL PROTECTED] wrote: At 02:33 PM 10/7/2007, you wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244 --- vice-chair http://ocjug.org/ ___ 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: [computer-go] Former Deep Blue Research working on Go
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Chris Fant wrote: I'm just now reading the article. Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. The author loses credibility with this statement. Monte Carlo is the best thing going right now and the most probable future direction, software or hardware - that's my hunch anyway! - - Don On 10/10/07, Ray Tayek [EMAIL PROTECTED] wrote: At 02:33 PM 10/7/2007, you wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244 --- vice-chair http://ocjug.org/ ___ 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/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHDZZMDsOllbwnSikRAj1JAJ94Msw1bcN0Iu4gpAR3XuQuCkpkKQCfeuwc T7o/PxRxGxSanLOc7kug3Wg= =6fTh -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 He is clearly posing for a picture, this is not a spontaneous photograph. Notice the Thinker pose. I'm not a good go player at all, but the board position seems a little unnatural to me. But it could be my lack of experience. Over the last few decades, there have been may movies and television shows where a chess board appears in some scene with perhaps someone player a game. These are almost always WRONG in some obvious way. For instance someone plays a move and announces check. Then the response is a checkmate!Possible, but highly improbably. Very common is the king and queen on the wrong squares or a pawn on the 1st rank or something else really silly. Although a king and queen could move to these squares, it's extremely unlikely, especially near the opening. - - Don Richard J. Lorentz wrote: Of no particular importance I suppose, but did any one else get the impression after looking at the picture (and the way he is holding the stone) that he is not a regular go player? Chris Fant wrote: I'm just now reading the article. Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won't play a significant role in creating a machine that can top the best human players in the 19-by-19 game. The author loses credibility with this statement. On 10/10/07, Ray Tayek [EMAIL PROTECTED] wrote: At 02:33 PM 10/7/2007, you wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244 --- vice-chair http://ocjug.org/ ___ 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/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHDZWKDsOllbwnSikRAjGzAKDKUOHaEPnme19+d/UxJkSsNbJrzwCgiJeH /CvKCzEEo8Ds5e8+ZFA1BbU= =t0zW -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
2007/10/9, Eric Boesch [EMAIL PROTECTED]: On 10/8/07, Tapani Raiko [EMAIL PROTECTED] wrote: May sound unpolite. But Deep Blue reached a very important step in IA. They will be known for ever. But, from a research point of view, they didn't much really. It was mainly a technological/technical achivement. Maybe they will reimplement Mogo, try a null-move tweak, use a supercomputer, and claim to have the strongest computer Go player ever. :-) Naive null move is unhelpful because throughout much of a go game, almost every move is better than passing, I think this is not the point of null move. Null move is if pass is good enough to an alpha cut, then will be a _better_ move. It is not important if pass is the worse move, is important that there is a better (=) move than pass (not zugzwang). Then you bet searching not so deep. But null nove is not a trick in Go, because pass is always a legal move. There isn't zugzwang in Go. Andrés Sorry my bad english ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
2007/10/10, Don Dailey [EMAIL PROTECTED]: Andrés, You are right about null move of course. The assumption that other moves are = to the value of a pass is much stronger in GO than in Chess, yet ironically it's not as effective in Go. That was what i was trying to say. Pass is one of the worst moves (except final) is good for null-move on Go. Of course you have reduced depth, probably bad with alpha-beta with a bad evaluation function, but looks interesting with UCT reducing the number of simulations and increasing the % value. I don't use UCT, so I haven't tried it. Andrés ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Deep Blue guy, but without cash, I don't see much to care about. May sound unpolite. But Deep Blue reached a very important step in IA. They will be known for ever. But, from a research point of view, they didn't much really. It was mainly a technological/technical achivement. Don't trow me veggies. :-) Eduardo --- Joshua Shriver [EMAIL PROTECTED] escribió: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 Interesting part for me so far: At my lab at Microsoft Research Asia, in Beijing, I am organizing a graduate student project to design the hardware and software elements that will test the ideas outlined here. If they prove out, then the way will be clear for a full-scale project to dethrone the best human players. Thoughts, comments? Deep Go anyone? -Josh ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Los referentes más importantes en compra/ venta de autos se juntaron: Demotores y Yahoo! Ahora comprar o vender tu auto es más fácil. Vistá ar.autos.yahoo.com/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
May sound unpolite. But Deep Blue reached a very important step in IA. They will be known for ever. But, from a research point of view, they didn't much really. It was mainly a technological/technical achivement. Maybe they will reimplement Mogo, try a null-move tweak, use a supercomputer, and claim to have the strongest computer Go player ever. :-) -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
If they have a supercomputer available, maybe they will have sufficient horsepower to add some interesting pattern-matching and other improvements. Even Microsoft might do something right once in a while. ;) IIRC, a few Microsoft researchers did some interesting work with SVMs and the prediction of pro-level moves. I've always wondered whether that could be integrated with UCT to narrow the search tree. Terry McIntyre [EMAIL PROTECTED] They mean to govern well; but they mean to govern. They promise to be kind masters; but they mean to be masters. -- Daniel Webster - Original Message From: Tapani Raiko [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Monday, October 8, 2007 6:45:13 AM Subject: Re: [computer-go] Former Deep Blue Research working on Go May sound unpolite. But Deep Blue reached a very important step in IA. They will be known for ever. But, from a research point of view, they didn't much really. It was mainly a technological/technical achivement. Maybe they will reimplement Mogo, try a null-move tweak, use a supercomputer, and claim to have the strongest computer Go player ever. :-) -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Building a website is a piece of cake. Yahoo! Small Business gives you all the tools to get online. http://smallbusiness.yahoo.com/webhosting ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
On 10/8/07, Tapani Raiko [EMAIL PROTECTED] wrote: May sound unpolite. But Deep Blue reached a very important step in IA. They will be known for ever. But, from a research point of view, they didn't much really. It was mainly a technological/technical achivement. Maybe they will reimplement Mogo, try a null-move tweak, use a supercomputer, and claim to have the strongest computer Go player ever. :-) Naive null move is unhelpful because throughout much of a go game, almost every move is better than passing, but generalizations of null move can help in local fights, where most of the board really doesn't matter. Thomsen calls lambda search an extension of null move. I implemented a local search that involved a pass to fill outside liberties move that acted as a stand-in for all nonlocal moves. Maybe Feng-hsiung has something similar in mind. For programs that read out local goals in the first place, it's natural to implement some method -- lambda proof-number search with inversions, as in Thomsen's MadLab, is probably one of the better ones -- to insure you're not searching the whole board just to solve, say, a lousy crane's nest (http://senseis.xmp.net/?CranesNestTesuji). I think Mogo and CrazyStone do not do this, instead using very good whole-board vision to compensate for relatively weak local tactics. Even MadLab can be slow to solve the kind of tactical problems you would think it. MadLab's search is admissible (though a bit buggy in case of ko), and it seems that admissible search is often very hard even when making a guess that is probably right is easy. With many harder problems (MadLab did solve some some tricky, let's say 3 dan level, problems very quickly, when the key variation stayed reasonably narrow all the way to the end) I concluded that MadLab was finding the tesujis that you would normally call the solution, but then getting bogged down in the easier (to human eyes) life and death problem of mopping up cut-off chains. There are endless practical examples of easy to guess, hard to prove positions, with wide-branching (even after narrowing the search region down to intersections that really matter), deep, boring, straightforward grinds towards inevitable victory, where a glance or 100 Monte Carlo simulations might reveal the correct answer. For example, can a black stone in the center of an empty 19x19 board live? Of course the answer is yes. Okay, now try to prove it -- or don't, because it's my bet that even with computer help, no one will succeed in doing so in the next five years. In running battles with sketchy boundaries and nothing resembling an eye yet, you can usually forget about trying to prove who will win. (If the aforementioned stone in the center of the board had the 17x17 region above the first line all to itself, it might still be dead -- strong players say that if just the border of the 19x19 board is filled with stones of one color, then with correct play by both sides, the other player cannot live anywhere inside.) Even in the closed and semi-closed go problems the Smart Tools team examined in their paper, they said (I'm paraphrasing from memory, but I hope I get the gist right) that often, proving the correct answer with their tsume-go solver took far longer than just being 95% sure. Similar issues also arise in chess, but are easier to handle within a classic alpha-beta framework -- if proving checkmate is hard but recognizing the sure win is easy, it's usually because one side forces a material advantage, which even the crudest static evaluator can recognize. If you're writing a generalize go playing program, there's plenty of opportunity to admissibly optimize tactical searches, but don't expect tweaking the admissible elements of your search to the limit to adequately compensate for lack of guessing skill when proof is not practical, even if the search is meant only for clearly tactical problems and not for direct application to opening play, strategic decisions, or loose positions. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Former Deep Blue Research working on Go
Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 Interesting part for me so far: At my lab at Microsoft Research Asia, in Beijing, I am organizing a graduate student project to design the hardware and software elements that will test the ideas outlined here. If they prove out, then the way will be clear for a full-scale project to dethrone the best human players. Thoughts, comments? Deep Go anyone? -Josh ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Quite interesting, but after all, it completely neglects the difficulties to a) determine the life status of groups b) build an evaluation function out of this Benjamin Joshua Shriver schrieb: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 Interesting part for me so far: At my lab at Microsoft Research Asia, in Beijing, I am organizing a graduate student project to design the hardware and software elements that will test the ideas outlined here. If they prove out, then the way will be clear for a full-scale project to dethrone the best human players. Thoughts, comments? Deep Go anyone? -Josh ___ 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] Former Deep Blue Research working on Go
I thought it was an interesting article, full of gems and annoyances. I couldn't help to get the feeling the author was poking fun at Kasparov at times. Despite that, I am curious to see what kind of hardware he and his students produce. Guess if there is going to be a Deep Go he'd be the one to design it. Should make for some interesting progress in our field. -Josh On 10/7/07, Benjamin Teuber [EMAIL PROTECTED] wrote: Quite interesting, but after all, it completely neglects the difficulties to a) determine the life status of groups b) build an evaluation function out of this Benjamin Joshua Shriver schrieb: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 Interesting part for me so far: At my lab at Microsoft Research Asia, in Beijing, I am organizing a graduate student project to design the hardware and software elements that will test the ideas outlined here. If they prove out, then the way will be clear for a full-scale project to dethrone the best human players. Thoughts, comments? Deep Go anyone? -Josh ___ 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: [computer-go] Former Deep Blue Research working on Go
On Sun, 2007-10-07 at 17:33 -0400, Joshua Shriver wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 Umm, this article was linked to and discussed heavily here within the past week: http://computer-go.org/pipermail/computer-go/2007-October/thread.html#11302 -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Oops sorry didnt realise. On 10/7/07, Jeff Nowakowski [EMAIL PROTECTED] wrote: On Sun, 2007-10-07 at 17:33 -0400, Joshua Shriver wrote: Found this link and thought you all might find it interesting. http://www.spectrum.ieee.org/oct07/5552 Umm, this article was linked to and discussed heavily here within the past week: http://computer-go.org/pipermail/computer-go/2007-October/thread.html#11302 -Jeff ___ 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/
