Very nice speed up Goncalo! This prompted me to check my playout speed and with the recent addition of 3x3 patterns I'm now down to 6pps on 19x19. Whoops! ;) I may need to do some optimisations ...
Urban On Fri, Oct 16, 2015 at 1:09 AM, Gonçalo Mendes Ferreira <[email protected]> wrote: > Thanks everyone for your responses. This is followup after implementing > Dusty Leary's very complete suggestion. > > My program is now running 547 playouts/sec and thread, but a lot of > optimizations were removed so I'm sure there's space for growth here. It is > now spending 75% of the time in the selection of the play itself by > probability distribution. The patterns were simplified to not needing > actual liberty/capture counts. > > I'm also considering the whole board for pattern matching only about 1/4 > of the time, like Petr suggested; simplified ko detection, hardcoded some > patterns, cached all matchable pattern configurations at startup (that's > 351882 from just 13 base patterns from GNU Go's montegnu_classic), etc. > > As for more complete heuristics, my UCT search does have itself some very > heavy heuristics and needs real liberty counts, but I need faster playouts > before feeling the impact of the UCT states initialization. > > Big thanks to Dusty for the structure explanation. I had already thought > of something similar but never tested it because group captures seemed too > heavy. I was wrong since the real cost is in testing atari/counting > liberties. > > Thanks again, > Gonçalo > > > On 15/10/2015 10:30, Petr Baudis wrote: > >> On Wed, Oct 14, 2015 at 06:00:56PM -0700, Dusty Leary wrote: >> >>> The trick to avoid recursively counting liberties: >>> Track the liberties for a group/chain using a simplified data structure >>> that looks like struct ChainLibertyInfo { int liberty_count; int >>> liberty_sum; int liberty_sum_squares; } >>> >>> The interesting thing about this data structure is that it's a Set which >>> can answer the isInAtari() query and the getAtariPoint() query, without >>> having to track a lot of data. But it doesn't support enumerating all >>> the >>> liberties. >>> >> This is a nice trick I once implemented too. But for any kind of >> interesting tactical evaluation (which is an important ingredient for >> a strong program), you end up needing to be able to enumerate at least >> two liberties, ideally even three. Then, you can't use this trick. >> >> >> In Pachi, I got inspired by GNUGo and track liberties only up to >> N liberties (N=5 I think). Any group with more than N is regarded >> as having N libs. This cuts off a lot of overhead, IIRC it helped >> me a lot. >> >> If you are doing probability distribution stuff, I think a popular >> trick is first deciding whether you are going to look just in last move >> neighborhood or tenuki; most of the time, your roll will go with the >> last move neighborhood and you won't need to spend a lot of time going >> through the whole board. >> >> In general, you may simply want to look at how other programs do >> things... There's plenty of fast open source stuff out there. >> >> > _______________________________________________ > Computer-go mailing list > [email protected] > http://computer-go.org/mailman/listinfo/computer-go > -- Blog: http://bettong.net/ Twitter: https://twitter.com/ujh Homepage: http://www.urbanhafner.com/
_______________________________________________ Computer-go mailing list [email protected] http://computer-go.org/mailman/listinfo/computer-go
