Hi Camerone,
your method is hardly new.
I don't think however anybody uses the very same algorithm as you
propose, for the reason it does not seem to be able to recognize suicide
(could you confirm this? I may be mistaken), which is mandatory for any
implementation (either to remove suicide stones if suicide is allowed by
the rules, or to recognize an invalid move if it is not). So a
"surround capture" algorithm as you name it does half the job.
You wrote "suicide and superko were not implemented to give a clear
picture of the capture test performance", but if you want to compare
with any other implementation you'll have to compare with similar
functionalities. BTW, does your implementation check for simple ko?
So my bet is that people that have bitboard algorithms do not use the
very same as you, but rather use a similar algorithm that will be able
to detect dead stones for both players at the same time, so that they
recognize suicide moves, rather than an algorithm that only checks for
captures.
Now regarding the "algorithm comparison", the shift from "there exists
implementation of algorithm A and implementation of algorithm B, such
that implementation A is faster than implementation B" to "algorithm A
is faster than algorithm B" is always amazing.
For a given algorithm, depending on who did the implementation
(programming skills, understanding of CPU architecture, data structure,
time invested, ...) you can have a difference in execution speed that
goes up to 2 or 3 times faster. This is why, as Erik pointed out, it
would be interesting that you compare your implementation to Lukasz
Lew's libego, which is believed (and probably is) to be the fastest open
source implementation.
As far as I recall, 5 to 6 years ago, on a Q6600 I got ~40-42 kpps/GHz
for 9x9 with libego. Which is 80-84 kpps at 2 Ghz. It is not unfair to
assume that an i7 is a little bit more efficient for the same code.
Let's say around 10% speedup (probably more) because of the processor at
the same speed which would lead to 90-100 kpps at 2 GHz. Perhaps you
could check and report the figures. If this is correct, the conclusion
would be that UF is faster... BTW, there is no need to report an error
estimation with 3 digits precision (table 1), when the error coming from
selecting the reference implementation is far higher.
On the other hand, still 5 to 6 years ago, I was playing with the
bitboard implementation idea, and I had writen some code that ran 1.7
faster than libego, that is around 130 kpps at 2 Ghz for 9x9 on a Q6600.
The implementation I made would run exactly twice as fast on a processor
with 256-bit registers (Q6600 had 128-bit registers), not taking into
account the increased efficiency of the processor. So, maybe bitboard
can be faster... at last.
Another lesson learned when I was playing with bitboards for Go is that
the random move generation scheme is not obvious. Having a scheme that
generates moves with uniform distribution is not that easy, and might
dominate the overall execution speed. Some open source implementation I
reviewed had some flaws regarding this point (including libego if I
recall well, but I'm not sure, so don't take this for granted). Not sure
this flaw is important for practical use anyway.
Best regards,
Antoine
From: Erik van der Werf<erikvanderw...@gmail.com>
This is not new; I've been using algorithms like this in my Go
programs for well over a decade. Anyone with some practical experience
in binary image processing should know basic operations for dilation,
erosion, growing objects under a mask, etc.
Hi Erik,
Thanks for the info. Were they algorithms like this or this actual algorithm?
Do you have any links to literature or code I can follow up?
Thanks,
Cameron
_______________________________________________
Computer-go mailing list
Computer-go@dvandva.org
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
Computer-go@dvandva.org
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
