[computer-go] Fast Board implementation

[Łukasz Lew]

On 12/8/06, Don Dailey <drd at mit.edu> wrote:
>
> 112 moves on average in a 9x9 game?   You are doing something a little
> different than I am and others have reported the same number I get,
> about 107.3 - 107.4
>
> What is your eye avoid rule?

Normal, i.e. local on 8 intersections, updated incrementally.
The games are longer, because I allow ko recaptures (i.e. any board repetition).


>
> - Don
>
> P.S.  30K on 1.4 Celeron is almost too good to be true.   If this is
> correct that's very impressive and I am interested in looking at the
> code.   I can
> believe it it's possible with a few tricks I haven't thought of - but I
> want
> to see for myself!

Soon I will publish the code on my web page.
But I don't have a web page yet. :)

The second issue is a licence.
Can I use my Go Board implementation in commercial program if I
publish it on Gnu?
If no, then can I change the licence when I want to?

But If You want to take look at the code, I will send it to You.
Here I give all tricks:

Efficient board summary:

Board:
- all objects (color, intersection) are int s
- one dimensional board with guards (9x9 => 121 ints)
- pseudo liberties at top of union-set tree
- very lightweight set-union with lightweight path compression
- no explicit liberties
- next_stone array
- black, white, empty, neighbour counters on one int for eye checking

Monte-Carlo:
- memcopy before playout with pointer correction (union-set currently
on pointers)
- randomized array of empty intersections
- (NEW! :) ) non-legal intersections moved to "rejected" array, used
at the end of the playout
- no ko handling
- only single-stone suicide forbidden (detected after play => try again)
- limit on playout length

Technical:
- all functions inlined
- assertions everywhere
- consistency function on assert
- precise profiling with oprofile and rdtsc
- no assembler :)

The most important are:
- pseudo liberties at top of union-set tree
- very lightweight set-union with lightweight path compression

Hope this help :)
Lukasz

>
> I wonder if it is the random list selection tricks you are using?

Not any more :)

Rejected array (the NEW one) improved speed to 33pps (distribution
slightly non uniform)

>
>
>
>
> On Fri, 2006-12-08 at 11:26 +0100, Łukasz Lew wrote:
> > Hi!
> >
> > Many people are spending a lot of effort on creating fast board implementation.
> >
> > I am considering releasing the one written by me.
> > I get 30 k playouts / s (112 moves on avg) on Celeron M 1.4Ghz. So I
> > consider it quite good.
> > If there is an interest in joint development, then I will do it.
> >
> > What say You ? :)
> >
> > Łukasz Lew
> > _______________________________________________
> > 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/
>