Re: [computer-go] How does MC do with ladders?
On Wed, Dec 19, 2007 at 12:21:18AM -0500, Chris Fant wrote: I just witnessed CrazyStone defend a fairly long ladder, resulting in a dead 17-stone block. Why not use a ladder reader at the root of the UCT tree to prevent provably bad ladder moves from being considered? I don't know for sure, but I suspect that even if it means that it would not play out a bad ladder, the UCT would still see it as a desirable thing, and direct the game towards one - and then not play it. Plus, it is not quite trivial to recognize a bad ladder - some times it pays off to extend a stone that is in atari, and then sacrifice two stones. Some nakade shapes also require sacrificing more than one stone... - Heikki -- 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] How does MC do with ladders?
On Dec 19, 2007 9:40 AM, Heikki Levanto [EMAIL PROTECTED] wrote: On Wed, Dec 19, 2007 at 12:21:18AM -0500, Chris Fant wrote: I just witnessed CrazyStone defend a fairly long ladder, resulting in a dead 17-stone block. Why not use a ladder reader at the root of the UCT tree to prevent provably bad ladder moves from being considered? I don't know for sure, but I suspect that even if it means that it would not play out a bad ladder, the UCT would still see it as a desirable thing, and direct the game towards one - and then not play it. Still better than actually playing it out. Another idea I had was to do a tactical analysis of a block whenever the UCT node has been hit X number of times. When the move is provably pointless (e.g. adding to a dead block), prevent that line from continuing to be explored. If X is large enough and the tactical analysis is restricted enough, hopefully it won't significantly affect the overall speed. And it has the nice trait that it can be used not only at the root but at any level in the tree. Plus, it is not quite trivial to recognize a bad ladder - some times it pays off to extend a stone that is in atari, and then sacrifice two stones. Some nakade shapes also require sacrificing more than one stone... But this was the trivial kind and it cost the game. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
On Dec 11, 2007 11:36 AM, Rémi Coulom [EMAIL PROTECTED] wrote: Question: how do MC programs perform with a long ladder on the board? Crazy Stone handles ladder with progressive widening. Ladder atari is usually ranked first or very high in the move list, and ladder extension lower. So, the tree-search part usually does not read out the ladder completely, but prunes the extension. It seems to work well in practice. Because progressive widening will include the ladder extension at some point, Crazy Stone may still play ladder extensions if it finds reasons to do so. I just witnessed CrazyStone defend a fairly long ladder, resulting in a dead 17-stone block. Why not use a ladder reader at the root of the UCT tree to prevent provably bad ladder moves from being considered? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
I just witnessed CrazyStone defend a fairly long ladder, resulting in a dead 17-stone block. Why not use a ladder reader at the root of the UCT tree to prevent provably bad ladder moves from being considered? I meant to include the CGOS-19 game number: 7613 The game is still in progress as of this writing, but once it's finished, it should be at http://www.lri.fr/~teytaud/SGF/2007/12/19/7613.sgf ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Forrest, similar multi-level or hierarchical/partitioned search concepts have been suggested by several people here over the years, myself included many times. I first suggested a chunking probability based search concept back in 1998. I have long been an advocate of goal-directed hierarchical search for Go, but haven't yet figured out how to make it work in practice. I tried some things years before MC/UCT popped up without any real success. There could perhaps be some promise in finding ways to combine some of these multi-level ideas with MC/UCT search techniques. I don't understand the follow-up to your post claiming that you can't do this for these kinds of games because they are not forcing move sequences. We're talking about the play-out part of the search used to sample the game tree. Anything goes, right? Of course, whether any particular play-out method helps or not is another question. -Matt Forrest Curo wrote: It's the approach I believe to be more human-like. Not necessarily the playing style. Human beings chunk. What all this fuss suggests to me is a meta-mc program... You include routines that work out good sequences, as a human would--and then you have the random part of the program include the more promising sequences, where applicable, as if they were individual moves. Forrest Curo This message was sent using IMP, the Internet Messaging Program. ___ 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] How does MC do with ladders?
On Dec 13, 2007 2:03 AM, Harald Korneliussen [EMAIL PROTECTED] wrote: Wed, 12 Dec 2007 07:14:48 -0800 (PST) terry mcintyre wrote: Heading back to the central idea, of tuning the predicted winning rates and evaluations: it might be useful to examine lost games, look for divergence between expectations and reality, repair the predictor, and test the new predictor against a large database of such blunders. Sounds a little like Temporal Difference Learning to me. I understand both MoGo and Crazystone use patterns, do anyone know whether they use such machine learning techniques to assign weights to them? MoGo uses TD to predict win rates. I haven't heard of any other methods to predict winning rates. I have seen some successful stuff with predicting the next move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
steve uurtamo wrote: Currently there is no evidence whatsoever that probability estimates are inferior and they are the ones playing the best GO right now are they? Yes - in both 9x9 and 19x19 go. - Don s. Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping ___ 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] How does MC do with ladders?
Currently there is no evidence whatsoever that probability estimates are inferior and they are the ones playing the best GO right now are they? s. Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
On 12/11/07, Mark Boon [EMAIL PROTECTED] wrote: Question: how do MC programs perform with a long ladder on the board? My understandig of MC is limited but thinking about it, a crucial long ladder would automatically make the chances of any playout winning 50-50, regardless of the actual outcome of the ladder. No, 50/50 would make too much sense. It might be higher or it might be lower, depending on whose move it is in the ladder and what style of playouts you use, but exactly 50/50 would be like flipping a coin and having it land on its edge. In test cases, MC-UCT evaluations tend to cluster near 50/50 in any case, because MC-UCT, especially dumb uniform MC-UCT, tends to be conservative about predicting the winner, especially in 19x19 where the opportunities for luck to overwhelm the actual advantage on the board are greater. But if you accept this as just a moot scaling issue -- that a clearly lopsided exchange can mean just a 2% increment in winning percentage even if read more or less correctly -- then the numbers may not look so even after all. I's certainly possible for MC-UCT to climb a broken ladder in a winning position (and climbing a broken ladder in an even position is at least half as bad as that anyhow). I tried testing this on 19x19 using libego at 1 million playouts per move. The behavior was not consistent, but the numbers trended in the defender's favor as the sides played out the ladder. In one bizarre case, the attacker played out the ladder until there were just 17 plies left, and then backed off. Why would the attacker give up a winning ladder? It appears the MC-UCT was never actually reading the ladder to begin with; just four or five plies in, sometimes just a few thousand simulations were still following the key line. 1 million playouts were not nearly enough for that in this case; maybe 100 million would be enough, but I couldn't test that. Also, after enough simulations, decisively inferior moves lead to fewer losses than slightly inferior ones. Suppose you have three moves available: one wins 75% of the time, one 50%, and one 25%. In the long run, the 75% move will be simulated almost all the time, but the middle move will be simulated roughly four times as often as the 25% one that, compared to the best move available, is twice as bad, and four times the simulations with half the loss per simulation adds up to twice the excess losses compared to the 25% move. That is apropos here, because giving up on an open-field ladder once it has been played out for a dozen moves is much more painful for the defender than for the attacker. The longer the ladder got, the more the evaluations trended in the defender's favor, and my best explanation would be the fact that -- until you actually read the ladder all the way out and find that the defender is dead -- every move except pulling out of atari is so obviously bad that even uniform MC-UCT did a better job of focusing on that one good move. (Incidentally, the conservative nature of MC-UCT ratings largely explains why maximizing winning probabilities alone is not a bad strategy, at least in even games. The classic beginner mistake, when you already have a clear lead in theory, is to fail to fight hard to grab still more points as blunder insurance. But an MC-UCT evaluation of 90% typically means a 90% probability of actually winning against even opposition, not just a 90% likelihood of a theoretical win. Assigning a 65% evaluation to an obvious THEORETICAL win allows plenty of room to assign higher evaluations to even more lopsided advantages. As Don said, when MC-UCT starts blatantly throwing away points for no obvious reason, it's almost certainly because the game is REALLY over, because MC-UCT's errors tend to be probabilistic instead of absolute -- it may in effect evaluate a dead group as 75% alive, but it won't call it 100% alive except in the rare cases when the underlying random playout rules forbid the correct line of play.) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Eric, Yes, as Magnus also stated MC play-out doesn't really accurately estimate the real winning probability but it still get the move order right most of the time. The situation is that if the position is really a win, it doesn't mean that a MC is able to find the proof tree. But it means that it's easier to find wins than losses as so the score as expressed by a winning percentage goes up - but not to 1.0 I have also found that if Lazarus says 60%, it is going to win much more than 60% against equal opposition. Of course it's not surprise if it beats weaker opposition from this point. I thought of mapping these percentages to actual percentages by playing a few thousand self play games, but this is pretty much futile. If the score is, for instance 65% it will tend to grow higher and higher depending on how long I let it think.Unless it discovers a clever defense that is - so it's possible that it will start declining at a deep level. So these numbers are really meaningless as absolute figures and have everything to do with the current context of the search. - Don Eric Boesch wrote: On 12/11/07, Mark Boon [EMAIL PROTECTED] wrote: Question: how do MC programs perform with a long ladder on the board? My understandig of MC is limited but thinking about it, a crucial long ladder would automatically make the chances of any playout winning 50-50, regardless of the actual outcome of the ladder. No, 50/50 would make too much sense. It might be higher or it might be lower, depending on whose move it is in the ladder and what style of playouts you use, but exactly 50/50 would be like flipping a coin and having it land on its edge. In test cases, MC-UCT evaluations tend to cluster near 50/50 in any case, because MC-UCT, especially dumb uniform MC-UCT, tends to be conservative about predicting the winner, especially in 19x19 where the opportunities for luck to overwhelm the actual advantage on the board are greater. But if you accept this as just a moot scaling issue -- that a clearly lopsided exchange can mean just a 2% increment in winning percentage even if read more or less correctly -- then the numbers may not look so even after all. I's certainly possible for MC-UCT to climb a broken ladder in a winning position (and climbing a broken ladder in an even position is at least half as bad as that anyhow). I tried testing this on 19x19 using libego at 1 million playouts per move. The behavior was not consistent, but the numbers trended in the defender's favor as the sides played out the ladder. In one bizarre case, the attacker played out the ladder until there were just 17 plies left, and then backed off. Why would the attacker give up a winning ladder? It appears the MC-UCT was never actually reading the ladder to begin with; just four or five plies in, sometimes just a few thousand simulations were still following the key line. 1 million playouts were not nearly enough for that in this case; maybe 100 million would be enough, but I couldn't test that. Also, after enough simulations, decisively inferior moves lead to fewer losses than slightly inferior ones. Suppose you have three moves available: one wins 75% of the time, one 50%, and one 25%. In the long run, the 75% move will be simulated almost all the time, but the middle move will be simulated roughly four times as often as the 25% one that, compared to the best move available, is twice as bad, and four times the simulations with half the loss per simulation adds up to twice the excess losses compared to the 25% move. That is apropos here, because giving up on an open-field ladder once it has been played out for a dozen moves is much more painful for the defender than for the attacker. The longer the ladder got, the more the evaluations trended in the defender's favor, and my best explanation would be the fact that -- until you actually read the ladder all the way out and find that the defender is dead -- every move except pulling out of atari is so obviously bad that even uniform MC-UCT did a better job of focusing on that one good move. (Incidentally, the conservative nature of MC-UCT ratings largely explains why maximizing winning probabilities alone is not a bad strategy, at least in even games. The classic beginner mistake, when you already have a clear lead in theory, is to fail to fight hard to grab still more points as blunder insurance. But an MC-UCT evaluation of 90% typically means a 90% probability of actually winning against even opposition, not just a 90% likelihood of a theoretical win. Assigning a 65% evaluation to an obvious THEORETICAL win allows plenty of room to assign higher evaluations to even more lopsided advantages. As Don said, when MC-UCT starts blatantly throwing away points for no obvious reason, it's almost certainly because the game is REALLY over, because MC-UCT's errors tend to be probabilistic instead of absolute -- it
Re: [computer-go] How does MC do with ladders?
Jason House wrote: MoGo uses TD to predict win rates. Really? Where did you get that information? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
On Dec 13, 2007 11:39 AM, Gian-Carlo Pascutto [EMAIL PROTECTED] wrote: Jason House wrote: MoGo uses TD to predict win rates. Really? Where did you get that information? I can't seem to load http://www.lri.fr/~gelly/MoGo.htm at the moment, but I found it there. One of the papers you can find from there is very heavy in ML terminology. It took me a very long time to work my way through it since I knew nothing about ML. The paper introduces RAVE and near the end talks about using heuristics for initial parameter estimation. The heuristic they used was based TD. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
It's the approach I believe to be more human-like. Not necessarily the playing style. Human beings chunk. What all this fuss suggests to me is a meta-mc program... You include routines that work out good sequences, as a human would--and then you have the random part of the program include the more promising sequences, where applicable, as if they were individual moves. Forrest Curo This message was sent using IMP, the Internet Messaging Program. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
On Dec 13, 2007 2:28 PM, Forrest Curo [EMAIL PROTECTED] wrote: It's the approach I believe to be more human-like. Not necessarily the playing style. Human beings chunk. What all this fuss suggests to me is a meta-mc program... You include routines that work out good sequences, as a human would--and then you have the random part of the program include the more promising sequences, where applicable, as if they were individual moves. You can't do that in two-player games, unless you are convinced that the opponent is forced throughout the entire sequence. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Jason House wrote: The paper introduces RAVE and near the end talks about using heuristics for initial parameter estimation. The heuristic they used was based TD. Ah, you're talking about RLGO. RLGO was trained with TD, but MoGo itself doesn't use TD (directly). There are posts from Sylvain and David here that the latest MoGo's use a simpler and faster heuristic which works just as well. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
On Dec 13, 2007 3:52 PM, Gian-Carlo Pascutto [EMAIL PROTECTED] wrote: Jason House wrote: The paper introduces RAVE and near the end talks about using heuristics for initial parameter estimation. The heuristic they used was based TD. Ah, you're talking about RLGO. RLGO was trained with TD, but MoGo itself doesn't use TD (directly). There are posts from Sylvain and David here that the latest MoGo's use a simpler and faster heuristic which works just as well. Is it possible for you to provide a link to those posts? I've missed them but would be highly interested in them. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Quoting Álvaro Begué [EMAIL PROTECTED]: On Dec 13, 2007 2:28 PM, Forrest Curo [EMAIL PROTECTED] wrote: It's the approach I believe to be more human-like. Not necessarily the playing style. Human beings chunk. What all this fuss suggests to me is a meta-mc program... You include routines that work out good sequences, as a human would--and then you have the random part of the program include the more promising sequences, where applicable, as if they were individual moves. You can't do that in two-player games, unless you are convinced that the opponent is forced throughout the entire sequence. Humans do a sort of skinny alpha-beta, automatically narrowing the search by applying constraints based on what they see as possible outcomes. (In the case of a ladder, most of this is searching a long branch one-move wide!) So if an opponent fails to follow the sequence you've expected, he might be on to something you missed, or he may have missed the point of the sequence. An unexpected move thus suggests a pair of local searches, concentrating both on the vicinity of that move and on the vicinity of the expected move. But for a program to do something similar, it does need some way of arriving at an idea of what moves in a certain area could reasonably be expected to accomplish. Seeing where the groups end up in a large number of playoffs might give a hint...(?) Forrest Curo This message was sent using IMP, the Internet Messaging Program. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
On Tue, 2007-12-11 at 21:17 -0500, Don Dailey wrote: But what does this have to do with anything? What we are arguing about is whether it's good to try to estimate probabilities. That's what you have been critical of. Adding ladder code will improve any evaluation function if done correctly but that's not relevant if you believe estimating probability is foolish. To the contrary, I believe it is brilliant - in my opinion it is a key factor in the success of these programs and I would call it a key breakthrough. Sorry, it just sounded like you lauded the failures of MC as virtues. I'm not opposed to random playouts as an evaluator. Just undue hope and reliance on it. I think that to make a breakthrough in go AI, we need diversity. Both within a program (use what works when it works, including dropping any randomness at all when pure knowledge or full search would yield results), and between bots. What we *don't* need is people giving up on an approach without even trying it, because others have failed at something similar before. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Raymond Wold wrote: I can code an algorithm that evaluates simple ladders correctly. I'll repeat that. I can code a program that reads ladders better than a pure MC program without knowledge of ladders. I can beat it. Human knowledge programmed into a computer that does that one thing, that basic go skill, better than the MC program. Are you saying that there is absolutely no way to combine such with an MC program to make it better? Not just that no one has done it (I don't know if anyone has) but that it is impossible? Are you saying that attempts to do so are wasted? If you are, I'd appreciate it if you did so clearly. Complaining that MC programs don't read ladders well is a bit like complaining that Forrest Gump can't tie his shoelaces, it seems to me. There will be many things an MC program will be good at that we won't be, and vice versa. It's not unreasonable to believe that progress with MC/UCT programs will be through making most of its strengths, rather than try to patch its weaknesses in a way not compatible with how their brains work. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
David Fotland wrote: I don't think traditional go programs tally features and weights. They estimate the final score. When I say tally features and weights I really mean that they estimate the final score. They basically tally the number of intersections expected to be won, although I'm sure there is a great deal of sophistication in this. I have seen descriptions where they estimate a groups survival likelihood, and if it's say 50% they give it 50% of the area encompassed. There have been prior global game tree approaches. Handtalk and GO Intellect and SmartGo did global searches a decade ago. This is not to detract from UCT, which works very well. UCT/MC programs make moves that look very unnatural, so in that sense they don't play at all like humans play go. It's the approach I believe to be more human-like. Not necessarily the playing style. - Don David -Original Message- From: [EMAIL PROTECTED] [mailto:computer-go- [EMAIL PROTECTED] On Behalf Of Don Dailey Sent: Tuesday, December 11, 2007 11:53 AM To: computer-go Subject: Re: [computer-go] How does MC do with ladders? Hi Petri, I happen to think that MC is the most human like approach currently being tried. The reason I say that is that humans DO estimate their winning chances and tally methods, where you simply tally up features/weights (regardless of how sophisticated) is not how strong humans think about the game. Also, the best first global game tree approach, whatever you call it such as UCT and others, is a very close model of how humans play the game too.We may notice 3 moves that look playable, but gradually come to focus on just 2 of those. Essentially monte carlo does this too.Very narrow focused trees. The play-out portion is a crude approximation for imagination. We basically look at a board and imagine the final position.The MC play-outs kill the dead groups in a reasonably accurate (but fuzzy) way and put the flesh on the skeleton. Near the end of the game, the play-outs end mostly the same the way the game itself would end - and the same way a human would expect it to look like. I attribute the success of MC to the fact that it's the best simulation of how WE do it.The other approaches are clearly more synthetic, including raw MC without a proper tree. - Don Petri Pitkanen wrote: 2007/12/11, terry mcintyre [EMAIL PROTECTED]: With Go, there are many situations which can be read out precisely, provided that one has the proper tools - ladders, the ability to distinguish between one and two eyes; the ability to reduce eyespaces to a single eye with an appropriate placement; and so forth. Failure to recognize such situations is like failing to spot a pinned piece or a passed pawn. I am no fan on MC approach but basically MC can read LD given enough of simulations. It will read them without knowing that they need to be analysed. Point in MC being that once you get more power you get better LD as well, but without extra coding. This approach will result in non-human like game BUT likewise chess programs did not get strong by emulating humans. They just took one simple thing humans do and took it to extreme. Whatever approach will do the trick in go it will be similar in this sense. ___ 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] How does MC do with ladders?
Russ Williams wrote: On Dec 11, 2007 8:53 PM, Don Dailey [EMAIL PROTECTED] wrote: The play-out portion is a crude approximation for imagination. We basically look at a board and imagine the final position.The MC play-outs kill the dead groups in a reasonably accurate (but fuzzy) way and put the flesh on the skeleton. Near the end of the game, the play-outs end mostly the same the way the game itself would end - and the same way a human would expect it to look like. This seems pretty fishy to me, given that MC can't read ladders accurately, for instance, but any competent human can, and that MC plays so bizarrely differently from humans in many positions, especially endgames. There may be strong theoretical arguments why MC is STRONG, and there are clearly empirical demonstrations that MC IS strong, but it is not at all clear that MC is somehow simulating/approximating the mental process of a human player playing the game. If it were, I would expect an MC player to make moves that look a lot more human. It's not surpising that other methods make it look more like a human playing because they are based more on mimicking the moves of a human. Usually a human expert watches the games, see's an error and then makes a pattern.The pattern basically says, play this move because a human would. That's not the human approach, even though it will look human. It's like the chat bot competitions which are turing tests. Try to fool people into believing they are talking to a human - but really it's a random phrase generator with some rules and patterns to mimic a person. - Don I attribute the success of MC to the fact that it's the best simulation of how WE do it.The other approaches are clearly more synthetic, including raw MC without a proper tree. But those synthetic approaches seem MORE like what many human players do (at least humans I've talked to), thinking discretely about different domain-specific concrete things like are there any appropriate josekis for this situation?, can I kill that group? what is its final internal eye shape going to look like?, are any of my groups endangered?, is my opponent's moyo invadable? or reducible?, does this ladder work?, can these 2 groups be separated?, can I make these stones live? can I do it in sente?, who has more ko threats now?, how big is that ko threat compared to the value of this ko?, where is the biggest endgame move right now?, where is the biggest sente endgame move right now?, which of these monkey jumps is bigger?, etc. At a literal detailed analysis level, MC is totally different from how we do it. I know of no human player who imagines the 2 players randomly dropping stones over and over to see what proportion of wins/losses results. The basic philosophy of MC is radically different from how humans think about the game. (Which is not to say that MC is a bad approach of course.) And at a higher level (in terms of the actual moves that actually get chosen by MC), they also look very bizarre compared to a human player, particularly in the end game where (as has been discussed a lot recently) a winning MC often fills its own territory or plays neutral points when real points still exist, something a better-than-beginner (to say nothing of strong) human player would never do. In the opening, strong humans typically are familiar with many joseki, which MC is much less likely to randomly follow. And (to mention the actual subject of this thread...) a competent human player can read out most ladders correctly with certainty, unlike MC. and so on... cheers, russ ___ 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] How does MC do with ladders?
Why does anybody care about how human-like our go programs' playing style is? When we design airplanes we don't care about how bird-like their flying style is; we care about objective measures like speed, acceleration, energy efficiency... The merits of go programs should be based basically on their ability to win games, although other measures might be useful (ability to solve life-and-death problems, or to estimate the final result of an incomplete game). Not being able to read ladders is definitely a weakness of most current MC programs, and discussing ways of incorporating that knowledge into them is interesting, but whether they have human styles or not is completely irrelevant in my opinion. Álvaro. On Dec 12, 2007 8:18 AM, Don Dailey [EMAIL PROTECTED] wrote: Russ Williams wrote: On Dec 11, 2007 8:53 PM, Don Dailey [EMAIL PROTECTED] wrote: The play-out portion is a crude approximation for imagination. We basically look at a board and imagine the final position.The MC play-outs kill the dead groups in a reasonably accurate (but fuzzy) way and put the flesh on the skeleton. Near the end of the game, the play-outs end mostly the same the way the game itself would end - and the same way a human would expect it to look like. This seems pretty fishy to me, given that MC can't read ladders accurately, for instance, but any competent human can, and that MC plays so bizarrely differently from humans in many positions, especially endgames. There may be strong theoretical arguments why MC is STRONG, and there are clearly empirical demonstrations that MC IS strong, but it is not at all clear that MC is somehow simulating/approximating the mental process of a human player playing the game. If it were, I would expect an MC player to make moves that look a lot more human. It's not surpising that other methods make it look more like a human playing because they are based more on mimicking the moves of a human. Usually a human expert watches the games, see's an error and then makes a pattern.The pattern basically says, play this move because a human would. That's not the human approach, even though it will look human. It's like the chat bot competitions which are turing tests. Try to fool people into believing they are talking to a human - but really it's a random phrase generator with some rules and patterns to mimic a person. - Don I attribute the success of MC to the fact that it's the best simulation of how WE do it.The other approaches are clearly more synthetic, including raw MC without a proper tree. But those synthetic approaches seem MORE like what many human players do (at least humans I've talked to), thinking discretely about different domain-specific concrete things like are there any appropriate josekis for this situation?, can I kill that group? what is its final internal eye shape going to look like?, are any of my groups endangered?, is my opponent's moyo invadable? or reducible?, does this ladder work?, can these 2 groups be separated?, can I make these stones live? can I do it in sente?, who has more ko threats now?, how big is that ko threat compared to the value of this ko?, where is the biggest endgame move right now?, where is the biggest sente endgame move right now?, which of these monkey jumps is bigger?, etc. At a literal detailed analysis level, MC is totally different from how we do it. I know of no human player who imagines the 2 players randomly dropping stones over and over to see what proportion of wins/losses results. The basic philosophy of MC is radically different from how humans think about the game. (Which is not to say that MC is a bad approach of course.) And at a higher level (in terms of the actual moves that actually get chosen by MC), they also look very bizarre compared to a human player, particularly in the end game where (as has been discussed a lot recently) a winning MC often fills its own territory or plays neutral points when real points still exist, something a better-than-beginner (to say nothing of strong) human player would never do. In the opening, strong humans typically are familiar with many joseki, which MC is much less likely to randomly follow. And (to mention the actual subject of this thread...) a competent human player can read out most ladders correctly with certainty, unlike MC. and so on... cheers, russ ___ 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
Re: [computer-go] How does MC do with ladders?
Álvaro Begué wrote: Why does anybody care about how human-like our go programs' playing style is? When we design airplanes we don't care about how bird-like their flying style is; we care about objective measures like speed, acceleration, energy efficiency... The merits of go programs should be based basically on their ability to win games, although other measures might be useful (ability to solve life-and-death problems, or to estimate the final result of an incomplete game). Not being able to read ladders is definitely a weakness of most current MC programs, and discussing ways of incorporating that knowledge into them is interesting, but whether they have human styles or not is completely irrelevant in my opinion. I'm with you on this. I don't care if they look like human players.I care about how strong they play. However I do believe you can make an argument that internally they think more like a human.Nevertheless, no matter how you slice it all program are synthetic. For some reason, and I don't know if it applies as much in GO, humans seem to value a program that plays more human-like. Perhaps it makes them feel that there is more intelligence behind it. Here is an odd experience from computer chess.Many years ago I had some experts over to my house and we played games all night long of speed chess against 2 well known stand-alone programs. One of them was well known for it's human-like playing style and interesting play. The other was well known for it's very solid style and playing strength. They very much enjoyed playing the human-like program but played many games against each. I asked them which was stronger and there was no question in their mind - it was the one that played human-like. When I told them that it was the other machine that was stronger (by quite a large margin) they did not believe me. So we played several games between the two and the human-like program lost every game. The continued to believe it was some kind of fluke and thus we ended up playing about 10 games, where every game was a loss for the machine the believed must be stronger. This was a bit of an experiment in human psychology I think.I also believe we are unduly influenced by our eyes. The weaker machine was enclosed inside a beautiful sensory board, was physically much larger and had nice wood pieces.The stronger machine was a couple of years more up to date but was enclosed in a cheap plastic housing, had a cheesy pressure sensitive board (you had to press on the squares) and had cheap looking plastic pieces - it was a budget computer but it was clearly stronger. Although I think the playing style was more of an influence I'm sure the outward appearance of the device played a role. This is something all retailers know - it's all about the packaging, advertising, presentation. Packaging over real substance. I think us humans are a bit ego-centric. If something plays like us, we probably equate this with actual intelligence.It's like the warthogs in the far-side comic where the female warthog is saying to the other female warthog (in a bar) that he thinks he is god's gift to warthogs. Warthogs probably think they are beautiful just as we think we are. - Don Álvaro. On Dec 12, 2007 8:18 AM, Don Dailey [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Russ Williams wrote: On Dec 11, 2007 8:53 PM, Don Dailey [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: The play-out portion is a crude approximation for imagination. We basically look at a board and imagine the final position.The MC play-outs kill the dead groups in a reasonably accurate (but fuzzy) way and put the flesh on the skeleton. Near the end of the game, the play-outs end mostly the same the way the game itself would end - and the same way a human would expect it to look like. This seems pretty fishy to me, given that MC can't read ladders accurately, for instance, but any competent human can, and that MC plays so bizarrely differently from humans in many positions, especially endgames. There may be strong theoretical arguments why MC is STRONG, and there are clearly empirical demonstrations that MC IS strong, but it is not at all clear that MC is somehow simulating/approximating the mental process of a human player playing the game. If it were, I would expect an MC player to make moves that look a lot more human. It's not surpising that other methods make it look more like a human playing because they are based more on mimicking the moves of a human. Usually a human expert watches the games, see's an error and then makes a pattern.The pattern basically says, play this move because a human would. That's not the human
Re: [computer-go] How does MC do with ladders?
Hear, hear! The question is not one of abandonment of the recognition of uncertainty. Like Don Dailey, I think it's brilliant that UCT programs explicitly manage uncertainty and winning probabilities. My concern is that existing implementations have some serious but possibly fixable flaws in those estimates; there are numerous situations where the game can actually be analytically proven to be won by a large margin, but the UCT/MC algorithms are mis-evaluating the situation considerably. I'd be careful about looking merely at winning rates against mediocre programs ( and even the best Go programs of today are not that great at 19x19 go ). Whenever a human thinks beating lots of mid-kyu players makes him Meijin, a few games with a high-dan player or a pro would dispel such notions. I'm just asking what are the next steps? It's great that cpu power is getting dramatically cheaper, and great that UCT algorithms do improve with more cpus and more playouts, but there's a lot of room for improvement. Here's hope that we find lots of interesting avenues for such improvements! Heading back to the central idea, of tuning the predicted winning rates and evaluations: it might be useful to examine lost games, look for divergence between expectations and reality, repair the predictor, and test the new predictor against a large database of such blunders. When I was learning to shoot, we were taught to focus first on accuracy, second on speed. Under tournament conditions, speed is very crucial, but tuning the accuracy of the evaluations is likely to reduce the noise rate, and winnow out a fair number of losing plays. 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: Raymond Wold [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, December 12, 2007 12:23:15 AM Subject: Re: [computer-go] How does MC do with ladders? On Tue, 2007-12-11 at 21:17 -0500, Don Dailey wrote: But what does this have to do with anything? What we are arguing about is whether it's good to try to estimate probabilities. That's what you have been critical of. Adding ladder code will improve any evaluation function if done correctly but that's not relevant if you believe estimating probability is foolish. To the contrary, I believe it is brilliant - in my opinion it is a key factor in the success of these programs and I would call it a key breakthrough. Sorry, it just sounded like you lauded the failures of MC as virtues. I'm not opposed to random playouts as an evaluator. Just undue hope and reliance on it. I think that to make a breakthrough in go AI, we need diversity. Both within a program (use what works when it works, including dropping any randomness at all when pure knowledge or full search would yield results), and between bots. What we *don't* need is people giving up on an approach without even trying it, because others have failed at something similar before. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Terry, Yes, I agree with everything here I think.Nobody ever suggested that we should not improve the accuracy of the probability estimator. In fact almost all the progress so far has been based on doing exactly that. The programs are getting slower but smarter. - Don terry mcintyre wrote: Hear, hear! The question is not one of abandonment of the recognition of uncertainty. Like Don Dailey, I think it's brilliant that UCT programs explicitly manage uncertainty and winning probabilities. My concern is that existing implementations have some serious but possibly fixable flaws in those estimates; there are numerous situations where the game can actually be analytically proven to be won by a large margin, but the UCT/MC algorithms are mis-evaluating the situation considerably. I'd be careful about looking merely at winning rates against mediocre programs ( and even the best Go programs of today are not that great at 19x19 go ). Whenever a human thinks beating lots of mid-kyu players makes him Meijin, a few games with a high-dan player or a pro would dispel such notions. I'm just asking what are the next steps? It's great that cpu power is getting dramatically cheaper, and great that UCT algorithms do improve with more cpus and more playouts, but there's a lot of room for improvement. Here's hope that we find lots of interesting avenues for such improvements! Heading back to the central idea, of tuning the predicted winning rates and evaluations: it might be useful to examine lost games, look for divergence between expectations and reality, repair the predictor, and test the new predictor against a large database of such blunders. When I was learning to shoot, we were taught to focus first on accuracy, second on speed. Under tournament conditions, speed is very crucial, but tuning the accuracy of the evaluations is likely to reduce the noise rate, and winnow out a fair number of losing plays. 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: Raymond Wold [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, December 12, 2007 12:23:15 AM Subject: Re: [computer-go] How does MC do with ladders? On Tue, 2007-12-11 at 21:17 -0500, Don Dailey wrote: But what does this have to do with anything? What we are arguing about is whether it's good to try to estimate probabilities. That's what you have been critical of. Adding ladder code will improve any evaluation function if done correctly but that's not relevant if you believe estimating probability is foolish. To the contrary, I believe it is brilliant - in my opinion it is a key factor in the success of these programs and I would call it a key breakthrough. Sorry, it just sounded like you lauded the failures of MC as virtues. I'm not opposed to random playouts as an evaluator. Just undue hope and reliance on it. I think that to make a breakthrough in go AI, we need diversity. Both within a program (use what works when it works, including dropping any randomness at all when pure knowledge or full search would yield results), and between bots. What we *don't* need is people giving up on an approach without even trying it, because others have failed at something similar before. ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://us.rd.yahoo.com/evt=51734/*http://tools.search.yahoo.com/newsearch/category.php?category=shopping ___ 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] How does MC do with ladders?
Wed, 12 Dec 2007 07:14:48 -0800 (PST) terry mcintyre wrote: Heading back to the central idea, of tuning the predicted winning rates and evaluations: it might be useful to examine lost games, look for divergence between expectations and reality, repair the predictor, and test the new predictor against a large database of such blunders. Sounds a little like Temporal Difference Learning to me. I understand both MoGo and Crazystone use patterns, do anyone know whether they use such machine learning techniques to assign weights to them? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Mark Boon wrote: Question: how do MC programs perform with a long ladder on the board? Mogo makes the 20k mistake to push an intrusion of ladder shape into the own territory like tooth paste. I do not know if this is caused by reading ladder-like, by juding the adjacent life wrongly (in a nakade there are often more death than life sequences even if a simple vital point makes life), or by the short but wrong pattern database. The UCT programmers should tell us. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Since Valkyria is slow anyway, I can have it read ladders in the simulations. The ladder code is really fast and a little buggy, but works often enough to not cause major problems. I never tested the benefits of the ladder code it just appeared to be much stronger. -Magnus Quoting Rémi Coulom [EMAIL PROTECTED]: Robert Jasiek wrote: Mark Boon wrote: Question: how do MC programs perform with a long ladder on the board? Crazy Stone handles ladder with progressive widening. Ladder atari is usually ranked first or very high in the move list, and ladder extension lower. So, the tree-search part usually does not read out the ladder completely, but prunes the extension. It seems to work well in practice. Because progressive widening will include the ladder extension at some point, Crazy Stone may still play ladder extensions if it finds reasons to do so. According to some discussions I had with Sylvain in Amsterdam, MoGo's approach is a little more primitive. If I remember correctly, it completely prunes ladder extensions. I am not sure if it is done only at the root, or inside the tree search too. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- 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] How does MC do with ladders?
Rémi Coulom wrote: I don't understand what you mean by push an intrusion of ladder shape into the own territory like tooth paste. The game below is a 9 stone handicap game between me and Mogo. It is my second game against Mogo, after a 7x7 test to understand the GUI and a first even game (further below). I do not know how to set up free handicap placement yet, so the first few moves are a sort of emulation to encourage Mogo to accept a free handicap. Its handicap placement style is very similar to mine. (In fact, Mogo plays pretty similar to my style in the fuseki.) Mogo shows good attacking and some moves are high dan level (while others are double digit kyu level; these occur only as systematic exceptions as with tooth paste or, as others have pointed out, local deep tactical reading; obviously these are the places to embed UCT into a context of go knowledge). The UCT program fuseki is about 3 dan level. (You know, I am in a position to judge about the seemingly random style.) Bad tooth paste ladder pushing moves were: 99, 101, 103, 105, 107, 109, 131 Impressive moves: 73, 139, 159, 161 *** 9 stone game *** (;SZ[19]FF[4]AP[GOWrite:2.1.24]CA[UTF-8]GM[1]PW[ ]PB[MoGo]OT[10 moves / 2 min]KM[7.5]GN[ ]DT[2007-12-08]TM[1200.0]RE[B+3.5] ;BL[119.0]B[dd] ;W[tt]WL[118.0] ;BL[119.0]B[tt] ;W[jj]WL[94.0] ;BL[91.0]B[pp] ;W[od]WL[92.0] ;BL[91.0]B[dp] ;W[pi]WL[87.0] ;BL[73.0]B[nm] ;W[tt]WL[83.0] ;BL[57.0]B[fn] ;W[tt]WL[81.0] ;BL[39.0]B[hd] ;W[tt]WL[79.0] ;BL[24.0]B[jn] ;W[tt]WL[77.0] ;BL[8.0]B[fi] ;W[tt]WL[74.0] ;BL[-8.0]B[hk] ;W[tt]WL[63.0] ;BL[-18.0]B[mj] ;W[tt]WL[59.0] ;BL[-29.0]B[hh] ;W[tt]WL[56.0] ;BL[-40.0]B[jh] ;W[ci]WL[45.0] ;BL[-50.0]B[cn] ;W[jq]WL[43.0] ;BL[-57.0]B[iq] ;W[ir]WL[41.0] ;BL[-73.0]B[jr] ;W[kr]WL[36.0] ;BL[-83.0]B[jp] ;W[js]WL[24.0] ;BL[-101.0]B[lq] ;W[hq]WL[22.0] ;BL[-106.0]B[ip] ;W[kq]WL[20.0] ;BL[-116.0]B[lp] ;W[pm]WL[16.0] ;BL[-129.0]B[mf] ;W[lc]WL[4.0] ;BL[-138.0]B[mb] ;W[nc]WL[0.0] ;BL[-150.0]B[jd] ;W[bf]WL[-40.0] ;BL[-167.0]B[df] ;W[dc]WL[-47.0] ;BL[-172.0]B[ec] ;W[cc]WL[-50.0] ;BL[-184.0]B[cd] ;W[bd]WL[-51.0] ;BL[-197.0]B[be] ;W[bc]WL[-59.0] ;BL[-215.0]B[bl] ;W[cf]WL[-79.0] ;BL[-225.0]B[dg] ;W[ed]WL[-85.0] ;BL[-239.0]B[ee] ;W[eb]WL[-93.0] ;BL[-249.0]B[fc] ;W[ce]WL[-96.0] ;BL[-266.0]B[mc] ;W[md]WL[-99.0] ;BL[-278.0]B[ld] ;W[kd]WL[-112.0] ;BL[-283.0]B[le] ;W[lb]WL[-128.0] ;BL[-301.0]B[kc] ;W[kb]WL[-130.0] ;BL[-315.0]B[pn] ;W[qn]WL[-134.0] ;BL[-325.0]B[qm] ;W[ro]WL[-142.0] ;BL[-338.0]B[pl] ;W[rm]WL[-152.0] ;BL[-351.0]B[om] ;W[qk]WL[-155.0] ;BL[-366.0]B[ke] ;W[of]WL[-176.0] ;BL[-376.0]B[me] ;W[nd]WL[-179.0] ;BL[-386.0]B[jb] ;W[fd]WL[-192.0] ;BL[-400.0]B[nb] ;W[ob]WL[-194.0] ;BL[-418.0]B[fq] ;W[gr]WL[-208.0] ;BL[-435.0]B[la] ;W[na]WL[-214.0] ;BL[-445.0]B[ka] ;W[pf]WL[-241.0] ;BL[-455.0]B[fe] ;W[de]WL[-244.0] ;BL[-472.0]B[ch] ;W[bh]WL[-252.0] ;BL[-482.0]B[di] ;W[cj]WL[-254.0] ;BL[-499.0]B[ck] ;W[dj]WL[-257.0] ;BL[-511.0]B[ej] ;W[dk]WL[-258.0] ;BL[-523.0]B[dl] ;W[ek]WL[-260.0] ;BL[-542.0]B[fk] ;W[el]WL[-263.0] ;BL[-558.0]B[em] ;W[fl]WL[-269.0] ;BL[-570.0]B[gl] ;W[mh]WL[-284.0] ;BL[-584.0]B[nh] ;W[ng]WL[-288.0] ;BL[-603.0]B[bj] ;W[bi]WL[-318.0] ;BL[-619.0]B[mi] ;W[mg]WL[-348.0] ;BL[-637.0]B[ki] ;W[gj]WL[-378.0] ;BL[-650.0]B[gk] ;W[eh]WL[-391.0] ;BL[-665.0]B[ei] ;W[dh]WL[-403.0] ;BL[-677.0]B[cg] ;W[ef]WL[-437.0] ;BL[-683.0]B[eg] ;W[ge]WL[-441.0] ;BL[-694.0]B[ff] ;W[gd]WL[-442.0] ;BL[-711.0]B[bg] ;W[ag]WL[-444.0] ;BL[-730.0]B[gf] ;W[he]WL[-449.0] ;BL[-750.0]B[rp] ;W[qq]WL[-465.0] ;BL[-762.0]B[qo] ;W[rn]WL[-467.0] ;BL[-775.0]B[qp] ;W[rq]WL[-473.0] ;BL[-794.0]B[er] ;W[pq]WL[-497.0] ;BL[-805.0]B[oq] ;W[sp]WL[-501.0] ;BL[-822.0]B[hb] ;W[op]WL[-519.0] ;BL[-830.0]B[po] ;W[nq]WL[-523.0] ;BL[-848.0]B[np] ;W[or]WL[-525.0] ;BL[-867.0]B[no] ;W[dm]WL[-530.0] ;BL[-872.0]B[cl] ;W[fm]WL[-531.0] ;BL[-882.0]B[en] ;W[gm]WL[-533.0] ;BL[-892.0]B[hm] ;W[gn]WL[-537.0] ;BL[-910.0]B[gc] ;W[fo]WL[-550.0] ;BL[-920.0]B[go] ;W[hn]WL[-555.0] ;BL[-935.0]B[in] ;W[eo]WL[-566.0] ;BL[-940.0]B[dn] ;W[aj]WL[-580.0] ;BL[-959.0]B[pc] ;W[oc]WL[-592.0] ;BL[-976.0]B[hp] ;W[gq]WL[-604.0] ;BL[-991.0]B[fp] ;W[al]WL[-607.0] ;BL[-1006.0]B[bk] ;W[fh]WL[-636.0] ;BL[-1021.0]B[fj] ;W[fg]WL[-647.0] ;BL[-1026.0]B[ef] ;W[hf]WL[-651.0] ;BL[-1031.0]B[gg] ;W[hg]WL[-652.0] ;BL[-1036.0]B[gh] ;W[bm]WL[-654.0] ;BL[-1041.0]B[cm] ;W[ak]WL[-661.0] ;BL[-1057.0]B[bn] ;W[fb]WL[-721.0] ;BL[-1070.0]B[pk] ;W[pj]WL[-723.0] ;BL[116.0]OB[9]B[ni] ;W[oh]WL[-737.0] ;BL[97.0]OB[8]B[lr] ;W[fs]WL[-750.0] ;BL[80.0]OB[7]B[cr] ;W[es]WL[-757.0] ;BL[62.0]OB[6]B[am] ;W[ah]WL[-775.0] ;BL[44.0]OB[5]B[ds] ;W[fr]WL[-788.0] ;BL[24.0]OB[4]B[ql] ;W[rl]WL[-791.0] ;BL[11.0]OB[3]B[rk] ;W[qj]WL[-793.0] ;BL[-2.0]OB[2]B[lh] ;W[gb]WL[-806.0] ;BL[-26.0]OB[1]B[hc] ;W[eq]WL[-814.0] ;BL[120.0]OB[10]B[dr] ;W[gp]WL[-818.0] ;BL[114.0]OB[9]B[ep] ;W[ho]WL[-820.0] ;BL[100.0]OB[8]B[oj] ;W[kp]WL[-836.0] ;BL[90.0]OB[7]B[ko] ;W[io]WL[-843.0]
Re: [computer-go] How does MC do with ladders?
Ladders are not hard, especially if one is permitted to place stones on the (virtual) board to trace the flow. A 20 kyu human can follow the logic. Don, you describe some subtle choices of playing one's opponent, and compare them to MC programs, but you are a fairly strong chess player. If you were counseling a beginner, you'd surely urge him/her to focus on getting the basics right before getting fancy with estimations of winning probability vis a vis particular opponents. Go and chess differ in a fundamental way. With chess, many positions may be genuinely unknowable, beyond human/machine ability to measure the exact outcome; a probabilistic approach may be well suited to such situations. With Go, there are many situations which can be read out precisely, provided that one has the proper tools - ladders, the ability to distinguish between one and two eyes; the ability to reduce eyespaces to a single eye with an appropriate placement; and so forth. Failure to recognize such situations is like failing to spot a pinned piece or a passed pawn. Every now and then, I have the opportunity to play a pro, or watch a pro against other amateur players. Even 4 and 5 dan amateurs find their groups crumbling against pro players. But in many cases, the pro simply exploits weak shape - reducing groups to the one eyed state. Evaluating winning odds depends upon evaluating the final score at the leaf nodes, which depends on being able to distinguish between one and two eyes, to count liberties in capturing races, to recognize seki, to read ladders, and other basic skills. At some point in the game, an evaluation function should be able to quickly and accurately report oops, just lost ten or twenty points, with no compensating gain, therefore the score is -15; this node should be reported as a lost game, back up and try something different. The earlier one can make such accurate assessments, the better one's game. Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Raymond Wold wrote: On Tue, 2007-12-11 at 11:42 -0500, Don Dailey wrote: In fact, this illustrates a wonderful strength of these programs. Only it's not strength to ignore a move to your benefit, Who suggested that it was? The strength of MC programs is how they deal with uncertainty, not the fact that there is uncertainty. So what method do you propose that is immune to uncertainty? when it's something a 20 kyu human can read out. Nor is it strength when you play out a dead ladder, no matter if you're behind. Do you know of an approach that evaluates go positions perfectly?You are attacking the fact that MC programs have errors in their probability estimates but completely ignoring the fact that SO DOES EVERY OTHER EVALUATION FUNCTION. Currently there is no evidence whatsoever that probability estimates are inferior and they are the ones playing the best GO right now, so the burden of proof is on you. It's not enough to simply find games where they played a bad move, unless you can show that other approaches are not as subject to bad moves. - Don Pure MC will /not/ cure cancer. ___ 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] How does MC do with ladders?
terry mcintyre wrote: Ladders are not hard, especially if one is permitted to place stones on the (virtual) board to trace the flow. A 20 kyu human can follow the logic. Don, you describe some subtle choices of playing one's opponent, and compare them to MC programs, but you are a fairly strong chess player. If you were counseling a beginner, you'd surely urge him/her to focus on getting the basics right before getting fancy with estimations of winning probability vis a vis particular opponents. For beginners I would strongly council to play the board, not the opponent. At the top level it's not really like this.You must play soundly but there is a huge element of playing the opponent. The most basic winning technique is to constantly present problems to your opponent - even though this may have little to do with the game theoretic score. Part of the reason for this is that if you do it to him, he is too busy to hurt you.But the real point is that you want to provoke an error. If you don't play this way at the higher level most games would end in a draw.2700 players do not want to draw 2500 players too much so must play provocatively. Top level players tend to draw each other a lot unless the results are very important - and even then it's difficult to get out of a draw. Here is some advice for playing against stronger players: Don't change your game. Play the same way you normally would.If you like tactics, don't be afraid to mix it up. It's not that this is likely to give you a win, but it's certainly not going the help you to change your style. When your opponent is in time pressure, naive players start playing really fast in order to add to their opponents time pressure.This is a really stupid mistake. You are giving away your only advantage, the fact that you have more time than your opponent. Duhhh! In fact, there might even be some benefit to playing a little slower than usual. In time pressure your opponent has the advantage of the adrenalin in his system and it actually helps him.But you cannot maintain an adrenalin rush for too long without it washing you out. So if he has 1 minute on his clock, you can keep his adrenalin going for 20 minutes he will be exhausted before long. Many mistakes are made immediately after time-control has been reach and the player thinks he is safe. All of these things are attempts to play the opponent and it usually turns out that this is foolish. You are upsetting and distracting yourself from the game when you do this and only if you really know what you are doing should playing the opponent be attempted. Go and chess differ in a fundamental way. With chess, many positions may be genuinely unknowable, beyond human/machine ability to measure the exact outcome; a probabilistic approach may be well suited to such situations. With Go, there are many situations which can be read out precisely, provided that one has the proper tools - ladders, the ability to distinguish between one and two eyes; the ability to reduce eyespaces to a single eye with an appropriate placement; and so forth. Failure to recognize such situations is like failing to spot a pinned piece or a passed pawn. But so far, the evidence says the probabilistic approach works in GO and so far nobody has demonstrated a strong chess program that uses this approach. However I don't know if anyone has seriously tried in chess. Every now and then, I have the opportunity to play a pro, or watch a pro against other amateur players. Even 4 and 5 dan amateurs find their groups crumbling against pro players. But in many cases, the pro simply exploits weak shape - reducing groups to the one eyed state. Evaluating winning odds depends upon evaluating the final score at the leaf nodes, which depends on being able to distinguish between one and two eyes, to count liberties in capturing races, to recognize seki, to read ladders, and other basic skills. At some point in the game, an evaluation function should be able to quickly and accurately report oops, just lost ten or twenty points, with no compensating gain, therefore the score is -15; this node should be reported as a lost game, back up and try something different. The earlier one can make such accurate assessments, the better one's game. I am a lousy go player, but I started out counting stones, trying to win everything. I think I definitely made a step forward when I started mentally mapping out the board. I actually learned this from my own monte carlo program. I try to figure out exactly what I need to win and then I focus on that.That doesn't mean you are not flexible and opportunistic - if I have a chance to grab a piece I didn't expect, it's that much less I have to worry about elsewhere.Then at some point I consolidate, making sure if I'm winning I don't attempt any foolish excursions.Instead I strengthen what I have a
Re: [computer-go] How does MC do with ladders?
At this point, it has to be said that _all_ computer go programs suck at 19xc19 go. MC programs happen to suck less, especially on small boards. On the other hand, we do have some very strong special-purpose go programs. There are several very strong tsumego/life-and-death programs and at least one endgame program. There are some fairly strong fuseki predictors. I'm hoping the goal is to develop programs strong enough to play a credible game against dan-level humans on a 19x19 board. If we ever figure out how to merge the great strengths of UCT/MC with these other strengths, we'd be a good bit closer. If a program is able able to learn from examples and experience. I'd feed it a library of go problems, and keep training until the right line of play, and the refutations of bad play, are quickly and reliably found for hundreds or thousands of games. Often, there is one right line of play, and very many bad lines. Hugh GrantImportant to know the difference. /Hugh Grant Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Hi Petri, I happen to think that MC is the most human like approach currently being tried. The reason I say that is that humans DO estimate their winning chances and tally methods, where you simply tally up features/weights (regardless of how sophisticated) is not how strong humans think about the game. Also, the best first global game tree approach, whatever you call it such as UCT and others, is a very close model of how humans play the game too.We may notice 3 moves that look playable, but gradually come to focus on just 2 of those. Essentially monte carlo does this too.Very narrow focused trees. The play-out portion is a crude approximation for imagination. We basically look at a board and imagine the final position.The MC play-outs kill the dead groups in a reasonably accurate (but fuzzy) way and put the flesh on the skeleton. Near the end of the game, the play-outs end mostly the same the way the game itself would end - and the same way a human would expect it to look like. I attribute the success of MC to the fact that it's the best simulation of how WE do it.The other approaches are clearly more synthetic, including raw MC without a proper tree. - Don Petri Pitkanen wrote: 2007/12/11, terry mcintyre [EMAIL PROTECTED]: With Go, there are many situations which can be read out precisely, provided that one has the proper tools - ladders, the ability to distinguish between one and two eyes; the ability to reduce eyespaces to a single eye with an appropriate placement; and so forth. Failure to recognize such situations is like failing to spot a pinned piece or a passed pawn. I am no fan on MC approach but basically MC can read LD given enough of simulations. It will read them without knowing that they need to be analysed. Point in MC being that once you get more power you get better LD as well, but without extra coding. This approach will result in non-human like game BUT likewise chess programs did not get strong by emulating humans. They just took one simple thing humans do and took it to extreme. Whatever approach will do the trick in go it will be similar in this sense. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
2007/12/11, terry mcintyre [EMAIL PROTECTED]: With Go, there are many situations which can be read out precisely, provided that one has the proper tools - ladders, the ability to distinguish between one and two eyes; the ability to reduce eyespaces to a single eye with an appropriate placement; and so forth. Failure to recognize such situations is like failing to spot a pinned piece or a passed pawn. I am no fan on MC approach but basically MC can read LD given enough of simulations. It will read them without knowing that they need to be analysed. Point in MC being that once you get more power you get better LD as well, but without extra coding. This approach will result in non-human like game BUT likewise chess programs did not get strong by emulating humans. They just took one simple thing humans do and took it to extreme. Whatever approach will do the trick in go it will be similar in this sense. -- Petri Pitkänen e-mail: [EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Make sure that you use the -19 argument when starting 19x19 Mogo, and restart GoGui (in order to restart Mogo indirectly) after you change the settings. Somewhat confusingly, Mogo does not automatically play 19x19 style just because it receives a request for 19x19 board. Poor ladder handling and squeezing the toothpaste are both behaviors that Mogo can exhibit when playing 9x9-style on the 19x19 board. If, assuming you're in GoGui, the GTP shell window shows shishoCheck is called comments, then you're really playing 19x19 style. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
On Tue, 2007-12-11 at 13:45 -0500, Don Dailey wrote: Do you know of an approach that evaluates go positions perfectly?You are attacking the fact that MC programs have errors in their probability estimates but completely ignoring the fact that SO DOES EVERY OTHER EVALUATION FUNCTION. I can code an algorithm that evaluates simple ladders correctly. I'll repeat that. I can code a program that reads ladders better than a pure MC program without knowledge of ladders. I can beat it. Human knowledge programmed into a computer that does that one thing, that basic go skill, better than the MC program. Are you saying that there is absolutely no way to combine such with an MC program to make it better? Not just that no one has done it (I don't know if anyone has) but that it is impossible? Are you saying that attempts to do so are wasted? If you are, I'd appreciate it if you did so clearly. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
2007/12/12, Raymond Wold [EMAIL PROTECTED]: Are you saying that there is absolutely no way to combine such with an MC program to make it better? Not just that no one has done it (I don't know if anyone has) but that it is impossible? Are you saying that attempts to do so are wasted? If you are, I'd appreciate it if you did so clearly. As already stated, Valkyria, a strong MC/UCT program, is known to read ladders in simulation. -- Seo Sanghyeon ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Since Valkyria is slow anyway, I can have it read ladders in the simulations. The ladder code is really fast and a little buggy, but works often enough to not cause major problems. I never tested the benefits of the ladder code it just appeared to be much stronger. -Magnus What do you do with the knowledge learned by reading out the ladder in a simulation? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
Raymond, Playing a strong game of go is a combination of many factors, not just reading ladders.You could probably isolate out any particular skill and write some code that does it pretty well. But the question will always be: How well does it actually play the game? As has been stated here many times, improving some specific skill could actually hurt the overall strength.What you want is the best program overall - one that knows how to win games. I don't care if you can make a great ladder reader if the program sucks. Raymond Wold wrote: On Tue, 2007-12-11 at 13:45 -0500, Don Dailey wrote: Do you know of an approach that evaluates go positions perfectly?You are attacking the fact that MC programs have errors in their probability estimates but completely ignoring the fact that SO DOES EVERY OTHER EVALUATION FUNCTION. I can code an algorithm that evaluates simple ladders correctly. I'll repeat that. I can code a program that reads ladders better than a pure MC program without knowledge of ladders. I can beat it. Human knowledge programmed into a computer that does that one thing, that basic go skill, better than the MC program. Are you saying that there is absolutely no way to combine such with an MC program to make it better? Not just that no one has done it (I don't know if anyone has) but that it is impossible? Are you saying that attempts to do so are wasted? If you are, I'd appreciate it if you did so clearly. This is the course MC programs have been taking all along, adding domain specific (and otherwise) knowledge to the play-outs.Of course you can add ladder code. But what does this have to do with anything? What we are arguing about is whether it's good to try to estimate probabilities. That's what you have been critical of. Adding ladder code will improve any evaluation function if done correctly but that's not relevant if you believe estimating probability is foolish. To the contrary, I believe it is brilliant - in my opinion it is a key factor in the success of these programs and I would call it a key breakthrough. - Don ___ 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] How does MC do with ladders?
I have had this experience many times: 1. You see a move that sucks. 2. You identify the problem and engineer a solution. 3. The solution indeed works - it cures the problem. 4. The program plays worse than it did before. By the way, you are being modest, Antigo is not bad on 9x9.It's true there is a pack of programs that are way out front, but they are mostly different version of just 3 or 4 programs. Your program would be the top program if it was on the server 2 years ago. Do you remember when CGOS started?It was an impressive feat to break 1800 back then. - Don [EMAIL PROTECTED] wrote: My engine, Antigo, is not one of the strongest and only plays 9x9 games. It does not read ladders correctly unless they are short enough for the tree to handle it. But I could uncomment a few lines of code and then the playouts would know how to handle simple ladders for external nodes. The rules in the heavy playouts can be tuned so that both colors will play out any ladder. Or each color can read ahead, during the playout, to decide whether or not to continue a ladder-like Valkyria does. In my experience, both ways produce a net decrease in playing strength for my particular bot. Adjusting the heavy playout rules to deal with particular tactical issues leads to a lot of unintended consequences. I've also tried doing a tactical analysis for each string (coincidentally also using MC/UCT) as a first pass at the root node and using information from that to inform the playouts. It almost helps... it ought to help... if I tried one more thing... I'd be happy to accept that any sort of traditional go information *might* improve MC/UCT. But until it gets down to specifics, there's not much to argue about. - Dave Hillis More new features than ever. Check out the new AIM(R) Mail http://o.aolcdn.com/cdn.webmail.aol.com/mailtour/aol/en-us/text.htm?ncid=aimcmp000501! ___ 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] How does MC do with ladders?
On Dec 11, 2007 8:53 PM, Don Dailey [EMAIL PROTECTED] wrote: The play-out portion is a crude approximation for imagination. We basically look at a board and imagine the final position.The MC play-outs kill the dead groups in a reasonably accurate (but fuzzy) way and put the flesh on the skeleton. Near the end of the game, the play-outs end mostly the same the way the game itself would end - and the same way a human would expect it to look like. This seems pretty fishy to me, given that MC can't read ladders accurately, for instance, but any competent human can, and that MC plays so bizarrely differently from humans in many positions, especially endgames. There may be strong theoretical arguments why MC is STRONG, and there are clearly empirical demonstrations that MC IS strong, but it is not at all clear that MC is somehow simulating/approximating the mental process of a human player playing the game. If it were, I would expect an MC player to make moves that look a lot more human. I attribute the success of MC to the fact that it's the best simulation of how WE do it.The other approaches are clearly more synthetic, including raw MC without a proper tree. But those synthetic approaches seem MORE like what many human players do (at least humans I've talked to), thinking discretely about different domain-specific concrete things like are there any appropriate josekis for this situation?, can I kill that group? what is its final internal eye shape going to look like?, are any of my groups endangered?, is my opponent's moyo invadable? or reducible?, does this ladder work?, can these 2 groups be separated?, can I make these stones live? can I do it in sente?, who has more ko threats now?, how big is that ko threat compared to the value of this ko?, where is the biggest endgame move right now?, where is the biggest sente endgame move right now?, which of these monkey jumps is bigger?, etc. At a literal detailed analysis level, MC is totally different from how we do it. I know of no human player who imagines the 2 players randomly dropping stones over and over to see what proportion of wins/losses results. The basic philosophy of MC is radically different from how humans think about the game. (Which is not to say that MC is a bad approach of course.) And at a higher level (in terms of the actual moves that actually get chosen by MC), they also look very bizarre compared to a human player, particularly in the end game where (as has been discussed a lot recently) a winning MC often fills its own territory or plays neutral points when real points still exist, something a better-than-beginner (to say nothing of strong) human player would never do. In the opening, strong humans typically are familiar with many joseki, which MC is much less likely to randomly follow. And (to mention the actual subject of this thread...) a competent human player can read out most ladders correctly with certainty, unlike MC. and so on... cheers, russ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
2007/12/11, Don Dailey [EMAIL PROTECTED]: Hi Petri, I happen to think that MC is the most human like approach currently being tried Ye in sense Alpha-Beta is human like. It one feature we do and takes it to extreme. And using different method of evaluation. . The reason I say that is that humans DO estimate their winning chances and tally methods, where you simply tally up features/weights (regardless of how sophisticated) is not how strong humans think about the game. Tallying up ius the non-human part. Extracting features and assigning meaning to them is very human. Good go player describe moves they make with terms like thicknes, wall, spere of influence,invasion. Obviously these are not needed if one searches deep enough but how deep that would be? game too.We may notice 3 moves that look playable, but gradually come to focus on just 2 of those. Essentially monte carlo does this too.Very narrow focused trees. Here we completely agree. It just picks the moves with different emphasis. And we do tactical analysis all the time. Something MC program is pretty weak at. I for instance played MOGO and it refused to resign until I places a dead group in atari. Any 20 would have seen that specific situation. Still that same 20 would have lost the game easily. So this is very unlike humans I attribute the success of MC to the fact that it's the best simulation of how WE do it.The other approaches are clearly more synthetic, including raw MC without a proper tree. It could be the best but it is not very close. And adding more go knowledge to it may make it weaker by consuming CPU. There must be a third way. But this is the best idea that has posppoed up in years - or more like a decade - Don Petri ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
