Try to compile thisjdart wrote:I have used ULL for a long time, and had no issues with gcc or clang. Even old gcc on an ancient SPARC system handled it.
--Jon
Code: Select all
int main() {
unsigned long long k = 1ull;
}
Moderators: hgm, Rebel, chrisw
Try to compile thisjdart wrote:I have used ULL for a long time, and had no issues with gcc or clang. Even old gcc on an ancient SPARC system handled it.
--Jon
Code: Select all
int main() {
unsigned long long k = 1ull;
}
Code: Select all
perft(5) = 4,865,609 needs 27 bits (covers 2 tests)
perft(6) = 119,060,324 needs 32 bits (covers 556 tests)
perft(7) = 3,195,901,860 needs 39 bits (covers 93,861 tests)
perft(8) = 84,998,978,956 needs 49 bits (covers 8,762,560 tests)
perft(9) = 2,439,530,234,167 needs 52 bits (covers 362,474,852 tests)
Code: Select all
static void PerftTableBitMismatching(PerftTable * const perfttableptr,
const Hash * const hashptr0, const Hash * const hashptr1)
{
si bitpos = -1;
// Determine and record the first mismatched bit of two different hash signatures.
Hash hash0 = *hashptr0, hash1 = *hashptr1;
hash0.qwrd0 &= ~PTTAddrMask;
hash1.qwrd0 &= ~PTTAddrMask;
if (!HashTestEqual(&hash0, &hash1))
{
if (hash0.qwrd0 != hash1.qwrd0)
{
ui index = PTTAddrBitLen;
while ((bitpos < 0) && (index < QwrdBitsLen))
{
if ((hash0.qwrd0 & BXL(index)) != (hash1.qwrd0 & BXL(index)))
bitpos = (si) index;
else
index++;
};
}
else
{
ui index = 0;
while ((bitpos < 0) && (index < QwrdBitsLen))
{
if ((hash0.qwrd1 & BXL(index)) != (hash1.qwrd1 & BXL(index)))
bitpos = (si) index + QwrdBitsLen;
else
index++;
};
};
perfttableptr->fbmm[bitpos]++;
perfttableptr->fbmmcount++;
};
}
Code: Select all
amanda:tmp sje$ ./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 9
TT: entry count: 16777216
TT: fetch count: 297017519
TT: match count: 135172584
TT: stash count: 161844935
TT: trash count: 145068108
TT: usage count: 16776827
TT: bits 0 through 23 used for addressing.
Bit As first bit mismatched
--- -----------------------
024 181137181
025 90642323
026 45196629
027 22813998
028 11486107
029 5604694
030 2785669
031 1402306
032 712016
033 345769
034 171531
035 83728
036 47902
037 22373
038 10783
039 6801
040 2637
041 1295
042 561
043 214
044 134
045 153
046 20
047 21
048 2
049 2
050 3
Total mismatch count: 362474852
At least 52 bits are needed to avoid false positive matches.
Utilization: 0.999977
2439530234167 1564.56 MHz
Code: Select all
perft(5) = 4,865,609 needs 24 bits (handled with address bits only)
perft(6) = 119,060,324 needs 33 bits (covers 510 tests)
perft(7) = 3,195,901,860 needs 38 bits (covers 88,352 tests)
perft(8) = 84,998,978,956 needs 47 bits (covers 8,685,705 tests)
perft(9) = 2,439,530,234,167 needs 52 bits (covers 361,712,273 tests)
Code: Select all
amanda:tmp sje$ ./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 10
TT: entry count: 16777216
TT: fetch count: 5368480244
TT: match count: 2489371364
TT: stash count: 2879108880
TT: trash count: 2862331664
TT: usage count: 16777216
TT: bits 0 through 23 used for addressing.
Bit As first bit mismatched
--- -----------------------
024 3488592295
025 1741179199
026 871629938
027 436823373
028 218508997
029 108743646
030 54054616
031 27046564
032 13650433
033 6721597
034 3409262
035 1647190
036 976874
037 393663
038 197728
039 116124
040 54577
041 24133
042 11371
043 8587
044 4335
045 1375
046 899
047 576
048 115
049 43
050 23
051 173
054 8
Total mismatch count: 6973797714
At least 56 bits are needed to avoid false positive matches.
Utilization: 1.000000
69352859712417 2368.09 MHz
I did a similar experiment twelve years ago on the 24 positions of the BK test.sje wrote:One last thing.
Oscar just finished running perft(10) using its own 16 prime PRNG. The run has shown that only the first 56 bits of hash are necessary and sufficient to avoid false positives. That leaves 72 bits to spare, a comfortable safety margin.
How many bits are required with hash codes from /dev/urandom, I don't know. These runs take many hours and I've tossed the instrumentation code anyway.
From the console:Code: Select all
amanda:tmp sje$ ./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 10 TT: entry count: 16777216 TT: fetch count: 5368480244 TT: match count: 2489371364 TT: stash count: 2879108880 TT: trash count: 2862331664 TT: usage count: 16777216 TT: bits 0 through 23 used for addressing. Bit As first bit mismatched --- ----------------------- 024 3488592295 025 1741179199 026 871629938 027 436823373 028 218508997 029 108743646 030 54054616 031 27046564 032 13650433 033 6721597 034 3409262 035 1647190 036 976874 037 393663 038 197728 039 116124 040 54577 041 24133 042 11371 043 8587 044 4335 045 1375 046 899 047 576 048 115 049 43 050 23 051 173 054 8 Total mismatch count: 6973797714 At least 56 bits are needed to avoid false positive matches. Utilization: 1.000000 69352859712417 2368.09 MHz
Steven's bucket size is 1.mvk wrote:I had a bucket size of 8. You don't give your bucket size, so I can't compare the results, but it appears that my results were still more pessimistic, given the tree size difference. Extrapolating, I would have needed 30 + 24 - 3 + 13 = 64 bits to have less than 0.5 probability of error under your load and single entry buckets.
At least the halving of errors for each additional bit is confirmed.
Code: Select all
// Preserved position data
typedef struct
{
Fss fss; // Saved FEN scalar set record
Apd apd; // Saved auxiliary position data record
Hash msig; // Saved main position signature
Move move; // Saved played move
} Ppd;
// Preserved position data storage node
typedef struct PpdNode
{
struct PpdNode *prev; // Pointer to prev Ppd storage node
struct PpdNode *next; // Pointer to next Ppd storage node
Ppd ppd; // Stored Ppd record
} PpdNode;
// Preserved position data storage list
typedef struct
{
PpdNode *head; // Pointer to head Ppd storage node
PpdNode *tail; // Pointer to tail Ppd storage node
ui count; // Number of elements
} PpdList;
// Chess position
typedef struct
{
Fss fss; // FEN scalar set
Apd apd; // Auxiliary position data
Board board; // Chessboard
Tracker tracker; // Target tracker
Hash msig; // Main position signature
PpdList usedppdlist; // List of saved Ppd records, one entry per played move
PpdList freeppdlist; // List of free Ppd records
} Position;
Code: Select all
if (positionptr->freeppdlist.count == 0)
PpdListAppendNode(&positionptr->freeppdlist, PpdNodeNew());
PpdNode * const ppdnodeptr = PpdListDetachTail(&positionptr->freeppdlist);
ppdnodeptr->ppd.fss = positionptr->fss;
ppdnodeptr->ppd.apd = positionptr->apd;
ppdnodeptr->ppd.msig = positionptr->msig;
ppdnodeptr->ppd.move = move;
PpdListAppendNode(&positionptr->usedppdlist, ppdnodeptr);
Code: Select all
PpdNode * const ppdnodeptr = PpdListDetachTail(&positionptr->usedppdlist);
positionptr->fss = ppdnodeptr->ppd.fss;
positionptr->apd = ppdnodeptr->ppd.apd;
positionptr->msig = ppdnodeptr->ppd.msig;
const Move move = ppdnodeptr->ppd.move;
PpdListAppendNode(&positionptr->freeppdlist, ppdnodeptr);