Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
I assume in Go the difference is also a very large handicap. in any case, i think that the difference is probably much larger than just one or two stones. :) It is said if has 4 stones handicap, every Pro will accept games play with God even if bet his life. When in limited local fighting like TumeGo, Pro plays just like God. igo One has to differentiate: In chess humans play very close to optimal in the subset of chess which is played by humans. But this is only a very small subset of what is really playable. E.g. There is currently a match between Kramnik and Fritz. I showed the Kramnik team a game were Hydra crashes Fritz in an important variation with a rook v. bishop sacrifice. But the team said: Theoretcially convincing, but of no use for us. Kramnik can not play this tactical massacre against a computer. Thats unhuman chess. Humans are very far away from optimal play in unknown positions. E.g. they are helpless against a perfect endgame database. Such a DB plays from the human point of view completly crazy moves. A human opponent would never play this. In human-machine matches it is very important for the machine team to deviate from the human-patterns and to get a chaotic position. In the preperation for the Adams-Hydra match we spent a lot of effort to deviate as soon as possible from known opening theory and also that the programm plays strange moves which are not necessarily optimal. The only requirement was, that this strange moves are not really bad. This is completly sufficient against a human. My personal criterion was: When the Hydra chess expert GM Lutz said Hmmm, whats this, I asked him if its bad. If he could not give a convincing reason why its bad within 10 seconds, it was a very good move against Adams (but not against God). I think the same will happen also in Go. They have only a chance if God plays human-Go. But against non-human moves they are certainly as helpless as the chess-players. I assume its even worse, because Go is more pattern related and more complex than chess. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
On 27-nov-06, at 08:35, igo wrote: It is said if has 4 stones handicap, every Pro will accept games play with God even if bet his life. I don't know if that's a generally accpted estimate. But I know that Otake Hideo once said he'd bet his life with 4 stones against God. He also added he wasn't so sure he'd win but that he had his pride too. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
In message [EMAIL PROTECTED], steve uurtamo [EMAIL PROTECTED] writes It is said if has 4 stones handicap, every Pro will accept games play with God even if bet his life. wow. i thought that there were at least two stones worth of slack in the opening, and another two in ko fighting. :) Seems unlikely. I can't imagine two competent players, say 1p or better, coming out of the opening with one of them having a two-stone lead. And, the right to win all ko fights without having to fight them is only worth half a stone. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
And, the right to win all ko fights without having to fight them is only worth half a stone. uh, that depends upon what the kos are for. and actually, what i meant was that its threats might be so complicated that they would be ignored. s. Sponsored Link Mortgage rates near 39yr lows. $510k for $1,698/mo. Calculate new payment! www.LowerMyBills.com/lre ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
A good point to consider - is God actively trying to confuse his opponent and complicate things, or is he simply playing objectively best moves? - Don On Mon, 2006-11-27 at 07:39 -0800, steve uurtamo wrote: wow. i thought that there were at least two stones worth of slack in the opening, and another two in ko fighting. :) Seems unlikely. I can't imagine two competent players, say 1p or better, coming out of the opening with one of them having a two-stone lead. one of them is not a competent 1p. one of them is a computer with knowledge of the end result of all possible game trees (my understanding of the definition of a god player). it could, for instance, create an opening whose branches are so complicated that W (or B) was forced to take small gains territorially, but lose, say, 20 pts. by the midgame. And, the right to win all ko fights without having to fight them is only worth half a stone. uh, that depends upon what the kos are for. s. Sponsored Link $420k for $1,399/mo. Think You Pay Too Much For Your Mortgage? Find Out! www.LowerMyBills.com/lre ___ 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] .. if Monte-Carlo programs would play infinitestrong
A good point to consider - is God actively trying to confuse his opponent and complicate things, or is he simply playing objectively best moves? good question. if his goal is to win with zero handicap, all he has to do is pick a branch that ends with a win for, say, W. if he is starting from a branch without such a terminus, he has to try to move the game into such a branch. if it's a handicap game, then the question boils down to getting over to a winning branch from the tree whose initial state is completely different -- there are handicap stones on the board. more likely is that you play with high komi -- then the goal is to move over to a branch whose terminus is both a win and is by more than komi points. since there's no guarantee that you can get to such a branch, and since it's unlikely that the absolute advantage of W over B is more than 4 stones (or, say, 30 komi), this means that you have to try to get your opponent to make a mistake that will take you over into one of these komi + win branches. likely the human opponent will play non-optimally in the first few moves. this will negate some of the komi. any move outside a win w/o komi branch will take you to a lose by X w/o komi branch, and god will know how to capitalize upon that to make up some more komi. this isn't enough to win the game, however, so god has to figure out how to maneuver the game over there. one approach might be to play moves where the greatest number of terminal nodes in that move subtree have winning scores in the komi range. then you maximize the probability that an error (or series of errors) by the human player will result in a win for you. of course, once you're in a win by komi branch, you're done. you just play it out with perfect refutations of every move. however, objectively the game is a win for only one player at the start, and the only way to overcome enough handicap (or komi) is to attempt to capitalize on errors (or inefficiencies, which in a completely solved game can be considered errors) made by your opponent. s. Sponsored Link $200,000 mortgage for $660/ mo - 30/15 yr fixed, reduce debt - http://yahoo.ratemarketplace.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
I've often wondered how I would program a computer to play a game, chess or go, if I had perfect information about the game.How do you make it more difficult to win against a fallible opponent? I assume that in many positions there are more than 1 maximizing move. I would of course restrict the computer to those moves (I call those moves good moves in an idealistic sense and everything else as bad) I guess you would simply steer towards positions where the computer had lot's of good moves and the opponent had very few good moves. If I were doing this for chess, I might just build an evaluation function based on trying to maintain the highest legal move count possible and do a limited depth search - restricting myself of course to only maximizing or good moves. In go, I think you would want to keep as many things going on at the same time as possible, and you would want to increase the number of interactions on the board. I am sure a perfect computer could gain a few stones by confusing the opponent in this way as opposed to playing a straightforward game. - Don On Mon, 2006-11-27 at 11:06 -0800, steve uurtamo wrote: A good point to consider - is God actively trying to confuse his opponent and complicate things, or is he simply playing objectively best moves? good question. if his goal is to win with zero handicap, all he has to do is pick a branch that ends with a win for, say, W. if he is starting from a branch without such a terminus, he has to try to move the game into such a branch. if it's a handicap game, then the question boils down to getting over to a winning branch from the tree whose initial state is completely different -- there are handicap stones on the board. more likely is that you play with high komi -- then the goal is to move over to a branch whose terminus is both a win and is by more than komi points. since there's no guarantee that you can get to such a branch, and since it's unlikely that the absolute advantage of W over B is more than 4 stones (or, say, 30 komi), this means that you have to try to get your opponent to make a mistake that will take you over into one of these komi + win branches. likely the human opponent will play non-optimally in the first few moves. this will negate some of the komi. any move outside a win w/o komi branch will take you to a lose by X w/o komi branch, and god will know how to capitalize upon that to make up some more komi. this isn't enough to win the game, however, so god has to figure out how to maneuver the game over there. one approach might be to play moves where the greatest number of terminal nodes in that move subtree have winning scores in the komi range. then you maximize the probability that an error (or series of errors) by the human player will result in a win for you. of course, once you're in a win by komi branch, you're done. you just play it out with perfect refutations of every move. however, objectively the game is a win for only one player at the start, and the only way to overcome enough handicap (or komi) is to attempt to capitalize on errors (or inefficiencies, which in a completely solved game can be considered errors) made by your opponent. s. Sponsored Link $200,000 mortgage for $660/ mo - 30/15 yr fixed, reduce debt - http://yahoo.ratemarketplace.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] .. if Monte-Carlo programs would play infinitestrong
On Mon, Nov 27, 2006 at 12:59:30PM -0500, Don Dailey wrote: A good point to consider - is God actively trying to confuse his opponent and complicate things, or is he simply playing objectively best moves? I have heard this terminology somewhere, but can't remember where: A god plays perfectly, without trying to confuse the opponent, assuming the opponent will play perfectly too, and the game flowing naturally to its logical conclusion. A devil plays nearly perfectly, but will put up traps for an unwary opponent, play to complicate things when it is in his advantage to do so. Thus a devil is more likely to win over human opponents, even from too large handicaps. But a god will win over the devil, as he will not fall in any of the traps, but can use the suboptimal play spent in setting those up. -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] .. if Monte-Carlo programs would play infinitestrong
I guess you would simply steer towards positions where the computer had lot's of good moves and the opponent had very few good moves. this is essentially the same thing -- if you play in a branch where the highest percentage of moves lead to a win for you, then this means that your opponent has less opportunities to play a winning move. any error whatsoever leads to a loss for them. this doesn't mean that your opponent would have difficulty choosing a correct move at many of the tree's nodes, but certainly they would not know the full tree, and could only eliminate *most* of the imperfect moves. some of these would be very straightforward to prevent, but some would not. for instance, you might be willing to include branches that led to draws. draws in go could be very tricky to prevent at the same time as trying to win. s. Sponsored Link Mortgage rates near 39yr lows. $510k for $1,698/mo. Calculate new payment! www.LowerMyBills.com/lre ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
But a god will win over the devil, as he will not fall in any of the traps, but can use the suboptimal play spent in setting those up. actually, whomever is slated to win with perfect play (1st or 2nd player) will win, because setting up traps isn't necessarily inefficient -- it just means choosing branches where the number of winning moves for your opponent is minimized. it is still optimal play. either you start in a winning branch and you just play it out and win (even by choosing such branches, you're just playing a cleaner version of the same winning game), or you start in a losing branch and it doesn't matter what you do, you're going to lose. s. Sponsored Link Don't quit your job - take classes online www.Classesusa.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
A good devil tries to win by MORE than he deserves and will try to win in a losing position. I have heard this terminology before and my understanding was that a devil still plays a perfect game, he just tries to be deceptive about it. I don't see any point in not playing perfect if you can unless you are happy to play non-optimally and don't mind the chance of getting a lesser score than you are guaranteed. One other issue, how much does the devil know about his opponent? That has everything to do with it. You might use a much different strategy against one player than another. A good devil doesn't care - he will still play perfect while still using whatever tricks have a chance of working against any imperfect opponent without compromising or taking chances. - Don On Mon, 2006-11-27 at 11:39 -0800, steve uurtamo wrote: But a god will win over the devil, as he will not fall in any of the traps, but can use the suboptimal play spent in setting those up. actually, whomever is slated to win with perfect play (1st or 2nd player) will win, because setting up traps isn't necessarily inefficient -- it just means choosing branches where the number of winning moves for your opponent is minimized. it is still optimal play. either you start in a winning branch and you just play it out and win (even by choosing such branches, you're just playing a cleaner version of the same winning game), or you start in a losing branch and it doesn't matter what you do, you're going to lose. s. Sponsored Link Don't quit your job - take classes online www.Classesusa.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] .. if Monte-Carlo programs would play infinitestrong
Don (and others), Depending upon your definition of God, I think most of the God conversation is kind of silly. Given He is omnipotent, he has the ability to alter one of His created entities such that it is not possible to beat Him PRIOR to casting His reply as white. The alteration could be as subtle as changing the active potential on some sub-set of neurons in his opponents brain or as acute as creating deep anxiety within his opponent's psyche by being so gargantuan in physical presence. And talk about self-esteem. Hard to top God's opinion of Himself give you are one of His creations. Give He is omniscient, he has no need for generating confusion for His opponent. He already knows his opponents weakness, how it will manifest and why it will do so. That's assuming an omniscient being has any interest in casting a stone in the first place, something very difficult to imagine in any sense of the meaning of the words. Given he is omnipresent, he is has/is/will be in a part of the universe where an animation of the game about to be played is already playing out to completion, so he can see how it ends before it begins (a slight lean on his omniscience here). Better, the game he is watching is on a board made of harp strings and with the stones represented by fairies and unicorns. Hey! When your God, you get to make up all sorts of crazy shite. Finally, what is an objectively best move? How would one measure it? It's as if there was some God knowable state transition diagram (STD) describing an starting go board where the entry points to the STD (OMG, the sexual references here abound) mostly show black to win. So of that set of initial black moves that perfectly state transition into wins for black, which is objectively superior to the other? The question itself is poorly framed? The moves are all peers. None is superior to the other win in n moves candidates, even if their n's vary. The n's only matter if there is some higher value placed on minimizing the number of moves from start to finish. Give He is timeless, the length of game, hence the value of n, is not meaningful. Now, if God had a younger brother who liked to play Go...none of what I said above means anythingwhich is still true even if He doesn't. (a nod to your logic dialog from the other day, Don) Jim - Original Message From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Monday, November 27, 2006 11:59:30 AM Subject: Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong A good point to consider - is God actively trying to confuse his opponent and complicate things, or is he simply playing objectively best moves? - Don On Mon, 2006-11-27 at 07:39 -0800, steve uurtamo wrote: wow. i thought that there were at least two stones worth of slack in the opening, and another two in ko fighting. :) Seems unlikely. I can't imagine two competent players, say 1p or better, coming out of the opening with one of them having a two-stone lead. one of them is not a competent 1p. one of them is a computer with knowledge of the end result of all possible game trees (my understanding of the definition of a god player). it could, for instance, create an opening whose branches are so complicated that W (or B) was forced to take small gains territorially, but lose, say, 20 pts. by the midgame. And, the right to win all ko fights without having to fight them is only worth half a stone. uh, that depends upon what the kos are for. s. Sponsored Link $420k for $1,399/mo. Think You Pay Too Much For Your Mortgage? Find Out! www.LowerMyBills.com/lre ___ 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] .. if Monte-Carlo programs would play infinitestrong
In the second game Fritz against Kramnik Fritz played strategically very poor (or Kramnik very strong), Kramnik avoided a 3-times repetition offer of Fritz, but at the end Kramnik missed an easy to see mate in 1!! and lost very badly. Thats the end of the match. He will not be able to recover from this blunder. This is a rather drastic example of Chrillys law: Humans can not play in a complicated position more than 10 moves in a row without making an serious blunder. And it also very drastic example how far they are away from God. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] .. if Monte-Carlo programs would play infinitestrong
Shodan players are far, far, from perfect play. Shodan players have a good understanding of most basic concepts, and can solve simple tactical problems during a game, but that's about it. I'm 3 Dan, and almost every move I make is a mistake of some kind. The gap in skill between a shodan and a professional player is huge. David This is something that should not be neglected because shodan players approach perfect play. Will MC development show some kind of ceiling? Who knows, but it certainly could be. Jacques. ___ 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] .. if Monte-Carlo programs would play infinitestrong
I assume in Go the difference is also a very large handicap. i think that this has come up before, but at one point someone suggested that top pros are only a few stones' handicap away from perfect play. i think that komi might be the right way to think about this at that level, as handicap stones aren't fine-grained enough. in any case, i think that the difference is probably much larger than just one or two stones. :) s. Sponsored Link $420k for $1,399/mo. Think You Pay Too Much For Your Mortgage? Find Out! www.LowerMyBills.com/lre ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
Eeh, am I missing some point here or would not any Go program that uses search and infinite computer power simply SOLVE the game - given that scoring is done right and infinite loops are ruled out? The question should be more precisley stated as: Is playing strength a strictly-monoton increasing and unlimited function of computing power. But I thought the meaning of the question was clear. Considering simple Monte Carlo approach to 9x9 Go, the answer to this question is, No. Experiments made by Yoshimoto showed that dimishing returns could be seen when adding samples. It is described in the following article: Haruhiro Yoshimoto, Kazuki Yoshizoe, Tomoyuki Kaneko, Akihiro Kishimoto, and Kenjiro Taura: Monte Carlo Go Has a Way to Go, Twenty-First National Conference on Artificial Intelligence (AAAI-06), pages 1070-1075, 2006 The paper could be found at the following location: http://www.fun.ac.jp/~kishi/publication.html -- Shunsuke SOEDA ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
on a practical note, i think that MC is a great idea for 9x9, and might even be a great idea as a subset of a larger piece of code that employs human knowledge, but that MC will never beat a decent human at 19x19. the time/space limitations are just too great. Does this mean that it does not converge to optimal play when processing power goes to infinite or do you mean that it converges from the practical point of view much too slow? I think an MC player with 10**10 nodes/sec is even with todays technology possible. A system like Deep Blue with 256 special purpose hardware chips could reach this number. (There is of course then also the question about the parallel speedup). E.g. running with 500 MHz and using 12 clock-cycles/position gives 40 MPos/sec per chip. Hydra uses 8-9 clock-cycles per position, but the programm runs only at 55 MHz. The FPGA chips are already dated, on the newest generation it would be = 100 MHz. ASICs like in Deep Blue are faster. Generally I assume that Go would run with a higher clock-rate than in chess. The speedup in relation to a software solution would be considerable greater, because the board is larger and one could use the fine grained parallelism of a hardware-chip better. One could even design a 3 GHz Go-chip, but then one has to invest about the same amout of money like for a Pentium. This would be even for a Sheikh too expensive. Up to 500 MHz the design costs should be within a Sheikhs budget (unfortunately Sheiks do not even know the game of Go). What would it mean for a 19x19 player? What would it mean to build a 10**12 nodes/sec machine (which is with todays technology not possible, but according to Moores law in 10 years). Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
