On 12/15/06, Luke Gustafson <[EMAIL PROTECTED]> wrote:
Are you using the union-find algorithm with path compression for joining
strings? It's very simple and very fast.
http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests
The other main thing to consider is reducing branch mispredictions, which
(I'm guessing) could very well use more clock cycles on a P4 than performing
the actual calculations themselves. I think this is why the next_stone list
is faster than using e.g. a recursive algorithm, which involves a lot of
if's that cannot be predicted.
I confirm branches are most costly.
Removing 1 not needed "if" gave me speedup of 5%.
Compact data I think is unnecessary, although perhaps eliminating the String
struct would speed things up a tad. In fact, on a P4, shift operations are
slower than L1 cache memory retrievals, so fancy packing of data is not
worthwhile. As long as all data fits in the L1 cache it should be max
speed.
:)
I am working on a program myself, and I will be porting it to assembly at
some point; right now I am just experimenting with the algorithm design in
C. (Although this happens pretty slowly since I am very busy with work.) I
think that this sort of algorithm is perfect for assembly language, where
hand-optimization can be much better than compiler optimization. I will let
you know how it turns out compared to Lukasz :)
I took a lot of willpower to stop myself from rewriting in assembler :)
I guess I would obtain then about 50-60 pps :) but any more complex
than random moves external algorithm is the bottle neck.
Anyway I would like to advertise HLA.
>> At the time of Your post I've had it already implemented and regarded
>> it like "my sweet secret" :)
>
> I don't know how sweet this secret is, but it does help. I just
> implemented it in Lazarus and I get about a 20% speedup. That's not
> bad, but nothing to write home about. To a chess programmer this is
> rather enormous! I am guessing that the win would be much greater on
> bigger boards.
>
> In principle it would probably be FAR faster, but it adds extra
> complexity,
> operations and overhead to executing a move which subtracts some from
> the
> savings.
>
> The question is: "what is the best way to implement it?" The problem
> is that you now must track pseudo liberty counts for every chain on
> the board. This is more complicated obviously.
>
> Every time a stone is placed or removed, 4 additional entries must be
> accessed in order to update the pseudo liberty counts.
>
> It's still a good trade-off because the testing for whether a move
> is a capture or suicide is cheap.
>
> I'm reviewing my design now and I think I see some ways to improve.
>
> Here is the current data structure (assuming the 9x9 board):
>
> 1. A 10x11 board (actually 10x11 plus 1 for diagonal checking.)
> 0 = empty
> 1 = white
> 2 = black
> 4 = off-board points.
>
> 2. Another 10x11 board-like array - if there is a occupied point on
> the board this array contains the index (hash key) of a "string"
> data type.
>
> 3. A list of string data types (a struct in C):
> 1. stone count
> 2. pseudo liberties for the whole string
> 3. a reference stone.
>
> To save time, the list of strings is really more like a hash table,
> not a proper list. It's a perfect hash table because the keys will
> never collide. I use the reference stone as the key for each string
> which is generally the first stone placed in the string. So the hash
> key computation is just a table lookup and is the only thing the
> second table is used for.
>
> So to summarize, I really have 3 10x11 arrays, one of them is an array
> of structs in C (actually in D) and is viewed as a hash table.
>
> I could pack all of the information into a single array. Here is one
> possible scheme which fits in 32 bits and accommodates all board sizes:
>
> 3 bits to identify white/black/empty/off-board
> 9 bits for the hash key (the reference stone)
> 9 bits for pseudo liberty count
> 9 bits for stone count
>
> It's kind of interesting when you think about it. A single array does
> triple duty as a:
>
> 1. Go board.
> 2. Hash table.
> 3. lookup table - to get the "hash key" (table index) of the data
> for
> the string that occupies this point.
>
> The hash table bits in the table are usually irrelevant, it is only
> valid for the single point that represent the hash table entry for a
> given string.
>
> So this scheme does no list manipulations and has a fixed size in
> memory. It's compact and I think fast. Is there anything obvious I'm
> missing that simplifies things?
>
> By the way, stone count field is helpful but not necessary. But it's
> trivial to keep updated and it's convenient.
>
> Using the compact representation would slow down some of the
> operations which are in fast inner loops now, but would probably be a
> win overall, perhaps a big win because I'm not manipulating several
> different arrays.
>
> So I will also try this compact implementation unless someone has a
> superior scheme to suggest.
>
>
> - Don
>
>
>
>
>
>
>
> On Mon, 2006-12-11 at 20:00 +0100, Łukasz Lew wrote:
>> At the time of Your post I've had it already implemented and regarded
>> it like "my sweet secret" :) , so I was expecting that when You
>> published it everybody will appreciate, and start using. But I guess
>> it wasn't easy to see benefits.
>> I wonder how many really good ideas came through this list unnoticed.
>>
>> Best Regards,
>> Lukasz
>>
>>
>> On 12/11/06, House, Jason J. <[EMAIL PROTECTED]> wrote:
>> > Wow. Did some of my early posts on liberties/chains actually get used
>> > by someone? Or did the idea of pseudo-liberties and union sets exist
>> > before my post(s) on the topic? I remember a lot of negative feedback
>> > on pseudo-liberties at the time of my post.
>> >
>> > -----Original Message-----
>> > From: [EMAIL PROTECTED]
>> > [mailto:[EMAIL PROTECTED] On Behalf Of Lukasz Lew
>> > Sent: Monday, December 11, 2006 1:31 PM
>> > To: [EMAIL PROTECTED]
>> > Cc: computer-go
>> > Subject: Re: [computer-go] Fast Board implementation
>> >
>> > Pseudo liberties of a group is a sum of liberties of each stone,
>> > example:
>> >
>> > OOOOO
>> > OXXXO
>> > OX.XO
>> > OXXXO
>> > OOOOO
>> >
>> > "X" group have 4 pseudo liberties.
>> >
>> > If You merge two groups just add pseudo liberties.
>> > If PL = 0 then group should be removed.
>> >
>> > This is simple and sufficient :)
>> >
>> > Lukasz
>> > On 12/11/06, Don Dailey <[EMAIL PROTECTED]> wrote:
>> > >
>> > >
>> > > On Mon, 2006-12-11 at 18:22 +0100, Łukasz Lew wrote:
>> > > > - pseudo liberties at top of union-set tree
>> > >
>> > >
>> > > Refresh my memory on this. I remember talking about this a long
>> > time
>> > > ago. A psuedo liberty is an upper bound on how many liberties there
>> > are
>> > > for a given string, correct? Sometimes a liberty gets counted twice
>> > or
>> > > more?
>> > >
>> > > But if it goes to zero or one it's correct for any given string?
>> > >
>> > > Is the idea that it's lightning fast to update incrementally?
>> > >
>> > > - Don
>> > >
>> > >
>> > >
>> > _______________________________________________
>> > 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/
