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.
Mark
> > 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
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
--
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:
Mark
> 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
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
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.
_______________________________________________
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
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
--
Lukasz
> 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
Without actually having done any tests or measurements, I'd guess it's
much less than 10. More like 4.
Mark
David
> -----Original Message-----
> From: computer-...@computer-go.org [mailto:computer-go-
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
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
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-
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)
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
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
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)
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
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. (?)
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
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
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.
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
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
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
If I would wan't fast checking I would probably use bloom filter.
http://en.wikipedia.org/wiki/Bloom_filter
Lukasz
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 :)
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.
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/
>
--
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)
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