A couple of notes. Some of us on this computer-go forum are also Chess programmers and many of write 64 bit chess programs. I am one of them but I know there are others.
My 64 bit chess program runs almost 2X faster if I compile it to run on a 64 bit OS - in other words I'm using real 64 bit values to represent the bit boards. So this really is a big deal - you can expect a pretty good gain. I also toyed with a bit board style go program and started working on one long ago. You still need several 64 bit words to represent the state of each color. I started to write some routines that did shift, popcount, etc as fast as possible. Basically you had to compile the program for each board size, and it figured out how many bits were needed and simulated (using struct) an integer data type that was large enough. About half way through I decided not to proceed - at the time I had some idea that I was more interested in and I never picked it back up - assuming that it would be too slow (but I didn't prove it.) I think you could look at glaurung (the chess program) to find great routines for the common bit operations. I think the author of Glaurung does it about as fast as it can be done and even has assembly code for finding the right-most bit, or something like that. But you could probably learn something from looking at that program. I'm not sure how useful this might be for go, but there are some pretty clever tricks with minimal perfect hashing - that you might find some use for. Perhaps there is a way to make this work for eye-detection or someting. There is some great explanations here: http://chessprogramming.wikispaces.com/ I think you want to look under move generation perhaps. Perhaps this cannot be used for GO, but it's fun to read anyway :-) The only issue of course is that you need more than 64 bits for go - but the general principles might be made to work. - Don 2009/8/25 René van de Veerdonk <rene.vandeveerd...@gmail.com> > Antoine, > I apologize for misrepresenting your feelings. What I wanted to convey is > that your e-mail expressed that with the same amount of computation, other > implementation strategies provide more information, so the information > gained for the effort put in is disappointing. In other words, bitmap-go had > better be much faster to make up for the lack of information gained ... and > it wasn't. That's pretty much what you are saying as well, I believe. As are > the others in this thread. I think we can all agree on this. > > Going into this project, I was well aware that I was going to end up with > light playouts only, and that heavy playouts is the way to go except perhaps > for some special purposes such as ladder readouts. I was also well aware of > the scaling argument. But, I hadn't thought that this would be the first > thing thrown at my first post, as there are many programmers that seem to be > stuck at 9x9. Nonetheless, bitmap-go as a topic keeps resurfacing on this > mailing list every once in a while and nobody ever put solid data and a > reference implementation behind it. That is what I wanted to accomplish with > my mockup. > > Confession #2: I have been working on my own MCTS implementation using the > standard implementation methods that almost everybody else is using. But > there is a never-ending laundry-list of things that I would like to include > before I would reach reasonable strength (where reasonable is a moving > target). In the mean time, there are many others that have demonstrated much > more capable programmers than I ever will be. So, by providing this > bitmap-go mockup at least I had the feeling that I was contributing > something newsworthy to the conversation. This may have never happened if I > would wait until my MCTS program is ready. I imagine that there are others > on this list in a similar situation. Besides, this was an interesting > side-project and perhaps someone else can benefit from it (go for it > Brian!). And, yes, it was fun. > > Okay, enough mesmerizing, on to the main topic. > > David, Lukasz, > > I did modify my mockup to do 19x19 bitmap-go (attached). It is a hardcoded > solution using arrays of three 128-bit variables. I did not even attempt to > optimize this version, so this is not the best possible solution. > Nonetheless, here is a comparison: > > Example output (9x9): > ===================== > > [game] = 30236.1, [moves] = 111.071 > [game] = 30249.7, [moves] = 111.068 > [game] = 30145.7, [moves] = 111.089 > [game] = 30237.7, [moves] = 111.122 > [game] = 30210.1, [moves] = 111.101 > > [game] = 78.0488 kpps, [moves] = 111.023 > [game] = 78.0488 kpps, [moves] = 111.045 > [game] = 78.0488 kpps, [moves] = 111.046 > [game] = 79.0123 kpps, [moves] = 111.131 > [game] = 78.0488 kpps, [moves] = 111.082 > > [legal] 110/51, [pick] 110/74, [play] 106/168, [score] 44, [win] 0.4187 > [legal] 111/51, [pick] 111/74, [play] 106/168, [score] 40, [win] 0.4201 > [legal] 111/52, [pick] 111/75, [play] 106/168, [score] 42, [win] 0.4276 > [legal] 111/52, [pick] 111/74, [play] 106/169, [score] 41, [win] 0.4092 > [legal] 111/52, [pick] 111/74, [play] 106/169, [score] 44, [win] 0.4221 > > Example output (19x19): > ======================= > > [game] = 316452, [moves] = 455.036 > [game] = 316378, [moves] = 455.126 > [game] = 316266, [moves] = 455.177 > [game] = 316017, [moves] = 455.08 > [game] = 316210, [moves] = 455.16 > > [game] = 7.45052 kpps, [moves] = 455.267 > [game] = 7.45921 kpps, [moves] = 455.055 > [game] = 7.45921 kpps, [moves] = 455.17 > [game] = 7.45921 kpps, [moves] = 455.188 > [game] = 7.47664 kpps, [moves] = 455.013 > > [legal] 454/144, [pick] 454/128, [play] 449/430, [score] 173, [win] 0.4592 > [legal] 455/144, [pick] 455/128, [play] 449/431, [score] 173, [win] 0.4655 > [legal] 454/144, [pick] 454/128, [play] 449/430, [score] 173, [win] 0.4611 > [legal] 454/144, [pick] 454/128, [play] 449/431, [score] 173, [win] 0.4674 > [legal] 455/144, [pick] 455/128, [play] 450/430, [score] 175, [win] 0.4661 > > Summary: > ======== > > function 9x9 19x19 ratio > ----------------------------------- > game [ cc ] 30216 316265 10.47 > game [kpps] 78 7.46 10.45 > moves 111 455 4.10 > legal [ cc ] 52 144 2.77 > pick [ cc ] 74 128 1.73 > play [ cc ] 168 430 2.56 > score [ cc ] 42 173 4.12 > > legal+pick+play 294 702 2.39 > > So, it looks that I was overly pessimistic in terms of performance drop per > move, which is a factor of 2.4x (with little effort to optimize for 19x19). > But, with 4.1x more moves, this still resulted in a 10x speed penalty. With > the provided reference numbers, Libego only drops 4.5-5.0x, indicating that > there is almost no performance loss per move (1.2x). Is this difference > roughly in line with others expectation? > > With that, I hope this at least provides some data for future discussions, > and reference implementation for others that may want to pick up the ball > from here. Someone could add a gtp-interface and make it available as one of > Don's reference implementations for starting go-programmers. I would still > be interested to improve this solution, but I think I need a fresh set of > eyes in order to make any more progress. I would like to re-iterate that I > expect significant gains on a 64-bit OS as a result on the doubling of the > number of available registers. It would be nice if someone would be able to > post some results. Newer CPU's (will) also have instructions available that > can significantly speed things up (bit-test, compare, popcount, wider > variables, etc). > > René van de Veerdonk > > On Tue, Aug 25, 2009 at 12:42 PM, Antoine de Maricourt < > antoine.de-marico...@m4x.org> wrote: > >> Hi René, >> >>> 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. >>> >>> >> As far as I remember, I was not disappointed by the speed itself on 9x9 >> boards, but mainly with the following 2 points: >> >> a) my feeling is that, as you say, it does not scale very well on 19x19 >> (on current hardware). >> I don't think other "classical" implementations suffer such a big penalty >> when scaling from 9x9 to 19x19. >> >> b) I also felt that this kind of implementation was not very flexible. >> For instance, I had another classical implementation, running at >> equivalent speed, but in which local 3x3 pattern matching was almost for >> free, as well as other more elaborated information. >> When I started to think about introducing 3x3 local patterns in the bitmap >> only implementation, it was clear it would not be for free. >> >> At that time, my conclusion was that if one only needs pure random play >> with no intelligence at all during playouts, then bitmap implementation >> could compete (at least on 9x9). >> If one needs more elaborated knowledge (such as small patterns matching, >> or even knowledge about blocks of stones), then pure bitmap implementation >> is probably not so competitive. >> I thus gave up with the idea and jumped to more promising ones. >> >> Anyway, I'm glad my post has been usefull to you. And I encourage you to >> improve your implementation and let us know, especially if you have fun. >> Starting with something and playing with it is a good way to have new ideas, >> even if this makes your initial ones look less interesting a while after. >> >> Best regards, >> >> Antoine >> >> >> _______________________________________________ >> 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/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
