Re: [computer-go] New ICGA web site
Nick Wedd wrote: Some results of Computer Go (and other computer games) events have long been available on the old ICGA web site at http://www.cs.unimaas.nl/icga/ . There is now a new ICGA web site at http://www.grappa.univ-lille3.fr/icga/ with fuller information on these events, including many game records that were not (so far as I know) previously available. (Urban Hafner will be pleased to see that this new site includes RSS feeds.) Nick Hi, We did not advertise this site earlier, because there is a possibility that it will get its own domain name in the future. So if you create links to it, beware that they may get broken. This being said, if anybody has any of the missing data, we would welcome it. All the Go tournaments are listed there: http://www.grappa.univ-lille3.fr/icga/game.php?id=12 Most of the go game records were collected from the previous ICGA sites. For many of those past tournaments, the game collection was extremely messy: missing player names, missing result, etc. I tried to do my best to guess who played which color and what was the result, but it was sometimes difficult. So I would appreciate if participants in those tournaments could check that their game records are correct. I would not be surprised at all if there were mistakes. I hope that this web site will improve the communication of ICGA tournaments. The plan is to have live broadcasting of the games on the web, with a Chinese and a Japanese version of the site. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On Tue, 2007-01-23 at 16:53 -0500, Don Dailey wrote: It's obvious that you can't program a 10 instruction per second computer to beat a human - so it's also clear that there would be some minimum level of hardware required. Obvious? You have proof of that? ;-) Don't underestimate God, there might exist some really really really clever mathematical way to select enough good moves with 1000 instructions on 19x19 board to beat a pro player. I could make a guess, but I certainly don't trust my intuition here. My guess is that God could program a core 2 duo system of today to beat a strong human. That is probably safe bet. -- Aloril [EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On Tue, 2007-01-23 at 16:53 -0500, Don Dailey wrote: It's obvious that you can't program a 10 instruction per second computer to beat a human - so it's also clear that there would be some minimum level of hardware required. Let's not forget VLIW ( Very Long Instruction Word ) computers, or various parallel architectures such as the Connection Machine, which operated on 64K bits at once. The instruction cycle time of a human brain is somewhere around ten per second - but we do a surprising amount of sophisticated processing nonetheless. It helps to have 10^15 processors working in parallel. I could make a guess, but I certainly don't trust my intuition here. My guess is that God could program a core 2 duo system of today to beat a strong human. There are limits to what a core 2 duo can compute in a reasonable amount of time, no matter how sophisticated the program. So many instructions per second, so many bits of change, so much information gathered ... does this approach what a Meijin does with a large fraction of 10^15 neurons all working in tandem? Now that I think on it, with perfect knowledge, God could write a compact opening book to handle the fuseki, and an engine which would deal with the remainder of the game quite well. Trading data storage for processing power could stretch the abilities of the core duo quite a bit. Would it be enough? Of course, there's the approach used by some www commerce sites - the ask an authority subroutine. When the computer gets really stuck, it simply executes Prayer(board, What's the best move, God?) followed by Sacrifice(12*unblemished_lamb) or Rosary(50). Hans Moravec estimated that processing power equivalent to a human brain will be available around 2020 - probably at supercomputer prices. Ten or twenty years after that, it will be available to the average hobbyist. Building a Go program to take advantage of hundreds of thousands of processors and terabytes of RAM will be an interesting challenge. God himself would surely be able, but are we? We're striving for the computer equivalent of Kami no itte. TV dinner still cooling? Check out Tonight's Picks on Yahoo! TV. http://tv.yahoo.com/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
At the 3rd International Conference on Baduk there was a paper presented on fMRI images of the brains of expert and non-expert players analyzing Go problems. The conclusion of the research is that experts use far less of their brains than non-experts. The volume of the brain used by experts is quite small. Cheers, David On 24, Jan 2007, at 9:17 AM, terry mcintyre wrote: does this approach what a Meijin does with a large fraction of 10^15 neurons all working in tandem? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
Moravec estimates that the computer which beat a grandmaster was equivalent to 1/30 of the processing capacity of a human brain. So, let's call it 10^13 neurons -- a fraction of the brain, but still a very large amount of processing capability. - Original Message From: David Doshay [EMAIL PROTECTED] At the 3rd International Conference on Baduk there was a paper presented on fMRI images of the brains of expert and non-expert players analyzing Go problems. The conclusion of the research is that experts use far less of their brains than non-experts. The volume of the brain used by experts is quite small. On 24, Jan 2007, at 9:17 AM, terry mcintyre wrote: does this approach what a Meijin does with a large fraction of 10^15 neurons all working in tandem? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Finding fabulous fares is fun. Let Yahoo! FareChase search your favorite travel sites to find flight and hotel bargains. http://farechase.yahoo.com/promo-generic-14795097___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On Wed, 2007-01-24 at 09:17 -0800, terry mcintyre wrote: I could make a guess, but I certainly don't trust my intuition here. My guess is that God could program a core 2 duo system of today to beat a strong human. There are limits to what a core 2 duo can compute in a reasonable amount of time, no matter how sophisticated the program. So many instructions per second, so many bits of change, so much information gathered ... does this approach what a Meijin does with a large fraction of 10^15 neurons all working in tandem? I envision God using something perhaps like an extremely sophisticated neural net. It would be enhanced way beyond what we know - and there would be no training involved, it would just be hard coded with the right connection weights. However it's quite certain that this program would be advanced WAY beyond the software we are writing today. Of course I don't know if anything resembling a neural network would be used, but I use it as an example. It could have the ideal topology, the ideal weights, and a far more advanced design in general. I also believe, based on the design of the human brain, that it might have on the fly learning features. When humans study a position for a long time, we tend to get waves of understanding.I know I have done that with chess, where I think I understand the basics of a position but as I consider it I keep getting updates that make me understand it better. Another thing we do when playing a game is that we don't start fresh at every move. Most of what we know about the 40th move we learned from the first 39 moves - we just keep updating information as it's added and removed. There are many possibilities that an omniscient begin would know how to add to a program. I am fairly sure a perfect program would be impossible, even among the set of all possible programs that could find a move within let's say 60 seconds per move. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
So if we assume 10 Hz in the brain and 4GHz on silicon, we need to do 25000 neuron-equivalent operations per cycle on silicon. On 1/24/07, terry mcintyre [EMAIL PROTECTED] wrote: Moravec estimates that the computer which beat a grandmaster was equivalent to 1/30 of the processing capacity of a human brain. So, let's call it 10^13 neurons -- a fraction of the brain, but still a very large amount of processing capability. - Original Message From: David Doshay [EMAIL PROTECTED] At the 3rd International Conference on Baduk there was a paper presented on fMRI images of the brains of expert and non-expert players analyzing Go problems. The conclusion of the research is that experts use far less of their brains than non-experts. The volume of the brain used by experts is quite small. On 24, Jan 2007, at 9:17 AM, terry mcintyre wrote: does this approach what a Meijin does with a large fraction of 10^15 neurons all working in tandem? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ The fish are biting. Get more visitors on your site using Yahoo! Search Marketing. ___ 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 a computer beat a human?
Question: were the experts analyzing problems which were difficult at their level, or the same problems analyzed by non-experts? I suspect that expert players are able to obtain better results for the same problem with less effort than average players. To borrow from some now-ancient research done in cognitive psychology at CMU by Simon, it is probable that one develops cognitive chunks which permit higher-order processing at greater speeds. It would be interesting to see what percentage of the brain is used under tournament conditions by expert players, especially when they need to dig deep into their resources. - Original Message From: David Doshay [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, January 24, 2007 10:02:18 AM Subject: Re: [computer-go] Can a computer beat a human? At the 3rd International Conference on Baduk there was a paper presented on fMRI images of the brains of expert and non-expert players analyzing Go problems. The conclusion of the research is that experts use far less of their brains than non-experts. The volume of the brain used by experts is quite small. Cheers, David On 24, Jan 2007, at 9:17 AM, terry mcintyre wrote: does this approach what a Meijin does with a large fraction of 10^15 neurons all working in tandem? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ TV dinner still cooling? Check out Tonight's Picks on Yahoo! TV. http://tv.yahoo.com/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: I am fairly sure a perfect program would be impossible, even among the set of all possible programs that could find a move within let's say 60 seconds per move. Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. cheers stuart ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
I am thinking that God would use a much larger portion of the memory as code space. Hardcoding lots of the programming. Reason being, there would be no point in learning and go has so many special cases that it might be easier to do it this way (for a being that has lots of time to program that is). On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: On Wed, 2007-01-24 at 09:17 -0800, terry mcintyre wrote: I could make a guess, but I certainly don't trust my intuition here. My guess is that God could program a core 2 duo system of today to beat a strong human. There are limits to what a core 2 duo can compute in a reasonable amount of time, no matter how sophisticated the program. So many instructions per second, so many bits of change, so much information gathered ... does this approach what a Meijin does with a large fraction of 10^15 neurons all working in tandem? I envision God using something perhaps like an extremely sophisticated neural net. It would be enhanced way beyond what we know - and there would be no training involved, it would just be hard coded with the right connection weights. However it's quite certain that this program would be advanced WAY beyond the software we are writing today. Of course I don't know if anything resembling a neural network would be used, but I use it as an example. It could have the ideal topology, the ideal weights, and a far more advanced design in general. I also believe, based on the design of the human brain, that it might have on the fly learning features. When humans study a position for a long time, we tend to get waves of understanding.I know I have done that with chess, where I think I understand the basics of a position but as I consider it I keep getting updates that make me understand it better. Another thing we do when playing a game is that we don't start fresh at every move. Most of what we know about the 40th move we learned from the first 39 moves - we just keep updating information as it's added and removed. There are many possibilities that an omniscient begin would know how to add to a program. I am fairly sure a perfect program would be impossible, even among the set of all possible programs that could find a move within let's say 60 seconds per move. - 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 a computer beat a human?
According to the presenter, the problems covered a range of difficulty from purely random boards to easy problems to hard problems. All of the problems shown to the subjects were not given in the paper. The same set of problems were shown to all subjects. It would be difficult, but not impossible to conduct a tournament with the participants inside an MRI machine. MRI machine time is worth something like $2000 per hour, so cost would add up quickly. I agree, it would be very interesting to see if brain volume usage goes up at the same time the pro uses lots of time. Cheers, David On 24, Jan 2007, at 10:52 AM, terry mcintyre wrote: Question: were the experts analyzing problems which were difficult at their level, or the same problems analyzed by non-experts? I suspect that expert players are able to obtain better results for the same problem with less effort than average players. To borrow from some now-ancient research done in cognitive psychology at CMU by Simon, it is probable that one develops cognitive chunks which permit higher-order processing at greater speeds. It would be interesting to see what percentage of the brain is used under tournament conditions by expert players, especially when they need to dig deep into their resources. - Original Message From: David Doshay [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, January 24, 2007 10:02:18 AM Subject: Re: [computer-go] Can a computer beat a human? At the 3rd International Conference on Baduk there was a paper presented on fMRI images of the brains of expert and non-expert players analyzing Go problems. The conclusion of the research is that experts use far less of their brains than non-experts. The volume of the brain used by experts is quite small. Cheers, David On 24, Jan 2007, at 9:17 AM, terry mcintyre wrote: does this approach what a Meijin does with a large fraction of 10^15 neurons all working in tandem? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Don't pick lemons. See all the new 2007 cars at Yahoo! Autos. ___ 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 a computer beat a human?
In my original question I stated minimum resources. I agree with you that lots of memory could be highly useful: ... I would say a computer with perfect software, 32 GB of RAM (so a lot) and a 300 Mhz processor (slow processor) would be able to beat a human. (from my original post) So it sounds to me like most people think that if we had a perfect program, computers would be able to win. So at this point hardware will only allow us to get away with writing less perfect code. On 1/24/07, Stuart A. Yeates [EMAIL PROTECTED] wrote: On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: I am fairly sure a perfect program would be impossible, even among the set of all possible programs that could find a move within let's say 60 seconds per move. Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. cheers stuart ___ 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 a computer beat a human?
I feel that it takes a good combination of impressive hardware/software to play a really good game. Human brains are rather impressive in this regard, the hardware is more advanced than anything we have, but I'll bet the human brain is really far from being optimized for go. - Don On Wed, 2007-01-24 at 13:12 -0600, Nick Apperson wrote: In my original question I stated minimum resources. I agree with you that lots of memory could be highly useful: ... I would say a computer with perfect software, 32 GB of RAM (so a lot) and a 300 Mhz processor (slow processor) would be able to beat a human. (from my original post) So it sounds to me like most people think that if we had a perfect program, computers would be able to win. So at this point hardware will only allow us to get away with writing less perfect code. On 1/24/07, Stuart A. Yeates [EMAIL PROTECTED] wrote: On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: I am fairly sure a perfect program would be impossible, even among the set of all possible programs that could find a move within let's say 60 seconds per move. Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. cheers stuart ___ 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 a computer beat a human?
On 1/24/07, Nick Apperson [EMAIL PROTECTED] wrote: In my original question I stated minimum resources. I agree with you that lots of memory could be highly useful: ... I would say a computer with perfect software, 32 GB of RAM (so a lot) and a 300 Mhz processor (slow processor) would be able to beat a human. (from my original post) So it sounds to me like most people think that if we had a perfect program, computers would be able to win. So at this point hardware will only allow us to get away with writing less perfect code. On 1/24/07, Stuart A. Yeates [EMAIL PROTECTED] wrote: On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: I am fairly sure a perfect program would be impossible, even among the set of all possible programs that could find a move within let's say 60 seconds per move. Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. You are right. It's been a long thread and I'd forgotten that. sorry stuart ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
Le mercredi 24 janvier 2007 19:56, Stuart A. Yeates a écrit : Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. Cheers. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. it'd also be difficult (time consuming-wise) to *produce* all valid boards. :) s. Be a PS3 game guru. Get your game face on with the latest PS3 news and previews at Yahoo! Games. http://videogames.yahoo.com/platform?platform=120121 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
If god is building it, does it need to be in the universe? cheers stuart On 1/24/07, alain Baeckeroot [EMAIL PROTECTED] wrote: Le mercredi 24 janvier 2007 19:56, Stuart A. Yeates a écrit: Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. Cheers. Alain ___ 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 a computer beat a human?
Oh no you didn't! On 1/24/07, alain Baeckeroot [EMAIL PROTECTED] wrote: Le mercredi 24 janvier 2007 19:56, Stuart A. Yeates a écrit: Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. Cheers. Alain ___ 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 a computer beat a human?
Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. cheers stuart You're going to need more than 300MHz to do that lookup. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
To do a complete lookup you would need more than 32 GB of memory, but I think that the question was more about making programs smarter more than it was about unlimited hardware. Infact, my question was what is the minimum hardware. That said, 300 Mhz should be plenty to do a lookup. There are what 10^170 legal positions. That means that if you were able to generate an index so that there was exactly one index into your lookup table for each legal position. You would need about a 564-bit number (or higher if it proved too difficult to make a unique continuous indexing function). You would be able to perform that lookup with a 1KHz computer in a reasonable amount of time (under a second) assuming the processor had a way to address all that memory (I think even 512-bit processors are still a bit over the horizen however...) On 1/24/07, Chris Fant [EMAIL PROTECTED] wrote: Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. cheers stuart You're going to need more than 300MHz to do that lookup. ___ 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 a computer beat a human?
Nah, hash tables are amortized O(1). As long as you can address all that memory, 300MHz should be sufficient. On 1/24/07, Chris Fant [EMAIL PROTECTED] wrote: Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. cheers stuart You're going to need more than 300MHz to do that lookup. ___ 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 a computer beat a human?
You can if you use some sort of compression scheme...involving multiple values per quanta. I bet there's more than enough room...in the universe...probably just in your eyelash. - Original Message From: alain Baeckeroot [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, January 24, 2007 2:11:23 PM Subject: Re: [computer-go] Can a computer beat a human? Le mercredi 24 janvier 2007 19:56, Stuart A. Yeates a écrit : Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. Cheers. Alain ___ 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 a computer beat a human?
On Wed, 24 Jan 2007, terry mcintyre wrote: surprising amount of sophisticated processing nonetheless. It helps to have 10^15 processors working in parallel. it's more like 10^11 Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
actually, one more trip to Gateway Electronics (the local circuit parts store) and my lookup table will be complete... suckers! On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote: Le mercredi 24 janvier 2007 19:56, Stuart A. Yeates a écrit : Since no one has mentioned bounding memory, a complete lookup table (a complete table of correct moves, perfect-hashed by board state) should do the trick. With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. I'm glad you set us straight on that. - Don Cheers. Alain ___ 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 a computer beat a human?
On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote: With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. I think the computer science greats should have consulted you before writing their textbooks - I just looked at this crazy thing called a turing machine in one of my textbooks. A universal turing machine supposedly has an infinite tape attached to it. Maybe they are smart about computers, but they don't know anything about physics. I think all these textbooks need to be thrown out because they are obviously of no practical value. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
Turing Machines have an infinite tape -- I'm glad you set us straight on that. -Tom On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote: With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. I think the computer science greats should have consulted you before writing their textbooks - I just looked at this crazy thing called a turing machine in one of my textbooks. A universal turing machine supposedly has an infinite tape attached to it. Maybe they are smart about computers, but they don't know anything about physics. I think all these textbooks need to be thrown out because they are obviously of no practical value. - 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 a computer beat a human?
On Wed, 2007-01-24 at 15:38 -0800, Thomas Johnson wrote: Turing Machines have an infinite tape -- I'm glad you set us straight on that. -Tom No they don't. The universe is too small to contain an infinite tape. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
Sooo... Anybody write or optimize any cool computer Go algorithms lately? On 1/24/07, Thomas Johnson [EMAIL PROTECTED] wrote: Turing Machines have an infinite tape -- I'm glad you set us straight on that. -Tom On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote: With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. I think the computer science greats should have consulted you before writing their textbooks - I just looked at this crazy thing called a turing machine in one of my textbooks. A universal turing machine supposedly has an infinite tape attached to it. Maybe they are smart about computers, but they don't know anything about physics. I think all these textbooks need to be thrown out because they are obviously of no practical value. - 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On Wed, 2007-01-24 at 18:48 -0500, Chris Fant wrote: Sooo... Anybody write or optimize any cool computer Go algorithms lately? Hey, aren't you the guy that thinks you can put a look-up table for 19x19 go on a computer?You're really dumb to think that. :-) - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On Wed, 2007-01-24 at 18:48 -0500, Chris Fant wrote: Sooo... Anybody write or optimize any cool computer Go algorithms lately? Actually, I'm working on a data compression scheme that will allow you to build a 19x19 full game look-up table and store it on an SD card. I have already figured out how to store the data so it fits but I want to keep it secret for now. It turns out that you have to build the complete database first before you can compress it so I have to use a universal turning machine since it has an infinite tape. - Don On 1/24/07, Thomas Johnson [EMAIL PROTECTED] wrote: Turing Machines have an infinite tape -- I'm glad you set us straight on that. -Tom On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote: With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. I think the computer science greats should have consulted you before writing their textbooks - I just looked at this crazy thing called a turing machine in one of my textbooks. A universal turing machine supposedly has an infinite tape attached to it. Maybe they are smart about computers, but they don't know anything about physics. I think all these textbooks need to be thrown out because they are obviously of no practical value. - 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/ ___ 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 a computer beat a human?
AFAIK this is not a philosophical list about god power, although (sadly) it is rapidly becoming one. 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 a computer beat a human?
On Thu, 2007-01-25 at 01:27 +0100, alain Baeckeroot wrote: Le mercredi 24 janvier 2007 22:34, Don Dailey a écrit : On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote: With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. I think the computer science greats should have consulted you before writing their textbooks Hmm didn't you notice the question mark ? I thought this list was to exchange ideas and point of vue. My remark is not so stupid that i have to endure your irony. It wasn't stupid, it was just too obvious and didn't have anything to do with our discussion which clearly WAS theoretical only. AFAIK this is not a philosophical list about god power, so considering physical limits is not out of topic. Imho go programming is difficult and thus an interesting problem _because of_ these physical limitation due to the world we live in. But Chris started the statement you responded to like this: Since no one has mentioned bounding memory, ... So his reply was based on the assumption that he could specify memory without limit. The physical limitations of computing is an interesting topic in it's own right, but that's a different discussion. When you are discussing the theoretical aspects of computer algorithms, such as turing machines and such, physics usually has no place in the discussion.Since we really don't know how big the universe is, or how long it will last, it's hard to use it anyway to prove or disprove anything.I assume that's why you referred to the visible universe, instead of the universe. - Don Regards. Alain - I just looked at this crazy thing called a turing machine in one of my textbooks. A universal turing machine supposedly has an infinite tape attached to it. Maybe they are smart about computers, but they don't know anything about physics. I think all these textbooks need to be thrown out because they are obviously of no practical value. - 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 a computer beat a human?
Le mercredi 24 janvier 2007 23:06, Jim O'Flaherty, Jr. a écrit : You can if you use some sort of compression scheme...involving multiple values per quanta. I bet there's more than enough room...in the universe...probably just in your eyelash. True i forgot about fantastic quantum-computer, which so far solved only very specific and tiny problems or quantum mechanics. Normal quantum computer need more than 564 qubit to store the 10^170 pos, Maybe one can do better for go with a 361 qubit computer wich behave with go rules :) This need some serious amount of research ... Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On 1/24/07, alain Baeckeroot [EMAIL PROTECTED] wrote: True i forgot about fantastic quantum-computer, which so far solved only very specific and tiny problems or quantum mechanics. In the spirit of this, lets bring the quantum computer built at U of Illinois that computers its answer without actually running.. By placing our photon in a quantum superposition of running and not running the search algorithm, we obtained information about the answer even when the photon did not run the search algorithm, said graduate student Onur Hosten, lead author of the Nature paper. We also showed theoretically how to obtain the answer without ever running the algorithm, by using a 'chained Zeno' effect. http://www.news.uiuc.edu/news/06/0222quantum.html That should take care of any objection like the universe would end before the computer finished searching the entire game-tree. ;) Lars Nilsson ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On Wed, 2007-01-24 at 16:31 -0800, steve uurtamo wrote: AFAIK this is not a philosophical list about god power, although (sadly) it is rapidly becoming one. If you want to leave God out of it, we can use a different metaphor - how about what is possible with a computer that has infinite memory and infinite speed? I have often day-dreamed about owning such a computer and what I could do with it. Such a computer could easily be used to build a very good program that would run on the computer you have at home today, just try all possible programs (up to some size and up to some total cpu cycles) and test each one. First test that your programs play legal moves in all positions, then test for strength (perhaps will a massive elimination tournament, the program that can survive a billion rounds is probably fairly strong.) - Don 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Best computer go development library?
At 02:52 PM 1/23/2007, you wrote: ... I'm interested in doing some experiments in developing a computer go algorithm. ... I'll probably be writing in C++ on Linux or C# on Windows, depending on the software available for each. take a look at http://www.lclark.edu/~drake/go/ it was in java, he tried c++ and went back. so you have some good examples of stuff there in java and c++. 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] Can a computer beat a human?
On a slightly (but not much) more serious note: The proposal that elicited (for better or for worse) Alain's size-of-the-universe comment was not for a complete table of all possible board states, but rather a table of winning moves. I expect that most positions will have multiple winning moves, but only a single one would need to be stored. The table does not need to store anything for a position that cannot be reached by playing those selected moves. I believe that this greatly reduces the size needed. I certainly don't know how much smaller, although someone may be able to come up with actual numbers for 5x5 and 7x7 games, and use an educated guess on how these will scale up to 19x19. My offhand guess is that this size is still _far_ greater than the meagre memory resources that were suggested in the original post. For what it is worth, I expect that it is also larger than the number of quantum states of one of Alain's eyelashes. I would guess that it is smaller, however, than 10^100 bits, which I believe is a common back-of-the-envelope number for the total information in the visible universe. One also has the freedom to pick and choose which winning moves to store. This can be used to maximize the overlap between the different stored variations. If you also take advantage of patterns within the table, you will certainly be able to compress it. (As has been mentioned already.) At the far extreme, of course, you only need one entry in the table for each of 282 possible moves, and a hash function that simply ... er, figures out which move to play. Or, one can strike a balance between these two extremes that gives an appropriate tradeoff between computation time and memory. I would guess that kami no itte would still be impossible on 32GB, 300Mhz. However, beating a professional dan player seems reasonable to me. Of course, Alain will still have a large enough lookup table that he will be able to beat it ... in the blink of an eye. Weston On 1/24/07, Don Dailey [EMAIL PROTECTED] wrote: On Wed, 2007-01-24 at 21:11 +0100, alain Baeckeroot wrote: With 10^170 legal position for 19x19 what would be the size of this table ? I m afraid we cannot build it with all the matter in visible universe. I think the computer science greats should have consulted you before writing their textbooks - I just looked at this crazy thing called a turing machine in one of my textbooks. A universal turing machine supposedly has an infinite tape attached to it. Maybe they are smart about computers, but they don't know anything about physics. I think all these textbooks need to be thrown out because they are obviously of no practical value. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
Le jeudi 25 janvier 2007 02:16, Lars Nilsson a écrit : On 1/24/07, alain Baeckeroot [EMAIL PROTECTED] wrote: True i forgot about fantastic quantum-computer, which so far solved only very specific and tiny problems or quantum mechanics. In the spirit of this, lets bring the quantum computer built at U of Illinois that computers its answer without actually running.. By placing our photon in a quantum superposition of running and not running the search algorithm, we obtained information about the answer even when the photon did not run the search algorithm, said graduate student Onur Hosten, lead author of the Nature paper. We also showed theoretically how to obtain the answer without ever running the algorithm, by using a 'chained Zeno' effect. http://www.news.uiuc.edu/news/06/0222quantum.html That should take care of any objection like the universe would end before the computer finished searching the entire game-tree. ;) Lars Nilsson Last paragraph begin by this sentence: While the researchers’ optical quantum computer cannot be scaled up,... and Kwiat’s team succeeded in counterfactually searching a four-element database using Grover’s quantum search algorithm. Grover's algorithm is O(N^1/2) instead of O(N) wich might not be enought for go. http://en.wikipedia.org/wiki/Grover%27s_algorithm Utilizing two coupled optical interferometers, nested within a third, I m afraid using 3 interferometer to search a 4 bit data base is slightly inefficient and costly :) If this could scale, it would need more than 500 interferometers to build a go-enabled machine. (or 500*501/2 ?) This is thermodynamical principe, you need an inifinetly big machine to do something infinitely small. This is already true for current computers, Moore law also describe the resources needed for building new more powerful computers (money, plants, complexity of the whole stuff ...) ,not doubling each 18 month , but regurlarly increasing, to such a point that financial or material resource can become the limiting factor soon. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
Le jeudi 25 janvier 2007 02:16, Lars Nilsson a écrit : In the spirit of this, lets bring the quantum computer built at U of Illinois that computers its answer without actually running.. By placing our photon in a quantum superposition of running and not running the search algorithm, we obtained information about the answer even when the photon did not run the search algorithm, said graduate student Onur Hosten, lead author of the Nature paper. We also showed theoretically how to obtain the answer without ever running the algorithm, by using a 'chained Zeno' effect. http://www.news.uiuc.edu/news/06/0222quantum.html That should take care of any objection like the universe would end before the computer finished searching the entire game-tree. ;) They implemented Zenbot :) http://senseis.xmp.net/?ComputerGoServer#toc69 Alain. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On 1/24/07, Weston Markham [EMAIL PROTECTED] wrote: 282 possible moves Um. Dunno where I got that number from. (I meant 362, I think.) Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Ray Tayek wrote: ... I can say that I don't feel overwhelmed when playing chess. ... Now with Go as a beginner still, on the other hand, I almost always felt and still feel quite overwhelmed ... yes, i usually feel this way in tournament games. and again more time will help (for some small powers of 2). I'm glad I'm not the only one that feels this way ;-) i think more time works better because go has more battles going on at the same time. Which also makes it harder when there is interplay between them. if you are analyzing one battle, maybe more powers of two. if it's many battles, maybe fewer powers of two as you will hit your mental limit sooner. This seems to support the idea I was trying to express... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/