Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
No wonder it plays so well at 9x9, because the max length of playout is only 81, it can 'see' what the board look like when the game ends. The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. On a 2.2Ghz Athlon64, I get about 10 000 playouts/second, at an average of 100 moves per game this is 1 million updates/second. There are many programs that are much faster. On the same hardware libego would be about 6 million updates/second. 19 x 19 is a bit slower, because strings are bigger on average. This also explains that when I read the games MoGo against GNUGo, toward the end of the game, GNUGo would play PASS, but MoGo would continue to play at some very uncommon positions that a normal player would never consider. Pass behaviour has little to do with the playouts themselves. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Playing randomly like that shouldn't work, but when you play Mogo et al, you see that intelligent behaviour emerges. Although interesting, I would hardly call that 'intelligence' :-) Ah, the traditional flamewar topic: the definition of intelligence shifts whenever a computer achieves what was formerly considered intelligence. And I suspect how far it can achieve on 19x19 board (compare to human players of course). Perfect play, no need to suspect anything. The real question is how far humans are away from that :-) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. Hmm, sorry if this is old subject but does it effect much for playout quality if I cut playouts for example max 110 moves in 9*9 board? Is that studied subject for almost random playouts. Another thing, do you include random moves for playouts, after some number of playouts or when there is K number empty points or using some other way. By the wat made java board for random playouts it is currently 30 games /13sec 9*9 board having max 110 moves(double core 4000+), I have no lightest clue how to make it faster as optimized it as much i can, using two threads it is 7 seconds/30 games. Have think that maybe somekind of state machine could be faster. t. Harri On a 2.2Ghz Athlon64, I get about 10 000 playouts/second, at an average of 100 moves per game this is 1 million updates/second. There are many programs that are much faster. On the same hardware libego would be about 6 million updates/second. 19 x 19 is a bit slower, because strings are bigger on average. This also explains that when I read the games MoGo against GNUGo, toward the end of the game, GNUGo would play PASS, but MoGo would continue to play at some very uncommon positions that a normal player would never consider. Pass behaviour has little to do with the playouts themselves. -- GCP ___ 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] On average how many board updates/sec can top Go programs do these days?
mingwu wrote: Hi, I read on the web, and some other places that most Go programs can only evaluate "a dozen" of moves per second. Is this still true today on a typical machine, say, single 2GHz CPU, 2GB memory? This is highly dependent on the program. You can evaluate fast if you don't care about the quality of the evaluation and don't mind having a crummy program. There is a general feeling that GO requires much smarter evaluation than what we have now and many are working on improving that. Of course this implies that current evaluation is much slower than it should be because strength and speed are highly correlated. I don't really understand what a dozen evaluations per second really means. I think MFGO does a shallow global search but at end nodes calls a special evaluation function that is relatively slow. However, this evaluation function has a search component inside of it - routines that check for life and death by doing ladder searches and such. All programs do a global search with some kind of static evaluation at end nodes. It is customary in computer go not to call it "global search" if the program just does a fixed 1 ply search. Perhaps the feeling is that if you don't actually call the evaluation function recursively it's not a search, but whatever the case it is just semantics. There are many who believe a 1 ply fixed depth search is the only number that works (which is nonsense.) Nevertheless, even the older classic programs do at least a 1 ply search. They call the search "selective" if you only consider a subset of the moves. However, even the subset not "considered" is evaluated in some sense to determine that it should not be considered! It is just evaluated less thoroughly, perhaps being quickly rejected by a simple pattern lookup or some other system. And if this is still true, how can we make it faster? There is such a think called a "static evaluation function", which is a non-recursive version of an evaluation function. Most programs give their evaluation function a name like "search()" or evaluate() or something similar. A recursive evaluation function tries to evaluate positions by moving pieces around on the board to see what happens - more like what humans do. Since recursive functions must have a termination condition, at some point you must stop and the general method is via a "static evaluation function", a routine that evaluates the position without moving pieces around. Having said that, it's true that many programs still move pieces around by further calling goal specific routines designed to discover something about the position via a goal specific search, such as determining if a specific group will live or die. To answer your question about how to make it faster, I think the answer is to find ways to replace the recursive components with static components. This falls into many categories: Routines that discover life and death statically. Routines that are effective at identifying moves not worthy of consideration. Any static or fast routine that can discover something useful about the position without having to recurse. Of course general optimizations will help, but cannot replace gains in the above areas. Same with faster computers. At some point we all have to stop thinking of evaluation and search as two different things. This in my opinion is the biggest stumbling block in our way. You can find heated arguments going back 30 years or more on the subject of search vs evaluation showing how most people have partitioned these two things into separate unrelated concepts. In some ways, computer go is ahead of chess in this regard. Chess programmers think the two things are different but many good go programs use local searches to discover things about the position - nicely and properly blurring the distinction between the two. You can look at ANY good game playing program and easily see that it's all about doing as much useful work as you can, in as little time as possible. Probably the biggest source of misconceptions are articles you can find on the web that claim search is out of the question for computer go. These well-meaning articles are misleading and imply that searching 1 ply with an incredible static evaluation function is the "one true way." They generally make the all or nothing assumption that you either don't use search at all, or you must design a program with a brain-dead but super-fast static evaluation function and then try to search 100 full-width ply deep to make up for this. So these articles have kept computer go in the dark ages longer than necessary and are written in an incredibly naive style showing a lack of understanding of the general principles of how to evaluate a position. Of course you can now see strong programs based on using the search component much more heavily in the evaluation process. Aya is one example for instance, which is based on alpha/beta searching (they now have a monte
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
I'm sure many of us are surprised how well this stuff works. I'm not surprised because I knew a little about the principle 10 years ago. I create a game based on English/British checkers but played on a 6x6 board and a slightly different jump rule (you can only jump one piece in a move.) It was just for testing idea on searching and I wanted to keep it simple. I discovered that a monte/carlo based evaluation function is superior compared to a simple hand crafted one. It was better even at the same time control. This game was small enough that I could search incredibly deep and discover diminishing returns (which must happen in all games but happens much more gradually than intuition would suggest.) I tried a naive version of this with GO and discovered that it could easily beat my alpha/beta searcher which had a naive static evaluation function (because I had just learned the rules and didn't understand the strategy whatsoever.) But it was still very weak and I temporarily lost interest in it. Then I saw a paper on the web about gobble, a go program that evolved a move list ordering using simulated annealing. My interest was rekindled, I continued to tinker and eventually produced some simple MC based programs which were predecessors of AnchorMan. During this period other papers started to appear which I followed closely and now it's a common technique. Searching randomly is probably the quickest way to get an overview of the landscape. It's not very methodical, but methodical methods are much slower at quickly discovering the big picture. I'm thinking that the next big leap in computer go will be based on generalizing the knowledge gained from the play-outs. Right now, we structure this knowledge into a tree which is certainly an appropriate representation but we are still throwing away a lot of useful (but fuzzy) knowledge about the positions.(For instance we have to discover over and over than a certain move is good, not just in one line but probably in most lines of play.) There has been a lot of progress in this direction but I'll bet there will be more. I have tried some ideas that were failures so far - but I think this is a productive direction in general. - 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] On average how many board updates/sec can top Go programs do these days?
mingwu wrote: Playing randomly like that shouldn't work, but when you play Mogo et al, you see that intelligent behaviour emerges. Although interesting, I would hardly call that 'intelligence' :-) And I suspect how far it can achieve on 19x19 board (compare to human players of course). The explanations given were greatly simplified. Actually, these programs have a ton of research behind them are not just explained simply by a a bunch of random games. So the approach is quite intelligence. One breakthrough has been making the play-outs less random and so they actually have been crafted to give the best results with a lot of outside knowledge added. Also, they are search based which means a search tree is built in memory and a great deal of effort has been spent on how to expand this tree in the most efficient way possible. This has already proved to be the best way forward (so far) as the 19x19 programs using the approach are playing the best go of all the programs. So you may worry about how far it can achieve on 19x19, but now it's not the Monte Carlo approach that is really in question, it's the OTHER approaches that you should now be doubting. With the current trend of Moores law to produce faster computers with more cores and memory, this is truly good news for go programs and especially this technique which is guaranteed to improve with more powerful hardware. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Harri Salakoski wrote: The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. Hmm, sorry if this is old subject but does it effect much for playout quality if I cut playouts for example max 110 moves in 9*9 board? Yes, that will significantly hurt your play-outs.Do you throw away the results or score it as is? I have a very liberal cutoff on my program - from any position I play to move 81*4 in 9x9 as long as I have played at least 20 moves. Is that studied subject for almost random playouts. What is commonly done is something called the mercy rule where you stop the play-outs early if one side appears to have an overwhelming advantage.Even this is somewhat risky if there is a large group with no eyes. I don't use that rule but it's been reported to be anywhere from no benefit to a minor benefit.I have not tested it, but the most you can hope for is a relatively small speedup for a small risk. Another thing, do you include random moves for playouts, after some number of playouts or when there is K number empty points or using some other way. This is all a black art - you must try many different things and see what works best for you. I haven't tried this, but it would be a major speedup to revert to light move strategy after a few heavy moves are tried in each play-out.My heavy play-outs are 3 - 4 times slower than the purely random play-outs. I suspect most of the benefit occurs in the first few moves. Is this what you are suggesting? By the wat made java board for random playouts it is currently 30 games /13sec 9*9 board having max 110 moves(double core 4000+), I have no lightest clue how to make it faster as optimized it as much i can, using two threads it is 7 seconds/30 games. Have think that maybe somekind of state machine could be faster. t. Harri On a 2.2Ghz Athlon64, I get about 10 000 playouts/second, at an average of 100 moves per game this is 1 million updates/second. There are many programs that are much faster. On the same hardware libego would be about 6 million updates/second. 19 x 19 is a bit slower, because strings are bigger on average. This also explains that when I read the games MoGo against GNUGo, toward the end of the game, GNUGo would play PASS, but MoGo would continue to play at some very uncommon positions that a normal player would never consider. Pass behaviour has little to do with the playouts themselves. -- GCP ___ 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] On average how many board updates/sec can top Go programs do these days?
Gian-Carlo Pascutto wrote: Playing randomly like that shouldn't work, but when you play Mogo et al, you see that intelligent behaviour emerges. Although interesting, I would hardly call that 'intelligence' :-) Ah, the traditional flamewar topic: the definition of intelligence shifts whenever a computer achieves what was formerly considered intelligence. You could not have said that any better.If a program with Mogo's strength had appeared 10 years ago, I can imagine some very flattering write-ups about it's incredible A.I. - Don And I suspect how far it can achieve on 19x19 board (compare to human players of course). Perfect play, no need to suspect anything. The real question is how far humans are away from that :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Harri Salakoski wrote: The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. The *average* length of a 9x9 playout is roughly 100 moves. The max length is much larger. Hmm, sorry if this is old subject but does it effect much for playout quality if I cut playouts for example max 110 moves in 9*9 board? Is that studied subject for almost random playouts. Another thing, do you include random moves for playouts, after some number of playouts or when there is K number empty points or using some other way. I play until there are only moves that put stones into a real eye, and then pass 2 times. I described my exact playout policy a few posts ago. Multi-stone suicide is allowed, single stone not. Light playouts (i.e. just random moves) were about as long, if I remember correctly the average playout length was 104 moves or so. It's good practise to measure this regularly over say 1 million games. Sometimes you will find that the average shifts at a moment you didn't expect it = Oops, introduced a bug :) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. Strange. The reverse would make more sense to me. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] CGOS server fixed.
We have not had a single server crash in the almost 5 days since this bug fix. So it's likely that this bug was causing most of the problems and now it's fixed. Thanks to Michael Williams who spotted the problem and proposed the fix. - Don Don Dailey wrote: I deployed a potential fix to the 9x9 cgos server as recommended by Michael Williams. If it goes over 3 days without crashing, the confidence that it is fixed will be high. Then I will ask Olivier to deploy the fix on the 19x19 server. - 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] On average how many board updates/sec can top Go programs do these days?
Surely he meant the opposite. - Don Rémi Coulom wrote: Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. Strange. The reverse would make more sense to me. Rémi ___ 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] On average how many board updates/sec can top Go programs do these days?
Single stone suicide is much easier to test for. :) - Dave Hillis -Original Message- From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tue, 15 Jan 2008 12:11 pm Subject: Re: [computer-go] On average how many board updates/sec can top Go programs do these days? Surely he meant the opposite. - Don Rémi Coulom wrote: Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. Strange. The reverse would make more sense to me. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ omputer-go mailing list [EMAIL PROTECTED] ttp://www.computer-go.org/mailman/listinfo/computer-go/ More new features than ever. Check out the new AIM(R) Mail ! - http://webmail.aim.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
2008/1/15, Rémi Coulom [EMAIL PROTECTED]: Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. Strange. The reverse would make more sense to me. Multi-stone suicide is sometimes the best move (if the rules allow it). This is because multi-stone suicide is sometimes a good ko thread (to kill a group). Andrés ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
No, God creates all the rest, integers are just work of man.? DL? God create integers, all the rest are just work of man :-) More new features than ever. Check out the new AOL Mail ! - http://webmail.aol.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Um, by easier I mean faster. Also, I think single point suicide is more likely to lead to infinite loops, depending on your eye-filling rule. - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tue, 15 Jan 2008 12:16 pm Subject: Re: [computer-go] On average how many board updates/sec can top Go programs do these days? Single stone suicide is much easier to test for. :) - Dave Hillis -Original Message- From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tue, 15 Jan 2008 12:11 pm Subject: Re: [computer-go] On average how many board updates/sec can top Go programs do these days? Surely he meant the opposite. - Don Rémi Coulom wrote: Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. Strange. The reverse would make more sense to me. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ omputer-go mailing list [EMAIL PROTECTED] ttp://www.computer-go.org/mailman/listinfo/computer-go/ More new features than ever. Check out the new AIM(R) Mail! ___ omputer-go mailing list [EMAIL PROTECTED] ttp://www.computer-go.org/mailman/listinfo/computer-go/ More new features than ever. Check out the new AIM(R) Mail ! - http://webmail.aim.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Rémi Coulom wrote: Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. Strange. The reverse would make more sense to me. I do not track liberties, so the speed penalty for doing it that way is too much. I wrote my program to track psuedoliberties because this is very fast and I thought I could take a lot of shortcuts and early exits when I had to know the real amount of liberties. Unfortunately the interesting cases seem to be the ones that don't allow for the shortcuts. I am now convinced designing the program with psuedoliberties was a mistake. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
[EMAIL PROTECTED] wrote: Um, by easier I mean faster. Also, I think single point suicide is more likely to lead to infinite loops, depending on your eye-filling rule. - Dave Hillis Yes. Particularly near the end of the game there are zillions of bad single stone suicides, but not often multi-stone suicides. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
How can you call it 'intelligence' if a person limits one's thoughts and viewpoints to a narrow domain? DL Although interesting, I would hardly call that 'intelligence' :-) More new features than ever. Check out the new AOL Mail ! - http://webmail.aol.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
On Jan 15, 2008, at 10:00 AM, [EMAIL PROTECTED] wrote: Um, by easier I mean faster. Also, I think single point suicide is more likely to lead to infinite loops, depending on your eye- filling rule. - Dave Hillis I don't understand why anyone would allow suicide in playouts. No commonly used (in particular CGOS) ruleset allows it. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
I think the only reasonable argument for suicide in the play-outs is speed. It's possible to improve the speed of play-outs significantly if you avoid the suicide test. But I'm convinced that it comes at a price. Suicide is the best move very rarely, and in rule-sets that do not allow it, it's NEVER the best move and it makes no sense to include them in the play-outs. - Don Christoph Birk wrote: On Jan 15, 2008, at 10:00 AM, [EMAIL PROTECTED] wrote: Um, by easier I mean faster. Also, I think single point suicide is more likely to lead to infinite loops, depending on your eye-filling rule. - Dave Hillis I don't understand why anyone would allow suicide in playouts. No commonly used (in particular CGOS) ruleset allows it. Christoph ___ 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] On average how many board updates/sec can top Go programs do these days?
[EMAIL PROTECTED] wrote: How can you call it 'intelligence' if a person limits one's thoughts and viewpoints to a narrow domain? Yes, I agree. It really took some imagination and open mindedness to discover UCT and Monte Carlo since it breaks so sharply away from the old traditional way of writing a go program. It's still not clear to me what the ultimate approach is. It could be that a properly written classical program can compete - such as the approach David Fotland is using where global search is an important component to an already knowledge rich program. These are all intelligent approach as far as I am concerned.You see that the programs continue to expand to utilize resources better and continue to improve slowly but surely. It's not uncommon in computer science and mathematics to eventually see many methods as a special case of some generalization. All approaches that are producing farily strong programs have a search component and an evaluation component mixed in different ratios. We just like to get hung up on the exact implementation details and imagine that different approaches have nothing in common. - Don DL Although interesting, I would hardly call that 'intelligence' :-) More new features than ever. Check out the new AOL Mail ! - http://webmail.aol.com ___ 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] On average how many board updates/sec can top Go programs do these days?
Christoph Birk wrote: On Jan 15, 2008, at 10:00 AM, [EMAIL PROTECTED] wrote: Um, by easier I mean faster. Also, I think single point suicide is more likely to lead to infinite loops, depending on your eye-filling rule. - Dave Hillis I don't understand why anyone would allow suicide in playouts. No commonly used (in particular CGOS) ruleset allows it. Passing is not allowed in chess. Yet nullmove is quite popular. There is no reason to follow the rules during playouts. If playing 10 moves at once made my program stronger, I would do just that. ...and yes, I did try that. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Go programs do these days?
Another possible reason could be for SIMD (vector) parallel processing. Years ago, I was a real-time image processing guy. Some time back, I did a back-of-the-envelope design for doing?light playouts on multiple go boards at once, on a dedicated parallel processing card. It meant?tiling all these boards into a large?image and using standard image processing-type operations. Avoiding single-stone suicide looked easy. Avoiding multi-stone suicide looked like a can of worms. If some one wanted to use, for instance, a graphics card to do fine grained parallel processing, permitting multi-stone suicides might be a tempting option. - Dave Hillis -Original Message- From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tue, 15 Jan 2008 1:43 pm Subject: Re: [computer-go] On average how many board updates/sec can top Go programs do these days? I think the only reasonable argument for suicide in the play-outs is speed. It's possible to improve the speed of play-outs significantly if you avoid the suicide test. But I'm convinced that it comes at a price. Suicide is the best move very rarely, and in rule-sets that do not allow it, it's NEVER the best move and it makes no sense to include them in the play-outs. - Don Christoph Birk wrote: On Jan 15, 2008, at 10:00 AM, [EMAIL PROTECTED] wrote: Um, by easier I mean faster. Also, I think single point suicide is more likely to lead to infinite loops, depending on your eye-filling rule. - Dave Hillis I don't understand why anyone would allow suicide in playouts. No commonly used (in particular CGOS) ruleset allows it. Christoph ___ 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/ More new features than ever. Check out the new AIM(R) Mail ! - http://webmail.aim.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
cgbg, was [computer-go] On average how many board updates/sec can top Go programs do these days?
Gian-Carlo Pascutto [EMAIL PROTECTED] said: I wrote my program to track psuedoliberties because this is very fast and I thought I could take a lot of shortcuts and early exits when I had to know the real amount of liberties. Unfortunately the interesting cases seem to be the ones that don't allow for the shortcuts. I am now convinced designing the program with psuedoliberties was a mistake. My friends and I have just finished an alpha version of a code generator that compares go board implementations in a wholistic manner. The results are complicated, but pseudo-liberties work reasonably well, too. See below. Michael Wing www.swcp.com/~wing/cgbg --- The Critters Go Board Generator Michael Wing January 15, 2008 Ive wanted to develop a fast go board for many years, and have spent the last few months helping write a go board generator to figure out what fast means. The current code was inspired in part by discussions on the computer-go email. CGBG generates many go board implementations: 4 methods of tracking liberties, 3 methods of tracking adjacent groups, 2 methods for mapping a location to a chain. It also can generate code with and without borders, and for many board sizes. It generates ptest, which runs 2 performance tests: filling the board to 90% full (which resembles Monte Carlo readouts) and ladder reading (which resembles local board analysis). It generates ftest, which runs many functional unit tests. Caveats. CGBG was intended to create apples-to-apples comparisons, but does not strictly do so. First, the current implementations are solid, but not necessarily optimal. For example, union-find uses classic 2-pass path compression, rather than the 1-pass version in libego. Also, Many other optimizations (loop unrolling) are not implemented. This is alpha code. Many ideas are just sketches. There is a lot of cruft. Main conclusions: * GnuGo data structures are pretty darn good, even for Monte Carlo simulation. I had hoped to find a linked-list data structure, but didnt. * Behavior at 9*9 can be very different than behavior at 19*19. * The complex nature of cache and processor architecture makes it very hard to predict the effect of any data structure decision. Trying it out empirically is the only way. * Many reasonable implementations run within a factor or 33% or so of the best. Main conclusions for 19*19: * Using union-find is slower than changing the smaller chain, by a tiny amount. * Using arrays to track liberties is best for board analysis. * Using pseudo-liberties only is best for pure simulation. * Using arrays to track adjacent groups is best for board analysis. * Using search-only to track adjacent groups is best for pure simulation. * For a program that does both Monte Carlo and local board analysis, I would use arrays to track both liberties and adjacencies. * For a program that does no local analysis, I would use pseudo liberties only. Other Notes * CGBG precomputes board and hash data, so they can be stored in read-only memory and do not need to be initialized. This can be used as an example, or cut and paste into other implementations. * This implements positional superko checking (though not tested), which GnuGo and libego do not. Situational superko checking is sketched, but not complete. * The play() routine uses gotos. The conventional technique of deciding the status of a move and then using a switch statement is about 1 percent slower. The code is written in Ruby, and currently generates C code for gcc under cygwin. It also needs to link in SFMT. It is available at www.swcp.com/~wing/cgbg To Use * ./cgbg config_file * make * ./ftest * ./ptest I would appreciate any feedback. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: cgbg, was [computer-go] On average how many board updates/sec can top Go programs do these days?
- Original Message From: [EMAIL PROTECTED] [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, January 15, 2008 2:59:15 PM Subject: cgbg, was [computer-go] On average how many board updates/sec can top Go programs do these days? Gian-Carlo Pascutto [EMAIL PROTECTED] said: I wrote my program to track psuedoliberties because this is very fast and I thought I could take a lot of shortcuts and early exits when I had to know the real amount of liberties. Unfortunately the interesting cases seem to be the ones that don't allow for the shortcuts. I am now convinced designing the program with psuedoliberties was a mistake. My friends and I have just finished an alpha version of a code generator that compares go board implementations in a wholistic manner. The results are complicated, but pseudo-liberties work reasonably well, too. See below. Michael Wing www.swcp.com/~wing/cgbg I visited the www page, and the combination of pre with very long lines does not work well at all. Tried both firefox and IE. pre prevents the browser from wrapping the text to fit the display page. --- Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: cgbg, was [computer-go] On average how many board updates/sec can top Go programs do these days?
terry mcintyre [EMAIL PROTECTED] said: www.swcp.com/~wing/cgbg I visited the www page, and the combination of pre with very long lines does not work well at all. Tried both firefox and IE. pre prevents the browser from wrapping the text to fit the display page. Thanks. Reformatted the text. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] How to get more participation in 19x19 CGOS?
I tried to send you a zip file, but the email failed, then it said it would be delivered. Let me know if you don't get it. -Original Message- From: [EMAIL PROTECTED] [mailto:computer-go- [EMAIL PROTECTED] On Behalf Of Mark Boon Sent: Tuesday, January 15, 2008 10:11 AM To: computer-go Subject: Re: [computer-go] How to get more participation in 19x19 CGOS? As suggested by David Fotland I made a simple referee type of setup so that I can have two engines play each other continuously. I got it working with GnuGo but with MoGo I get an Access denied message when I try to start it from the referee program. When starting from the command-line I have no trouble. Since I expect the games against MoGo to be much longer and thereby uncover more bugs I figured it would be a better test-opponent. Is anyone familiar with this error? In case it's relevant, I'm running it under Windows XP on a Mac using VMWare. 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/
Re: [computer-go] On average how many board updates/sec can top Goprograms do these days?
Hmm, sorry if this is old subject but does it effect much for playout quality if I cut playouts for example max 110 moves in 9*9 board? Yes, that will significantly hurt your play-outs.Do you throw away the results or score it as is? I have a very liberal cutoff on my program - from any position I play to move 81*4 in 9x9 as long as I have played at least 20 moves. Aha, sounds fair. I asked that when I noticed that my impl have constant 110 moves preventing max playouts. After investigated that more that particular case NaruGo project ArrayBoard it really seems not to matter, because current implementation throws away empty points after point is investigated to be illegal only for other player. That I think should be corrected after it is figure out how should that be done. Other hand playouts non-naturally end more early than 110 moves regulary because empty points which are illegal for other are thrown away(and removed from playable empty points array) and so on change for that constant made no big effect. So thats situation no clue should I fix that, it seems so painfull to fix as afraid which slowdown it makes. But I am sure that atleast in end game playouts(which start near end game) all moves should offcourse be included, so I have think to use different playout code for playouts starting near end or starting early positions. So I should be asking is it bad for playouts throw away empty points if those are only illegal for other player? I afraid to hear yes it is very bad for playout quality :| t. hArri ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many board updates/sec can top Goprograms do these days?
I'm trying to understand what you are saying. If a point is illegal for black, are you saying that black can never play at that point, or are you saying white can never play there? Or are you saying neither side can? What is the reason for this? I'm not sure I understand what you are saying. Once I tried something I hoped would speed up play-outs a lot without hurting the quality. I considered all large captured points as out of play.For instance if white captures a 10 stone group, it becomes permanently owned by white and neither side can move there again.The assumption is that if you capture a large group, you will more than likely be able to hold that space down.I tried a few variations of this, but these things only hurt the program.I think with more analysis you might be able to find shortcuts - one example is the mercy rule which leans on certain assumptions. - Don Harri Salakoski wrote: Hmm, sorry if this is old subject but does it effect much for playout quality if I cut playouts for example max 110 moves in 9*9 board? Yes, that will significantly hurt your play-outs.Do you throw away the results or score it as is? I have a very liberal cutoff on my program - from any position I play to move 81*4 in 9x9 as long as I have played at least 20 moves. Aha, sounds fair. I asked that when I noticed that my impl have constant 110 moves preventing max playouts. After investigated that more that particular case NaruGo project ArrayBoard it really seems not to matter, because current implementation throws away empty points after point is investigated to be illegal only for other player. That I think should be corrected after it is figure out how should that be done. Other hand playouts non-naturally end more early than 110 moves regulary because empty points which are illegal for other are thrown away(and removed from playable empty points array) and so on change for that constant made no big effect. So thats situation no clue should I fix that, it seems so painfull to fix as afraid which slowdown it makes. But I am sure that atleast in end game playouts(which start near end game) all moves should offcourse be included, so I have think to use different playout code for playouts starting near end or starting early positions. So I should be asking is it bad for playouts throw away empty points if those are only illegal for other player? I afraid to hear yes it is very bad for playout quality :| t. hArri ___ 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] On average how many board updates/sec cantop Goprograms do these days?
I'm trying to understand what you are saying. If a point is illegal for black, are you saying that black can never play at that point, or are you saying white can never play there? Or are you saying neither side can? Yep currently neither side can anymore use that point. What is the reason for this? I'm not sure I understand what you are saying. Reason is that I have empty point array, it is fast to choose played points from that array. Points which are consireded illegal or bad are thrown away. Once I tried something I hoped would speed up play-outs a lot without hurting the quality. I considered all large captured points as out of play.For instance if white captures a 10 stone group, it becomes permanently owned by white and neither side can move there again.The assumption is that if you capture a large group, you will more than likely be able to hold that space down.I tried a few variations of this, but these things only hurt the program. I add empty points from killed groups to back that empty points array; sound like that is not mandatory either. I know if I don't add points from killed groups back for empty stone array that is about 20% speedup. I agree if group is big, other hand if group is big, game is usually over so maybe should stop playout for that, wonder if that only hurts program.. I think with more analysis you might be able to find shortcuts - one example is the mercy rule which leans on certain assumptions. mercy rule? t. Harri - Don Harri Salakoski wrote: Hmm, sorry if this is old subject but does it effect much for playout quality if I cut playouts for example max 110 moves in 9*9 board? Yes, that will significantly hurt your play-outs.Do you throw away the results or score it as is? I have a very liberal cutoff on my program - from any position I play to move 81*4 in 9x9 as long as I have played at least 20 moves. Aha, sounds fair. I asked that when I noticed that my impl have constant 110 moves preventing max playouts. After investigated that more that particular case NaruGo project ArrayBoard it really seems not to matter, because current implementation throws away empty points after point is investigated to be illegal only for other player. That I think should be corrected after it is figure out how should that be done. Other hand playouts non-naturally end more early than 110 moves regulary because empty points which are illegal for other are thrown away(and removed from playable empty points array) and so on change for that constant made no big effect. So thats situation no clue should I fix that, it seems so painfull to fix as afraid which slowdown it makes. But I am sure that atleast in end game playouts(which start near end game) all moves should offcourse be included, so I have think to use different playout code for playouts starting near end or starting early positions. So I should be asking is it bad for playouts throw away empty points if those are only illegal for other player? I afraid to hear yes it is very bad for playout quality :| t. hArri ___ 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] On average how many board updates/sec cantop Goprograms do these days?
I think with more analysis you might be able to find shortcuts - one example is the mercy rule which leans on certain assumptions. mercy rule? Mercy rule: if one side is way ahead, stop the game early. t. Harri - Don Harri Salakoski wrote: Hmm, sorry if this is old subject but does it effect much for playout quality if I cut playouts for example max 110 moves in 9*9 board? Yes, that will significantly hurt your play-outs.Do you throw away the results or score it as is? I have a very liberal cutoff on my program - from any position I play to move 81*4 in 9x9 as long as I have played at least 20 moves. Aha, sounds fair. I asked that when I noticed that my impl have constant 110 moves preventing max playouts. After investigated that more that particular case NaruGo project ArrayBoard it really seems not to matter, because current implementation throws away empty points after point is investigated to be illegal only for other player. That I think should be corrected after it is figure out how should that be done. Other hand playouts non-naturally end more early than 110 moves regulary because empty points which are illegal for other are thrown away(and removed from playable empty points array) and so on change for that constant made no big effect. So thats situation no clue should I fix that, it seems so painfull to fix as afraid which slowdown it makes. But I am sure that atleast in end game playouts(which start near end game) all moves should offcourse be included, so I have think to use different playout code for playouts starting near end or starting early positions. So I should be asking is it bad for playouts throw away empty points if those are only illegal for other player? I afraid to hear yes it is very bad for playout quality :| t. hArri ___ 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] On average how many board updates/sec cantop Goprograms do these days?
If a point is illegal for black, are you saying that black can never play at that point, or are you saying white can never play there? Or are you saying neither side can? Yep currently neither side can anymore use that point. This is a mistake. There are often moves that are illegal for black that are big for white. If you don't let white play there, white can lose a lot of points. Connections through false eyes are one example. David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On average how many boardupdates/sec cantop Goprograms do these days?
This is a mistake. There are often moves that are illegal for black that are big for white. If you don't let white play there, white can lose a lot of points. Connections through false eyes are one example. Yep agree that, knowing that it is not fair for other but kind of rationalized it that it is same for both players and there is half chance that other player tries it before. I kind of think that it keeps spirit of random result still because it is same for both players, but I change it. t. Harri - Original Message - From: David Fotland [EMAIL PROTECTED] To: 'computer-go' computer-go@computer-go.org Sent: Wednesday, January 16, 2008 8:56 AM Subject: RE: [computer-go] On average how many boardupdates/sec cantop Goprograms do these days? If a point is illegal for black, are you saying that black can never play at that point, or are you saying white can never play there? Or are you saying neither side can? Yep currently neither side can anymore use that point. This is a mistake. There are often moves that are illegal for black that are big for white. If you don't let white play there, white can lose a lot of points. Connections through false eyes are one example. David ___ 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/
