Re: [computer-go] IEEE Spectrum article by Deep Blue creator
David Fotland: [EMAIL PROTECTED]: Many Faces does not use null move, but does extensive caching of life and death and other tactical results. The problem of such caching scheme is when and how programs can make correctly the cache be dirty (ie, invalid). It may be very hard even for human players. -gg (Hideki) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of terry mcintyre Sent: Tuesday, October 02, 2007 9:21 AM To: computer-go Subject: Re: [computer-go] IEEE Spectrum article by Deep Blue creator - Original Message From: Don Dailey [EMAIL PROTECTED] I think [Hsu] is betting on null move proving - but I'm real skeptical that it will be effective in Computer Go. It will indeed reduce the tree significantly, but this comes at a qualitative price that is not so bad in Chess but is a lot in Go. Hsu also discusses the gains from caching life-and-death analysis of groups. I suspect that this will greatly reduce computational effort, once an efficient mechanism is implemented. Existing monte carlo programs cache information about playable/non playable points; when augmented with knowledge about life and death, search should more quickly home in on crucial lines of play. I've been playing against Mogo the last few weeks. It has a very interesting style of play, and it often does quite well in tactical analysis, but sometimes it misses a key move and fails to kill or fails to preserve a large group - game over! A good life-and-death cache would be a definite improvement. Caching parts of trees works better in Go, since well-defined sections of the board can sometimes be partitioned from the rest of the board. Where such partitions leak, analysis is likely to be critical; for example, ladders and ladder breakers can extend across the board; invasions often depend on cutting points halfway across the board. _ Building a website is a piece of cake. Yahoo! Small Business gives you all http://us.rd.yahoo.com/evt=48251/*http://smallbusiness.yahoo.com/webhosting /?p=PASSPORTPLUS the tools to get online. inline file ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] IEEE Spectrum article by Deep Blue creator
It's a very difficult problem, but I have something that works reasonably well. David -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Hideki Kato Sent: Wednesday, October 03, 2007 12:27 AM To: computer-go Subject: Re: [computer-go] IEEE Spectrum article by Deep Blue creator David Fotland: [EMAIL PROTECTED]: Many Faces does not use null move, but does extensive caching of life and death and other tactical results. The problem of such caching scheme is when and how programs can make correctly the cache be dirty (ie, invalid). It may be very hard even for human players. -gg (Hideki) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of terry mcintyre Sent: Tuesday, October 02, 2007 9:21 AM To: computer-go Subject: Re: [computer-go] IEEE Spectrum article by Deep Blue creator - Original Message From: Don Dailey [EMAIL PROTECTED] I think [Hsu] is betting on null move proving - but I'm real skeptical that it will be effective in Computer Go. It will indeed reduce the tree significantly, but this comes at a qualitative price that is not so bad in Chess but is a lot in Go. Hsu also discusses the gains from caching life-and-death analysis of groups. I suspect that this will greatly reduce computational effort, once an efficient mechanism is implemented. Existing monte carlo programs cache information about playable/non playable points; when augmented with knowledge about life and death, search should more quickly home in on crucial lines of play. I've been playing against Mogo the last few weeks. It has a very interesting style of play, and it often does quite well in tactical analysis, but sometimes it misses a key move and fails to kill or fails to preserve a large group - game over! A good life-and-death cache would be a definite improvement. Caching parts of trees works better in Go, since well-defined sections of the board can sometimes be partitioned from the rest of the board. Where such partitions leak, analysis is likely to be critical; for example, ladders and ladder breakers can extend across the board; invasions often depend on cutting points halfway across the board. _ Building a website is a piece of cake. Yahoo! Small Business gives you all http://us.rd.yahoo.com/evt=48251/*http://smallbusiness.yahoo .com/webhosting /?p=PASSPORTPLUS the tools to get online. inline file ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ 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] IEEE Spectrum article by Deep Blue creator
Hi, Has anyone else done scaling experiments with 19x19 and UCT? I did some months ago, and reported them in that list with the title 19x19 Go, scalability with time vs handicap (http://www.mail-archive.com/computer-go%40computer-go.org/msg02775.html) The results are old, but now everyone can do those experiments as you all have the newest binaries ;) (you can only do the experiments with time but not number of simulations, so you would have to run on the same type of machines). Cheers, Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
Le mardi 2 octobre 2007 16:46, Ian Osgood a écrit : Greetings, I noticed that the following link was recently added to the Computer Go Wikipedia article. http://www.spectrum.ieee.org/oct07/5552 Cracking Go, by Feng-hsiung Hsu, IEEE Spectrum magazine, October 2007. He claims it should be possible to build a Go machine stronger than any human player. Ian Unless i missed something in this 4 pages article, there is nothing in it ! Just vague phrase, and assumption that brute force (ala deep blue) _may_ give a strong go machine. I think classical, MC and UCT programmers have contributed much more to computer go than this respectable researcher. Alain. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
I think he is betting on null move proving - but I'm real skeptical that it will be effective in Computer Go. It will indeed reduce the tree IMHO null-move mixes badly with ko-tactics, effectively doubling (or squaring ? ;-) the tree size. It might be of some use in solving local sub-problems. It still has the scent of alpha-beta-with-some-evaluation-function, which is probably not the right paradigm for go. We'll see. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
- Original Message From: Don Dailey [EMAIL PROTECTED] I think [Hsu] is betting on null move proving - but I'm real skeptical that it will be effective in Computer Go. It will indeed reduce the tree significantly, but this comes at a qualitative price that is not so bad in Chess but is a lot in Go. Hsu also discusses the gains from caching life-and-death analysis of groups. I suspect that this will greatly reduce computational effort, once an efficient mechanism is implemented. Existing monte carlo programs cache information about playable/non playable points; when augmented with knowledge about life and death, search should more quickly home in on crucial lines of play. I've been playing against Mogo the last few weeks. It has a very interesting style of play, and it often does quite well in tactical analysis, but sometimes it misses a key move and fails to kill or fails to preserve a large group - game over! A good life-and-death cache would be a definite improvement. Caching parts of trees works better in Go, since well-defined sections of the board can sometimes be partitioned from the rest of the board. Where such partitions leak, analysis is likely to be critical; for example, ladders and ladder breakers can extend across the board; invasions often depend on cutting points halfway across the board. Moody friends. Drama queens. Your life? Nope! - their life, your story. Play Sims Stories at Yahoo! Games. http://sims.yahoo.com/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 I don't believe null move pruning will be effective in Go. The basic principle of null move pruning has been described in a couple of ways: 1. threat analysis 2. bounds checking. It does both things - this is more about how to think about it. In bounds checking you are relying on the null move assumption which is that it's always bad to give up a move. This assumption is more true in Go than it is in chess so that is one argument in favor of null move pruning. The null move test is to play 2 moves in a row for one side and consider the result an upper bound. (or conversely to consider the result a lower bound for the other side.) In order to be a reduction of effort, the null move is combined with a reduced depth search. That's where the trouble begins with Go. More about that in a second. The other way to think about null move pruning is as a threat test. If I am given 2 moves in a row and I still can't create any problems for my opponent, the assumption is that I have no threats. This is of course combined with a depth reduction effort - the assumption being that with 2 moves in a row, I should be able to create trouble even at a reduced depth. A dangerous assumption in GO! Even in Chess null move pruning can be a problem. It fails most spectacularly in endings and in slow attacks. A slow attack might be a clever knight move, that puts the program one move closer to marching the knight to a critical square on the other side of the board. There are direct threats, there are threats of threats, and threats of threats of threats and so on.Null move pruning (with depth reduction) is GREAT at finding the most direct threats, but cannot see more distant threats. Unfortunately, Go is much like a chess endgame or a slow attack in this regard. A single seemingly innocent move is a powerful but very LONG TERM threat from a finite and limited search point of view. Null move pruning with reductions would fail to consider these moves. The scalable solution is recursive null move pruning, which will pick up all threats eventually if you search deeply enough. This will work in GO, but I'm quite confident that you will need several extra ply of depth to see the same tactics a brute force search would find - and the extra speed is not enough to buy that back. And this will be a very common thing - not like in chess where it still happens, but is relatively rare. It's possible that it could made to work if the evaluation function is really powerful about recognizing long term threat potential - it would have to be really good at statically recognizing life and death as well as being able to sense that life is in trouble. However that's the problem with are trying to solve - this kind of evaluation does not yet exist. - - Don Don Dailey wrote: I know Hsu from my computer chess days.Of course most of us probably realize he was on the Deep Blue team. I think he is betting on null move proving - but I'm real skeptical that it will be effective in Computer Go. It will indeed reduce the tree significantly, but this comes at a qualitative price that is not so bad in Chess but is a lot in Go. I would like to see that kind of hardware (which was described in the article) applied to 19x19 GO using UCT combined with more research on UCT, that could produce something that plays in the Dan range, although I'm very skeptical it will be in the high Dan range, certainly not the stronger than any human player. Having said that, one must be very careful about making predictions, lest one ends up with egg on their face. Computer chess started with wild optimism, then extreme pessimism then big surprise! I clearly remember the days when it was ludicrous to imagine chess computers ever touching even the weak masters. It was just not possible and a simple calculation on a paper napkin proved that it could never happen. Woops! In those days you were considered an idealistic fool if you were optimistic but it turns out the optimistic ones were the most realistic and the ones who were objectively reasonable and pragmatic were the fools. I never did scaling experiments on 19x19 with UCT, but I have no reason to believe it would not show the same amazing scaling curve. Lazarus is so weak at 19x19 that it would take a few doublings of speed to get competitive with reasonably good programs. Has anyone else done scaling experiments with 19x19 and UCT? - Don Ian Osgood wrote: Greetings, I noticed that the following link was recently added to the Computer Go Wikipedia article. http://www.spectrum.ieee.org/oct07/5552 Cracking Go, by Feng-hsiung Hsu, IEEE Spectrum magazine, October 2007. He claims it should be possible to build a Go machine stronger than any human player. Ian ___ computer-go mailing list computer-go@computer-go.org
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 It still has the scent of alpha-beta-with-some-evaluation-function, which is probably not the right paradigm for go. No matter how you slice it, the problem is evaluation. I'm a strong believe in tree search, but it must be combined with knowledge in the right proportions. UCT is a very clever tree search algorithm, very smart because it's incredibly selective and yet it uses on the fly experience to simulate GO knowledge. I think it also happens to simulate how we humans play better than even the pure knowledge and pattern approach. Humans use pattern knowledge at a low level and imagination at a high level and good UCT implementations simulate this well in my opinion. In my opinion, UCT is the best thing we have right now. If UCT had not been discovered, then Hsu's approach is perfectly reasonable and would be the best known try although it would surely produce weak play. But I think he is capable of making a piece of hardware using alpha beta that will beat the current best programs. I have done experiments with patterns that suggest that it would be possible to build a heavily pruned tree which could be used in a global searcher using ordinary alpha beta pruning. The amount of pruning possible (in a reasonably fast way) is hard to determine, I never found enough to make a global searcher very feasible in 19x19. The idea is to use patterns to find moves that have very low probability of being playable.For a scalable alpha beta searcher the probability of being playable would have to be considered by depth (prune more near leaf nodes.) So I personally believe a feasible alpha/beta searcher is possible, if a high quality evaluation function is combined with a highly selective global search in a pragmatic way.One has to be very aggressive about finding moves that can be thrown out and this is tough problem. It's not hard to find a few moves that can be pruned, but it's difficult to eliminate the MAJORITY of moves without throwing out the baby with the bathwater. - - Don We'll see. AvK ___ 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 iD8DBQFHAnd2DsOllbwnSikRAoFWAJ46NF6RFmyd0+xKzDirD8ZmCfsA3ACfcntX HubWY0nNQa8bDtJ3JsMLefA= =LwC5 -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
The null move test is to play 2 moves in a row for one side and consider the result an upper bound. (or conversely to consider the result a lower bound for the other side.) I take it that without a good evaluation function to distinguish the value of a move with other moves one or two ply down into the tree, especially in the early game, that null move prune is ineffective for pruning the tree. And worse, if the evaluation function is wrong. Also, is it just me that a good evaluation function early in the game is difficult to write? On a slight different topic, for those of you with experience writing an evaluation function for an alpha-beta search, do you use the number of total moves played to weight different parts of the evaluation function? For example, it is easier towards the end of the game to know the certainly of certain points and use that as the evaluation function. But at the beginning of the game, an estimate of territory seems to be a better function (in light of not knowing the certain of any or few points). How do you merge these functions as the game transitions between middle game to end game? (and as different parts of the board are in various stages too). Phil___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On 10/2/07, Phil G [EMAIL PROTECTED] wrote: Also, is it just me that a good evaluation function early in the game is difficult to write? I think it's doable. It's just not trivial. Simple pattern matching should give a reasonable approximation for corner spats at the start of the game. Feeding group safety into an overall evaluation should be able to give tenuki plays. Books on opening theory seem relatively straightforward. I've neither coded it into my bot or mastered it in my play... So it could be tougher than I think it is ;) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
From my conversations with dan-level players, analysis in the fuseki is not broad. They'll consider a handful of moves at any point - should I play in the open corner first, or respond to an approach move, or make my own approach move? Candidate moves are chosen from a small set of patterns - mostly 3rd and 4th line plays. The evaluation function is approximate - do I have more influence and profit than my opponent or not? Behind this higher-level analysis is an understanding of tactics - a good player knows not only that a particular play is joseki and another is not, but knows why; knows how to follow up to gain local advantage; how to give up a little to gain something more. If this sort of knowledge could be grafted together with the extensive search capabilities of computer programs, especially on the multicore architectures now becoming available, dan-level programs should be in reach. Be a better Globetrotter. Get better travel answers from someone who knows. Yahoo! Answers - Check it out. http://answers.yahoo.com/dir/?link=listsid=396545469___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On Oct 2, 2007, at 10:33 AM, Phil G wrote: On a slight different topic, for those of you with experience writing an evaluation function for an alpha-beta search, do you use the number of total moves played to weight different parts of the evaluation function? For example, it is easier towards the end of the game to know the certainly of certain points and use that as the evaluation function. But at the beginning of the game, an estimate of territory seems to be a better function (in light of not knowing the certain of any or few points). How do you merge these functions as the game transitions between middle game to end game? (and as different parts of the board are in various stages too). Phil This problem crops up in computer chess. The middlegame evaluation differs markedly from endgame evaluation. For example, in the former you wish to keep the king protected whereas in the endgame it becomes a mobile, active piece. One technique is to perform both evaluations, then combine them continuously weighted on how much the current position is middle-game-like or endgame-like. For example, it could be a linear combination dependent on the amount of material left on the board. In Go, it could be some other measure of the progress of the game, such as stone density or move number. It is important that the evaluations be combined continuously instead of via a sudden cutoff or threshold, in order to avoid border effects. Ian___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
Hsu wrote: If we assume the top Go players calculate about as deeply as the top chess players do, the result should be a machine that plays Go as well as Deep Blue played chess. I don't think this assumption holds. A high level player reads 25-30 ply sequences (very low branching, but not a ladder, of course). Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 I don't think he was talking about this kind of reading, strong chess players also read in this sense.Especially in the end games where you might envision then next 10 moves or more (which is 20 ply or more.) It's harder to do in chess (because the pieces don't always stay put), but it's still done quite a bit. - - Don Christoph Birk wrote: Hsu wrote: If we assume the top Go players calculate about as deeply as the top chess players do, the result should be a machine that plays Go as well as Deep Blue played chess. I don't think this assumption holds. A high level player reads 25-30 ply sequences (very low branching, but not a ladder, of course). Christoph ___ 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 iD8DBQFHAsG7DsOllbwnSikRAqOeAKCBtDOP3PNjAeScw8CoOcGU+S2oBQCgxgJp g9jbIWuxE9NrFBnYFZ0yQqI= =UO7E -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On Tue, 2 Oct 2007, Don Dailey wrote: I don't think he was talking about this kind of reading, strong chess players also read in this sense. What other kind of reading is there? I was am talking about the common term (in Go and Chess) reading ahead. It's harder to do in chess (because the pieces don't always stay put), but it's still done quite a bit. Yes it is ... that's why humans cannot read as deep in Chess as they can in Go. That's my point. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 He wasn't talking about reading at all. I was being nice when I said he wasn't talking about that kind of reading - giving you the benefit of the doubt. - - Don Christoph Birk wrote: On Tue, 2 Oct 2007, Don Dailey wrote: I don't think he was talking about this kind of reading, strong chess players also read in this sense. What other kind of reading is there? I was am talking about the common term (in Go and Chess) reading ahead. It's harder to do in chess (because the pieces don't always stay put), but it's still done quite a bit. Yes it is ... that's why humans cannot read as deep in Chess as they can in Go. That's my point. Christoph ___ 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 iD8DBQFHAsvkDsOllbwnSikRAhaYAKDHtqm8dcYZDZIGLYog4OWNBbu9wACfaQXA b9GzmHBeZrj3WN4DjJOjrDc= =U7th -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On Tue, Oct 02, 2007 at 12:27:28PM -0400, Don Dailey wrote: I don't believe null move pruning will be effective in Go. The basic principle of null move pruning has been described in a couple of ways: 1. threat analysis 2. bounds checking. In go terms, doesn't that translate to something like understanding sente? And to the problems of local sente vs. global sente? -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On Tue, Oct 02, 2007 at 06:02:53PM +0200, Alain Baeckeroot wrote: Unless i missed something in this 4 pages article, there is nothing in it ! Just vague phrase, and assumption that brute force (ala deep blue) _may_ give a strong go machine. I think classical, MC and UCT programmers have contributed much more to computer go than this respectable researcher. I wouldn't put it as strongly, but I also noticed that MC and UCT and suclike techniques were not mentioned at all. I am not sure how that affects the predictions. On one hand, the article seems overly optimistic, but on the other hand, it does not consider the latest techniques that have shown some real promise, indicating that it may be underestimating the future programs... Maybe there are other inventions coming up in the near future that make the optimism more justified? -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On Tue, Oct 02, 2007 at 10:33:09AM -0700, Phil G wrote: Also, is it just me that a good evaluation function early in the game is difficult to write? No, it is not you. The rest of people can be divided in two groups. Some believe such a function is easy to write. Let them come forth and show their results! The rest of us believe such a function is (almost?) impossible to write. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
I wouldn't put it as strongly, but I also noticed that MC and UCT and suclike techniques were not mentioned at all. to be fair to the article, in fact they were. you just have to click on all of the links in the article to see it. s. Yahoo! oneSearch: Finally, mobile search that gives answers, not web links. http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
I wouldn't put it as strongly, but I also noticed that MC and UCT and suclike techniques were not mentioned at all. to be fair to the article, in fact they were. you just have to click on all of the links in the article to see it. For others, like me, who missed the link, it is here: http://www.spectrum.ieee.org/oct07/5552/monte But this is just talking about monte carlo; no mention of UCT, which (as Don said earlier in this thread) is the best (global) search algorithm we have right now, and it would be dangerous to ignore it. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
For others, like me, who missed the link, it is here: http://www.spectrum.ieee.org/oct07/5552/monte But this is just talking about monte carlo; no mention of UCT, which (as Don said earlier in this thread) is the best (global) search algorithm we have right now, and it would be dangerous to ignore it. actually, direct search is better, for instance, on 3x3 boards. the relevant issue is 19x19 boards. s. Don't let your dream ride pass you by. Make it a reality with Yahoo! Autos. http://autos.yahoo.com/index.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Christoph Birk wrote: On Tue, 2 Oct 2007, Don Dailey wrote: He wasn't talking about reading at all. I was being nice when I said he wasn't talking about that kind of reading - giving you the benefit of the doubt. Please explain what he meant by calculating about as deeply. Hsu thinks in terms of chess programming and from the article he was comparing the depth of the search of Chess to Go, trying to make a case that with modern hardware you would be able to search to the same depths that Deep Blue used to search in chess.So a chess search normally iterates until it runs out of time - searching 1 ply, then 2, then 3 etc. So when he says as deeply he means that if Deep blue did a 12 ply search (for instance) he thought a Go program might manage a 12 ply search (I disagree, but that's beside the point.) Of course 12 ply doesn't really mean exactly 12 ply - it means a highly selective search where you might look up to 20 or 30 ply with extensions and quiescence.I'm using 12 ply as an example, I don't know how deep Deep Blue actually searched. In Chess it is very common for good players to look very deeply in tactical situations and endgames. There is nothing special about searching this deeply in chess, it's done in most 2 player games of perfect information and of course in Go it's called reading. - - Don Thank you, Christoph ___ 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 iD8DBQFHAuq9DsOllbwnSikRAt3nAKCudyGRKCuMmYgQggfBZc5Pfvd73wCfeWtF A3Gi4fb4yx7PoQetLSB7Mhg= =ylAl -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] IEEE Spectrum article by Deep Blue creator
Many Faces does not use null move, but does extensive caching of life and death and other tactical results. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of terry mcintyre Sent: Tuesday, October 02, 2007 9:21 AM To: computer-go Subject: Re: [computer-go] IEEE Spectrum article by Deep Blue creator - Original Message From: Don Dailey [EMAIL PROTECTED] I think [Hsu] is betting on null move proving - but I'm real skeptical that it will be effective in Computer Go. It will indeed reduce the tree significantly, but this comes at a qualitative price that is not so bad in Chess but is a lot in Go. Hsu also discusses the gains from caching life-and-death analysis of groups. I suspect that this will greatly reduce computational effort, once an efficient mechanism is implemented. Existing monte carlo programs cache information about playable/non playable points; when augmented with knowledge about life and death, search should more quickly home in on crucial lines of play. I've been playing against Mogo the last few weeks. It has a very interesting style of play, and it often does quite well in tactical analysis, but sometimes it misses a key move and fails to kill or fails to preserve a large group - game over! A good life-and-death cache would be a definite improvement. Caching parts of trees works better in Go, since well-defined sections of the board can sometimes be partitioned from the rest of the board. Where such partitions leak, analysis is likely to be critical; for example, ladders and ladder breakers can extend across the board; invasions often depend on cutting points halfway across the board. _ Building a website is a piece of cake. Yahoo! Small Business gives you all http://us.rd.yahoo.com/evt=48251/*http://smallbusiness.yahoo.com/webhosting /?p=PASSPORTPLUS the tools to get online. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
