[computer-go] Fast Board implementation

Łukasz Lew lukasz.lew at gmail.com
Fri Dec 15 03:10:47 PST 2006 

On 12/15/06, Luke Gustafson <lukeg3 at gmail.com> 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. <jhouse at mitre.org> 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: computer-go-bounces at computer-go.org
> >> > [mailto:computer-go-bounces at computer-go.org] On Behalf Of Lukasz Lew
> >> > Sent: Monday, December 11, 2006 1:31 PM
> >> > To: drd at mit.edu
> >> > 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 <drd at mit.edu> 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 at computer-go.org
> >> > http://www.computer-go.org/mailman/listinfo/computer-go/
> >> >
> >> _______________________________________________
> >> computer-go mailing list
> >> computer-go at computer-go.org
> >> http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> > _______________________________________________
> > computer-go mailing list
> > computer-go at computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>

More information about the computer-go mailing list