http://www.codeguru.com/forum/showthread.php?t=520797
It could be a new addition to the list of swedish (I think) engines when finished. He probably hasn't found CCC yet from what I saw in his code. His bitToIndex function is
int bitToIndex(unsigned __int64* bit) {
switch (*bit) {
case 1: return 0;
case 2: return 1;
case 4: return 2;
case 8: return 3;
case 16: return 4;
case 32: return 5;
case 64: return 6;
case 128: return 7;
case 256: return 8;
case 512: return 9;
case 1024: return 10;
case 2048: return 11;
case 4096: return 12;
case 8192: return 13;
case 16384: return 14;
case 32768: return 15;
case 65536: return 16;
case 131072: return 17;
case 262144: return 18;
case 524288: return 19;
case 1048576: return 20;
case 2097152: return 21;
case 4194304: return 22;
case 8388608: return 23;
case 16777216: return 24;
case 33554432: return 25;
case 67108864: return 26;
case 134217728: return 27;
case 268435456: return 28;
case 536870912: return 29;
case 1073741824: return 30;
case 2147483648: return 31;
case 4294967296: return 32;
case 8589934592: return 33;
case 17179869184: return 34;
case 34359738368: return 35;
case 68719476736: return 36;
case 137438953472: return 37;
case 274877906944: return 38;
case 549755813888: return 39;
case 1099511627776: return 40;
case 2199023255552: return 41;
case 4398046511104: return 42;
case 8796093022208: return 43;
case 17592186044416: return 44;
case 35184372088832: return 45;
case 70368744177664: return 46;
case 140737488355328: return 47;
case 281474976710656: return 48;
case 562949953421312: return 49;
case 1125899906842624: return 50;
case 2251799813685248: return 51;
case 4503599627370496: return 52;
case 9007199254740992: return 53;
case 18014398509481984: return 54;
case 36028797018963968: return 55;
case 72057594037927936: return 56;
case 144115188075855872: return 57;
case 288230376151711744: return 58;
case 576460752303423488: return 59;
case 1152921504606846976: return 60;
case 2305843009213693952: return 61;
case 4611686018427387904: return 62;
case 9223372036854775808: return 63;
}
return -1;
}
Daniel Shawul wrote:http://www.codeguru.com/forum/showthread.php?t=520797
It could be a new addition to the list of swedish (I think) engines when finished. He probably hasn't found CCC yet from what I saw in his code. His bitToIndex function is
int bitToIndex(unsigned __int64* bit) {
switch (*bit) {
case 1: return 0;
case 2: return 1;
case 4: return 2;
case 8: return 3;
case 16: return 4;
case 32: return 5;
case 64: return 6;
case 128: return 7;
case 256: return 8;
case 512: return 9;
case 1024: return 10;
case 2048: return 11;
case 4096: return 12;
case 8192: return 13;
case 16384: return 14;
case 32768: return 15;
case 65536: return 16;
case 131072: return 17;
case 262144: return 18;
case 524288: return 19;
case 1048576: return 20;
case 2097152: return 21;
case 4194304: return 22;
case 8388608: return 23;
case 16777216: return 24;
case 33554432: return 25;
case 67108864: return 26;
case 134217728: return 27;
case 268435456: return 28;
case 536870912: return 29;
case 1073741824: return 30;
case 2147483648: return 31;
case 4294967296: return 32;
case 8589934592: return 33;
case 17179869184: return 34;
case 34359738368: return 35;
case 68719476736: return 36;
case 137438953472: return 37;
case 274877906944: return 38;
case 549755813888: return 39;
case 1099511627776: return 40;
case 2199023255552: return 41;
case 4398046511104: return 42;
case 8796093022208: return 43;
case 17592186044416: return 44;
case 35184372088832: return 45;
case 70368744177664: return 46;
case 140737488355328: return 47;
case 281474976710656: return 48;
case 562949953421312: return 49;
case 1125899906842624: return 50;
case 2251799813685248: return 51;
case 4503599627370496: return 52;
case 9007199254740992: return 53;
case 18014398509481984: return 54;
case 36028797018963968: return 55;
case 72057594037927936: return 56;
case 144115188075855872: return 57;
case 288230376151711744: return 58;
case 576460752303423488: return 59;
case 1152921504606846976: return 60;
case 2305843009213693952: return 61;
case 4611686018427387904: return 62;
case 9223372036854775808: return 63;
}
return -1;
}
Looks like a non-functioning BSF? unless not more than one bit is set. And about as slow a BSF as one can write to boot... 64 comparisons???
The compiler will likely do a sort of "binary search" by checking to see if the initial value is > 32 bits or not, then in each of those, test to see if it is >16 bits or > 48 bits, etc...
Ugly beyond belief when it can be replaced by a single BSF...
Daniel Shawul wrote:http://www.codeguru.com/forum/showthread.php?t=520797
It could be a new addition to the list of swedish (I think) engines when finished. He probably hasn't found CCC yet from what I saw in his code. His bitToIndex function is
int bitToIndex(unsigned __int64* bit) {
switch (*bit) {
case 1: return 0;
case 2: return 1;
case 4: return 2;
case 8: return 3;
case 16: return 4;
case 32: return 5;
case 64: return 6;
case 128: return 7;
case 256: return 8;
case 512: return 9;
case 1024: return 10;
case 2048: return 11;
case 4096: return 12;
case 8192: return 13;
case 16384: return 14;
case 32768: return 15;
case 65536: return 16;
case 131072: return 17;
case 262144: return 18;
case 524288: return 19;
case 1048576: return 20;
case 2097152: return 21;
case 4194304: return 22;
case 8388608: return 23;
case 16777216: return 24;
case 33554432: return 25;
case 67108864: return 26;
case 134217728: return 27;
case 268435456: return 28;
case 536870912: return 29;
case 1073741824: return 30;
case 2147483648: return 31;
case 4294967296: return 32;
case 8589934592: return 33;
case 17179869184: return 34;
case 34359738368: return 35;
case 68719476736: return 36;
case 137438953472: return 37;
case 274877906944: return 38;
case 549755813888: return 39;
case 1099511627776: return 40;
case 2199023255552: return 41;
case 4398046511104: return 42;
case 8796093022208: return 43;
case 17592186044416: return 44;
case 35184372088832: return 45;
case 70368744177664: return 46;
case 140737488355328: return 47;
case 281474976710656: return 48;
case 562949953421312: return 49;
case 1125899906842624: return 50;
case 2251799813685248: return 51;
case 4503599627370496: return 52;
case 9007199254740992: return 53;
case 18014398509481984: return 54;
case 36028797018963968: return 55;
case 72057594037927936: return 56;
case 144115188075855872: return 57;
case 288230376151711744: return 58;
case 576460752303423488: return 59;
case 1152921504606846976: return 60;
case 2305843009213693952: return 61;
case 4611686018427387904: return 62;
case 9223372036854775808: return 63;
}
return -1;
}
Looks like a non-functioning BSF? unless not more than one bit is set. And about as slow a BSF as one can write to boot... 64 comparisons???
The compiler will likely do a sort of "binary search" by checking to see if the initial value is > 32 bits or not, then in each of those, test to see if it is >16 bits or > 48 bits, etc...
Ugly beyond belief when it can be replaced by a single BSF...
As far as I could see, he has a function that is supposed to isolate a LSB from a bitboard and returns a bitboard with that bit set. Then he applies that huge switch...
However, out of interest, I'd have a question about switches in general. I suck at ASM and compilers but I sort of remember from a MIPS architecture class (long ago... ) that compilers can avoid comparisons in switches by using the case values as indices to a jump table.
This surely can't be done with case values such as the above, but would that happen with GCC or MSVC if the values went from, say, 0 to 8?
However, out of interest, I'd have a question about switches in general. I suck at ASM and compilers but I sort of remember from a MIPS architecture class (long ago... ) that compilers can avoid comparisons in switches by using the case values as indices to a jump table.
His code below will probably be optimized as you described
unsigned __int64 indexToBit(int index) {
switch (index) {
case 0: return 1;
case 1: return 2;
case 2: return 4;
case 3: return 8;
case 4: return 16;
case 5: return 32;
case 6: return 64;
case 7: return 128;
case 8: return 256;
case 9: return 512;
case 10: return 1024;
case 11: return 2048;
case 12: return 4096;
case 13: return 8192;
case 14: return 16384;
case 15: return 32768;
case 16: return 65536;
case 17: return 131072;
case 18: return 262144;
case 19: return 524288;
case 20: return 1048576;
case 21: return 2097152;
case 22: return 4194304;
case 23: return 8388608;
case 24: return 16777216;
case 25: return 33554432;
case 26: return 67108864;
case 27: return 134217728;
case 28: return 268435456;
case 29: return 536870912;
case 30: return 1073741824;
case 31: return 2147483648;
case 32: return 4294967296;
case 33: return 8589934592;
case 34: return 17179869184;
case 35: return 34359738368;
case 36: return 68719476736;
case 37: return 137438953472;
case 38: return 274877906944;
case 39: return 549755813888;
case 40: return 1099511627776;
case 41: return 2199023255552;
case 42: return 4398046511104;
case 43: return 8796093022208;
case 44: return 17592186044416;
case 45: return 35184372088832;
case 46: return 70368744177664;
case 47: return 140737488355328;
case 48: return 281474976710656;
case 49: return 562949953421312;
case 50: return 1125899906842624;
case 51: return 2251799813685248;
case 52: return 4503599627370496;
case 53: return 9007199254740992;
case 54: return 18014398509481984;
case 55: return 36028797018963968;
case 56: return 72057594037927936;
case 57: return 144115188075855872;
case 58: return 288230376151711744;
case 59: return 576460752303423488;
case 60: return 1152921504606846976;
case 61: return 2305843009213693952;
case 62: return 4611686018427387904;
case 63: return 9223372036854775808;
}
return 1337;
}
He is a beginner who probably does things his own way without checking what others ddid. Before I discovered ccc myself, I have made much much worse code like writing a draughts program by matching patterns. I didn't know alpha-beta at that time. His alpha-beta is also a little unconventional creating nodes at run time etc... Doing it your own way has a good and bad side I think.
Daniel Shawul wrote:He is a beginner who probably does things his own way without checking what others ddid. Before I discovered ccc myself, I have made much much worse code like writing a draughts program by matching patterns. I didn't know alpha-beta at that time. His alpha-beta is also a little unconventional creating nodes at run time etc... Doing it your own way has a good and bad side I think.
Hi Daniel,
please check your PM.
I even missed that "creating nodes at run time" aspect, which is most probably the main reason for the bad performance. Replacing this concept by a normal move list + search stack concept would already help tremendously even though there is a lot of other work to do.
Reminds me of a program I wrote when I was a kid and starting to learn programming. It was meant to count the frequency of letters in a text, but I had no concept of dynamic indexing into an array so there was a huge switch with a different case for 'a', 'A', 'b', 'B' etc...
On the plus side, the fact that the guy bothered to write such a huge function shows that he really wants to get it working...
rbarreira wrote:Reminds me of a program I wrote when I was a kid and starting to learn programming. It was meant to count the frequency of letters in a text, but I had no concept of dynamic indexing into an array so there was a huge switch with a different case for 'a', 'A', 'b', 'B' etc...
On the plus side, the fact that the guy bothered to write such a huge function shows that he really wants to get it working...
When I began chess programming I also didn't have a clue. I learned about bitboards from some internet resource but didn't know how to do a LSB.
Daniel Shawul wrote:Hi Sven
Did you get my reply? Should I post your reply on your behalf here or will you do it?
Thanks
Yes, I read your reply. No, don't post yet what I wrote, it was not "ready" yet. I'll try to come back to it later in the evening (European time) when I have more time.