Re: [computer-go] .. if Monte-Carlo programs would play infinite strong
At 04:24 AM 11/26/2006, you wrote: This is something that should not be neglected because shodan players approach perfect play ... pm4ji, and i may have the context wrong, but shodan players are about 10 stones from perfect play. if you have a pro review a shodan's game, *many* of his moves are 1) not the best locally, and/or 2) not in the biggest area of the board to play in (globally). thanks --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinite strong
Maybe I did no explain my point well enough. The problem with infinite is that we get a better approximation to a wrong value. With few simulations we get that value with, say 1/10 error. With an astronomical amount of simulations we get the same value with an error of 1e-200, but it's still wrong!. It is proved that simulating a go position converges, but it does not converge to the same value as if the position was played by perfect players, it only converges to the asymptotic limit of random play. I am not an MC developer, but as far as I know, UCT keeps a limited (i.e. n-ply) tree in memory and intentionally unbiasses the nodes to make the convergence faster, that does not change anything, assuming constant tree size. A simple test : 1: after 100 simulations, choose the highest number in (0.96, 2.1, 3.18) 2: after 1e9 simulations, choose it in (0.999, 2.001, 3.01) You chose the same value (= same move). That's why, I insist, if you don't increase the size of the tree and only get a better approximation to a wishful but frequently misconceived value (the limit of random play) witch is *not* a good evaluation of the game, you don't significantly improve your play. Of course, if you increase the tree, you reach perfect play, that's not the point. Jacques. ___ 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 infinite strong
Yes, I agree with the point you are making. Random play is a relatively good evaluator, but it is not a great evaluator. And it's very weak at tactics. Letting it do a lot of simulations does not cause it converge to the correct value. But the current breed of MC computer players do not have a fixed tree - they continuously expand the tree in best first manner. Perhaps we use the wrong terminology when we call these MC players because they are hybrids. But I think that's understand now when we say Monte Carlo player. - Don On Sat, 2006-11-25 at 10:05 +, Jacques Basaldúa wrote: Maybe I did no explain my point well enough. The problem with infinite is that we get a better approximation to a wrong value. With few simulations we get that value with, say 1/10 error. With an astronomical amount of simulations we get the same value with an error of 1e-200, but it's still wrong!. It is proved that simulating a go position converges, but it does not converge to the same value as if the position was played by perfect players, it only converges to the asymptotic limit of random play. I am not an MC developer, but as far as I know, UCT keeps a limited (i.e. n-ply) tree in memory and intentionally unbiasses the nodes to make the convergence faster, that does not change anything, assuming constant tree size. A simple test : 1: after 100 simulations, choose the highest number in (0.96, 2.1, 3.18) 2: after 1e9 simulations, choose it in (0.999, 2.001, 3.01) You chose the same value (= same move). That's why, I insist, if you don't increase the size of the tree and only get a better approximation to a wishful but frequently misconceived value (the limit of random play) witch is *not* a good evaluation of the game, you don't significantly improve your play. Of course, if you increase the tree, you reach perfect play, that's not the point. 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 infinite strong
Hello, Chrilly wrote: (thread was Positions illustrative of computer stupidity) With an infinite fast chip chess programs would be infinite strong. Most current Go programs would only play infinite fast. Its an interesting question if Monte-Carlo programs would also play infinite strong. I think it is so important, it deserves its own thread. I think the answer is *NO*. Monte-Carlo programs do an n-ply deep search of nodes evaluated by a simulation. The Monte-Carlo programs which use UCT do not do an n-ply deep search, as this n increase with the number of simulations. So with infinite power, the entire tree will be explored, then the leafs will be at the end of the game, so the best move will be found. This is true for UCT with ANY evaluation function, even random, even the one which always answers 0, or always 1, as soon as the scoring of FINAL position is well done. However I agree that it is not interesting (as the infinite in this case is very far), and this does not come from MC, only the UCT (or equivalent) part. Sylvain ___ 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 infinite strong
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? This is a common misconception. The problem lies in that pesky word, infinite. Two inescapable facts prevent such a computer from ever existing: - There are a finite number of atomic particles in the universe. - The age of the universe is a finite length of time. The one who counts will never reach infinity ... I did not say that infinite computing power was something that existed in any sense in the universum as humans gasp it. Nor did I say that it will eventually emerge when someone waits long enough for it to appear. When I said infinite I meant infinite. If the moon were made of green cheese, I am the pope. Period. Hmmm, I guess you are right after all. So are you. aquarius -- german commercial - can savely be ignored: Ein Herz für Kinder - Ihre Spende hilft! Aktion: www.deutschlandsegelt.de Unser Dankeschön: Ihr Name auf dem Segel der 1. deutschen America's Cup-Yacht! ___ 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 infinite strong
Richard, The key word is not infinite, it's the word if The statement was IF we had an infinite computer It doesn't matter one bit whether such a device is possible - it's a perfectly valid thought device for thought experiments.It's easy to imagine what we would do with such a computer and how it could be used without stretching our brains too far. We can also imagine the moon being made of green cheese without this actually being the case. I don't see any problem with considering the behavior of a machine with certain characteristics just because we can't produce one. We cannot even be sure such a thing is impossible. It might not be constructed they way you assume it has to be to be called a computer. And just because we cannot imagine how such a machine could possible exist doesn't mean it cannot. It defies the laws of the universe as we know them assuming any kind of construction that we know about - but that in itself might mean that we currently lack the imagination to build such a device. Another problem is that we are a subset of our universe. We don't know much about the universe and we are constrained by it. It's entirely possible that such a computer could exist OUTSIDE our universe. It couldn't be explained or understood by us and probably could not operate as a physical device in our universe. The incompleteness theorem might explain why such a device might not be understood in our universe. But just saying it cannot exist is a pretty limited way of thinking about it and doesn't disqualify our ability to reason about it. - Don On Fri, 2006-11-24 at 08:42 -0600, Richard Brown wrote: [EMAIL PROTECTED] 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? This is a common misconception. The problem lies in that pesky word, infinite. Two inescapable facts prevent such a computer from ever existing: - There are a finite number of atomic particles in the universe. - The age of the universe is a finite length of time. These facts mean that, even _if_ one were able to use each and every atomic particle as a bit in one huge universe-sized computer, there would _never_ be sufficient room to store the results of such a search, even _if_ one had infinite time! And conversely, even _if_ there were an _infinite_ number of atomic particles in the universe, permitting sufficient room to store the results, the calculation of those results would take longer than the age of the universe, which is finite. If we had infinite computing power Go would resemble tic tac toe from a programmer's perspective. period. You seem mighty certain about that. If the moon were made of green cheese, I am the pope. Period. Hmmm, I guess you are right after all. ___ 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 infinite strong
The key word is not infinite, it's the word if i can't believe i want to extend this conversation any further, but i'll simply say that in mathematics and computer science it is important to consider abstract relationships between formally defined objects without regard to whether or not they do actually exist (numbers for instance, do not exist apart from us talking about them). computational complexity is an important example, as is convergence in a limit. the question as phrased earlier was simply whether a finite deterministic game could be solved by a particular algorithm, given enough time. nothing wrong with that question. 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. s. The all-new Yahoo! Mail beta Fire up a more powerful email and get things done faster. http://new.mail.yahoo.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 infinite strong
On Fri, 2006-11-24 at 13:38 -0800, steve uurtamo wrote: 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. s. Hi Steve, Just a few years ago these kinds of statements were made about computer chess and at the time they appeared to be REALLY SAFE predictions to make. Computers were doing 4 or 5 ply searches, they played absolutely horrible by master standards and it was absolutely inconceivable that a computer would ever search 2 or 3 ply deeper in the foreseeable future. Not only was that underestimated, but it was commonly believed that even 3 or 4 more ply wouldn't help it much. The improvement of even 1 ply was seriously underestimated. The reasons given are the SAME reasons given for computer GO. It was common to see mistakes that would require many extra ply for the computer to wake up. The common wisdom of the day was that an extra ply was close to worthless. I think the biggest myth of all was that humans were good at chess and that a computer had to be better at EVERYTHING in order to beat the human masters who were practically given god-like status. I'm probably a bit older than most on this list - and I have a very strong sense of historical perspective. I was there when micro-chess for the TSR-80 came out and I was bitterly disappointed with how badly it played. Back then I completely sucked at chess and yet I could beat the program without wasting many brain cells. The most common reason give was the same one you just made, The time/space limitations are just too great.And that did not seem like a silly statement at all - the arguments were powerful and convincing ... and wrong! The typical argument started by showing a position that required a few extra ply to see that a human master knew almost intuitively. Then a projection was made about how much extra computing power was needed and the conclusion was completely obvious - it couldn't possibly happen in your lifetime! Then it went into wild speculation - even if a computer COULD look 10 ply deeper it wouldn't make much difference because computers can never have the positional understanding of even an advanced beginner, let alone a master. If you look back over the years, you will see that no matter how much progress had been made, many believed we had hit a wall - that further depth wouldn't help any while reluctantly admitting that the last increase did help a lot, but only because of tactics - after this tactics won't matter any more. This is just typical of us humans - we tend to have a very limited horizon ourselves and we only see the immediate surroundings - a shortcoming that computers are accused of. A lot of people take exception to this and say, yes, but chess is nothing like GO and the cycle starts all over again. And it's true - GO is more complicated and has it's own special difficulties. But I am not so pessimistic and I would never embarrass myself with claims like you made. You could turn out to be right - but I think it's rather bold of you.Perhaps in 40 years, if you are still alive - you will have to eat your words! Along the way there will be many other advancements. I can't envision a pure Monte/Carlo exactly like we have now doing the job - but even in chess there were numerous advancements to the basic alpha/beta idea. The old programs would not stand a chance on modern hardware against modern programs.This will surely happen in GO too and is part of the reason I think you are probably wrong and shortsighted just like the chess masters were who predicted it would take hundreds of years and basically embarrassed themselves. - Don ___ 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 infinite strong
To be quite honest, I have only a vague understanding of what is called computational complexity -- but it's clear enough that, _even_given_an_infinite_amount_of_storage_ it would take longer than the age of the universe to exhaustively search the game tree, and it is equally clear that, _even_given_infinite_time_ it would take more bits than there are particles in the universe. and if it turns out that the game of go can be equally well represented by a simpler structure that we can finitely search in reasonable time, then it will matter that we have considered this. s. Sponsored Link Mortgage rates near 39yr lows. $420k for $1,399/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/
