You are noting that you spend most of your time in counting liberties. I
am not an expert at computer Go, but I know a little bit about this so I
can write an answer for you.
There is a paper out there written by someone who is probably on this list
that talks about a few efficient datastructures for computer Go. My
apologies but I can neither remember the paper where I read this, nor the
author.
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 data structure supports adding and removing liberties, and crucially,
it supports adding the same liberty multiple times, and only counting it
once for atari purposes. So, when you add a stone to a chain, you just
examine the 4 neighbors of the stone, and for each one, if it's empty, add
it to the liberties for that chain. Double or triple-counting the same
point will still work.
Address each point on the board as an integer. When you add a liberty,
that looks like: void add(int pt) { ++liberty_count; liberty_sum += pt;
liberty_sum_squares += pt*pt; }
Removing liberties and merging chains is pretty straightforward.
If you add point 3 to the chain four times, then you have {
liberty_count=4; liberty_sum=12; liberty_sum_squares=36; }
If you then remove point 3 four times, you get back to empty {
liberty_count=0; liberty_sum=0; liberty_sum_squares=0; }
isInAtari() looks like: (liberty_count > 0) && (liberty_count *
liberty_sum_squares) == (liberty_sum * liberty_sum)
(Note that this answers 'true' for the above case of adding point 3 to the
chain 4 times... This chain is in atari because it only has one liberty,
even though it was multiply-added)
If the chain is in atari, then the atari point is (liberty_sum /
liberty_count);
This allows you to track information for life/death of groups with very
little overhead. But if your heavy playouts need to know actual liberty
count for capture race etc, then you'll still need something else.
-D
On Wed, Oct 14, 2015 at 5:09 PM, Gonçalo Mendes Ferreira <go...@sapo.pt>
wrote:
> This reply is to both Erik and Petr,
>
> I was running a profile on the program just now. It spends about 90%
> updating information to speed up the playout, these are captures and
> liberties after play and the resulting 3x3 codified part of the board.
> These are updated when needed, so about 4-8 intersections per play on
> average.
>
> In the updating information part, the most costly is a recursive function
> that counts liberties (it spends itself 33% of all time).
>
> It is in C in a modern PC, board size is 19x19. The heavy playout count in
> the meanwhile was raised to 66 per sec/thread. I'm doing a lot of
> optimizing and in the playouts part there is not much I can thin out more.
> With these profiling results I'll attack the liberty counting primitives
> next. You probably know some method more efficient than a recursive search
> over the board surface.
>
> Gonçalo
>
>
> On 15/10/2015 00:43, Erik van der Werf wrote:
>
>> I don't know, what language are you using? Did you do any
>> optimizations? How many clock cycles does it take your program on
>> average to make and undo a move (just counting the core board update)?
>>
>> BTW you didn't specify board size and hardware, so I assumed 19x19 and
>> a modern PC.
>>
>> Erik
>>
>> On Thu, Oct 15, 2015 at 12:56 AM, Gonçalo Mendes Ferreira <go...@sapo.pt>
>> wrote:
>>
>>> Really? I didn't mention it but it's uses MCTS-UCT with RAVE, progressive
>>> pruning, mercy thresholds and max playout depth, etc. What could I be
>>> missing that is that much of a boost in the playouts, in your experience?
>>>
>>> Gonçalo
>>>
>>>
>>> On 14/10/2015 23:40, Erik van der Werf wrote:
>>>
>>>> You should be able to do at least 50 times faster.
>>>>
>>>> Erik
>>>>
>>>> On Thu, Oct 15, 2015 at 12:27 AM, Gonçalo Mendes Ferreira <
>>>> go...@sapo.pt>
>>>> wrote:
>>>>
>>>>> Hi, I've been searching the mailing list archive but can't find an
>>>>> answer
>>>>> to
>>>>> this.
>>>>>
>>>>> What is currently the number of playouts per thread per second that the
>>>>> best
>>>>> programs can do, without using the GPU?
>>>>>
>>>>> I'm getting 2075 in light playouts and just 55 in heavy playouts. My
>>>>> heavy
>>>>> playouts use MoGo like patterns and are probability distributed, with
>>>>> liberty/capture counts/etc only updated when needed, so it should be
>>>>> pretty
>>>>> efficient.
>>>>>
>>>>> What would be a good ballpark for this?
>>>>>
>>>>> Thank you,
>>>>> Gonçalo F.
>>>>>
>>>>
> _______________________________________________
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
_______________________________________________
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
