Author: Michael White
Date: 14:50:07 08/23/98
Go up one level in this thread
On August 19, 1998 at 15:27:10, Peter Fendrich wrote: >continuing from Part1... > >Method C (The Hacker trick without loops. Used by DarkThought) >.............................................. >#define ONES ((uint64) 0x5555555555555555) >#define TWOS ((uint64) 0x3333333333333333) >#define FOURS ((unsigned __int32) 0x0f0f0f0f) > register unsigned __int32 n; > const uint64 a = TheBitBoard - ((TheBitBoard >> 1) & ONES); > const uint64 c = (a & TWOS) + ((a >> 2) & TWOS); > n = ((unsigned __int32) c) + ((unsigned __int32) (c >> 32)); > n = (n & FOURS) + ((n >> 4) & FOURS); > n = (n & 0xFFFF) + (n >> 16); > n = (n & 0xFF) + (n >> 8); > return n; >.............................................. > > Pos Time Iter Mve# Nodes N/S > --- --- ---- ---- -------- ----- > d1 111 10 1 3373271 30389 > d2 179 9 13 5482500 30628 > d3 92 8 2 1906069 20718 > d4 93 8 3 2469504 26553 > d5 92 9 6 3498022 38021 > N1 97 8 30 3847980 39669 > N2 92 9 6 2711814 29476 > N3 116 9 1 3352784 28903 > N4 91 8 13 3177590 34918 > N5 103 9 1 4545646 44132 > Total: 1066 87 34365180 > Mean: 107 9 32238 > > >Method D (Table lookup) >........................................ > UINT register c; > > c = table[TheBitBoard.row[0]]; > c += table[TheBitBoard.row[1]]; > c += table[TheBitBoard.row[2]]; > c += table[TheBitBoard.row[3]]; > c += table[TheBitBoard.row[4]]; > c += table[TheBitBoard.row[5]]; > c += table[TheBitBoard.row[6]]; > c += table[TheBitBoard.row[7]]; > return c; >......................................... > > Pos Time Iter Mve# Nodes N/S > ---- ---- ---- ---- -------- ----- > d1 116 10 1 3373153 29078 > d2 148 9 2 4530241 30609 > d3 96 8 6 2097610 21850 > d4 92 8 4 2508042 27261 > d5 92 9 7 3393436 36885 > N1 91 8 27 3457069 37989 > N2 95 9 6 2647945 27873 > N3 124 9 1 3359300 27091 > N4 92 8 11 2965104 32229 > N5 108 9 1 4456583 41264 > Total: 1054 87 32788483 > Mean: 105 9 31109 >==================================================================== > >Conclusion: >Method A, "the Crafty" method works best for my program. This is confirmed by >other tests. >My program Terra uses the bitcounter very much in the Evaluation. Therefore it >has a big so impact on performance. > >Comments? >I will continue with different getFirstBit, getLastBit, popFirstBit, popLastBit >etc... >//Peter Oh, please do continue! I'm especially interested to see if there are any good getFirstBit, etc., that do not rely on the machine instruction _leadz() or _trailz(). It's a pain on platforms that don't supply them... On one level its kind of intriguiging that some looping algorithms are faster than the non-loopers. On the other hand, it "feels" like there should be a blazing fast non-looper to pull off the edge bits and report their locations. The "trick" a&=a-1 and the like probably has a few relatives. I hope so. The way you test the algorithms may depend on the positions that you evaluate. This made me wonder. Are chess pieces distributed randomly throughout the 64bit field? Are there typical bit distributions that getFirst, etc. might be tuned for? At first, I thought it would be enough to randomly distribute n bits in a 64bit field and time the algorithms on that. Seems wrong: there's almost always a pattern. It seems like one has to apply the algorithms to real positions. Well, I'm staying tuned... Regards, Mike White
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.