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
