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 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/
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?
[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?
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?
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?
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?
[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?
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?
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 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?
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?
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?
Single stone suicide is much easier to test for. :) - Dave Hillis -Original Message- From: Don Dailey <[EMAIL PROTECTED]> To: computer-go 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?
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?
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/
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?
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?
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?
> > 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: 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.
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?
>> 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?
> 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?
Many Faces is a strong traditional program. It evaluates about 100 to 150 positions/sec in the middle game, and up to 500 positions/sec in the endgame. This is on one processor of a 2.3 GHz core duo. It's for version 12 (not released). Version 11 is slower. I plan to make it faster, but right now I'm working on making the search more efficient. Here is output from a middle game position against gnugo (at move 80). Each iteration only takes about twice as long as the previous one. This one is 125 evaluations per second. The tactical search evaluates 220377 nodes per second. Search 18-36 seconds (1 max evals), 0.3 secs in life reading level 5, life reading 35 life() New best 2432 (strat 352)d16 d16 d18 e18 c19 New best 2691 (strat 497)d18 d18 New best 2741 (strat 447)m13 m13 d18 b17 New best 2994 (strat 151)q11 q11 q12 Iteration 1 complete 20 moves in 2.46 secs. Total evals 304, search life() 269, Final value is 2994 for q11 : q11 q12 New best 2994 (strat 151)q11 q11 q12 Iteration 2 complete 20 moves in 5.59 secs. Total evals 698, search life() 663, Final value is 2994 for q11 : q11 q12 New best 2898 (strat 151)q11 q11 q12 m13 o16 Iteration 3 complete 20 moves in 11.56 secs. Total evals 1420, search life() 1385, Final value is 2898 for q11 : q11 q12 m13 o16 New best 2831 (strat 151)q11 q11 q12 p10 o12 Iteration 4 complete 20 moves in 25.74 secs. Total evals 3223, search life() 3188, Final value is 2831 for q11 : q11 q12 p10 o12 Pass val 40.2, best val 56.6 25.7 secs. life() 3223 (125/s), searchevals 1124, Nodes 1851 ( 72/s), full gen 72, Q gen 1603, Moves 1848( 72/s), tree nodes 114/114, list 11472/11472, tac nodes 5672726 (220377/s), evalopj 483514 ( 9%), life 5153443 ( 91%) [ fixgralive 13538182 (239%) miai 3823111 ( 67%) tvpot 3669677 ( 65%), group 270464 ( 5%), conn 342851 ( 6%), eye 604303 ( 11%) ] David From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of mingwu Sent: Monday, January 14, 2008 5:45 PM To: computer-go@computer-go.org Subject: [computer-go] On average how many board updates/sec can top Go programs do these days? 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? And if this is still true, how can we make it faster? To make the question more precise, I define a board updates as: suppose the program places a new move on an existing board, and then update all the blocks, dragons, eyes, connections, territory ... info, and output the evaluation as a score ( e.g. B leads by 15.5 points). I also read that UTC programs choose a move by running lots of simulations, are their update speed any faster? Or they evaluation lots of boards, but for each move they only calculate some very simple information (to me, it will still be a surprise, because to evaluate a Go board, one at least have to know the life/death of each dragon, that would require lots of computation, which I think is the primary reason that why Go programs is slow compared to Chess programs that can evaluate thousands or even millions of boards per second). I'm just curious, any info / thoughts / comments is appreciated. ___ 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?
> > It does this by generating random legal moves. A string of legal moves, to > the end, is one "playout." > OK, now I understand it generates a sequence of moves, all the way to the game end; which means a playout typically contains 200 (from middle game) ~ 300 (from opening) moves, and the so-called 'evaluation' becomes just counting the stones. Very interesting! Then it doesn't need to know anything about those secondary, or 3rd-ary, 4th-ary ... concepts like 'eyes', 'connections', ...; it only need to know the very basic game rules that any stone un-capturable is alive. Haha. "God create integers, all the rest are just work of man" :-) 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. This is kind of similar to the exhaustive search approach (depth-first in this case). 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. > 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). ___ 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 problem here is that you asked mutually contradictory things. You defined what you meant by a board update, in which you specified a list of things, and you also asked about "top programs." The top programs do not do the kinds of evaluations you specify, although older conventional programs do. The newer programs that are now the strongest are variations of the Monte Carlo method, which does statistical sampling, not the kinds of evaluation you specify. Cheers, David On 14, Jan 2008, at 7:41 PM, mingwu wrote: On Jan 14, 2008 6:15 PM, Jason House <[EMAIL PROTECTED]> wrote: slow. UCT (or generically Monte Carlo) can "evaluate" a position fairly quickly (maybe 1k-100k per second depending on how heavy the playout is), they don't give a reliable estimate. To improve this, they end up 1K ~ 100 K / sec is much faster than "a dozen" / sec of a conventional program. Do they calculate dragon safety (eyes, connections, patterns ...)? if not, the estimate will be VERY unreliable. But if they do, how can they be this fast compared to the more conventional programs? reevaluating positions more than once (maybe 100 times?) to get a more reliable estimate. why "reevaluating" the same position? Sorry, I didn't go into their papers, can people who knows UCT, or actually working on UCT programs explain in a way that a layman can understand. Thanks. ___ 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?
> 1K ~ 100 K / sec is much faster than "a dozen" / sec of a conventional > program. > > Do they calculate dragon safety (eyes, connections, patterns ...)? if not, > the estimate will be VERY unreliable. No, because they play the game out to the end where everything is as safe as it can be. Then, because they had to guess what the best move is at each point when playing it out, they play it out many thousands of time, and see what percentage of those playouts led to a win for each side. Playing randomly like that shouldn't work, but when you play Mogo et al, you see that intelligent behaviour emerges. > Sorry, I didn't go into their papers, can people who knows UCT, or actually > working on UCT programs explain in a way that a layman can understand. Sensei's has something. http://senseis.xmp.net/?UCT Searching the archives to this list would also give explanations (though you'll be overwhelmed by the noise I guess). Darren ___ 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 Mon, 2008-01-14 at 19:41 -0800, mingwu wrote: > 1K ~ 100 K / sec is much faster than "a dozen" / sec of a conventional > program. > > Do they calculate dragon safety (eyes, connections, patterns ...)? if > not, the estimate will be VERY unreliable. That's just it, they don't. They play a *random* game and get a win or loss (0 or 1) out of it. Random games in better positions tend to win more frequently. > reevaluating positions more than once (maybe 100 times?) to > get a more > reliable estimate. > > > > why "reevaluating" the same position? It's like flipping a weighted coin... It takes many flips to figure out how frequently it comes up heads or tails. > Sorry, I didn't go into their papers, can people who knows UCT, or > actually working on UCT programs explain in a way that a layman can > understand. Thanks. That's really the basics of how monte carlo go works. UCT is a method of choosing which coins to flip and how to combine results deep in the search tree. I'm sure many of us are surprised how well this stuff works. ___ 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 14, 2008 6:15 PM, Jason House <[EMAIL PROTECTED]> wrote: > slow. UCT (or generically Monte Carlo) can "evaluate" a position fairly > quickly (maybe 1k-100k per second depending on how heavy the playout > is), they don't give a reliable estimate. To improve this, they end up > 1K ~ 100 K / sec is much faster than "a dozen" / sec of a conventional program. Do they calculate dragon safety (eyes, connections, patterns ...)? if not, the estimate will be VERY unreliable. But if they do, how can they be this fast compared to the more conventional programs? > reevaluating positions more than once (maybe 100 times?) to get a more > reliable estimate. > why "reevaluating" the same position? Sorry, I didn't go into their papers, can people who knows UCT, or actually working on UCT programs explain in a way that a layman can understand. Thanks. ___ 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 your question boils down to answering what is meant by "evaluate". Chess has a heuristic that is easy to compute and gives a good evaluation. Go lacks this. While probably an inferior evaluator, the Bouzy 5/21 score estimator is an example from go that can be quite slow. UCT (or generically Monte Carlo) can "evaluate" a position fairly quickly (maybe 1k-100k per second depending on how heavy the playout is), they don't give a reliable estimate. To improve this, they end up reevaluating positions more than once (maybe 100 times?) to get a more reliable estimate. On Mon, 2008-01-14 at 17:44 -0800, 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? > > And if this is still true, how can we make it faster? > > To make the question more precise, I define a board updates as: > suppose the program places a new move on an existing board, and then > update all the blocks, dragons, eyes, connections, territory ... info, > and output the evaluation as a score ( e.g. B leads by 15.5 points). > > I also read that UTC programs choose a move by running lots of > simulations, are their update speed any faster? Or they evaluation > lots of boards, but for each move they only calculate some very simple > information (to me, it will still be a surprise, because to evaluate a > Go board, one at least have to know the life/death of each dragon, > that would require lots of computation, which I think is the primary > reason that why Go programs is slow compared to Chess programs that > can evaluate thousands or even millions of boards per second). > I'm just curious, any info / thoughts / comments is appreciated. > > > ___ > 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/
