[computer-go] Pseudo liberties: Detect 2 unique liberties?

[Isaac Deutsch]

Hi

I'm currently using the method described here to detect if a group is in
atari (1 real liberty):

http://computer-go.org/pipermail/computer-go/2007-November/012350.html

Thus I store the number of pseudo libs, the sum and the sum of squares for
each group.

Now for heavy playouts, it would be useful if I could somehow modify this so
I can easily detect if a group can be put into atari (meaning it has exactly
2 real liberties).

My intuition tells me it should be possible by also storing the sum of
positions^3. However, I can't quite wrap my head around how to do the check.
Has anyone looked into this before, and found an answer? I like this approach
because it's so easy and fast.

Regards,
Isaac
--
Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a
_______________________________________________
computer-go mailing list
compu...@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[Álvaro Begué]

When John Tromp and I were thinking about these things in 2007 we
decided to switch to counting real liberties instead of
pseudo-liberties. Someone (Rémi?) told us that in the end the
performance difference wasn't very large, and we verified this.

Álvaro.

[Mark Boon]

I can confirm, with a bit of optimization, counting real liberties is
only marginally slower than counting pseudo-liberties. So there's
really no benefit that I can see from using pseudo liberties.

Mark

[David Fotland]

Many Faces also counts real liberties, and is quite fast enough.

[Isaac Deutsch]

> Many Faces also counts real liberties, and is quite fast enough.
>

> > I can confirm, with a bit of optimization, counting real liberties is

> > only marginally slower than counting pseudo-liberties. So there's
> > really no benefit that I can see from using pseudo liberties.
> >
> > Mark
> >

> > > When John Tromp and I were thinking about these things in 2007 we

> > > decided to switch to counting real liberties instead of
> > > pseudo-liberties. Someone (Rémi?) told us that in the end the
> > > performance difference wasn't very large, and we verified this.
> > >
> > > Álvaro.
> > >

Thanks. What is a fast way to track liberties?

I thought about bit arrays. Merging to groups would take O(1), counting
takes O(1)-ish, and memory required would be small.

Of course I could also use STL's "set" structure, but I found it to be
quite slow - it implements a set using a RB-tree. This was actually the
reason I switched to pseudo libs.

-ibd.
--
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01

[wi...@swcp.com]

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.

Michael Wing

--

[Mark Boon]

On Thu, Apr 2, 2009 at 5:14 AM, <wi...@swcp.com> 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 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).

You can find my implementation in the reference-bots I made. The file
that counts liberties (and does a bit of other house-keeping) is here:

https://plug-and-go.dev.java.net/source/browse/plug-and-go/TesujiRefBot/source/tesuji/games/go/reference/monte_carlo/MCLibertyAdministration.java?rev=267&view=markup

Mark

[Isaac Deutsch]

> On Thu, Apr 2, 2009 at 5:14 AM, <wi...@swcp.com> 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.

--
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01

[Heikki Levanto]

On Fri, Apr 03, 2009 at 05:07:41PM +0200, Isaac Deutsch wrote:
> > > 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.

besides, most often you only need to know if a string has zero, one, two, or
many liberties, so the counting can be aborted early.

-H

--
Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk

[terry mcintyre]

---

From: Heikki Levanto <hei...@lsd.dk>

On Fri, Apr 03, 2009 at 05:07:41PM +0200, Isaac Deutsch wrote:
> > > 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.

> besides, most often you only need to know if a string has zero, one, two, or
many liberties, so the counting can be aborted early.

Most cases do test for zero/one/two/many, but if we want smart playouts, it helps to know in advance exactly how many liberties some strings have, compared to others in a capturing race. Any program which assumes that "n liberties is enough to live" may be tricked by a player who can count to n+1.

[wi...@swcp.com]

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, <wi...@swcp.com> 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.

_______________________________________________

[Isaac Deutsch]

I made some artificial tests where I do x inserts, 1 delete, 10 counts and
1 merge. For x=4 inserts, linear arrays are about 4 times faster. For x=8
inserts, linear arrays are about 3 times faster. From your data I calculated
an average liberty count of 2.8 (which seems low to me). This means that for
the used board sizes, the constant time merge does not pay off vs. the
constant time count.

So I can confirm that the linear arrays do seem to be faster, however I
haven't tested how they compare to pseudo libs. For heavier playouts, I
reckon that true liberties might be a bit faster and more useful.

Isaac

-------- Original-Nachricht --------
> Datum: Fri, 3 Apr 2009 10:22:37 MDT
> Von: wi...@swcp.com
> An: "computer-go" <compu...@computer-go.org>
> Betreff: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

> 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.
>

> data here.

--

Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01

[wi...@swcp.com]

Isaac,

My numbers were extracted from the insert() function,
so my numbers don't say how long the average search.
would be. When you place a stone on the board, you
immediately add up to 4 adjacent liberties, one at a
time. Never-the-less, it does say something.

I have intended to measure the distributions of all
set operations in the board funcions, but I have not
finished them.

Space is also very significant when choosing a
representation. Another issue is whether the board
can undo or rewind to saved positions. The arrays
that store liberties take 19*19*256 shorts or
184832 bytes. (A chain can only have about 2/3 of
the locations on the board as liberties, if you
follow the usual rules.) This overwhelms all
other data in the board.

Michael Wing

--

[Łukasz Lew]

What other methods have you tried?

Lukasz

[Isaac Deutsch]

I actually found a bug in my test, and corrected it. The gap is far less
large now. I found that for 10 inserts (and 1 delete, so 9 total libs),
The arrays are faster by a small amount. For 11 inserts (10 libs), bit
arrays are faster. This leads us to the question if groups in average have
<=10 or >10 liberties... :)

> Space is also very significant when choosing a
> representation.
>

> Michael Wing

Can you explain?

Isaac

--
Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a

[Mark Boon]

On Mon, Apr 6, 2009 at 10:54 AM, Isaac Deutsch <i...@gmx.ch> wrote:
This leads us to the question if groups in average have
> <=10 or >10 liberties... :)

Without actually having done any tests or measurements, I'd guess it's
much less than 10. More like 4.

Mark

[David Fotland]

In Many Faces' playouts I don't keep arrays of liberties. I just keep the
counts. In the older program I keep linked lists of liberties.

David

> -----Original Message-----
> From: computer-...@computer-go.org [mailto:computer-go-

[Łukasz Lew]

On Tue, Apr 7, 2009 at 07:40, David Fotland <fot...@smart-games.com> wrote:
> In Many Faces' playouts I don't keep arrays of liberties.  I just keep the
> counts.  In the older program I keep linked lists of liberties.

How do you count the number of liberties when you merge two groups?
Do you walk over both chains searching for duplicates in their empty
neighbourhoods (duplicated liberties)?

Lukasz

[David Fotland]

Yes, I walk both chains looking for duplicates. This is quite fast if done
efficiently, since group merging is rare enough. I found keeping the
liberty arrays to be slower since they are big, so there is more copy
overhead in the UCT tree, and they are not cache friendly.

[Łukasz Lew]

Thanks. What about linked lists?
They seem to be both compact and fast to merge and detect duplicates.
Why have you abandoned them?

Lukasz

[Colin Kern]

On Tue, Apr 7, 2009 at 12:33 PM, Łukasz Lew <lukas...@gmail.com> wrote:
> Thanks. What about linked lists?
> They seem to be both compact and fast to merge and detect duplicates.
> Why have you abandoned them?
>
> Lukasz
>

Or a Hash Set, which has constant time insert, delete, contains, and
size operations and guarantees no duplicates. Merging groups would be
linear, I think.

Colin

[Jason House]

This reminds me of a related question I had a while back. In a single
MCTS/UCT search node, how do people store the children? Does a node
contain summaries of all their children, or just pointers to the
children?

Pure pointers are simple but requires allocating many more objects,
including greater hashtable usage. Local summaries should be more
cache friendly, but may miss out on updates to children searched
through other paths.

Sent from my iPhone

On Apr 7, 2009, at 12:33 PM, Łukasz Lew <lukas...@gmail.com> wrote:

> Thanks. What about linked lists?
> They seem to be both compact and fast to merge and detect duplicates.
> Why have you abandoned them?
>
> Lukasz
>

> On Tue, Apr 7, 2009 at 17:42, David Fotland <fotland@smart-

> games.com> wrote:
>> Yes, I walk both chains looking for duplicates. This is quite fast
>> if done
>> efficiently, since group merging is rare enough. I found keeping the
>> liberty arrays to be slower since they are big, so there is more copy
>> overhead in the UCT tree, and they are not cache friendly.
>>
>> David
>>
>>> -----Original Message-----
>>> From: computer-...@computer-go.org [mailto:computer-go-
>>> bou...@computer-go.org] On Behalf Of Lukasz Lew
>>> Sent: Tuesday, April 07, 2009 2:32 AM
>>> To: computer-go
>>> Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique
>>> liberties?
>>>

>>> On Tue, Apr 7, 2009 at 07:40, David Fotland <fotland@smart-

[Łukasz Lew]

2009/4/7 Colin Kern <colin...@gmail.com>:

> On Tue, Apr 7, 2009 at 12:33 PM, Łukasz Lew <lukas...@gmail.com> wrote:
>> Thanks. What about linked lists?
>> They seem to be both compact and fast to merge and detect duplicates.
>> Why have you abandoned them?
>>
>> Lukasz
>>
>
> Or a Hash Set, which has constant time insert, delete, contains, and
> size operations and guarantees no duplicates.  Merging groups would be
> linear, I think.

Hash set is usually bigger than array of liberties.
The bigger problem is that you can't get the single element of singleton.
(btw you don't need hashing to store liberties as liberties usually
are integers from some not too big interval)

[Adriaan van Kessel]

computer-...@computer-go.org wrote on 07-04-2009 18:33:34:

> Thanks. What about linked lists?
> They seem to be both compact and fast to merge and detect duplicates.
> Why have you abandoned them?

Linked lists have a terrible cache behaviour: every pointer (or index)
dereference has a nearly 100% chance of causing a cache miss.

Lists as arrays and bitmaps have the smallest cache footprint.
Not storing them at all, but recomputing them as David Fotland does
(only in the playouts) has no memory footprint at all.

AvK


Disclaimer RIVM

[Łukasz Lew]

2009/4/7 Adriaan van Kessel <Adriaan.v...@rivm.nl>:

It's quite easy and efficient to put all lists (cyclic, linked in one
direction) of liberties (on one 19x19 board)
into 4*19*19*sizeof (vertex) array. If vertex is int32 then it is about 1.5 kB.
Is it too much for cache?
Which cache we are talking about?

Lukasz

>
> AvK
>
>
> Disclaimer RIVM

[Gian-Carlo Pascutto]

David Fotland wrote:
> Yes, I walk both chains looking for duplicates. This is quite fast if done
> efficiently, since group merging is rare enough. I found keeping the
> liberty arrays to be slower since they are big, so there is more copy
> overhead in the UCT tree, and they are not cache friendly.

Leela also just keeps a liberty count. When two strings are merged, it
walks the shortest chain and looks for empty neighbours that are shared.

This is very simple, and very fast.

--
GCP

[Łukasz Lew]

On Wed, Apr 8, 2009 at 01:13, Darren Cook <dar...@dcook.org> wrote:
>>> Linked lists have a terrible cache behaviour: every pointer (or index)
>>> dereference has a nearly 100% chance of causing a cache miss.

>>>...

>>
>> It's quite easy and efficient to put all lists (cyclic, linked in one
>> direction) of liberties (on one 19x19 board)
>> into 4*19*19*sizeof (vertex) array. If vertex is int32 then it is about 1.5 kB.
>

> Hi Lukasz,  (private reply, but reply to the list is fine by me)
> Do you have some code demonstrating the above idea? It sounds
> interesting, but I cannot grasp what the data and algorithm look like.

4*19*19*4 is around 5.5 kB
On 9x9 it will be less than 1.5 kB

My mistake.

Are you still interested?

>
> Darren
>
>
> --
> Darren Cook, Software Researcher/Developer
> http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
>                        open source dictionary/semantic network)
> http://dcook.org/work/ (About me and my work)
> http://dcook.org/blogs.html (My blogs and articles)

[Darren Cook]

>> Do you have some code demonstrating the above idea? It sounds
>> interesting, but I cannot grasp what the data and algorithm look like.
>
> 4*19*19*4 is around 5.5 kB
> On 9x9 it will be less than 1.5 kB
>

> Are you still interested?

My own method is a large pre-allocated pool of Chain objects, which use
std::vector, or fixed-size arrays, to store liberties. So I'm using a
lot more memory. If your idea actually works and is just as quick then
of course I'm interested.

[Łukasz Lew]

On Wed, Apr 8, 2009 at 09:12, Darren Cook <dar...@dcook.org> wrote:
>>> Do you have some code demonstrating the above idea? It sounds
>>> interesting, but I cannot grasp what the data and algorithm look like.
>>
>> 4*19*19*4 is around 5.5 kB
>> On 9x9 it will be less than 1.5 kB
>>
>> Are you still interested?
>
> My own method is a large pre-allocated pool of Chain objects, which use
> std::vector, or fixed-size arrays, to store liberties. So I'm using a
> lot more memory. If your idea actually works and is just as quick then
> of course I'm interested.

The problem is similar to the problem of storing lists of stones in one group.
For a reference you can take a look for a libego implementation:
The file is in the spirit one class for all including unit tests, so
it's big. But just ignore it and track
chain_next_v

http://github.com/lukaszlew/libego/blob/00264d126ef6aa909dd7f52a668e8fe33e62aeb4/ego/board.cpp

chain_next_v is essentially a map vertex -> next_vertex (vertex is
board location).
chain_next_v implements cyclic linked lists.
The trick is that it is implemented as an array of size 19*19*sizeof(vertex).
This is possible because one vertex can be always only in one group.

Now merging groups is as simple as crossing the lists (line 500).

If you have any questions so far, go ahead and ask :)

Now the liberties. One liberty can be in many groups. But in only as many as 4.
Let's call links between neighboring vertices "pseudoliberties".
Now we can create a structure similar to chain_next_v that track all
pseudo-liberties of a group.
It would be again map implemented as an array indexed by vertex and
direction (N,W,S,E).

Now when you merge you just go over this list and throw away
duplicates. This can be done in linear time
using another map-array vertex -> bool. That will have info whether
particular liberty (vertex without direction) was already in visited.

Hope this helps :)
Lukasz

[Darren Cook]

>> lot more memory. If your idea actually works and is just as quick then
>> of course I'm interested.

> ...

> For a reference you can take a look for a libego implementation:

Ah, so you already use this idea in libego? That is all I need to know,
because, unless something has changed, libego does light playouts faster
than any other program. (?)

[Łukasz Lew]

>> ...
>> For a reference you can take a look for a libego implementation:
>
> Ah, so you already use this idea in libego?

libego uses this idea only for list of stones in chain.
list of liberties are not implemented.
but I guess I will implement it sometime soon.

> That is all I need to know,
> because, unless something has changed, libego does light playouts faster
> than any other program. (?)

I don't know about the speed of other programs.

libego currently does 40-45 kpps / GHz.
So if you have 3 GHz processor you will get around 130k playouts per second.

Lukasz Lew

[Isaac Deutsch]

Hi Lukasz,

I think I understand the way it is done for storing the stones; I do it
exactly the same way.

For the liberties: Does the index of the direction (NWSE) state where the
chain is in respect to the liberty? So if you place a single stone on the
board at "position", you add 4 liberties and link them:
- left of position, E
- right of position, W
- below of position, N
- above of position, S
Is that correct?

I have another question. How do you efficiently track visited positions to
avoid superko?
I use zobrist hashing, but the memory it uses is quite big, and I think
copying it from board to board takes a lot of time. Of course I don't do
superko checks in the playouts, but in the UCT tree I have to check for it.

Isaac

> Now the liberties. One liberty can be in many groups. But in only as many
> as 4.
> Let's call links between neighboring vertices "pseudoliberties".
> Now we can create a structure similar to chain_next_v that track all
> pseudo-liberties of a group.
> It would be again map implemented as an array indexed by vertex and
> direction (N,W,S,E).
>
> Now when you merge you just go over this list and throw away
> duplicates. This can be done in linear time
> using another map-array vertex -> bool. That will have info whether
> particular liberty (vertex without direction) was already in visited.
>
> Hope this helps :)
> Lukasz

--

Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a

[Łukasz Lew]

On Wed, Apr 8, 2009 at 13:10, Isaac Deutsch <i...@gmx.ch> wrote:
> Hi Lukasz,
>
> I think I understand the way it is done for storing the stones; I do it
> exactly the same way.
>
> For the liberties: Does the index of the direction (NWSE) state where the
> chain is in respect to the liberty? So if you place a single stone on the
> board at "position", you add 4 liberties and link them:
> - left of position, E
> - right of position, W
> - below of position, N
> - above of position, S
> Is that correct?

Yep.
I'm thinking about implementing it in libego with heavy playouts for
demonstration.
Maybe It will get libego some attention. :)

>
> I have another question. How do you efficiently track visited positions to
> avoid superko?
> I use zobrist hashing, but the memory it uses is quite big, and I think
> copying it from board to board takes a lot of time. Of course I don't do
> superko checks in the playouts, but in the UCT tree I have to check for it.

I use zobrist hashing as well. But the random base is separated from
board and shared so I don't copy it.
I copy just a xor hash which is no more than 8 bytes per board.

[Gunnar Farnebäck]

Łukasz Lew wrote:
>>> ...
>>> For a reference you can take a look for a libego implementation:
>> Ah, so you already use this idea in libego?
>
> libego uses this idea only for list of stones in chain.
> list of liberties are not implemented.
> but I guess I will implement it sometime soon.

You can find this idea in the GNU Go montecarlo board implementation,
although with doubly linked lists, see for example
http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c
starting at line 43. This code is doing quite a lot of book-keeping to
support tunable pattern-based heavy playouts, however, so it may be
easier to start with a previous iteration of the code at
http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b

/Gunnar

[Isaac Deutsch]

> Yep.
> I'm thinking about implementing it in libego with heavy playouts for
> demonstration.
> Maybe It will get libego some attention. :)

Thanks for your answers. I'm impressed with the speed of your library.

> I use zobrist hashing as well. But the random base is separated from
> board and shared so I don't copy it.
> I copy just a xor hash which is no more than 8 bytes per board.

I have an array that stores for each position and color combination a random
ushort (2 bytes). It is global. Also every board has its own hash which
is derived from all the positions/colors that have been played xored into it.
So I think it is similar to yours in these aspects.

What I don't understand is: How do you know from just a single xor hash
if you have played a certain position/color before? Don't you somehow have
to store for each possible hash (which is 2 bytes in my example) if it has
been used before? The amount of possible hashes even for 2 bytes is quite large.

-ibd

[Colin Kern]

On Wed, Apr 8, 2009 at 2:07 PM, Isaac Deutsch <i...@gmx.ch> wrote:
>
> What I don't understand is: How do you know from just a single xor hash
> if you have played a certain position/color before? Don't you somehow have
> to store for each possible hash (which is 2 bytes in my example) if it has
> been used before? The amount of possible hashes even for 2 bytes is quite large.
>

Like any hash function, multiple board positions can hash to the same
value. The idea is that the probability of encountering two board
positions in the same game that have the same hash value is so low,
that if you get a duplicate hash value you are practically guaranteed
that it's a superko.

Colin

[Isaac Deutsch]

> Like any hash function, multiple board positions can hash to the same
> value. The idea is that the probability of encountering two board
> positions in the same game that have the same hash value is so low,
> that if you get a duplicate hash value you are practically guaranteed
> that it's a superko.
>
> Colin

Yes, that is clear, but Lukasz didn't mention how he stores the past hash
values. Sorry if my statement was not clear.

Isaac

--
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01

[Łukasz Lew]

Ah, that's what you mean. :)
Actually I don't care too much about superko. I just care about the
move the genmove returns.
It would be better If I check at least some part of MCTS tree.
I just replay the game to check whether there is a hash collision. (I
use 64 bits)

If I would wan't fast checking I would probably use bloom filter.
http://en.wikipedia.org/wiki/Bloom_filter

Lukasz

[Łukasz Lew]

2009/4/8 Gunnar Farnebäck <gun...@lysator.liu.se>:

> Łukasz Lew wrote:
>>>> ...
>>>> For a reference you can take a look for a libego implementation:
>>> Ah, so you already use this idea in libego?
>>
>> libego uses this idea only for list of stones in chain.
>> list of liberties are not implemented.
>> but I guess I will implement it sometime soon.
>
> You can find this idea in the GNU Go montecarlo board implementation,
> although with doubly linked lists, see for example
> http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c
> starting at line 43. This code is doing quite a lot of book-keeping to
> support tunable pattern-based heavy playouts, however, so it may be
> easier to start with a previous iteration of the code at
> http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b

Indeed that's almost exactly what I meant.
I can see that you are using doubly linked list to have a constant
time liberty_edge removal. Is there any other reason?
Have you considered amortized constant time (we remove it when we have
an occasion) approach?

Lukasz
PS
This is nice code to read :)

[Gunnar Farnebäck]

Łukasz Lew wrote:
> 2009/4/8 Gunnar Farnebäck <gun...@lysator.liu.se>:
>> Łukasz Lew wrote:
>>>>> ...
>>>>> For a reference you can take a look for a libego implementation:
>>>> Ah, so you already use this idea in libego?
>>> libego uses this idea only for list of stones in chain.
>>> list of liberties are not implemented.
>>> but I guess I will implement it sometime soon.
>> You can find this idea in the GNU Go montecarlo board implementation,
>> although with doubly linked lists, see for example
>> http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c
>> starting at line 43. This code is doing quite a lot of book-keeping to
>> support tunable pattern-based heavy playouts, however, so it may be
>> easier to start with a previous iteration of the code at
>>
http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b
>
> Indeed that's almost exactly what I meant.
> I can see that you are using doubly linked list to have a constant
> time liberty_edge removal. Is there any other reason?

To be honest I don't really remember but that was probably the most
important reason. Another possibility is that I became annoyed by the look
of the code needed to traverse around a single linked cyclic list. :-)

> Have you considered amortized constant time (we remove it when we have
> an occasion) approach?

No, not seriously at least. Actually this code hasn't been optimized
at all, so there should be some gains left to be made.

> Lukasz
> PS
> This is nice code to read :)

Thanks.

[wi...@swcp.com]

Lukasz,

My performance test suite did 7 ways of tracking liberties:
* dense linked lists, (where 4 * number of positions are allocated)
* sparse linked lists, (where 256 * number of positions are allocated)
* arrays of liberties, (256 * number of positions are allocated)
* trivial pseudo-liberties
* boesch computation for pseudo-liberties
* bitsets
* bitsets, with each bit in a separate word.

I tested all of them using 2 techniques:
* simple mc, (which never asked for the list of liberties for a group)
Note that it also tests reseting the board in 3 ways.
* ladder reading exercises, which asked for the liberties of a group
and used undo.

Results are were pretty striking. Below is raw data.
Tests were on a 3 year old Core2.
* for pure mc: simple pseudo liberties was by far the fastest.
* for ladder reading: arrays of liberties was by far the fastest.
* as noted in other emails, linked lists have horrible cache behavior.
* So, as far as I can see the only question is whether you will
do any classic reading or not, which will determine the
best implementation.

Michael Wing

-------------------

DENSE LINKS
normal 324 moves: total 3000 ms, each game 0.300000 ms, 3333.333333 games/sec
undo 324 moves: total 3860 ms, each game 0.386000 ms, 2590.673575 games/sec
reset 324 moves: total 3062 ms, each game 0.306200 ms, 3265.839321 games/sec
ladder: total 3469 ms, each ladder 0.346900 ms, 2882.675123 ladders/sec

SPARSE LINKS
normal 324 moves: total 7109 ms, each game 0.710900 ms, 1406.667604 games/sec
undo 324 moves: total 7703 ms, each game 0.770300 ms, 1298.195508 games/sec
reset 324 moves: total 10890 ms, each game 1.089000 ms, 918.273646 games/sec
ladder: total 8062 ms, each ladder 0.806200 ms, 1240.387001 ladders/sec

BOESCH PSEUDO LIBERTIES
normal 324 moves: total 2281 ms, each game 0.228100 ms, 4384.042087 games/sec
undo 324 moves: total 3422 ms, each game 0.342200 ms, 2922.267680 games/sec
reset 324 moves: total 2532 ms, each game 0.253200 ms, 3949.447077 games/sec
ladder: total 5797 ms, each ladder 0.579700 ms, 1725.030188 ladders/sec

SIMPLE PSEUDO LIBERTIES
normal 324 moves: total 1985 ms, each game 0.198500 ms, 5037.783375 games/sec
undo 324 moves: total 2328 ms, each game 0.232800 ms, 4295.532646 games/sec
reset 324 moves: total 1922 ms, each game 0.192200 ms, 5202.913632 games/sec
ladder: total 4890 ms, each ladder 0.489000 ms, 2044.989775 ladders/sec

ARRAYS
normal 324 moves: total 2578 ms, each game 0.257800 ms, 3878.975950 games/sec
undo 324 moves: total 3313 ms, each game 0.331300 ms, 3018.412315 games/sec
reset 324 moves: total 2703 ms, each game 0.270300 ms, 3699.593045 games/sec
ladder: total 2703 ms, each ladder 0.270300 ms, 3699.593045 ladders/sec

BITSET
normal 324 moves: total 3453 ms, each game 0.345300 ms, 2896.032436 games/sec
undo 324 moves: total 4203 ms, each game 0.420300 ms, 2379.252915 games/sec
reset 324 moves: total 3828 ms, each game 0.382800 ms, 2612.330199 games/sec
ladder: total 6735 ms, each ladder 0.673500 ms, 1484.780995 ladders/sec

BITSET IN WORDS
normal 324 moves: total 6172 ms, each game 0.617200 ms, 1620.220350 games/sec
undo 324 moves: total 7203 ms, each game 0.720300 ms, 1388.310426 games/sec
reset 324 moves: total 10157 ms, each game 1.015700 ms, 984.542680 games/sec
ladder: total 7172 ms, each ladder 0.717200 ms, 1394.311210 ladders/sec

> What other methods have you tried?
>
> Lukasz

>
> On Thu, Apr 2, 2009 at 17:14, <wi...@swcp.com> 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.
> >

> > Michael Wing
> >
> >> > Many Faces also counts real liberties, and is quite fast enough.
> >> >
> >>
> >> > > I can confirm, with a bit of optimization, counting real liberties
is
> >> > > only marginally slower than counting pseudo-liberties. So there's
> >> > > really no benefit that I can see from using pseudo liberties.
> >> > >
> >> > > Mark
> >> > >
> >>
> >> > > > When John Tromp and I were thinking about these things in 2007 we
> >> > > > decided to switch to counting real liberties instead of
> >> > > > pseudo-liberties. Someone (Rémi?) told us that in the end the
> >> > > > performance difference wasn't very large, and we verified this.
> >> > > >
> >> > > > Álvaro.
> >> > > >
> >>
> >> Thanks. What is a fast way to track liberties?
> >>
> >> I thought about bit arrays. Merging to groups would take O(1), counting
> >> takes O(1)-ish, and memory required would be small.
> >>
> >> Of course I could also use STL's "set" structure, but I found it to be
> >> quite slow - it implements a set using a RB-tree. This was actually the
> >> reason I switched to pseudo libs.
> >>
> >> -ibd.

> >> --
> >> Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
> > http://www.gmx.net/de/go/multimessenger01

> >> _______________________________________________
> >> computer-go mailing list
> >> compu...@computer-go.org
> >> http://www.computer-go.org/mailman/listinfo/computer-go/
> >>
> >
> >
> >

> > --

> >
> >
> >
> > _______________________________________________
> > computer-go mailing list
> > compu...@computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> _______________________________________________
> computer-go mailing list
> compu...@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>

--

[Łukasz Lew]

Can you give some more info about experimental setup and the
algorithms you used?

On Thu, Apr 9, 2009 at 01:42, <wi...@swcp.com> wrote:
> Lukasz,
>
> My performance test suite did 7 ways of tracking liberties:
> * dense linked lists, (where 4 * number of positions are allocated)

I guess this is what gnugo-montecarlo implemented?

> * sparse linked lists, (where 256 * number of positions are allocated)

?

> * arrays of liberties, (256 * number of positions are allocated)

Is it like regular gnugo board implementation.
> * trivial pseudo-liberties
like libego I guess.

> * boesch computation for pseudo-liberties

an link?
> * bitsets
one bit per board location per string?

> * bitsets, with each bit in a separate word.

?

>
> I tested all of them using 2 techniques:
> * simple mc, (which never asked for the list of liberties for a group)
>  Note that it also tests reseting the board in 3 ways.

one playout over and over again, or many randomized playouts? (you
mention 324 moves)

> * ladder reading exercises, which asked for the liberties of a group
>  and used undo.

>
> Results are were pretty striking. Below is raw data.
> Tests were on a 3 year old Core2.
> * for pure mc: simple pseudo liberties was by far the fastest.
> * for ladder reading: arrays of liberties was by far the fastest.
> * as noted in other emails, linked lists have horrible cache behavior.

can you elaborate on that?
Does it apply to dense lists?

In general I'm about to implement dense lists.
What is slow about them in your implementation?
(in playouts)

[wi...@swcp.com]

£ukasz,

My code is online in the directory:
http://pages.swcp.com/~wing/cgbg/

The file cgbg is a ruby program, which
generates a C program, as well as a performance
test. So the only difference is the
desired distinction.

My implementation of dense links is similar
to, but not identical to the gnugo version.

The file README has instructions. The
functional test are broken. (Sorry)
Use the config file call "config" to
compare liberty representations.
The other config files compare a wide
variety of other go board representation
attributes.

Let me know if you want a specific
data structure tested, and I can help
write the performance test.

Michael Wing