Re: [computer-go] Elo move prediction
Hi! On Thu, Nov 19, 2009 at 07:03:56PM -0800, Seth Pellegrino wrote: 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]). But you said the 70pps is even _before_ you turn on the ELO prediction - so you are effectively saying that your base speed is useless, then no matter how fast you make ELO, of course your final speed will remain useless. I think it is obvious you should forget about gamma computation and feature checks for now completely, and focus on bringing your base engine up to reasonable speed - of course you should at the same time consider which features you need provided by the engine (e.g. real liberties) and move them there. (You could also choose a better base to work from, e.g. libego, Pachi or Fuego, but maybe you are expected to use Orego for your project. ;-) P.S.: I wonder what's the top speed Java-based engines can currently achieve? Anyone has any data? How fast is refbot? -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Elo move prediction
On Thu, Nov 19, 2009 at 08:25:53PM -0800, Seth Pellegrino wrote: Apologies all for replying to myself so many times, but Darren Cook has been kind enough to help me clear the matter up. Essentially, I had misread his paper. I was trying to compute the expensive features Rémi uses for progressive widening as a move selector for playouts rather than the stripped down, speedy features he actually uses. Thank you all for your help in increasing my understanding. 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. A thing to always get in mind is compute incrementaly, so for each features you have to check each time you play a stone, if this play chane features somewhere on the board. For example, for the atari feature, when you play a stone, just check if it's group or one of the neighboorin groups go to one liberty, if it's the case, update the weights and flags the group as in atari. When you add this stone, you also check if it's group is flagged as in atari, if it's the case and now it have more than one liberty, update the weight and flag. In order to have this work, you must also add little update when connecting and removing groups, but all this can be done incrementaly. For the patterns, I keep two things: - For all points on the board I keep a 16 bit value containing the 3x3 pattern of the surrounding cell like you said. This can be easily done and update each on cell change. If you change the content of a cell, just update the neighbooring patterns. This is very fast to do and require no branching. - For empty points only, a list of bigger patterns. First, those cost a lot more so I update them only for empty cells. These are stored as zobrist hash key, so for each cell I have an array of wiht hash value for patterns from size 2 to 9. When the content of one cell change, I have to lookup for empty cells in it's 9-neighbooring, and for them I have to update the patterns. The pattern update is done by first computing the old weights of modified patterns, updating the patterns and updating the weight by the difference between old and new weights. When a stone is captured, his cell become empty and you have to recompute each pattern for this cell because it was not updated incrementally, but in practice, this cost you less than keeping all non-empty cell upto date. Surely this cost a lot more than simples 3x3 patterns but if implemented carefully it's tracktable and I've got them even in playouts. In playouts I don't go as far as size 9, just upto size 4. Without them I do 41kpps and with them I've dropped to 26kpps as stated in my previous mail. This is one of the more costly addition to my engine but it was a very big improvement in the playout quality. A pure playout bots, i.e. no tree search, can play nicely one 9x9. It's not very strong and I can beat it easily but his playing style is a lot better. For sure, on 19x19 the speeds are a lot lower but the impact of patterns is just different. On one hand, on 9x9 each time you change a cell, you almost have to update all the cell on the board as opposed to 19x19 where you just update a subset of them generally between 10% and 20% of the cells. But, on the other hand, of these cells to update, on 19x19 there is more empty ones than on 9x9. On small board, it's hard to build big territory, so the board finish almost full of stone. On 19x19 you build big territory and each time on stone is played near the border of aterritory, you have to update patterns of all empty cells in it. So even if there is, less percent of the board covered by a change, a bigger portion of this set is concerned by updates. I focus for the moment on 9x9 so I have no bench for the 19x19 boards, but I will try to make them. Last time I've looked, if I remember well I have similar drop in performance than in 9x9, but this have to be checked more carefully. The main things you don't want to do in playouts is complexe analysis which can take a long time like ladder reading or life and death reading. For all thing that you can simply compute incrementaly, it's good to have the possibility to enable them also during playouts and test if the improvement of the playouts value the slowdown. You never can guess it without testing. It's, in my opinion, one of the most difficult things to do. Choosing exactly what enabling and what not require a lot of testing of a lot of combination and the improvement of each of them is small so you have to do a lot of games for seeing if there is an improvement. It's my big damn that I don't have actually a computer that can be up and connected a lot of time to run my bot
Re: [computer-go] Elo move prediction
On Fri, Nov 20, 2009 at 10:21:25AM +0100, Thomas Lavergne wrote: On Thu, Nov 19, 2009 at 08:25:53PM -0800, Seth Pellegrino wrote: Apologies all for replying to myself so many times, but Darren Cook has been kind enough to help me clear the matter up. Essentially, I had misread his paper. I was trying to compute the expensive features Rémi uses for progressive widening as a move selector for playouts rather than the stripped down, speedy features he actually uses. Thank you all for your help in increasing my understanding. 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. A thing to always get in mind is compute incrementaly, so for each features you have to check each time you play a stone, if this play chane features somewhere on the board. For the liberties, of course that applies since they are used very often and take little memory (if you are sensible about it), but also always get in mind to avoid universal truths - not all features pay off to be maintained incrementally. E.g. for my heavy playouts, I tried to incrementally update features (mainly is-a-self-atari), but it turned out the cache hits for all the stored information _and_ the work involved in finding out what parts of the board I actually need to recompute noticeably outweighted the benefit. Maybe if I optimized it further, I would reduce the costs, but hardly much below the current costs of re-computing the features around the play condidate on each move. -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Elo move prediction
On Fri, Nov 20, 2009 at 10:31:21AM +0100, Petr Baudis wrote: For the liberties, of course that applies since they are used very often and take little memory (if you are sensible about it), but also always get in mind to avoid universal truths - not all features pay off to be maintained incrementally. E.g. for my heavy playouts, I tried to incrementally update features (mainly is-a-self-atari), but it turned out the cache hits for all the stored information _and_ the work involved in finding out what parts of the board I actually need to recompute noticeably outweighted the benefit. Maybe if I optimized it further, I would reduce the costs, but hardly much below the current costs of re-computing the features around the play condidate on each move. For sure, there is no universal truth, but my point here that recomputing some features have a hard additional cost. For drawing play random from weighted points you have to keep these weights and additional data-structure, in my case an array with sum of line's weights and the total sum of weights. If you need to recompute some features each time you have to draw a play, you have to update these data each time and next to restore them and this can also be very costly. In effect, there is some features where this cost is still inferior to the cost of maintaining them incrementaly, but for thoses I prefer to fall back to approximations that can be easily computed incrementaly. All of this really depend on the design of the engine I think, and I have to ponder a bit what I have said. It's probaly something more like: try to reduce to the minimum what you recompute each time in favor on computing it incrementaly because it's generaly more cheaper, but make some test ;-) For the cache point, the proble here is it's very hardware specific. My goban even with all fancy removed, never fit in a few L1 cache line, so in all case it will be in L2, and there is enought room there for me even on my old computer. As profiled, the prefetching done by the processor seems to work well in my case and for the moment there is no big problems here, but my big fear is that a small change in the engine can always make this fall by introducing a pattern badly handle by the processor... and another processor with small difference can badly handle the current situation, so I take all cache informations with care. Tom -- Thomas LavergneEntia non sunt multiplicanda praeter necessitatem. (Guillaume d'Ockham) thomas.laver...@reveurs.orghttp://oniros.org ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Elo move prediction
On Nov 20, 2009, at 12:08 AM, Petr Baudis wrote: On Thu, Nov 19, 2009 at 07:03:56PM -0800, Seth Pellegrino wrote: * I've already got a stable base that I'm working from (specifically, Peter Drake's Orego[1]). (You could also choose a better base to work from, e.g. libego, Pachi or Fuego, but maybe you are expected to use Orego for your project. ;-) In my defense (and Orego's), the speeds Seth has reported are not representative. With light playouts, running 4 threads on a 4-core, 3 GHz machine, Orego gets about 50 kpps on 9x9, about 16 on 19x19. (Of course, it's somewhat slower with heavy playouts, but not THAT bad!) If I only run playouts (no tree), I can get those up to 35 and 8 kpps with a single thread. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Elo move prediction
On Fri, Nov 20, 2009 at 05:19:01AM -0800, Peter Drake wrote: On Nov 20, 2009, at 12:08 AM, Petr Baudis wrote: On Thu, Nov 19, 2009 at 07:03:56PM -0800, Seth Pellegrino wrote: * I've already got a stable base that I'm working from (specifically, Peter Drake's Orego[1]). (You could also choose a better base to work from, e.g. libego, Pachi or Fuego, but maybe you are expected to use Orego for your project. ;-) In my defense (and Orego's), the speeds Seth has reported are not representative. With light playouts, running 4 threads on a 4-core, 3 GHz machine, Orego gets about 50 kpps on 9x9, about 16 on 19x19. (Of course, it's somewhat slower with heavy playouts, but not THAT bad!) If I only run playouts (no tree), I can get those up to 35 and 8 kpps with a single thread. Thank you, that's good to know then. :) Sorry that I assumed this is Orego's general speed. P.S.: So this also gives a good idea about speeds possible in java implementation (i.e. quite reasonable speeds). Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Elo move prediction
Just a wild guess here. One way to get catastrophically slow performance is to have superfluous nested loops. For instance, one could iterate over each board space, calling a routine to check for legality. If the legality routine also iterates over the whole board (perhaps by updating all liberty counts), then things will get pretty slow. This kind of bug can be elusive because it does give the correct results. - Dave Hillis 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. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Optiizing combinations of flags
On that topic, I have around 17 flag who enable or not features in my pure playouts bots, and I want to search the best combinations of them. I known this is almost a dream but does anyone know the best way to approximate this. Pebbles randomly chooses (using a zero asymptotic regret strategy) parameter values before each game. I literally never manually tune parameters for Pebbles. I just set up experiments, and put them on a parameter for my optimizer to manage. After a few hundred games it is clear what the right choices are. My favorite exploration strategy is a declining epsilon greedy strategy. I like it because it is a randomized strategy, so I can optimize all parameters concurrently using a single stream of games. In this strategy, one chooses a random number p, and then select the strategy with highest historical mean if p epsilon, and the strategy taken least often otherwise. If epsilon = C*log(n)/n, where n is the number of experiments so far, then the strategy has zero asymptotic regret. Pebbles has about 50 parameters right now. Most are pretty settled because they have thousands of games of experience. All are potentially modified before each game. Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
