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. 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 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 <[email protected]> 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) > [email protected] http://oniros.org > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
