[computer-go] incremental liberty counts

[Łukasz Lew]

I propose to introduce a benchamrk for a board implementation.
playouts / second (pps)
and
moves / second

To deal with different hardware let's use crazyStone benchmark as a reference
http://remi.coulom.free.fr/CrazyStone/CrazyStone-0006-9x9.exe

(On Celeron M 1.4Ghz (laptop) Crazy stone makes 8k pps)

$ echo "crazy-analyst MonteCarlo benchmark 100000" | wine
./CrazyStone-0006-9x9.exe
= 100000 simulations in 12.49 seconds.
8006.41 simulations per second
h = 13708747238564438213
TotalBlackScore = -789416

My old program's benchmark gets on the same hardware about 2300 pps
with avg playout length 113 moves (passes not included).
It is based on Gnugo.

So what are Yours stats?

Best Regards

On 8/30/06, Chris Fant <chrisfant at gmail.com> wrote:
> Rerun the tests at 19x19 and see how they compare.
>
> On 8/30/06, Don Dailey <drd at mit.edu> wrote:
> > I have implemented, tested and timed the code with the trick and if
> > there is a speedup, it's so small it's difficult to measure.
> >
> > The problem is now I have 3 tests inside an inner loop.  In both cases I
> > have to look for a liberty.   But now, instead of just testing for an
> > enemy stone, I have to have a separate test to see if I've visited that
> > point before.   It was implicit before because the flag bit helped
> > distinguish it.
> >
> > Here is the difference in code for ONE of the direction tests stripped
> > of all irrelevant details:
> >
> > OLD:
> >
> > if (p->bd[t+1] == ene) {
> >     elist[cc++] = t+1;
> >     p->bd[t+1] |= FLAG;
> > }
> >
> > NEW:
> >
> > if (p->bd[t+1] == ene && clear[t+1] != age) {
> >    elist[cc++] = t+1;
> >    clear[t+1] = age;
> > }
> >
> >
> > In the old code, I did not have to test to see if the point was clear
> > because the flag bit automatically made the test fail.
> >
> > Age is a variable that is incremented at the beginning of the function
> > call and is unique for every run.
> >
> >
> > The NEW version of course doesn't have to clear the flag bits from the
> > board, otherwise it probably would be slower.   In the old version,
> > clearing the flag bits is fast because the points are all stored in
> > elist, a flat array with no holes.
> >
> > Is there something I am missing?
> >
> > - Don
> >
> >
> >
> >
> >
> >
> > On Wed, 2006-08-30 at 08:59 +0200, Rémi Coulom wrote:
> > > Don Dailey wrote:
> > > > It takes approximately 25% of the time to see if something gets
> > > > captured.   That routine stops as soon as it notices the target group is
> > > > safe, but it still has to repair the flag bit for those points it has
> > > > already visited.   It's actually a very simple routine but it does a lot
> > > > of work.
> > > >
> > > The GNU-Go mark trick I rapidly explained in a previous mail saves the
> > > effort of repairing a flag bit for visited points (or strings). You may
> > > have good reasons not to use it, but I thought I'd repeat this just in
> > > case it was not clear the first time I wrote it (which is very likely
> > > since my explaination was very short).
> > >
> > > Rémi
> >
> > _______________________________________________
> > 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/
>