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 <lukasz....@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 <fotl...@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-go-boun...@computer-go.org [mailto:computer-go-
boun...@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 <fotl...@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
-----Original Message-----
From: computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org] On Behalf Of w...@swcp.com
Sent: Monday, April 06, 2009 10:36 AM
To: computer-go
Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique
liberties?
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
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: w...@swcp.com
An: "computer-go" <computer-go@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.
On Thu, Apr 2, 2009 at 5:14 AM, <w...@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.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
--
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kan
n`s mit
allen:
http://www.gmx.net/de/go/multimessenger01
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
--
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
