Re: [computer-go] Re: libgoboard v0.97 released
On 1/22/07, David Doshay [EMAIL PROTECTED] wrote: Randomization of seed may not be a good idea. For some experiments it is better to know the starting seed and keep it the same, for others, like play against humans, randomization is probably preferable. I would suggest having a runtime flag that can be set either way. Cheers, David You are right, I will do something like that in next release. Thanks Lukasz On 22, Jan 2007, at 2:01 PM, Łukasz Lew wrote: On Cygwin, the results are ok and always the same. I will add randomization of seed. ___ 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] Go Board Library v0.98
Thanks. This is fixed in v 0.98 Łukasz On 1/23/07, terry mcintyre [EMAIL PROTECTED] wrote: I was able to reproduce the problem with the odd White Wins value. Turns out that win_cnt was not initialized in playout_benchmark. Adding an explicit initialization fixed that problem. My c++ is extremely rusty, so I used win_cnt[0]=0; win_cnt[1]=0; There is probably a c++ specific idiom which I am unaware of. Terry McIntyre - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, January 23, 2007 8:17:40 AM Subject: [computer-go] Go Board Library v0.98 I will annoy You once again, because: I added a mercy rule to the simple playout, and it turned out that it is *faster* that my previous mega-optimised playout. In current release old playout_t is gone, we have only simple_playout::run. Some beautification, and helpful macros. Also whole package is much more user friendly (README, automagic.gtp). http://duch.mimuw.edu.pl/~lew/download.php?file_no=9 Best Regards, Łukasz Lew ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ No need to miss a message. Get email on-the-go with Yahoo! Mail for Mobile. Get started. ___ 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] Fast Board implementation
Here is another MC speedup trick. I think it may have been mentioned before but it's worth repeating. This applies to the case where my program is going to run N playout games and then select the most visited node as its move for that turn (which will not always be the node with the highest percentage of wins). It is rarely necessary to run all N playout games. After more than half of the playout games have been completed, some moves may become mathematically eliminated because they have been visited too few times for them to be able to catch up to the leader. So, at regular intervals thereafter, I can perform a popularity pruning operation at the root. If there are M playout games to go, and a move at the root would need more than M more visits to catch up with the most popular (visited) move, then any further playout games through that move would be wasted. I might as well prune it now. When all but one move at the root has been pruned away, no further playout games are needed for this turn. Popularity pruning averages to about a 20% speedup free and clear. Of course, one can prune a move at the root a little earlier, or prune moves beyond the root, but then you have moved into a different regime. - Dave Hillis antminder on KGS Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ 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
- Oorspronkelijk bericht - Van: Matt Gokey [EMAIL PROTECTED] Datum: maandag, januari 22, 2007 9:59 pm Onderwerp: Re: [computer-go] an idea... computer go program's rank vs time Nick Apperson wrote: He is saying this (I think): to read m moves deep with a branching factor of b you need to look at p positions, where p is given by the following formula: p = b^m (actually slightly different, but this formula is close enough) which is: log(p) = m log(b) m = log(p) / log(b) We assume that a doubling in time should double the number of positions we can look at, so: m(with doubled time) = log(2p) / log(b) m(with doubled time) = log(2) * log(p) / log(b) Your math is wrong (I think). The correct equivalency for the last line would be: m(with doubled time) = (log(2) + log(p)) / log(b) Yes. Don's scalability argument states that ELO gain is proportional to time doubling. For me scalable use of time implies that time translates into depth. The extra depth is: m - m0 = log(2)/log(b). So if the ELO gain for time doubling in Chess equals 100 over a wide time scale and if Go has a 10 times larger branching factor than Chess, then the ELO gain for time doubling in Go would equal 100/log (10) = 43 (everything else assumed equal). I'm not sure i agree with Don, but i just want so say that if he is right, than mathematically he is also right with a larger branching factor. Dave ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] position
About 2 months ago I sent a note to this email list about a research chair position and a postdoc position, both financed through the SHACRNET High Perfomance Consortium. The advert below does not have high performance computing as a requisite attached. But because it mentions discrete math, combinatorics and experience in computation as valuable strengths, this might be of interest to someone on the email list. Together with a few students we already have a small but active computer Go group at our math department. Thomas Wolf Prof at Department of Mathematics Brock University Ontario, Canada --- BROCK UNIVERSITY FACULTY OF MATHEMATICS AND SCIENCES MATHEMATICS The Department of Mathematics invites applications for a tenure-track appointment in an area of discrete and computational mathematics at the rank of Assistant Professor starting July 1, 2007. The Department offers an MSc in Mathematics and Statistics, has an innovative and unique B.Sc. Mathematics program called MICA (Mathematics Integrated with Computers and Applications) and plays a leading role in Mathematics Education. The successful candidate must have a PhD in Mathematics or related field by the time of the appointment, a proven record of or potential for research excellence, and an active research program that will attract external funding. Ideally, the candidate’s area of research would complement that of current faculty. The position requires undergraduate teaching including Combinatorics and Mathematics for Computer Science, graduate teaching, and supervision of graduate students. The successful candidate must demonstrate strong teaching abilities and a committed interest in the use of technology for the exploration, understanding and applications of mathematics. The appointment is subject to the availability of funds. The review of applications will start on February 28, 2007 and will continue until the position is filled. Applicants should send a curriculum vitae, an outline of their research plan and a description of teaching philosophies, and arrange for at least three letters of reference (one of which should address teaching) to be sent directly to: Chair of the Mathematics Search Committee Department of Mathematics Brock University St. Catharines, Ontario L2S 3A1, Canada E-mail: [EMAIL PROTECTED] In accordance with Canadian Immigration requirements, priority will be given to citizens and permanent residents of Canada. Brock University encourages applications from all qualified individuals including women, members of minorities, native people, and persons with disabilities. ___ 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
you are right about my math being wrong. I wasn't paying that much attention to that step, but with the correct math (as was pointed out) you end up with a linear equation assuming what I said to assume. Man, its only been a couple years and my precalc skills have gone to crap... Thanks for the correction. And Dave, you said what I was trying to say, except better. The only thing I have to add is that one major difference between humans and computers is that brains are able to think in parallel much more effeciently. For a game such as go, we are able to use that ability more because of the larger branching factor. On 1/23/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: - Oorspronkelijk bericht - Van: Matt Gokey [EMAIL PROTECTED] Datum: maandag, januari 22, 2007 9:59 pm Onderwerp: Re: [computer-go] an idea... computer go program's rank vs time Nick Apperson wrote: He is saying this (I think): to read m moves deep with a branching factor of b you need to look at p positions, where p is given by the following formula: p = b^m (actually slightly different, but this formula is close enough) which is: log(p) = m log(b) m = log(p) / log(b) We assume that a doubling in time should double the number of positions we can look at, so: m(with doubled time) = log(2p) / log(b) m(with doubled time) = log(2) * log(p) / log(b) Your math is wrong (I think). The correct equivalency for the last line would be: m(with doubled time) = (log(2) + log(p)) / log(b) Yes. Don's scalability argument states that ELO gain is proportional to time doubling. For me scalable use of time implies that time translates into depth. The extra depth is: m - m0 = log(2)/log(b). So if the ELO gain for time doubling in Chess equals 100 over a wide time scale and if Go has a 10 times larger branching factor than Chess, then the ELO gain for time doubling in Go would equal 100/log (10) = 43 (everything else assumed equal). I'm not sure i agree with Don, but i just want so say that if he is right, than mathematically he is also right with a larger branching factor. Dave ___ 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] Re: libgoboard v0.97 released
On Mon, Jan 22, 2007 at 06:48:34PM +0100, ?ukasz Lew wrote: Few interesting things has happened so I decided to announce new version: Hi, I just downloaded it and had a quick look. I am running on a Debian/etch system, dual-core AMD-64. Make finished fine, and the program seems to run. engine_opt without arguments displays an empty 9x9 board and Performance: 20 playouts 6.25239 seconds 31.9878 kpps Black wins = 3086277172 White wins = 3221005275 P(black win) = 1.53369 So far so good. When I try to load one of the example positions, I get exactly the same numbers. When I try to add a few more stones to get a totally unbalanced position, I still get Initial board: komi 7 A B C D E F G H J 9 . . . . . . . . . 9 8 . . # . . . . . . 8 7 . # O . . . # . . 7 6 . # . # . # . . . 6 5 . . . . . # . O . 5 4 . . . . . # O . O 4 3 . # . . . # # O . 3 2 . . . . # . # O . 2 1 . . . . . # . . . 1 A B C D E F G H J Performance: 10 playouts 2.68816 seconds 37.2001 kpps Black wins = 3085887684 White wins = 3220998203 P(black win) = 1.5338 Obviously I am doing something wrong here, but what? - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
The answer is yes. Many computer programs (including my own) can beat me easily on today's hardware and I am, indeed, a human. Glad I could clear that up for you. ;-) - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tue, 23 Jan 2007 4:22 PM Subject: [computer-go] Can a computer beat a human? This is something I have been wrestling with. It is kind of a theoretical question. Assuming a program that utilizes all avaliable resources perfectly. It plays the best game you could ever program it to play. How fast would the computer have to be to beat a human? I could see people argue that if the program had enough knowledge it could be a pretty slow computer (less than 100 Mhz), I could also see someone state the reality that our brains (when you sum up the computational power of an entire thinking brain) have way more processing power than a cluster of high performance workstations and so technology isn't able to provide computer hardware that would be fast enough. I think I vastly underestimate the human brain, but 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. Thoughts? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ 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?
My 500mhz computer beats me fairly easy ;) with Gnugo so depends on the person you're comparing. -Josh On 1/23/07, Nick Apperson [EMAIL PROTECTED] wrote: This is something I have been wrestling with. It is kind of a theoretical question. Assuming a program that utilizes all avaliable resources perfectly. It plays the best game you could ever program it to play. How fast would the computer have to be to beat a human? I could see people argue that if the program had enough knowledge it could be a pretty slow computer (less than 100 Mhz), I could also see someone state the reality that our brains (when you sum up the computational power of an entire thinking brain) have way more processing power than a cluster of high performance workstations and so technology isn't able to provide computer hardware that would be fast enough. I think I vastly underestimate the human brain, but 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. Thoughts? ___ 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] an idea... computer go program's rank vs time
On Tue, 2007-01-23 at 21:08 +0100, [EMAIL PROTECTED] wrote: Yes. Don's scalability argument states that ELO gain is proportional to time doubling. For me scalable use of time implies that time translates into depth. The extra depth is: m - m0 = log(2)/log(b). So if the ELO gain for time doubling in Chess equals 100 over a wide time scale and if Go has a 10 times larger branching factor than Chess, then the ELO gain for time doubling in Go would equal 100/log (10) = 43 (everything else assumed equal). I'm not sure i agree with Don, but i just want so say that if he is right, than mathematically he is also right with a larger branching factor. It's trivial to prove programs are infinitely scalable. It's a bit more difficult to prove humans are - but I think it's probably a similar proof. I believe a scalable program can be highly scalable or less scalable meaning they improve less or more with time. Humans appear to be of the highly scalable variety, at least in chess they improve with time faster than computers do. A chess program playing at 3 minutes per move is about 300 ELO stronger than the same program playing at 5 seconds per move. A human is more like 400-500 ELO stronger. There is strong evidence that in chess this doubling tapers off at strong levels. This makes a great deal of sense. Ernst Heinz did some experiments that proved empirically (with high statistical confidence) that strength tapers off with search depth in computers. Although he measured this using search depth, I believe the tapering is more related to strength. It just happens that the deeper searching programs were playing stronger. If someone could construct a computer that played just as well with half the search depth, I think the tapering would be approximately consistent with the deep searching program of similar levels. The tapering is very gradual and even at high ply depths the ELO improvement for a doubling is quite good. That's why I believe in GO it will be hard to see this tapering effect. I believe GO players are farther from the ultimate top that chess players (I mean the very best players.) Once you are playing almost perfectly, you won't get quite as much from the extra thinking time. I did an experiment long ago with a checkers-like game I made up. It is simple checkers on a 6x6 board and only 1 jump allowed. It's possible to construct an enormously deep searching program with this little mini-game.I also found that the really super deep levels taper off, and yet it is gradual and you never seem to stop benefiting measurably from each additional ply of search. The program searches deep enough that it's easily to imagine that it can't make errors, but obviously one side is making errors. The worlds best checkers program are like this too. They go much deeper than in chess and they are quite amazing how deeply they search. I think they are way beyond human strength now, but they still lose games to each other and make mistakes that 1 more ply of search would solve. That's really the point - 1 extra ply always solves a thick layer of problems that you couldn't solve before. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: libgoboard v0.97 released
On Tue, Jan 23, 2007 at 10:35:08PM +0100, Heikki Levanto wrote: I just downloaded it and had a quick look. Perfect timing - while I was writing my mail, you released 0.98 That works much more better. Now I get something like playout_benchmark 100 = Initial board: komi 7 A B C D E F G H J 9 . . . . . . . . . 9 8 . . . . . . . . . 8 7 . # O # . . . . . 7 6 . . # # . . . . . 6 5 . . . . . # . O . 5 4 . . . . . # O . O 4 3 . . # . . # # O . 3 2 . . . . # . # O . 2 1 . . . . . # . . . 1 A B C D E F G H J Performance: 100 playouts 13.3568 seconds 74.868 kpps Black wins = 890260 White wins = 109740 P(black win) = 0.89026 Much more reasonable number of wins for both players, P in range, and seems to correlate with the the position. Problem solved. Now I just need the time to play with it all... - Heikki P.S. and better n umbers too, once I got my cpufreq scaling to give me full cpu speed when needed... -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can a computer beat a human?
On Tue, 2007-01-23 at 15:22 -0600, Nick Apperson wrote: This is something I have been wrestling with. It is kind of a theoretical question. Assuming a program that utilizes all avaliable resources perfectly. It plays the best game you could ever program it to play. How fast would the computer have to be to beat a human? I could see people argue that if the program had enough knowledge it could be a pretty slow computer (less than 100 Mhz), I could also see someone state the reality that our brains (when you sum up the computational power of an entire thinking brain) have way more processing power than a cluster of high performance workstations and so technology isn't able to provide computer hardware that would be fast enough. I think I vastly underestimate the human brain, but 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. Thoughts? Excellent question. So you really mean, if God would program a computer to be as strong as possible would it beat humans at human-like time-controls? 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. 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. - 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] Best computer go development library?
Hi folks, I'm interested in doing some experiments in developing a computer go algorithm. I definitely don't want to rewrite any of the basic stuff (board management, scoring, etc) if it's already available somewhere. What's the best library available (if any) for doing this kind of thing? If it makes a difference, I'll probably be writing in C++ on Linux or C# on Windows, depending on the software available for each. Thanks Tom ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea for a new measure of a computer go program's rank.
Personally, I use the terminology in much the same way as Heikki. I use the word mistake to describe (for example) a move that loses a large group, but does not change the game from a win to a loss. It makes sense to me to generally apply mistake to any move that loses points relative to the best move on the board. The term blunder means, essentially, a move that lost the game. It can be quite difficult, of course, to determine unambiguously whether or not a particular move is a blunder. In an otherwise close match, a large mistake (i.e., loses many points) is probably a blunder. Toward the end of a close game, it may be possible to find unambiguous blunders, and some of these could be single point mistakes. Weston On 1/23/07, Heikki Levanto [EMAIL PROTECTED] wrote: On Sun, Jan 21, 2007 at 08:16:07PM -0800, Ray Tayek wrote: I don't know the percentage of blunders. It also depends on what you call a blunder. Is a 1 point mistake a blunder? no, maybe 10 or more points My gut feeling is that a real blunder is enough to loose the game. Between equally strong players, a one point mistake can be a blunder, if it was late in the yose, and the game was won by half a point. On the other hand, throwing away a 20-stone group may not be a blunder if you were already going to loose by 100 points. It could even be a (mis?)calculated risk, ignoring a threatening move in order to get an attack on an even larger group, even if that attack later turns out not to work... Just my uninformed gut feeling, of course. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ 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 strongly believe it's not hardware but software (ie. when we will develop a strong enough algorithm) issue. - gg Nick Apperson: [EMAIL PROTECTED]: Let me clear one thing up... I mean, a professional go player. A rough approximation of what the human brain is capable of when it is optimized for go compared with a computer that has its software optimized (not limited by programming ability and programmer time) for go. On 1/23/07, Joshua Shriver [EMAIL PROTECTED] wrote: My 500mhz computer beats me fairly easy ;) with Gnugo so depends on the person you're comparing. -Josh On 1/23/07, Nick Apperson [EMAIL PROTECTED] wrote: This is something I have been wrestling with. It is kind of a theoretical question. Assuming a program that utilizes all avaliable resources perfectly. It plays the best game you could ever program it to play. How fast would the computer have to be to beat a human? I could see people argue that if the program had enough knowledge it could be a pretty slow computer (less than 100 Mhz), I could also see someone state the reality that our brains (when you sum up the computational power of an entire thinking brain) have way more processing power than a cluster of high performance workstations and so technology isn't able to provide computer hardware that would be fast enough. I think I vastly underestimate the human brain, but 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. Thoughts? ___ 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/ inline file ___ 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 a computer beat a human?
At 01:22 PM 1/23/2007, you wrote: ... It plays the best game you could ever program it to play. How fast would the computer have to be to beat a human? ... but 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. the programs seem to be about 10-kyu (based on my observations of slugo and smart go at the cotsen open and manyfaces on my pc). 32gb/300 mhz is probably about 3gb/3ghz. so they can beat some 11-kyu humans. my suspicion is that the programs could play a few (4?) stones stronger with better heuristics and less brute force (except in the end game). 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?
At 01:51 PM 1/23/2007, you wrote: Let me clear one thing up... I mean, a professional go player. ... this would be equivalent to somewhere between 7-10 dan amateur. at least decades. probably much longer. (at least without quantum stuff). 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?
At the Cotsen Open 1.5 years ago SlugGo beat an 8k, and lost on time to his 8k brother, but the board position was a win by more than 100 points for SlugGo. But I agree that 10k is about right; SlugGo also lost to a few 12k players. I also agree that picking up 4 stones seems within reach, even though I have not quite pulled that off ... yet. To beat any pro player is going to take a breakthrough and probably a new method. It is just a little early to tell if MC is that method, but it seems to scale well, so it may be. If the required new method is not MC, then it is impossible to know when that breakthrough will happen, because by its nature, it is not going to simply evolve out of what we are doing now, but requires some new insight. Cheers, David On 23, Jan 2007, at 10:17 PM, Ray Tayek wrote: the programs seem to be about 10-kyu (based on my observations of slugo and smart go at the cotsen open and manyfaces on my pc). 32gb/ 300 mhz is probably about 3gb/3ghz. so they can beat some 11-kyu humans. my suspicion is that the programs could play a few (4?) stones stronger with better heuristics and less brute force (except in the end game). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
