All,
I completed a new, improved, still not perfect, but hopefully more portable
version of the bitmapgo mockup.
The 9x9 source will be send out separately as a reply. I am still cleaning
up the 19x19 version and send it later.
Some general observations and questions:
o drop-off in playout speed from 9x9 to 19x19 is (still) steeper than for
conventional implementations (tested with libEgo)
I still have a few ideas to pursue that may improve 19x19 more than 9x9
however, a big part of this difference is intrinsic
the data-structure to maintain scales with board area (squared)
basic bitmap operations are mostly global (i.e., not localized as
is typical in more conventional implementations)
playouts are longer for larger boards (this is true for all
implementations)
o there is much intrinsic parallellism in bitmap operations if the bitmaps
are stored in an array
could be a good alternative algorithm to try on GPU (e.g., one thread
per array element)
[especially given that GPU's are memory limited and threads are
relatively cheap]
o much complexity could be removed by not maintaining atari status for
strings (especially for capturing moves)
but atari information is essential for my move generation algorithm (to
disallow suicides, etc)
question: does the "do not play in your own eye" selection rule require
atari information? (my guess is yes)
follow-up question: do you maintain atari status incrementally or
determine it on demand?
o I don't believe the playout policy is restricted to ultra-light even with
the limited information that is already maintained
question: which move-orderings are especially effective for others?
I am tempted to implement a "waterfall" strategy for move-selection
What changed:
o more portable (MSVC and g++ both work for x86_32)
most compiler specific changes are collected in single header file
not all features that were available to me in MSVC are supported
for g++ yet
suggestions in this area are very welcome, I have not much
experience with other compilers
includes test process for available instruction set, but the result is
only reported, not explicitly used
you may need to set some compile directives manually (should not
be needed with default values)
replaced some instructions with more widely available ones (with
compile directives)
for example, the "phaddd" instruction is not available on AMD
cpu's
default compile directives were not chosen for highest speed, but eying
portability potential (see "doc/readme.txt")
o tested on Microsoft Visual C++ 2008/2010 and g++ on MinGW32 + MSYS under
WinXP x86_32
MSVC solution files included, g++ command line described in
"doc/readme.txt" file
not tested under x86_64 operating systems, but a prior version ran into
an infinite loop in "bitmap_r::pick_random" (could still be there)
compiles without warnings using both compilers
the resulting executable is ~20% faster (and much smaller) using MSVC
as compared to g++ (MinGW32 + MSYS)
any suggestions on these differences are highly appreciated
even the random number generator sees vastly different
performances in the benchmark routine
sample output shown in "doc/readme.txt"
o improved testing strategy of implementation correctness
hopefully provides better warnings for where errors are caused by on
your particular system
hopefully it catches more errors
o no more external dependencies
includes self-contained source-code for SFMT based Mersenne Twister
random number generator and tsc-counter readout
the inline assembly for reading the tsc-counter may not work with MSVC
x86_64 and still need an external library call (or MASM source)
o improved playout speed by changing bitmap algorithm / data-structure
for 9x9: 78 kpps --> 88-90 kpps (for 19x19: 7.5 kpps --> ~10 kpps)
for 9x9: move selection ~100cc (identify candidates ~ 45cc, pick
randomly ~60cc), play a move: ~145cc
instead of maintaining liberties of strings, maintain "adjacencies" of
strings (thanks to a suggestion by Antoine de Maricourt)
["adjacencies" includes enemy stones and may include stones of string
itself]
inserting "edge" bits in bitmap especially improves 19x19
compile random number generator from sourcecode instead of library call
fixed a bug in the random move picking process for 19x19 (did not
influence statistics very much)
I would like to ask that some people try to compile and run this mockup on
various systems and let me know if it works (or not) for you. The principle
goal of this mockup is to provide anybody with a reasonably efficient,
documented, and working starting point to pursue their own "bitmap" ideas.
This as an alternative to already established other reference implementation
choices, such as GnuGo, Brown, RefBot, libEgo, Fuego, Orego, Patchy, etc.
There is (some) documentation in the source-code and in the "doc/readme.txt"
file. Please let me know when those are insufficient and/or unclear and I
will attempt to improve them.
Other than testing if things work, I am also open for suggestions and
improvements. I encourage anybody to tinker with or use the code in any way,
shape, or form, there are no licencing restrictions from my end. There is
also no need to let me know, although that would be very much appreciated.
Special thanks to those whom provided me with feedback, in particular
Antoine de Maricourt.
Comments and criticisms welcome,
René
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
