Author: Dan Newman
Date: 00:50:22 02/03/00
Go up one level in this thread
On February 03, 2000 at 00:58:42, Michael Neish wrote: >On February 03, 2000 at 00:04:38, Dan Newman wrote: > >> >>I first tried bitboards maybe 2 yrs ago and decided they'd be a good deal >>slower than (say) 0x88. I tried a few experiments in move generation that >>seemed to indicate bitboard move generation was about half the speed I could >>get with 0x88, so I concentrated on 0x88 and got what I thought were fair >>results (aprox. 130 knps on a P6/200 with almost no eval). Then I decided to >>try bitboards again--just for the heck of it--and now find that I'm now >>getting much better performance than I thought possible--much better than >>with 0x88. (I'm running just under 500 knps on a P3/500 with quite a few >>eval terms thrown in too.) > >Very interesting reply, thanks for your time. I'm still a novice at this >computer programming business, so pardon me, but what is 0x88? > 0x88 is a trick for detecting the edge of the board without having to test rank and file separately. You make the board 16 squares wide by 8 tall and use only the left half as the chess board. Then all the valid board coords have a bit layout like this: 0xxx0xxx. That is bit 3 and bit 7 (counting from zero) are always 0 for a valid coord. If you then calculate a coordinate that is off the (immediate) edge of the board, it will have a 1 at bit 3 or 7. So, you can test if you are off the board by calculating (coord & 0x88)--hence 0x88. There is also a neat trick you can do with 0x88 coordinate differences used as indices into tables which can speed up in-check and attack detection. In fact I think it's this trick that really makes 0x88 worthwhile. >I'm using CodeWarrior on the Mac. On a 300MHz G3 I'm getting about 50 knps >which I think is pretty pathetic. For starters, the BSF and BSR operations >don't work here; I have to replace them with CNTLZW (count leading zeroes word) >which means that, because it applies to words only, I have to test each half of >the bitboard individually and shift 32 bits in between. I'm not sure how much >slower this is, but as the most often-used routine in the program it must >surely have some measurable effect. > The BSF and BSR instructions work on 32-bit words too, so I have to do something similar. What I did is create a bitboard class that just has two 32-bit integers in it and put in a bunch of member functions and operators to hide the ugly details. I didn't use the 64-bit data type because the Watcom compiler inserted subroutine calls for many (all?) of the operations on the 64-bit types. (BTW, it might be better not to shift by 32 bits to get the other half, but instead make a union with a pair of 32-bit ints or something like that to avoid the cost of shifting--assuming the compiler doesn't do something clever already...) >>The change is due in part to using the BSF and BSR operations for doing >>first_one() and last_one() instead of the C++ code I had been using, and >>also in part to the compiler I'm using now (MSVC 5.0). (I had been using >>Watcom, and with Watcom the bitboard code is a bit slower than the 0x88. >>I think some of this is due to the way I'm getting at the BSF and BSR >>operations in MSVC vs Watcom.) > >Really very interesting. I had no idea that different compilers could make >such a big difference in performance. > Well, I was really surprised too. I had been getting this 10-20% difference with other codes and then I got this +50%... -Dan. >Thanks for the comments. > >Mike.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.