Author: Peter Fendrich
Date: 01:27:15 08/24/98
Go up one level in this thread
On August 23, 1998 at 17:50:07, Michael White wrote: >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 Yes, the positions certainly affect the outcome of tests like this but I'm not to worried however in this case... I later went through the "Win At Chess" test set and got about the same results. People have done some good testing before me and found out that the "a&a-1" algorithm works best on bitboards with less than 6-7 bits set. The "hacker" algorithm is better in the other cases. My experiment shows that, at least in my program, the number of bits set in a bitboard are quite few. I think that the mean number is maybe 2-4 bits. I will continue one of these days! :) //Peter
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.