Isaac,
Most groups have only say 4 to 8 liberties. This is why simple arrays of
liberty locations work so well. The new Intel CPUs have instructions
that can search strings 16 bytes at a time, so it could run even faster.
Bit vectors also work, but if you want a true liberty count, then you have
to avoid counting (1 or 1) as 2, which is the pseudo liberty problem, and
which takes more code to write and more time to compute.
When I started, I wanted to find a better implementation than gnugo, and
I was unable to do so. Of course one can refine or simplify the gnugo code
in many different ways, but gnugo has all of the good ideas.
Michael Wing
PS: Here is the data for how many times the program tried to insert
a stone into a chain that has x liberties or x adjacencies. It was taken
from a run that combined monte carlo simulations and ladder reading
exercises. Note that there are only 2% as many liberties/adjacencies
of size 8 as there are of size 0. Chains with liberties/adjacency lists
of size 16 are so few as to be irrelevant.
0 => 4662825
1 => 3524214
2 => 2323725
3 => 1167185
4 => 368184
5 => 245659
6 => 167392
7 => 117655
8 => 84715
9 => 61126
10 => 44407
11 => 32309
12 => 24105
13 => 17639
14 => 13111
15 => 9935
16 => 7378
17 => 5417
18 => 3975
19 => 2900
20 => 2111
21 => 1566
22 => 1055
23 => 783
24 => 616
25 => 399
26 => 290
27 => 221
28 => 174
29 => 127
30 => 95
31 => 71
32 => 60
33 => 44
34 => 15
35 => 4
36 => 2
37 => 1
38 => 1
39 => 0
40 => 0
41 => 0
42 => 0
>> On Thu, Apr 2, 2009 at 5:14 AM, <[email protected]> wrote:
>>> Isaac,
>>>
>>> I implemented about 6 way to track liberties,
>>> a couple years ago, and measured the running
>>> performance, and by far the best is also the
>>> simplest: keep an array of liberties for each
>>> chain, and do a simple linear search.
>>>
>>> This may seem slow, but it has a couple real
>>> advantages. First, it works with the cache
>>> to maximize locality. Second it is very simple.
>>>
>
> This *does* seem slow, even when caching the number of liberties. You
> mentioned that you did this a couple years ago, do you think it still holds
> true? Thank you for the information.
>
>> This is what I do too. I never bothered with bit-arrays but possibly
>> that's simply because I fail to see how you can merge two chains and
>> count liberties in O(1).
>
> Merging would be a simple OR operation. Counting can be done, for example,
> with some kind of binary search. Counting the bits set has been well
> researched and many different algorithms exist.
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
