Re: [computer-go] Can Go be solved???... PLEASE help!
On Wed, 2007-01-17 at 03:47 -0600, Nick Apperson wrote: I bet Windows Vista would still run slow on God's computer though. Go Microsoft! Sorry to get off topic, I just figure we have beat this subject to death. You would probably just have to reboot it more often. - Nick ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On Wed, 2007-01-17 at 06:03 -0300, Eduardo Sabbatella wrote: As far I know, just coffee speaking with some physics friends. WE ALL live in multi dimensional world. Indeed, if more then 3 dimensions exists, we exist in them, also our computers. The thing is, our eyes only see the first three ones. I think you are talking about the God's computer ;-). I'll bet there is something more out there in computing hardware that we haven't figured, which will seemingly help us go beyond the limitations we imagine that we now have.Perhaps just wishful thinking on my part. I like to imagine that such a super computer is possible, even if it's not possible for us to build it or understand it. Maybe it can exist but cannot ever be accessible to us. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Way off topic, on behalf of physical evidence of the dimension of universe: In an n-dimensional universe any radiation that propagates under common circumstances: 1. Conservation of energy 2. Constant speed 3. Isotropy (same intensity in all directions) satisfies: At a distance d from the source, the energy emitted at a moment d/c is contained in a n-dimensional hypersphere. Therefore, the energy measured at a distance d is = constant*intensity/d^(n-1) where n is the dimension of universe. All propagation laws (including gravity) have the form: constant*intensity/d^2 That is: n - 1 = 2 -- n = 3 Any coherent higher dimension model should explain which of the three circumstances is not met, how and why and without making any particular dimension different from the others. Something a lot more complicated than just drawing easy conclusions from analytic geometry. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On Wed, 17 Jan 2007, Jacques Basaldúa wrote: Any coherent higher dimension model should explain which of the three circumstances is not met, how and why and without making any particular dimension different from the others. Something a lot more complicated than just drawing easy conclusions from analytic geometry. Of course the higher dimensions are way smaller, otherwise we would see them :-) Seriously, string-theory requires higher dimensions with a very small curvature (they are different from the 3). And you are correct, it gets very complicated. The geometrical examples were just meant as an easy to understand explanation why higher dimension do not increase the 3-d volume of the universe. Christoph___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On Sat, 13 Jan 2007, Don Dailey wrote: One of the theoretical limitations to computing power (which was layed out in someones posts) and I have always understood to be the case, is related to space - the physical size of the universe. The problem with higher dimensions is that they are small AND they do NOT increase the 3-dimensional volume of our universe. Imagine a 2 dimesional (finite) surface and bend it in some way (eg. cylinder) ... even though your 2-dim universe exists now in 3 dimensions, it did not increase in area. If a computer can exist in 3 dimensions, couldn't an infinite number of them exist with 1 more dimension? Nope; see above. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On Tue, 2007-01-16 at 16:21 -0800, Christoph Birk wrote: On Sat, 13 Jan 2007, Don Dailey wrote: One of the theoretical limitations to computing power (which was layed out in someones posts) and I have always understood to be the case, is related to space - the physical size of the universe. The problem with higher dimensions is that they are small AND they do NOT increase the 3-dimensional volume of our universe. Imagine a 2 dimesional (finite) surface and bend it in some way (eg. cylinder) ... even though your 2-dim universe exists now in 3 dimensions, it did not increase in area. If a computer can exist in 3 dimensions, couldn't an infinite number of them exist with 1 more dimension? I'm suggesting computers that might exist outside our 3 dimensional space, not confined to our 3 dimensional space. Perhaps there are beings that see our space as flat from their many dimensions and any physical objects they deal with, are infinitely bigger that we can observe. For instance if there existed 2 dimensional beings, we could not show them 3 dimensional objects, just reflections of them and any of our objects would be infinitely large to them.If we could build 2 dimensional computers, we could stack any number of them on top of each other and they would not take up any extra space, no? - Don Nope; see above. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On 16, Jan 2007, at 5:45 PM, Don Dailey wrote: For instance if there existed 2 dimensional beings, we could not show them 3 dimensional objects, The answers to this are in Flatland: A romance of many dimensions a nice short book by E.A. Abbott. just reflections of them slices and any of our objects would be infinitely large to them. No, they would only be aware of the slice that intersects their world. It would still have finite extent in their world. If we could build 2 dimensional computers, we could stack any number of them on top of each other Which is essentially what we really do ... and they would not take up any extra space, no? No. Cheers, David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Joshua Shriver a écrit : I agree, anyone play othello/Reversi? Yes, I do othello programming. From my understanding it has been solved. Yet when I try to find info Othello 6x6 has been solved (and can be easily played perfectly on modern computer), but othello 8x8 is still unsolved, as far as I know; although this can be probably done within a few years of intensive computations. Other board sizes (10x10 and more) are out of reach for several years. on reversi computer tournaments they all seemed to die out several years ago. There is a small community of othello programmers still active on GGS: telnet://opal.cs.ualberta.ca:5000 -- Richard ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Blokus www.blokus.com looks like an interesting challenge that is similar to go, but doesn't have so large a state space. It has some similarities to go if you are using pattern templates to look for structures. NIck On 1/14/07, Richard Delorme [EMAIL PROTECTED] wrote: Joshua Shriver a écrit : I agree, anyone play othello/Reversi? Yes, I do othello programming. From my understanding it has been solved. Yet when I try to find info Othello 6x6 has been solved (and can be easily played perfectly on modern computer), but othello 8x8 is still unsolved, as far as I know; although this can be probably done within a few years of intensive computations. Other board sizes (10x10 and more) are out of reach for several years. on reversi computer tournaments they all seemed to die out several years ago. There is a small community of othello programmers still active on GGS: telnet://opal.cs.ualberta.ca:5000 -- Richard ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Nick ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Can Go be solved???... PLEASE help!
I have a strong blockus program. If anyone wants to set up a server I'll put it up. Blockus has 4 players, so there is the issue of cooperation between several players against one other. My implementation is just alpha-beta iterative deepening, transposition table, etc. David Fotland -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Nick Leaton Sent: Sunday, January 14, 2007 3:40 AM To: computer-go Subject: Re: [computer-go] Can Go be solved???... PLEASE help! Blokus www.blokus.com looks like an interesting challenge that is similar to go, but doesn't have so large a state space. It has some similarities to go if you are using pattern templates to look for structures. NIck On 1/14/07, Richard Delorme [EMAIL PROTECTED] wrote: Joshua Shriver a écrit : I agree, anyone play othello/Reversi? Yes, I do othello programming. From my understanding it has been solved. Yet when I try to find info Othello 6x6 has been solved (and can be easily played perfectly on modern computer), but othello 8x8 is still unsolved, as far as I know; although this can be probably done within a few years of intensive computations. Other board sizes (10x10 and more) are out of reach for several years. on reversi computer tournaments they all seemed to die out several years ago. There is a small community of othello programmers still active on GGS: telnet://opal.cs.ualberta.ca:5000 -- Richard ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Nick ___ 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] Can Go be solved???... PLEASE help!
I would first just like to say, there have been many times in my life where I have known 1000 times more than someone else and I didn't feel the need to be an ass. I'm sure you are a nice person, but please don't treat me like I am a moron. Some assumptions you made about me that aren't true: 1) you assume I didn't understand what solvable means in a mathematical sense. I think in a more important way, solvable means is able to be solved and frankly that question is still able to be debated regarding go. From a mathematical standpoint, any game with a finite set of states is solvable. 2) You assume that I took 1 billion years literally... Oh my, I would venture to say that I have had a whole lot more physics than you have my friend and I understand how people get those numbers. 3) You assume that I don't know that changing the board size doesn't necessariyl change all the properties of the game. I mean how dumb do you think I am? But, I am going to point out a couple problems in what you said since you seem to be up for being an ass. 1) Multiple dimensions doesn't help at all. Information processing ability as well as informataion storing ability is proportional to a 2D surface surrounding the area that is able to be used for the computation. This is the upper limit given with thermodynamics which is probably the only part of physics that has laws that are well founded. 2) The reason I object to infinity as a concept is not because of my mental inferiority. In fact, infinity is a concept that comes quite readily to me. I learned it early in my youth and when I first saw a graph of velocity versus time (age 12 maybe) I knew that the area under it was displacement. I had taken calc 2 as a sophmore in highschool. The problem I have with it in regards to what you were talking about is that it has never been proven to exist anywhere in the actual world and there is lots of evidence that it doesn't exist. That said, I have seen you post before and I enjoy reading your posts, but please don't flame me. Just because I am new to computer go doesn't mean I am a moron. I might bring something new. If you all had it figured out already, we wouldn't be having this discussion. I have a lot to learn from you and I look forward to that. Please be more respectful. I am sorry that this was a harsh message, but I feel you were unfair to attack me as you did. Sincerely, Nick On 1/12/07, Don Dailey [EMAIL PROTECTED] wrote: On Fri, 2007-01-12 at 15:43 -0600, Nick Apperson wrote: yeah, there are upper limits placed on computation rate by thermodynamics. 19x19 is way beyond those as Dave pointed out. But, even if you believe that technology will improve and the most revolutionary change yet will come to understanding of physics and that change will give us signifigantly more computational power and time etc... You can always make a bigger board. If life comes to a point where go could be solved for any size board, you will no longer be in this world and solving things such as is go solvable? will have no meaning. Yes, you can always make a bigger problem by making a bigger go board but that doesn't change the theoretical properties of the game. The game will always be solvable. The game might be trivially solvable even now to a being not confined to our 3 physical dimensions. I hate to get philosophical like this, but there are theories of other dimensions that (if true) say we live in a multi-dimensional universe.There may be much more here than we can sense and that we can perhaps take advantage of. But it doesn't matter. When Chris said 1 billion years you should have instantly realized that he didn't mean this literally, he just meant a correct procedure exists for solving the game. Since no one has proved how long the universe will last, I don't think you can even prove that in a practical sense it's unsolvable. If you lack imagination you can simply say it's not solvable because you believe it can't be done in your lifetime - as if science and math cares about how long we live or even the universe.If the universe will die in 10 trillion years does that mean the number 20 trillion is an impossible number? The concept of infinity is important in mathematics. It's even useful, but I suppose that it really should be considered meaningless since we all die after 70 or 80 years. - 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] Can Go be solved???... PLEASE help!
On Fri, 2007-01-12 at 15:51 +, Mehdi Ahmadi wrote: Hello thank in advance for any interests/ responses. I'm unfortunately (or not) doing a dissertation as part of my final year project (undergraduate) on the game of Go. The exact title is: Can the game of go be solved? Analysis of computational methodologies for go. And I have included my overall objectives below. I have many works from different people on different aspects of Computer Go which would make for great inclusion at different parts - but overall I am still gravely struggling. In reviewing some of these my greatest difficulty is in understanding exactly how say Monte-Carlo-UCT or even Alpha-Beta testing (pruning, etc) occur so as to be able to give a simplified depiction (illustrated or otherwise) of the process. Can this be done without having to go through the source code of say something like GNU Go? Also another difficulty I've had is in trying to get further information on the commonly referred top ranking packages, Handtalk, Go++, Many Faces of Go, etc due to their commercial nature? (the only thing I've been able to find which is a bit outdated: http://www.inventivity.com/OpenGo/Papers/EditedGoPapers.html). If they still exist online, most of these papers are suggested reading, IMHO WRT classic methods (alpha-beta, evaluation, Zobrist hashing, etc) a lot of material can be found in computer-chess publications. Another source of links can be found at Markus Enzenberger's online bibliography: http://www.cs.ualberta.ca/~emarkus/compgo_biblio/ Most of the computer go authors have posted on this mailing list, and discussed their views and methods, and the design of their programs. The archive of this mailinglist can be found at: http://computer-go.org/pipermail/computer-go/ This archive starts at approx 2003. I have an archive of older stuff (1993-) from this mailinglist stored on my personal website: http://nngs.ziar.net/cgml/ HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Ok Nick, The funny thing about this, is that I was originally defending someone who after making a simple post got flooded with all the stale size of the universe and grains of sands arguments - presumably to prove he was wrong when he made a simple statement which was correct. He made the horrible mistake of saying 1 billion years and I guess that's where he went wrong. Everyone jumped in as if he was an idiot for thinking it would only take 1 billion years. I also admit I got annoyed with those arguments about the size of the game, I felt it was pretty redundant and I don't know of anyone on this group that needed a refresher course on this - everyone knows how huge this problem is. I'm sure you understand physics much more than I do. However, I disagree about dimensionality and if I'm wrong I have a thick skin and you can explain it to me and I will believe you. One of the theoretical limitations to computing power (which was layed out in someones posts) and I have always understood to be the case, is related to space - the physical size of the universe.If a computer can exist in 3 dimensions, couldn't an infinite number of them exist with 1 more dimension? Couldn't one be constructed that is far more highly parallel that what we can construct in our 3 physical dimensions? - Don On Sat, 2007-01-13 at 03:38 -0600, Nick Apperson wrote: I would first just like to say, there have been many times in my life where I have known 1000 times more than someone else and I didn't feel the need to be an ass. I'm sure you are a nice person, but please don't treat me like I am a moron. Some assumptions you made about me that aren't true: 1) you assume I didn't understand what solvable means in a mathematical sense. I think in a more important way, solvable means is able to be solved and frankly that question is still able to be debated regarding go. From a mathematical standpoint, any game with a finite set of states is solvable. 2) You assume that I took 1 billion years literally... Oh my, I would venture to say that I have had a whole lot more physics than you have my friend and I understand how people get those numbers. 3) You assume that I don't know that changing the board size doesn't necessariyl change all the properties of the game. I mean how dumb do you think I am? But, I am going to point out a couple problems in what you said since you seem to be up for being an ass. 1) Multiple dimensions doesn't help at all. Information processing ability as well as informataion storing ability is proportional to a 2D surface surrounding the area that is able to be used for the computation. This is the upper limit given with thermodynamics which is probably the only part of physics that has laws that are well founded. 2) The reason I object to infinity as a concept is not because of my mental inferiority. In fact, infinity is a concept that comes quite readily to me. I learned it early in my youth and when I first saw a graph of velocity versus time (age 12 maybe) I knew that the area under it was displacement. I had taken calc 2 as a sophmore in highschool. The problem I have with it in regards to what you were talking about is that it has never been proven to exist anywhere in the actual world and there is lots of evidence that it doesn't exist. That said, I have seen you post before and I enjoy reading your posts, but please don't flame me. Just because I am new to computer go doesn't mean I am a moron. I might bring something new. If you all had it figured out already, we wouldn't be having this discussion. I have a lot to learn from you and I look forward to that. Please be more respectful. I am sorry that this was a harsh message, but I feel you were unfair to attack me as you did. Sincerely, Nick On 1/12/07, Don Dailey [EMAIL PROTECTED] wrote: On Fri, 2007-01-12 at 15:43 -0600, Nick Apperson wrote: yeah, there are upper limits placed on computation rate by thermodynamics. 19x19 is way beyond those as Dave pointed out. But, even if you believe that technology will improve and the most revolutionary change yet will come to understanding of physics and that change will give us signifigantly more computational power and time etc... You can always make a bigger board. If life comes to a point where go could be solved for any size board, you will no longer be in this world and solving things such as is go solvable? will have no meaning. Yes, you can always make a bigger problem by making a bigger go board but that doesn't change the theoretical properties of the game. The game will always be solvable. The game might be trivially solvable even now to a
Re: [computer-go] Can Go be solved???... PLEASE help!
On Friday 12 January 2007 16:16, Chris Fant wrote: Seems like a silly title. Any game of perfect information that has a clear rule set can be solved. Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). A better question is, Can Computer Go Surpass Human Go? But again, clearly it will. It's just a question of how long until it occurs. Don´t be rude. I understood what he means. Game of go for is not solved for me. (19x19). The thing is, nobody found an optimisation good enough that is able to calc the perfect game in human time. You changed the topic of the disertation to humans vs machines. Eduardo __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
CM-1's processing element is not a transputer but a custom (CMOS) 1-bit ALU with 4Ki bit of RAM. I know this is not essential but believe this kind of correction is old men's role :-). alain Baeckeroot: [EMAIL PROTECTED]: Le samedi 13 janvier 2007 15:06, Don Dailey a écrit : If a computer can exist in 3 dimensions, couldn't an infinite number of them exist with 1 more dimension? Couldn't one be constructed that is far more highly parallel that what we can construct in our 3 physical dimensions? The first Connection-Machine CM1 (from Thinking Machine Inc) was 65 536 transputer connected on a 12d hypercube (one transputer at each corner) Itw was quite hard to program, but i think it could be a very good hardware for a strong go program :) Sadly it is now in museum. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Le samedi 13 janvier 2007 16:46, Hideki Kato a écrit : CM-1's processing element is not a transputer but a custom (CMOS) 1-bit ALU with 4Ki bit of RAM. I know this is not essential but believe this kind of correction is old men's role :-). oops, true, my memory mixed up some old stuff :) Also 2^12 != 65536 but still CM1 was 12d, with 16 tiny proc at each corner of the hyper cube. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On 1/14/07, Nick Apperson [EMAIL PROTECTED] wrote: From: Nick Apperson [EMAIL PROTECTED] ... Essentially says that the maximum amount of information is proportional to the 2D surface around it. Even if we live in a many-dimensional world (I happen to believe we do), the area surrounding it would still be 2 dimensional as long as these are small dimensions. I don't understand why that boundary would necessarily be 2 dimensional. Isn't the boundary of an N dimensional hypervolume simply an N-1 dimensional hypersurface? E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Seems like a silly title. Any game of perfect information that has a clear rule set can be solved. Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). A better question is, Can Computer Go Surpass Human Go? But again, clearly it will. It's just a question of how long until it occurs. On 1/12/07, Mehdi Ahmadi [EMAIL PROTECTED] wrote: Hello thank in advance for any interests/ responses. I'm unfortunately (or not) doing a dissertation as part of my final year project (undergraduate) on the game of Go. The exact title is: Can the game of go be solved? Analysis of computational methodologies for go. And I have included my overall objectives below. I have many works from different people on different aspects of Computer Go which would make for great inclusion at different parts - but overall I am still gravely struggling. In reviewing some of these my greatest difficulty is in understanding exactly how say Monte-Carlo-UCT or even Alpha-Beta testing (pruning, etc) occur so as to be able to give a simplified depiction (illustrated or otherwise) of the process. Can this be done without having to go through the source code of say something like GNU Go? Also another difficulty I've had is in trying to get further information on the commonly referred top ranking packages, Handtalk, Go++, Many Faces of Go, etc due to their commercial nature? (the only thing I've been able to find which is a bit outdated: http://www.inventivity.com/OpenGo/Papers/EditedGoPapers.html). Lastly can any general categorisation - distinction be made of current approach/ implementations in trying to 'solve' Go. in comparison to say traditional disciplines used in trying to solve games (complex or otherwise) via computer? To put simply I am trying to have some core root comparison in current methodologies (if there is any?). If anyone has any suggestions/ guidance on anything mentioned - I would be eternally indebted. == 5.1 OBJECTIVES . To concisely review all game playing aspects of Go (rules, openings, middle game, etc) and its relevance to the complication of meaningful measurements of interest. . To evaluate, gain and develop further understanding of specific game aspects including (eg): - Representation: . Eyes . life-and-death . territory estimates and weakness - Move Evaluation: . Territorial and strategic affluence. . Address specific and current implementation methodologies including: - Search algorithms (Alpha-Beta - local/global, Monte-Carlo -UCT) - Move Generation - Positional Evaluation (Patterns, Neural Networks) . To detail inadequacies in research and reasons for shortfalls where applicable. ___ 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] Can Go be solved???... PLEASE help!
From http://senseis.xmp.net/?7x7BestPlay it looks like 7x7 Go may already have been solved. 5x5 was solved in 2002, according to http://erikvanderwerf.tengen.nl/5x5/5x5solved.html AFAIK, 9x9 Go has not been solved yet. 19x19 Go will surely exceed the capabilities of computers in my lifetime, I suspect. -- Terry McIntyre - Original Message From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Friday, January 12, 2007 8:16:35 AM Subject: Re: [computer-go] Can Go be solved???... PLEASE help! Seems like a silly title. Any game of perfect information that has a clear rule set can be solved. Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). A better question is, Can Computer Go Surpass Human Go? But again, clearly it will. It's just a question of how long until it occurs. On 1/12/07, Mehdi Ahmadi [EMAIL PROTECTED] wrote: Hello thank in advance for any interests/ responses. I'm unfortunately (or not) doing a dissertation as part of my final year project (undergraduate) on the game of Go. The exact title is: Can the game of go be solved? Analysis of computational methodologies for go. And I have included my overall objectives below. I have many works from different people on different aspects of Computer Go which would make for great inclusion at different parts - but overall I am still gravely struggling. In reviewing some of these my greatest difficulty is in understanding exactly how say Monte-Carlo-UCT or even Alpha-Beta testing (pruning, etc) occur so as to be able to give a simplified depiction (illustrated or otherwise) of the process. Can this be done without having to go through the source code of say something like GNU Go? Also another difficulty I've had is in trying to get further information on the commonly referred top ranking packages, Handtalk, Go++, Many Faces of Go, etc due to their commercial nature? (the only thing I've been able to find which is a bit outdated: http://www.inventivity.com/OpenGo/Papers/EditedGoPapers.html). Lastly can any general categorisation - distinction be made of current approach/ implementations in trying to 'solve' Go. in comparison to say traditional disciplines used in trying to solve games (complex or otherwise) via computer? To put simply I am trying to have some core root comparison in current methodologies (if there is any?). If anyone has any suggestions/ guidance on anything mentioned - I would be eternally indebted. == 5.1 OBJECTIVES . To concisely review all game playing aspects of Go (rules, openings, middle game, etc) and its relevance to the complication of meaningful measurements of interest. . To evaluate, gain and develop further understanding of specific game aspects including (eg): - Representation: . Eyes . life-and-death . territory estimates and weakness - Move Evaluation: . Territorial and strategic affluence. . Address specific and current implementation methodologies including: - Search algorithms (Alpha-Beta - local/global, Monte-Carlo -UCT) - Move Generation - Positional Evaluation (Patterns, Neural Networks) . To detail inadequacies in research and reasons for shortfalls where applicable. ___ 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/ Need Mail bonding? Go to the Yahoo! Mail QA for great tips from Yahoo! Answers users. http://answers.yahoo.com/dir/?link=listsid=396546091___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
A much more up-to-date bibliography is maintained by Markus Enzenberger: http://www.cs.ualberta.ca/~emarkus/compgo_biblio/ Terry McIntyre Bored stiff? Loosen up... Download and play hundreds of games for free on Yahoo! Games. http://games.yahoo.com/games/front___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
There are a number of definitions of solved, ranging from a program exists that can beat any human to we can quickly determine, for any position, the best move and the result under optimal play. In the latter strong sense, I believe Go has only been solved up to 5x5, maybe 6x6. There are some games, such as Hex, for which we know who wins from the starting position given optimal play, but we don't know how to figure out the best move. Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ On Jan 12, 2007, at 8:45 AM, terry mcintyre wrote: From http://senseis.xmp.net/?7x7BestPlay it looks like 7x7 Go may already have been solved. 5x5 was solved in 2002, according to http://erikvanderwerf.tengen.nl/5x5/5x5solved.html AFAIK, 9x9 Go has not been solved yet. 19x19 Go will surely exceed the capabilities of computers in my lifetime, I suspect. -- Terry McIntyre - Original Message From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Friday, January 12, 2007 8:16:35 AM Subject: Re: [computer-go] Can Go be solved???... PLEASE help! Seems like a silly title. Any game of perfect information that has a clear rule set can be solved. Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). A better question is, Can Computer Go Surpass Human Go? But again, clearly it will. It's just a question of how long until it occurs. On 1/12/07, Mehdi Ahmadi [EMAIL PROTECTED] wrote: Hello thank in advance for any interests/ responses. I'm unfortunately (or not) doing a dissertation as part of my final year project (undergraduate) on the game of Go. The exact title is: Can the game of go be solved? Analysis of computational methodologies for go. And I have included my overall objectives below. I have many works from different people on different aspects of Computer Go which would make for great inclusion at different parts - but overall I am still gravely struggling. In reviewing some of these my greatest difficulty is in understanding exactly how say Monte-Carlo-UCT or even Alpha- Beta testing (pruning, etc) occur so as to be able to give a simplified depiction (illustrated or otherwise) of the process. Can this be done without having to go through the source code of say something like GNU Go? Also another difficulty I've had is in trying to get further information on the commonly referred top ranking packages, Handtalk, Go++, Many Faces of Go, etc due to their commercial nature? (the only thing I've been able to find which is a bit outdated: http://www.inventivity.com/OpenGo/Papers/EditedGoPapers.html). Lastly can any general categorisation - distinction be made of current approach/ implementations in trying to 'solve' Go. in comparison to say traditional disciplines used in trying to solve games (complex or otherwise) via computer? To put simply I am trying to have some core root comparison in current methodologies (if there is any?). If anyone has any suggestions/ guidance on anything mentioned - I would be eternally indebted. == 5.1 OBJECTIVES . To concisely review all game playing aspects of Go (rules, openings, middle game, etc) and its relevance to the complication of meaningful measurements of interest. . To evaluate, gain and develop further understanding of specific game aspects including (eg): - Representation: . Eyes . life-and-death . territory estimates and weakness - Move Evaluation: . Territorial and strategic affluence. . Address specific and current implementation methodologies including: - Search algorithms (Alpha-Beta - local/global, Monte-Carlo -UCT) - Move Generation - Positional Evaluation (Patterns, Neural Networks) . To detail inadequacies in research and reasons for shortfalls where applicable. ___ 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/ We won't tell. Get more on shows you hate to love (and love to hate): Yahoo! TV's Guilty Pleasures list. ___ 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] Can Go be solved???... PLEASE help!
Seems like a silly title. Any game of perfect information that has a clear rule set can be solved. Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). A better question is, Can Computer Go Surpass Human Go? But again, clearly it will. It's just a question of how long until it occurs. Without being too pedantic, I'd like to note that although all two-player games with perfect information and finite length have winning strategies, it is not always the case that they are either computable or decidable. This caveat likely does not apply to games such as 19x19 go, but it just might apply to the question of finding a winning strategy for go on an NxN board, for instance. For an example of such a game, see: J.P. Jones, Some undecidable determined games, International Journal of Game Theory, 11 (1982) s. 8:00? 8:25? 8:40? Find a flick in no time with the Yahoo! Search movie showtime shortcut. http://tools.search.yahoo.com/shortcuts/#news ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On 12-jan-07, at 14:16, Chris Fant wrote: Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). To 'solve' a game in the strict sense you need to know the best answer to every move. And you need to be able to prove that it's the best move. To do so you need to look at the following number of positions AMP^(AGL/2) where AMP is average number of moves in a position and AGL is the average game length. If I take a conservative AGL of 260 moves, we can compute the AMP from that, being (365+(365- AGL))/2=235 So we get 235^130, which is about 10^300 as a lower bound. The upper bound is something like 195^170 (play until all groups have 2 eyes) which my calculator is unable to compute, but I think it's roughly 10^400. I'm guessing it's questionable whether we'd be able to compute that even with a computer the size of this planet before the sun goes out. Distributing the work over other planets or star-sysems will only help marginally due to the time it takes to send information to Earth by the speed of light. So I'd say it's impossible. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
And Mark Boon also neglected the future use of wormholes, replicators and who knows what? :) Sorry, but how do you what future quantum computers can churn so much data? 10^400 is a rediculously large number. Even if you multiply the volume of the visible universe expressed in in cubic Planck lengths (1.4 e26 1.6x10^-36 m) by the age of the universe expressed in Planck times (5.4x10^-44 s) and the higher estimate for the number of particles in the universe (10^87) you get only 10^326, wich is much, much smaller than 10^400. It is impossible to handle this much data in the lifetime of the universe, whatever the technology. Even if a device would use every particle and every spacetime wrinkle in the universe in a big parallel quantum computer at a clock cycle of 10^44 hz. I do believe someone (something?) will eventually be able to build a program that beats any human. But solve go? Never. Dave - Oorspronkelijk bericht - Van: Chris Fant [EMAIL PROTECTED] Datum: vrijdag, januari 12, 2007 7:03 pm Onderwerp: Re: [computer-go] Can Go be solved???... PLEASE help! You neglected to consider the power of future quantum computers. On 1/12/07, Mark Boon [EMAIL PROTECTED] wrote: On 12-jan-07, at 14:16, Chris Fant wrote: Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). To 'solve' a game in the strict sense you need to know the best answer to every move. And you need to be able to prove that it's the best move. To do so you need to look at the following number of positions AMP^(AGL/2) where AMP is average number of moves in a position and AGL is the average game length. If I take a conservative AGL of 260 moves, we can compute the AMP from that, being (365+(365-AGL))/2=235 So we get 235^130, which is about 10^300 as a lower bound. The upper bound is something like 195^170 (play until all groups have 2 eyes) which my calculator is unable to compute, but I think it's roughly 10^400. I'm guessing it's questionable whether we'd be able to compute that even with a computer the size of this planet before the sun goes out. Distributing the work over other planets or star- sysems will only help marginally due to the time it takes to send information to Earth by the speed of light. So I'd say it's impossible. Mark ___ 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] Can Go be solved???... PLEASE help!
yeah, there are upper limits placed on computation rate by thermodynamics. 19x19 is way beyond those as Dave pointed out. But, even if you believe that technology will improve and the most revolutionary change yet will come to understanding of physics and that change will give us signifigantly more computational power and time etc... You can always make a bigger board. If life comes to a point where go could be solved for any size board, you will no longer be in this world and solving things such as is go solvable? will have no meaning. On 1/12/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: And Mark Boon also neglected the future use of wormholes, replicators and who knows what? :) Sorry, but how do you what future quantum computers can churn so much data? 10^400 is a rediculously large number. Even if you multiply the volume of the visible universe expressed in in cubic Planck lengths (1.4 e26 1.6x10^-36 m) by the age of the universe expressed in Planck times (5.4x10^-44 s) and the higher estimate for the number of particles in the universe (10^87) you get only 10^326, wich is much, much smaller than 10^400. It is impossible to handle this much data in the lifetime of the universe, whatever the technology. Even if a device would use every particle and every spacetime wrinkle in the universe in a big parallel quantum computer at a clock cycle of 10^44 hz. I do believe someone (something?) will eventually be able to build a program that beats any human. But solve go? Never. Dave - Oorspronkelijk bericht - Van: Chris Fant [EMAIL PROTECTED] Datum: vrijdag, januari 12, 2007 7:03 pm Onderwerp: Re: [computer-go] Can Go be solved???... PLEASE help! You neglected to consider the power of future quantum computers. On 1/12/07, Mark Boon [EMAIL PROTECTED] wrote: On 12-jan-07, at 14:16, Chris Fant wrote: Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). To 'solve' a game in the strict sense you need to know the best answer to every move. And you need to be able to prove that it's the best move. To do so you need to look at the following number of positions AMP^(AGL/2) where AMP is average number of moves in a position and AGL is the average game length. If I take a conservative AGL of 260 moves, we can compute the AMP from that, being (365+(365-AGL))/2=235 So we get 235^130, which is about 10^300 as a lower bound. The upper bound is something like 195^170 (play until all groups have 2 eyes) which my calculator is unable to compute, but I think it's roughly 10^400. I'm guessing it's questionable whether we'd be able to compute that even with a computer the size of this planet before the sun goes out. Distributing the work over other planets or star- sysems will only help marginally due to the time it takes to send information to Earth by the speed of light. So I'd say it's impossible. Mark ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Hi, On 1/12/07, Nick Apperson [EMAIL PROTECTED] wrote: yeah, there are upper limits placed on computation rate by thermodynamics. 19x19 is way beyond those as Dave pointed out. But, even if you believe that technology will improve and the most revolutionary change yet will come to understanding of physics and that change will give us signifigantly more computational power and time etc... You can always make a bigger board. If life comes to a point where go could be solved for any size board, you will no longer be in this world and solving things such as is go solvable? will have no meaning. Well, if I may be excused for being way too pedantic on this topic, raw computing power isn't the only way. Mathematical solutions might easily reduce the search space just enough to allow a full search of what's left of it. On the other hand, I'm not worried. There will always be challenging games to play and to try to master. best regards, Vlad ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
I appreciate your response. Mathematical solutions are certainly a good possibility to reduce the amount of processing power needed. However, a person would not be able to solve 19x19 because a person lacks the necessary computational resources to form a solution in any reasonable amount of time. A computer would therefore have to solve go. I think this is as close to a possibility as we can get, but it isn't enough to solve go. And if somehow it ever is, make the board bigger... But, as I said, I think your comment is a good one and suggests a strategy for computer go that I think could be highly fruitful and I have been exploring. - Nick On 1/12/07, Vlad Dumitrescu [EMAIL PROTECTED] wrote: Hi, On 1/12/07, Nick Apperson [EMAIL PROTECTED] wrote: yeah, there are upper limits placed on computation rate by thermodynamics. 19x19 is way beyond those as Dave pointed out. But, even if you believe that technology will improve and the most revolutionary change yet will come to understanding of physics and that change will give us signifigantly more computational power and time etc... You can always make a bigger board. If life comes to a point where go could be solved for any size board, you will no longer be in this world and solving things such as is go solvable? will have no meaning. Well, if I may be excused for being way too pedantic on this topic, raw computing power isn't the only way. Mathematical solutions might easily reduce the search space just enough to allow a full search of what's left of it. On the other hand, I'm not worried. There will always be challenging games to play and to try to master. best regards, Vlad ___ 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] Can Go be solved???... PLEASE help!
Peter Drake wrote: There are a number of definitions of solved, ranging from a program exists that can beat any human to we can quickly determine, for any position, the best move and the result under optimal play. In the latter strong sense, I believe Go has only been solved up to 5x5, maybe 6x6. There are some games, such as Hex, for which we know who wins from the starting position given optimal play, but we don't know how to figure out the best move. Another interesting question would be the score (eg. territorry) that black/white can reach assuming perfect play on both sides. If we knew that, a perfectly fair komi could be calculated. From what I know, even chess is still unsolved conserning this matter - noone knows if white (or even black) can force a win. eph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
White in 42 moves ;) Have a good weekend everyone. -Josh that, a perfectly fair komi could be calculated. From what I know, even chess is still unsolved conserning this matter - noone knows if white (or even black) can force a win. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
I agree, anyone play othello/Reversi? From my understanding it has been solved. Yet when I try to find info on reversi computer tournaments they all seemed to die out several years ago. -Josh On 1/12/07, Chrilly [EMAIL PROTECTED] wrote: Besides the technical question if it is possible, there is the ethical/philosophical one if it should be done. I think solving a game is killing a game. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Another interesting question would be the score (eg. territorry) that black/white can reach assuming perfect play on both sides. If we knew that, a perfectly fair komi could be calculated. From what I know, even chess is still unsolved conserning this matter - noone knows if white (or even black) can force a win. eph Such a Komi would not be fairer than the current one. If a perfect player would win with 15 points. Should the komi be increased to 15 points, although humans can not realize this advantage and there would a much higher winning-rate for white? The most fair decisiion is that the Komi brings the winning chances in practical play as close to 50% as possible. One could compute the black advantage from a big games database and set then the Komi to the mean value. This is much simpler than solvint the game and also fairer than some theoretical limit which is irrelevant for human-human play. It would be interesting if the empirical Komi depends on the playing strength. I would assume,that the tempo of Black is worth more for strong players. But there is on the other side the law of the balance of stupity. Also white loosed due too his lack of skills tempo/sente and the net effect is for all playing levels the same. Monte-Carlo Go is based on this law. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
In article [EMAIL PROTECTED], wrote: Sorry, but how do you what future quantum computers can churn so much data? Chris Fant isn't a modern-day human but an android sent back through a wormhole from future times (Future ^2, Left **7, Right **.13, to the root of SQRT(-1) in hex coords). But he'll self-destruct before admitting such, so lines of questioning like this will yield, at best, an uninteresting silence. Ooops, I've said too much. Boom -- Aidan Karley, Aberdeen, Scotland Written at Fri, 12 Jan 2007 21:40 GMT, but posted later. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On Fri, 2007-01-12 at 15:43 -0600, Nick Apperson wrote: yeah, there are upper limits placed on computation rate by thermodynamics. 19x19 is way beyond those as Dave pointed out. But, even if you believe that technology will improve and the most revolutionary change yet will come to understanding of physics and that change will give us signifigantly more computational power and time etc... You can always make a bigger board. If life comes to a point where go could be solved for any size board, you will no longer be in this world and solving things such as is go solvable? will have no meaning. Yes, you can always make a bigger problem by making a bigger go board but that doesn't change the theoretical properties of the game. The game will always be solvable. The game might be trivially solvable even now to a being not confined to our 3 physical dimensions. I hate to get philosophical like this, but there are theories of other dimensions that (if true) say we live in a multi-dimensional universe.There may be much more here than we can sense and that we can perhaps take advantage of. But it doesn't matter. When Chris said 1 billion years you should have instantly realized that he didn't mean this literally, he just meant a correct procedure exists for solving the game. Since no one has proved how long the universe will last, I don't think you can even prove that in a practical sense it's unsolvable. If you lack imagination you can simply say it's not solvable because you believe it can't be done in your lifetime - as if science and math cares about how long we live or even the universe.If the universe will die in 10 trillion years does that mean the number 20 trillion is an impossible number? The concept of infinity is important in mathematics. It's even useful, but I suppose that it really should be considered meaningless since we all die after 70 or 80 years. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
On Fri, 2007-01-12 at 21:51 +, Vlad Dumitrescu wrote: Hi, On 1/12/07, Nick Apperson [EMAIL PROTECTED] wrote: yeah, there are upper limits placed on computation rate by thermodynamics. 19x19 is way beyond those as Dave pointed out. But, even if you believe that technology will improve and the most revolutionary change yet will come to understanding of physics and that change will give us signifigantly more computational power and time etc... You can always make a bigger board. If life comes to a point where go could be solved for any size board, you will no longer be in this world and solving things such as is go solvable? will have no meaning. Well, if I may be excused for being way too pedantic on this topic, raw computing power isn't the only way. Mathematical solutions might easily reduce the search space just enough to allow a full search of what's left of it. Finally. A sensible voice of reason! - Don On the other hand, I'm not worried. There will always be challenging games to play and to try to master. best regards, Vlad ___ 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/
