Ah, curse the accidental send. A few clarifications below: On Thu, Nov 19, 2009 at 7:03 PM, Seth Pellegrino <se...@lclark.edu> wrote: > Hello Tom and Petr! > > Thank you both for your speedy replies. I do apologize, though, as I > seem to have left some important information out: > > * I know that 70pps is useless, hence my dismay when that's the speed > I was getting. > * I am running these playouts on a 19x19 board, which does slow things > down a little bit > * I've already got a stable base that I'm working from (specifically, > Peter Drake's Orego[1]). > > I tried as you suggested, Tom, and didn’t check for the legality of > each move before computing the associated gamma, but that still > doesn't get me to a feasible play level. It seems that, the way mode > code is written, iterating over a collection of vacant points and > computing which features are present is too expensive.
That should be "my" code, not "mode" code. > At present, Orego doesn't store real liberties, so I'm paying a huge > price trying to look those up every time. However, after running the > code through a profiler, it seems that only 50% of my time or so is > being spent looking up those liberties. Granted, eliminating that > bottleneck should double the speed of my code, but jumping from 80pps > to 160pps still leaves me a bit underwater. > > Unfortunately, I'm a bit at a loss of how to compute the features > faster. I am considering creating a method that would compute whether > the last move put any groups into atari (and then store that answer > until the board's state changed), but I can't help but feel that I'm > doing something very wrong. For instance, I'm presently doing To complete this thought: I'm presently computing each level of each feature for each point. Would it make more sense to compute each level of each point for each feature (i.e. nesting the point loop inside the feature loop rather than vice versa), or (as I suspect) does it not make that much a difference? > Also, Tom, I was wondering if you could speak to adding patterns > larger than 3x3. A nice feature of 3x3 patterns is that they can be > jammed into two bytes (4 possibilities [black, white, vacant, off > board] for 8 positions), which facilitates the creation of a lookup > table. I've yet to figure out as fast a method for 4x4 patterns (or > larger), so I was wondering both how you've done it and how much it > helped. > > Thank you much, > > Seth > > [1] http://legacy.lclark.edu/~drake/Orego.html > > On Thu, Nov 19, 2009 at 9:27 AM, Thomas Lavergne > <thomas.laver...@reveurs.org> wrote: >> On Thu, Nov 19, 2009 at 09:43:41AM +0100, Petr Baudis wrote: >>> Hi! >>> >>> On Thu, Nov 19, 2009 at 12:35:09AM -0800, Seth Pellegrino wrote: >>> > I'm working on an implementation of Rémi Coulom's Elo-based move >>> > prediction algorithm[1], and I seem to be running into efficiency >>> > issues. With my current implementation, I'm running at around 8 or 10 >>> > playouts per second. I can't imagine that the playouts would be so >>> > accurate that I would be able to accurately evaluate my next move at >>> > that speed. It seems that simply visiting each vacant point on the >>> > board and checking whether that move would be a legal move for the >>> > current player (without even computing which gammas are present at a >>> > point) takes me down to about 60-75 playouts per second. >>> >>> What language are you using for your implementation? 60-75 playouts >>> per second is still *extremely* slow, it seems you are in for much >>> optimizing yet. Common speed of heavy playouts is at least _thousands_ >>> of playouts per second (per core of modern CPU), in case of light >>> playouts it should be getting into tens of thousands. >>> >>> I'm not sure how much slowdown in general you get by implementing ELO >>> patterns, the improvement has not been implemented commonly yet in >>> public codebases (though it does seem very promising, no doubt); I plan >>> to implement it in Pachi later, but I want to try out few different >>> things first yet. >>> >> >> This is indeed extremly slow. As a reference, some number from my own >> bot who is still in full rewrite. On my rather old Pentium4 at 1.6Ghz I >> get the following on 9x9 board: >> v1 : ~54000pps >> v2 : ~49000pps >> v3 : ~41000pps >> v4 : ~26000pps >> v1 do pure random playouts by selecting play randomly in the empty point >> list and testing for validity. >> v2 do pure random playouts but select play from the empty list according >> to their weight who is set to 1.0 for all plays. (this is for testing >> the impact of drawing from weights) >> v3 do weighted playouts using elo rating to weights plays with only 3x3 >> patterns. >> v4 same as v3 but use big patterns: up to size 9 manathan paterns. >> >> This is probably not the speedest implementation you can have, but I >> think its good performance for a programme fully written in ansi/C >> without assembly. >> You can also use libego to check speed on your machine for pure random >> playouts. >> >> >> Some tricks from my experiences : >> - A lot of thing can be computed incrementally and will be a lot more >> slower if you recompute them each times: the list of empty points, the >> patterns, the cell weights... >> - Don't check for validity of each play in the empty list before drawing >> one, just pick one until you find a laid one. This not theoreticaly >> exact but in practice, there is no problems and you can gain a lot of >> speed here. >> - Don't try to undo all move at the end of playout before the next one, >> just make a copy before starting playout and do it on the copy. >> >> >> As a plan to build a bot, I first think you must build a basic bot with >> pure random playouts only and get it fast enough. You don't have to go >> to 50kpps, but I think at least you must go to 10kpps. >> >> When this works and it's fully tested, start to add weighted drawing and >> small fixed size patterns. Those are easy to implement and to maintain >> incrementally, and will allow you to debug more your base. At this point >> you start to get strong playouts. >> >> Only when you have this you can add bigger patterns. >> >> >> The Elo ratting from Remy is very powerfull but it's also very tricky to >> implement efficiently in your bot, so start with a good base before >> trying it. >> >> >> When I've written the first version of goober, I've tried to put all my >> ideas and all ideas of others I find nice at the same time and after a >> will this starting to be unmanageable and very difficult to debug. Now, >> I'm rewritting it fully from scratch, and don't do the same mistake. The >> numbers above show you the progress of it : >> - I've started to build a bot without tree search, with only pure random >> playouts ; >> - Next I've made it work with weighted plays ; >> - Next I've added small fixed size patterns with elo-ratings ; >> - Adding big patterns was the more tricky and difficult part to get them >> efficients. >> Now I have a reliable playout engine, with weighted plays. Weights are >> computed from small or big patterns and a lot of other features. And I'm >> currently working on the tree search part of the bot. >> I've already a basic UCT without RAVE but using a lockless transposition >> table (the only part not in ansi/c) and I test it a lot before starting >> to add anything fancy. >> >> >> Another advantage of this approach is you can see the progress of your >> bot and check for the efficienty of each addition. >> >> Writting a bot is a lot of work but it's also a lot of pleasure, so good >> luck for your one. >> >> Tom >> >> -- >> Thomas Lavergne "Entia non sunt multiplicanda praeter >> necessitatem." (Guillaume d'Ockham) >> thomas.laver...@reveurs.org http://oniros.org >> _______________________________________________ >> 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/
