Re: [computer-go] Positions illustrative of computer stupidity ?
I can't help but feel we are missing something. With UCT we miss those wonderful beta cutoff's that you get with straightforward alpha beta pruning - but with alpha beta pruning you are still exploring a lot more useless nodes.It seems the 2 are just not very compatible. Currently UCT does seem like the best choice by far. Yes, in the current state of the art. What would be great is to understand in what extend this would continue to be true if we change the evaluation function. What I believe (but this is only intuition, this have to be proved !), is that UCT is very efficient in Go because our evaluation function is bad. With a good/(very)^+ good evaluation function, alpha-beta would become much better than UCT. I think this is clearly the case if you can reach the end of the game in the tree for example. I don't know if someone tried UCT in chess to see the results. As we often assume that the evaluation function in chess is much better than in Go, it would be a good test case? [...] But UCT may be a rather extreme example of this phenomenon - better to go deep even without a huge number of simulations. Of course with UCT none of the evaluations are completely wasted, they all have an impact on potential root choices. It is an interesting point of view indeed. I did not see UCT on that angle... This would confirm our results where launching several simulations for each node (instead of node) where not improving the results (comparing at equal number of nodes. Comparing at equal number of simulations this was much worse !). Yet, one of the property of UCT which I think is very useful in Go is the smooth pruning. The other is that the value is between the mean and the min-max in a smooth manner, while keeping the convergence toward the min-max. 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
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 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 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 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/
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/
Re: [computer-go] Positions illustrative of computer stupidity ?
Le mercredi 22 novembre 2006 20:44, Rémi Coulom a écrit : Hi, Hi Rémi I am in search of Go positions that are easy to understand for humans, and difficult for computers. One incredibly simple example for human, where GNU Go horribly fails. The only move is tengen (center of the board). I don't know if its a simple bug, or a more difficult evaluation problem. It happens even if all databases are disabled (fuseki and joseki). Thanks to Aloril, who tell it to Min-u Kang (my go teacher :) Cheers. Alain. simple-test-19.sgf Description: application/go-sgf simple-test-99.sgf Description: application/go-sgf ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
