David, Confession: I have not tested 19x19. As you have noted, and others before you over the years, a 19x19 board does not fit in one but three 128-bit registers and there would be a rather big penalty as a result, perhaps (likely?) wiping out all of the benefits of bitmaps. Antoine voiced his disappointment about the speed advantage even on 9x9 in the e-mail to the list that served as my basis. My hope, as Hideko Kato points out, is in longer registers or perhaps being able to port this to a GPU. A 64-bit OS with twice the number registers would also surely help out. Nevertheless, I was surprised that I was able to get to almost the same level of speed as Libego provides.
The goals for this mockup were very humble: (1) to provide a basic implementation to see what it can do (and if I could do it), and (2) learn how to work with assembly and/or intrinsic functions (I had never done that before). It may not be too hard to try 19x19 and just see what happens. I may attempt this as a follow-up. René van de Veerdonk 2009/8/23 David Fotland <fotl...@smart-games.com> > How much would you lose for 19x19 board? A board representation is not > very interesting unless it scales to 19 line boards. > > > > David > > > > *From:* computer-go-boun...@computer-go.org [mailto: > computer-go-boun...@computer-go.org] *On Behalf Of *René van de Veerdonk > *Sent:* Sunday, August 23, 2009 1:11 PM > *To:* computer-go@computer-go.org > *Subject:* [computer-go] Bitmap Go revisited and mockup implementation > > > > Hi all, > > > > After years of reading this very interesting list, I decided to make my > first contribution this week after reading once again about bitmap go. There > is no freely available implementation of a bitmap based engine that I know > of, so here is a start. Note that I am not a professional programmer, > self-taught, and this is a part-time hobby, so do not expect perfect form. > > > > The attachment is an attempt to create an efficient implementation of a > bitmap based light playout engine, following mostly the recommendations as > spelled out by Antoine de Maricourt in his November 2006 message to this > list. The application is single threaded and achieves around 75-80 kpps on > my Centrino Duo 2.4 GHz Intel labtop. The mockup was developed in C/C++ > using the Microsoft Visual Studio 2008 IDE for Windows XP (32-bit) and > undoubtedly suffers from portability issues as a result. The 128-bit SSE > instructions are called through intrinsic functions, hopefully at least > these interfaces are the same for other compilers. The single goal of this > mockup was to do some benchmarking, so there is no gtp-interface, but that > would be rather easy to add for those skilled in the art. The standard rules > are used with one exception, the Brown eye-rule is used. Multi-stone suicide > is explicitly forbidden. No superko checks are performed during playouts, > and there is no mercy-rule either. > > > > I would be particularly interested to know if a 64-bit OS will improve the > performance significantly, as it does have a lot less register pressure. > Moving to a 64-bit OS will also make some instructions available that allow > for further simplifications/efficiency improvements in the code. As will > enabling SSE3 or SSE4.1 instructions. > > > > One note, the random number generator used is from Agner Fog's public > library and was not included in the attachment. You will have to provide a > random number generator yourself or download the appropriate version from > his well-known website (www.agner.org/optimize) > > > > I hope this is the start of a discussion about further improvements that > can be made, but you may use this code as you wish with no restrictions or > guarantees. See the readme.txt file included in the attachment for more > details (also partially included below). > > > > Comments and feedback welcome, > > > > René van de Veerdonk > > > > Excerpts from the readme.txt file: > > > > Introduction: > > ============= > > > > Mockup of a high performance implementation of the game of Go using bitmaps > > as the principle datastructures. This implementation is limited to > measuring > > the performance of the principle components by playing random playouts from > > an empty 9x9 board, using Chinese scoring, not allowing pass moves until > > no other moves are available. Suicide is not allowed, neither for single > > or multi-stone groups. No checks are implemented for superko, but simple > > ko's are disallowed explicitly. > > > > Some implementation details: > > ============================ > > > > Benchmarking is done in test_board.cpp, where the number of playouts (n) > and > > repeats (j) for each test is set. Benchmarking is done starting from an > empty > > 9x9 board until two (three with ko) passes are played in sequence. The > > benchmark playout follow the same scheme as method > board_t::play_random_game, > > but with timing instrumentation added. > > > > Clock counts (cc) are measured using the cc_time_of macro. Total run-time > > measurement relies on the windows library. > > > > For each move during a playout, the program goes through a sequence of > > (1) identify all legal moves (~50cc) > > this follows Brown's standard definition; this definition differs from > > most Monte-Carlo engines and has a different set of pros and cons; > > bitmaps allow all moves to be processed in parallel > > (2) pick a uniformly random move from the available choices (~75cc) > > relies on a modulus operation; is not 100% uniform to save speed > > (3) playing it on the board (~170cc) > > lengthiest method; but rather straightforward > > > > Playouts end after 256 moves or whenever two passes are played in > succession > > (three in case of a ko). The routines for each of these basic steps are > > contained in the file board.cpp. The underlying datastructures are 128-bit > > bitmaps, for which the sse2 instructions used to manipulate them are > contained > > in the file bitmap.cpp. > > > > Further improvements can be expected from using any 64-bit OS that supports > > several more assembly instructions, and from using sse4.1 instructions. > > > > Example output (on a Intel 2.40 GHz Centrino Duo labtop): > > ========================================================= > > > > [game] = 30469.7, [moves] = 111.071 > > [game] = 30245.4, [moves] = 111.068 > > [game] = 30221.7, [moves] = 111.089 > > [game] = 30264.8, [moves] = 111.122 > > [game] = 30205.8, [moves] = 111.101 > > > > [game] = 77.1084 kpps, [moves] = 111.023 > > [game] = 78.0488 kpps, [moves] = 111.045 > > [game] = 77.1084 kpps, [moves] = 111.046 > > [game] = 78.0488 kpps, [moves] = 111.131 > > [game] = 78.0488 kpps, [moves] = 111.082 > > > > [legal] 110/51, [pick] 110/74, [play] 106/169, [score] 40, [win] 0.4187 > > [legal] 111/51, [pick] 111/74, [play] 106/168, [score] 42, [win] 0.4201 > > [legal] 111/52, [pick] 111/74, [play] 106/169, [score] 43, [win] 0.4276 > > [legal] 111/52, [pick] 111/75, [play] 106/170, [score] 41, [win] 0.4092 > > [legal] 111/51, [pick] 111/74, [play] 106/171, [score] 45, [win] 0.4221 > > > > finished, press any key to exit > > > > Explanation of output: > > ====================== > > > > There are three sets of repeated (5x) measurements, performed and timed > > independently to avoid cross-contamination of inserted serialization > > instructions and timing overhead (which still does not quite prevent > > reordering of instructions across timing boundaries). > > > > [game] cc's per full playout > > [moves] average number of moves per playout > > > > [game] thousands of playouts per second (kpps) > > [moves] average number of moves per playout > > > > "calls per playout" / "cc's per call" > > [legal] identifies all legal moves on the board > > [pick] picks a random move > > [play] processes a move > > [score] scores a final position > > [win] winrate for black > > > > Acknowledgements: > > ================= > > > > Antoine de Maricourt, for his very helpful description of his bitmap go > > implementation in detail on the computer-go mailing list: > > http://computer-go.org/pipermail/computer-go/2006-November/007136.html > > Gunnar Farneback, for providing the well documented Brown engine, > > whoms legal move definition is used in this mockup > > Lukasz Lew, for the high performance Libego implementation, which has > inspired > > various parts of this mockup as well > > Agner Fog, for the Mersenne Twister and clock-cycle timing library > > Computer-go mailing list, where many ideas are posted and discussed > > > > > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
