Re: [computer-go] Definition for monte carlo
and which, i agree, gives far too much credit to MC players, since they roughly emulate this line of play purely by accident. I don't agree with that.There is no accident here, MC really only cares about winning and has no ego about winning big. It was intended as a little play on words, since they're roughly random draws. I'm not as funny as I think I am, apparently. if you can prove* that you can stop an invasion with no risk to yourself, people will generally play to stop it, but of course MC programs don't care. They might stop it by accident but not on purpose. Is this what you mean by unbalanced? Monte Carlo programs don't have a specific policy to lose stones on purpose just to keep the score balanced or close. They simply don't care either way. No, but as a technique for very slightly reducing the error in your measure of the win probability, once you have secured all of your territory in a provable way (likely testing for this is time consuming), and the rest of the moves are dame or new invasions (i.e. the first off-color stone dropped into secure territory), those invasions can be stopped at will by a strong enough player, and probably should be. i can't think of any counterexamples off hand, which doesn't mean that i'm right, of course. similarly, connecting not-yet live stones to provably live groups to prevent them from being captured should often very slightly reduce the error in the measure of the win probability. there are times when doing so is not as valuable as reducing an opponent's territory, so this would only be an interesting mode to switch to if there were no more reduction to be had anywhere on the board for the player involved. again, this is perhaps painful to test for. one thing i wonder is how close to the end of a 19x19 game any particular MC machine (with some number of draws at some cpu strength, etc.) plays perfectly, in the sense of not being able to lose a won game. at moves near and before this point, some heuristics like this should help. i think that there are likely some moves during which a player has provably won the game in an efficiently computable way but isn't yet aware of the fact and still has an opportunity to screw it up. s. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Definition for monte carlo
On Wed, Oct 31, 2007 at 01:00:07PM -0400, Don Dailey wrote: I think the right approach was mentioned just recently, add a very tiny incentive that cannot effect any bits of the main calculation as a kind of tie-breaker. I doubt this will buy much, but it might help just slightly and make it appear to play more natural by our standards. But I know trying to fix this any other way reduces the playing strength significantly. Yes, I did experiment that the last time I was playing with computer go. It does work. I did not see any decrease in strength, and I did see an improvement in the look of the game. But I did not run systematical tests to prove that there was no negative effects. The extra benefit has to be so small that it can not affect the result when there is a single game difference in the MC scores, of course. -H P.S. I am about to start playing with a go program again, I have some more ideas to improve simple MC things. UCT etc will have to wait until I can see what happens with those... -- 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/
[computer-go] Definition for monte carlo
There has been a lot of talk about monte carlo and while I have the jist not sure exactly what it is? Would someone explain it? What I've read online is just to play a bunch of random games and pick the best one. Is there now real evaluation between the games or sorted method for generating movements? -Josh ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Definition for monte carlo
On Tue, Oct 30, 2007 at 12:43:35PM -0400, Joshua Shriver wrote: There has been a lot of talk about monte carlo and while I have the jist not sure exactly what it is? Would someone explain it? Here is my (amateurish) understanding: Evaluation of a go position is very difficult. Monte Carlo (MC) is one way to shortcircuit this. The idea is to play the game to the bitter end, very quickly, and badly, on the assumption that if the position favours white, then white is likely to win, even if both players play equally bad quality moves. Taken to the extreme, they play pure random games. This can be done very quickly, and doing it many times gives some sort of measure of how good the position is. Now all is left for a pure MC player is to try every legal move, evaluate them with enough MC playouts, and choose the one that is most likely to win. This works surprisingly well, although there are some drawbacks. Evaluating positions this way prefers safe, solid groups. And in the end game, when the result is decided, the programs play unnatural moves, since all moves lead to the same result - the resulting score is usually not considered, so to the program it is the same if it wins by 0.5 points or the whole board... On its own MC is not all too strong, but it solves the evaluation problem. This can be included in some tree-search based programs, most commonly UCT or similar. And the results are surprisingly good. Lukasz Lew has written a simple C library that makes it easy to experiment with the thing. Google on 'Lew libEGO' and you should find him. - Heikki P.S. If any of the above is not right, I am sure the better informed people will rush in to correct me. I welcome that! -- 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] Definition for monte carlo
Heikki's answer is close. I would think it important to add that MC is a statistical sampling algorithm, so the attempt is to simplify the difficult job of evaluating a board state by sampling a large number of random continuations, with the assumption that if enough samples are checked, you will have some idea of the likely outcome starting at that board. Any one continuation is of virtually no value, it is only the statistics that are meaningful. By substituting board state plus one more move for board state you get an estimated value for the move you are adding to the board as long as you start the random sequence many times with that particular move. Now my personal bias: This method is extremely valuable and accurate in physics because we have a very solid theory for determining the distributions in thermal or quantum systems. This means that we do not simulate every possibility with equal probability, but use a bias that is specified by equations we trust and that have proved to work. The problem in Go is that we have no such theory yet, so, we end up with hand-tuned rules and biases created by other means, such as a UCT tree, to slowly and somewhat inefficiently (compared with having the right bias from an equation) move from what is being called pure MC (but really means uniform random) sampling towards a bias better for Go. Cheers, David On 30, Oct 2007, at 9:58 AM, Heikki Levanto wrote: On Tue, Oct 30, 2007 at 12:43:35PM -0400, Joshua Shriver wrote: There has been a lot of talk about monte carlo and while I have the jist not sure exactly what it is? Would someone explain it? Here is my (amateurish) understanding: Evaluation of a go position is very difficult. Monte Carlo (MC) is one way to shortcircuit this. The idea is to play the game to the bitter end, very quickly, and badly, on the assumption that if the position favours white, then white is likely to win, even if both players play equally bad quality moves. Taken to the extreme, they play pure random games. This can be done very quickly, and doing it many times gives some sort of measure of how good the position is. Now all is left for a pure MC player is to try every legal move, evaluate them with enough MC playouts, and choose the one that is most likely to win. This works surprisingly well, although there are some drawbacks. Evaluating positions this way prefers safe, solid groups. And in the end game, when the result is decided, the programs play unnatural moves, since all moves lead to the same result - the resulting score is usually not considered, so to the program it is the same if it wins by 0.5 points or the whole board... On its own MC is not all too strong, but it solves the evaluation problem. This can be included in some tree-search based programs, most commonly UCT or similar. And the results are surprisingly good. Lukasz Lew has written a simple C library that makes it easy to experiment with the thing. Google on 'Lew libEGO' and you should find him. - Heikki P.S. If any of the above is not right, I am sure the better informed people will rush in to correct me. I welcome that! -- 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Definition for monte carlo
When an MC bot is ahead, it'll play safe moves that help guarantee a coast to victory (many times by 1/2 point). I am surprised by how often an MC bot wins by exactly 0.5 point.It's almost as if it is converging to a 0.5 victory. One way to look at this is that an MC program is all about consolidating just the amount of territory it needs to win.It will never go for a big win and doesn't associate extra goodness to a bigger win.It's much easier to win small so I guess it makes sense that really tiny victories are very common in MC programs. - Don Jason House wrote: On 10/30/07, *Heikki Levanto* [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: This works surprisingly well, although there are some drawbacks. Evaluating positions this way prefers safe, solid groups. And in the end game, when the result is decided, the programs play unnatural moves, since all moves lead to the same result - the resulting score is usually not considered, so to the program it is the same if it wins by 0.5 points or the whole board... I don't think MC evaluation favors stable groups. It's really a function of the perceived chances of winning. When behind, it'll play bold moves since it's the only real way to win. An MC bot that is behind in endgame (even if by 1/2 point) plays so wildly, it frequently loses all of its stones! When an MC bot is ahead, it'll play safe moves that help guarantee a coast to victory (many times by 1/2 point). P.S. If any of the above is not right, I am sure the better informed people will rush in to correct me. I welcome that! I thought it was a great summary. My only caveat is up above. ___ 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] Definition for monte carlo
On Tue, Oct 30, 2007 at 01:33:07PM -0400, Jason House wrote: I don't think MC evaluation favors stable groups. I guess I didn't really say what I meant here. MC evaluation sees weaknesses in groups that can be killed by random play, even if they are safe enough in the eyes of human players. For example a group with one long eye, 4 points long, is considered unconditionally alive, but a MC evaluator sees some chance in killing it, because the defending side plays pure random, and is as likely to shorten it to 3-space eye as to split it in two independent eyes. In real games this may not make much of a difference, but it is possible to construct positions that get evaluated wrong by MC. Perhaps a clever program might even take advantage of such... It's really a function of the perceived chances of winning. When behind, it'll play bold moves since it's the only real way to win. An MC bot that is behind in endgame (even if by 1/2 point) plays so wildly, it frequently loses all of its stones! When an MC bot is ahead, it'll play safe moves that help guarantee a coast to victory (many times by 1/2 point). I think you are reading a bit too much intention into its play. When the game is already decided, it makes no difference where to play. So a pure MC program will end up playing totally random. If it is winning, it will happily let parts of a group die, as long as that does not change the result. If behind, it will not try to collect small points here and there, but just play where ever - often leading to death and destruction among its own groups. -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] Definition for monte carlo
On 10/30/07, Heikki Levanto [EMAIL PROTECTED] wrote: It's really a function of the perceived chances of winning. When behind, it'll play bold moves since it's the only real way to win. An MC bot that is behind in endgame (even if by 1/2 point) plays so wildly, it frequently loses all of its stones! When an MC bot is ahead, it'll play safe moves that help guarantee a coast to victory (many times by 1/2 point). I think you are reading a bit too much intention into its play. When the game is already decided, it makes no difference where to play. So a pure MC program will end up playing totally random. If it is winning, it will happily let parts of a group die, as long as that does not change the result. If behind, it will not try to collect small points here and there, but just play where ever - often leading to death and destruction among its own groups. In a decided game, you're right. When the game is not decided, it's an important consideration to take into account. Let's say you have to decide between gently containing your enemy or going for an all-out kill. Certainly, containment will give more reliable results. If that reliable result is a victory, it's the right move. If the result would be a loss, it's time to go for a kill. This type of decision (maybe in less extreme cases) is a common decision criteria for players stronger than me. As a moderately strong human, I play with a fixed strategy. I accept a fixed level of risk for all my groups and territory, and rarely waiver from that. In my relatively conservative strategy, I've coasted to a loss by 10 point or less more times than I care to count. This concept is quite foreign to a reasonable MC player. Similarly, I've been in won games and gotten bitten by a tesuji by the opponent. If I had been just a bit safer in my play, I could have had a comfortable win. Similarly, reasonable MC bots solidify the core to win rather than try to keep everything. A lot of times, when these factors have a big impact on the MC play (as a deviation from human-like play), humans consider it to be blunders by the MC bot. They really aren't, it just feels unnatural. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Definition for monte carlo
If you're ahead and go for a bigger win, generally you're just risking more to gain more when you don't need more. there is *absolutely* no advantage from a game-theoretical point of view to try to win by more than 0.5 points. and in practice, it's generally not a great idea to try to win by any more than you absolutely have to. this goes toward the game-goal of the first person to really explain the game to me, who said that both sides should strive for a balanced game. a 0.5 pt. game is a perfectly played game. which is not exactly the western view of winning. and which, i agree, gives far too much credit to MC players, since they roughly emulate this line of play purely by accident. however, most people won't go so far as to ignore an unreasonable invasion where you *let your opponent live inside your territory* even if it wouldn't add up to enough to cause them to lose the game. it's pride, or something. if you can prove* that you can stop an invasion with no risk to yourself, people will generally play to stop it, although to be fair, if you knew you didn't have to, by ignoring it you are not treating it like a huge source of ko threats for your opponent, which is a good thing. they might not really be ko threats, if they don't add up to enough for you to lose if you win the ko fight by ignoring them. which is part of the tricky nature of a ko. measuring the size of the threat. one way that people will often play that i think has no basis in an attempt to win, but which is simply human nature, is to occasionally fight a ko fight to the bitter end regardless of whether it will affect the outcome of the game. you'll see games that are decided by 10-15 points with 30 moves worth of ko threats to determine who gets the extra fraction of a point. this may be under the assumption that, if i win the fight, i definitely won't lose the game, but if i lose the fight, maybe there's something that i didn't see that could cause me to lose the game or it could just be kiai. but neither seem game-theoretically justifiable. for some reason this gets great cheers from the audience, whereas a computer player sacrificing 10 stones unnecessarily seems horrifying. even with very, very good computer players, i think that with sufficiently tight time controls we will always see this happen, since it's an easy decision to make, and much better than losing on time. s. *i.e. that any unconditionally alive group with a border of single-colored stones should be able to prevent any freshly invading stones from living. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Definition for monte carlo
Hi Steve, steve uurtamo wrote: If you're ahead and go for a bigger win, generally you're just risking more to gain more when you don't need more. there is *absolutely* no advantage from a game-theoretical point of view to try to win by more than 0.5 points. and in practice, it's generally not a great idea to try to win by any more than you absolutely have to. this goes toward the game-goal of the first person to really explain the game to me, who said that both sides should strive for a balanced game. a 0.5 pt. game is a perfectly played game. which is not exactly the western view of winning. and which, i agree, gives far too much credit to MC players, since they roughly emulate this line of play purely by accident. I don't agree with that.There is no accident here, MC really only cares about winning and has no ego about winning big.They don't go out of their way to win small either if that's what you mean.Unless you are saying that you should strive to go out of your way to win small so that the game is balanced then I don't know what you are talking about. Because they are not perfect players they don't always do this perfectly, so you could say they are not balanced in this sense, but that applies to all imperfect players including the very best human players. They may strive to play balanced but they don't quite succeed either. however, most people won't go so far as to ignore an unreasonable invasion where you *let your opponent live inside your territory* even if it wouldn't add up to enough to cause them to lose the game. it's pride, or something. if you can prove* that you can stop an invasion with no risk to yourself, people will generally play to stop it, but of course MC programs don't care. They might stop it by accident but not on purpose. Is this what you mean by unbalanced? Monte Carlo programs don't have a specific policy to lose stones on purpose just to keep the score balanced or close. They simply don't care either way. although to be fair, if you knew you didn't have to, by ignoring it you are not treating it like a huge source of ko threats for your opponent, which is a good thing. they might not really be ko threats, if they don't add up to enough for you to lose if you win the ko fight by ignoring them. which is part of the tricky nature of a ko. measuring the size of the threat. one way that people will often play that i think has no basis in an attempt to win, but which is simply human nature, is to occasionally fight a ko fight to the bitter end regardless of whether it will affect the outcome of the game. you'll see games that are decided by 10-15 points with 30 moves worth of ko threats to determine who gets the extra fraction of a point. this may be under the assumption that, if i win the fight, i definitely won't lose the game, but if i lose the fight, maybe there's something that i didn't see that could cause me to lose the game or it could just be kiai. but neither seem game-theoretically justifiable. I agree. I think in some sense it dishonors players to do this. It's very western isn't it?I say that it dishonors a player to do this because the assumption is that it shows honor to give your very best effort to win (it would show disrespect to throw the game) but after having secured the win trying to do more is like kicking a man when he is down, as if to humiliate him. for some reason this gets great cheers from the audience, whereas a computer player sacrificing 10 stones unnecessarily seems horrifying. even with very, very good computer players, i think that with sufficiently tight time controls we will always see this happen, since it's an easy decision to make, and much better than losing on time. s. *i.e. that any unconditionally alive group with a border of single-colored stones should be able to prevent any freshly invading stones from living. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ 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] Definition for monte carlo
Heikki Levanto wrote: On Tue, Oct 30, 2007 at 12:55:21PM -0700, steve uurtamo wrote: If you're ahead and go for a bigger win, generally you're just risking more to gain more when you don't need more. there is *absolutely* no advantage from a game-theoretical point of view to try to win by more than 0.5 points. and in practice, it's generally not a great idea to try to win by any more than you absolutely have to. On the other hand, it is equally pointless to throw out points in order to win by exactly 0.5 points. Especially if doing so increases your risk of miscalculation etc. But MC programs really are reasonable in this sense. If there is the SLIGHTEST doubts in their silicon minds about their winning chances, they will not throw out points that could save the game. There is this hidden assumption that MC programs are weakened because of not maximizing their territory (due to miscalculation) but the truth of the matter is that they are as pragmatic as you can get.WE are the ones irrational about it. We are the ones that feel we need to win a few more points just in case for good measure. An MC will win a few more points for good measure if it increases the probability of winning the game. We may see it miscalculate in this regard, but we can't fault the logic, only the miscalculation. Attempts to change the behavior to our more irrational point of view has always resulted in weakened play. This is part of the reason they are so good and probably a weakness of most if not all conventional GO programs.This is behavior that I can imagine would be very difficult to emulate in a conventional program, although there might be some attempts to do so. - Don I bet most of us have played a game where we thought things were nicely under control, only to have the opponent to play a surprising tesuji and gain a few points in the endgame. If one was pointedly aiming at a 0.5 point victory, such a tesuji could loose the game. If one was avoiding risks, but among equal moves, choosing the one that maximizes the score, such risk would be smaller. Of course this does not apply if one has confidence in having the game perfectly well analysed, and will know how the game will end. Such finesse is seldomly seen in kyu-level human players. And computer programs are not quite that perfect either... - H ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
