Line data Source code
1 : #include "hash.hpp"
2 :
3 : #include "bitboardTools.hpp"
4 : #include "logging.hpp"
5 : #include "position.hpp"
6 : #include "tools.hpp"
7 :
8 : namespace Zobrist {
9 : array2d<Hash,NbSquare,14> ZT;
10 : array1d<Hash,16> ZTCastling;
11 :
12 : inline constexpr int hash_seed = 42;
13 :
14 : namespace {
15 : // Test bit distribution across all Zobrist hash values
16 22 : void testBitDistribution() {
17 22 : std::array<uint64_t, 64> bitCounts = {0};
18 : uint64_t totalHashes = 0;
19 :
20 : // Count bits across ZT table
21 1430 : for (int k = 0; k < NbSquare; ++k) {
22 21120 : for (int j = 0; j < 14; ++j) {
23 19712 : Hash h = ZT[k][j];
24 1281280 : for (int bit = 0; bit < 64; ++bit) {
25 1261568 : if (h & (1ULL << bit)) bitCounts[bit]++;
26 : }
27 19712 : totalHashes++;
28 : }
29 : }
30 :
31 : // Count bits in castling table
32 374 : for (int k = 0; k < 16; ++k) {
33 352 : Hash h = ZTCastling[k];
34 22880 : for (int bit = 0; bit < 64; ++bit) {
35 22528 : if (h & (1ULL << bit)) bitCounts[bit]++;
36 : }
37 352 : totalHashes++;
38 : }
39 :
40 22 : Logging::LogIt(Logging::logInfo) << "Zobrist bit distribution test (should be ~0.5 for each bit):";
41 : bool allGood = true;
42 1430 : for (int bit = 0; bit < 64; ++bit) {
43 1408 : double ratio = bitCounts[bit] / static_cast<double>(totalHashes);
44 1408 : if (ratio < 0.45 || ratio > 0.55) {
45 0 : Logging::LogIt(Logging::logWarn) << " Bit " << bit << " has poor distribution: " << ratio;
46 : allGood = false;
47 : }
48 : }
49 22 : if (allGood) {
50 22 : Logging::LogIt(Logging::logInfo) << " All bits have good distribution (between 0.45 and 0.55)";
51 : }
52 22 : }
53 :
54 : // Calculate Hamming distance between two hashes
55 : int hammingDistance(Hash a, Hash b) {
56 39116 : return __builtin_popcountll(a ^ b);
57 : }
58 :
59 : // Test average Hamming distance (should be around 32 for random 64-bit values)
60 22 : void testHammingDistance() {
61 : const int sampleSize = 1000;
62 : uint64_t totalDistance = 0;
63 : int comparisons = 0;
64 :
65 : // Sample random pairs from ZT table
66 19734 : for (int i = 0; i < sampleSize && i < NbSquare * 14; ++i) {
67 19712 : int k1 = (i * 7) % NbSquare;
68 19712 : int j1 = (i * 13) % 14;
69 19712 : int k2 = ((i + 1) * 11) % NbSquare;
70 19712 : int j2 = ((i + 1) * 17) % 14;
71 :
72 19712 : if (k1 != k2 || j1 != j2) {
73 19712 : totalDistance += hammingDistance(ZT[k1][j1], ZT[k2][j2]);
74 19712 : comparisons++;
75 : }
76 : }
77 :
78 22 : double avgDistance = static_cast<double>(totalDistance) / static_cast<double>(comparisons);
79 22 : Logging::LogIt(Logging::logInfo) << "Zobrist Hamming distance test:";
80 22 : Logging::LogIt(Logging::logInfo) << " Average Hamming distance: " << avgDistance << " (ideal: ~32)";
81 :
82 22 : if (avgDistance < 28 || avgDistance > 36) {
83 0 : Logging::LogIt(Logging::logWarn) << " Hamming distance outside expected range [28, 36]";
84 : }
85 22 : }
86 :
87 : // Test for unwanted correlations (adjacent squares)
88 22 : void testCorrelations() {
89 22 : Logging::LogIt(Logging::logInfo) << "Zobrist correlation test (adjacent squares):";
90 :
91 : // Check adjacent squares for the same piece type
92 : int poorDistances = 0;
93 : int totalComparisons = 0;
94 :
95 1408 : for (int k = 0; k < NbSquare - 1; ++k) {
96 20790 : for (int j = 0; j < 14; ++j) {
97 19404 : int dist = hammingDistance(ZT[k][j], ZT[k+1][j]);
98 19404 : totalComparisons++;
99 : // Count outliers (very low or very high Hamming distance)
100 19404 : if (dist < 20 || dist > 44) {
101 44 : poorDistances++;
102 : }
103 : }
104 : }
105 :
106 22 : double poorRatio = poorDistances / static_cast<double>(totalComparisons);
107 22 : Logging::LogIt(Logging::logInfo) << " Outliers: " << poorDistances << "/" << totalComparisons
108 22 : << " (" << (poorRatio * 100) << "%)";
109 :
110 : // More than 10% outliers would indicate a real problem
111 22 : if (poorRatio > 0.10) {
112 0 : Logging::LogIt(Logging::logWarn) << " WARNING: High correlation detected (>10% outliers)";
113 : } else {
114 22 : Logging::LogIt(Logging::logInfo) << " No significant correlations detected";
115 : }
116 22 : }
117 : }
118 :
119 22 : void initHash() {
120 22 : Logging::LogIt(Logging::logInfo) << "Init hash";
121 22 : Logging::LogIt(Logging::logInfo) << "Size of zobrist table " << (sizeof(ZT)+sizeof(ZTCastling)) / 1024 << "Kb";
122 1430 : for (int k = 0; k < NbSquare; ++k)
123 21120 : for (int j = 0; j < 14; ++j) ZT[k][j] = randomInt<Hash, hash_seed>(std::numeric_limits<Hash>::min(), std::numeric_limits<Hash>::max());
124 374 : for (int k = 0; k < 16; ++k) ZTCastling[k] = randomInt<Hash, hash_seed>(std::numeric_limits<Hash>::min(), std::numeric_limits<Hash>::max());
125 :
126 : // Run quality tests on generated Zobrist values
127 22 : testBitDistribution();
128 22 : testHammingDistance();
129 22 : testCorrelations();
130 22 : }
131 : } // namespace Zobrist
132 :
133 23447380 : Hash computeHash(const Position &p) {
134 : #ifdef DEBUG_HASH
135 : Hash h = p.h;
136 : p.h = nullHash;
137 : #endif
138 23447380 : if (p.h != nullHash) return p.h;
139 : //++ThreadPool::instance().main().stats.counters[Stats::sid_hashComputed]; // shall of course never happend !
140 20020 : for (Square k = 0; k < NbSquare; ++k) { ///todo try if BB is faster here ?
141 19712 : const Piece pp = p.board_const(k);
142 19712 : if (pp != P_none) p.h ^= Zobrist::ZT[k][PieceIdx(pp)];
143 : }
144 308 : if (p.ep != INVALIDSQUARE) p.h ^= Zobrist::ZT[p.ep][NbPiece];
145 308 : p.h ^= Zobrist::ZTCastling[p.castling];
146 308 : if (p.c == Co_White) p.h ^= Zobrist::ZT[3][NbPiece];
147 308 : if (p.c == Co_Black) p.h ^= Zobrist::ZT[4][NbPiece];
148 : #ifdef DEBUG_HASH
149 : if (h != nullHash && h != p.h) { Logging::LogIt(Logging::logFatal) << "Hash error " << ToString(p.lastMove) << ToString(p, true); }
150 : #endif
151 308 : return p.h;
152 : }
153 :
154 946030 : Hash computePHash(const Position &p) {
155 : #ifdef DEBUG_PHASH
156 : Hash h = p.ph;
157 : p.ph = nullHash;
158 : #endif
159 946030 : if (p.ph != nullHash) return p.ph;
160 : //++ThreadPool::instance().main().stats.counters[Stats::sid_hashComputed]; // shall of course never happend !
161 1379 : BB::applyOn(p.whitePawn(), [&](const Square & k){ p.ph ^= Zobrist::ZT[k][PieceIdx(P_wp)]; });
162 1313 : BB::applyOn(p.blackPawn(), [&](const Square & k){ p.ph ^= Zobrist::ZT[k][PieceIdx(P_bp)]; });
163 308 : BB::applyOn(p.whiteKing(), [&](const Square & k){ p.ph ^= Zobrist::ZT[k][PieceIdx(P_wk)]; });
164 308 : BB::applyOn(p.blackKing(), [&](const Square & k){ p.ph ^= Zobrist::ZT[k][PieceIdx(P_bk)]; });
165 : #ifdef DEBUG_PHASH
166 : if (h != nullHash && h != p.ph) {
167 : Logging::LogIt(Logging::logFatal) << "Pawn Hash error " << ToString(p.lastMove) << ToString(p, true) << p.ph << " != " << h;
168 : }
169 : #endif
170 308 : return p.ph;
171 : }
|
