In Satana I was computing hash value move by move, removing previous "from-to" squares hash value and xor the new one. Now I'm testing the "on the fly" computing of hash, not in the ExecuteMove but directly using the bitboards. It is still to refine (I have some false-positive hash hits) but it seems faster than previous approach: about 6400 Knps vs 5900 Knps, with about 20% of cache hits for both methods:
stegemma wrote:In Satana I was computing hash value move by move, removing previous "from-to" squares hash value and xor the new one. Now I'm testing the "on the fly" computing of hash, not in the ExecuteMove but directly using the bitboards. It is still to refine (I have some false-positive hash hits) but it seems faster than previous approach: about 6400 Knps vs 5900 Knps, with about 20% of cache hits for both methods:
It is essential that you encode both piece-type and piece-location in your hash value, in your example this doesn't seem to happen.
For instance when you exchange location of the 2 knights with the location of the 2 rooks you will get the same hash value etc.
NPS doesn't say much, when the search tree is shaped a little bit different because of the altered hash calculation it may generate more quiescence nodes which are usually faster compared to full nodes.
I have already changed the formula, to avoid this problem. It gives good hashing from the starting position and when all pieces/pawns are on the chessboard but poor hashing when you have few pieces. I'm experimenting various options.
(I've quiescence disabled, so the nps is a good indicator, in my engine)
That particular code is full of problems. For instance, think of what would happen if ~bOK happens to end in a whole bunch of 0s. Then the upper bits of boKings, boQueens, etc. are ignored in your computation.
Computing hash keys on the fly is doable, but you need to be more careful than that.
stegemma wrote:I have already changed the formula, to avoid this problem. It gives good hashing from the starting position and when all pieces/pawns are on the chessboard but poor hashing when you have few pieces. I'm experimenting various options.
(I've quiescence disabled, so the nps is a good indicator, in my engine)
You are trying to re-invent a wheel that has never worked. Zobrist has been THE way to produce a hash signature since the 70's. It is critical that each piece have an influence on the final hash signature, and that you can't interchange pieces and get the same signature...
stegemma wrote:I have already changed the formula, to avoid this problem. It gives good hashing from the starting position and when all pieces/pawns are on the chessboard but poor hashing when you have few pieces. I'm experimenting various options.
(I've quiescence disabled, so the nps is a good indicator, in my engine)
You are trying to re-invent a wheel that has never worked. Zobrist has been THE way to produce a hash signature since the 70's. It is critical that each piece have an influence on the final hash signature, and that you can't interchange pieces and get the same signature...
Ok, I already have Zobrist key working but I'm not satisfied in the speed of my implementation, that's why I'm experimenting. I know that I'll lose a few hours but this useless work will let me more comfortable with TT, that works very bad in Satana.
stegemma wrote:I have already changed the formula, to avoid this problem. It gives good hashing from the starting position and when all pieces/pawns are on the chessboard but poor hashing when you have few pieces. I'm experimenting various options.
(I've quiescence disabled, so the nps is a good indicator, in my engine)
You are trying to re-invent a wheel that has never worked. Zobrist has been THE way to produce a hash signature since the 70's. It is critical that each piece have an influence on the final hash signature, and that you can't interchange pieces and get the same signature...
Ok, I already have Zobrist key working but I'm not satisfied in the speed of my implementation, that's why I'm experimenting. I know that I'll lose a few hours but this useless work will let me more comfortable with TT, that works very bad in Satana.
Can you post some code from your implementation? Updating the Zobrist key incrementally as the board changes should be very fast.
My low-level code that modifies the board looks something like this:
stegemma wrote:I have already changed the formula, to avoid this problem. It gives good hashing from the starting position and when all pieces/pawns are on the chessboard but poor hashing when you have few pieces. I'm experimenting various options.
(I've quiescence disabled, so the nps is a good indicator, in my engine)
You are trying to re-invent a wheel that has never worked. Zobrist has been THE way to produce a hash signature since the 70's. It is critical that each piece have an influence on the final hash signature, and that you can't interchange pieces and get the same signature...
Ok, I already have Zobrist key working but I'm not satisfied in the speed of my implementation, that's why I'm experimenting. I know that I'll lose a few hours but this useless work will let me more comfortable with TT, that works very bad in Satana.
If it works very bad, then your problem is not Zobrist hashing as such.
inline uint64_t uRandS(uint64_t &seed0, uint64_t &seed1)
{
uint64_t x = seed0;
uint64_t const y = seed1;
seed0 = y;
x ^= x << 23; // a
x ^= x >> 17; // b
x ^= y ^ (y >> 26); // c
seed1 = x;
return x + y;
}
uint64_t clsBoard::GetHash()
{
#if FAST_TT
uint64_t seeds[] = { 0xA10E014701010401ULL, 0x02C070202CDE2ULL };
#define HH(a) seeds[0] ^= a; boHash ^= uRandS(seeds[0], seeds[1]);
boHash = boAllPieces;
HH(boKings);
HH(boQueens);
HH(boRooks);
HH(boBishops);
HH(boKnights);
HH(boPawns);
HH(color);
HH(boFriends);
HH(boEnpPawn - boCastlings);
return boHash;
#else
return boHash ^ boAllPieces ^ (boEnpPawn - boCastlings) ^ zobcol[color];
#endif
}
This way I don't get false positive anymore and it has the same speed as the standard mode.
It must be further tested and optimized (I've tested only a few positions) but it could be a good solution for low memory systems (similar to my old "overlapping Zobrist key" post) or to limit memory access.
In the new GetHash function I'm trying a faster mode (those with "HH(boKings-boQueens)") that it seems to works too (but it is more dangerous, I think). The Marsaglia code can be simplified, removing the "b" part or other parts but still then it needs more tests. All this changes get the nps increase, without changing the TT hits ratio.
Zobrist has been THE way to produce a hash signature since the 70's. It is critical that each piece have an influence on the final hash signature, and that you can't interchange pieces and get the same signature...