Aleks Peshkov wrote: ↑Thu Oct 02, 2025 1:17 am
Your problem is not collisions. You should store depth in TT record. "position startpos moves g1f3 g8f6 f3g1 f6g8" is legal transposition and have different perft from startpos, because it has remaining depth-4.
'perft 2' and 'perft 6' are different perft numbers of the same position, but you store them in the same slot in TT.
But it seems he has a separate table by depth:
chessbit wrote:My TT is declared as a matrix [depth][2^28]
Yes I'm pretty sure there's no depth issue. I think the issue is false positives. But is this a risk that is unavoidable? Sure you can make 128 bits keys, even 256 bits, and your chances might be astronomically low to get a false positive, but it's never 0. If one would undertake the project of computing perft 16, or more, then there is no way of knowing if it is correct. Do we even know if the current number for perft 15 is correct, since it was only computed once?
Btw, I have setup a 128 bits keys to compute perft 12, I will run it tonight to confirm the problem.
chessbit wrote: ↑Thu Oct 02, 2025 3:48 pm
Yes I'm pretty sure there's no depth issue. I think the issue is false positives. But is this a risk that is unavoidable? Sure you can make 128 bits keys, even 256 bits, and your chances might be astronomically low to get a false positive, but it's never 0. If one would undertake the project of computing perft 16, or more, then there is no way of knowing if it is correct. Do we even know if the current number for perft 15 is correct, since it was only computed once?
Btw, I have setup a 128 bits keys to compute perft 12, I will run it tonight to confirm the problem.
Ah, you were still using 64-bit keys. I had overlooked that in your previous post. Yes, then the straightforward calculation I outlined earlier applies. (Typically people come up with birthday paradox calculations, but the situation is much easier if you assume the hashtable is full for most of the time, which of course it is.)
It is avoidable by using the whole position as the key, but I think 128-bit keys is enough for now.
You could even redo the computation later with the same program but different Zobrist keys to reduce the probability that your result is wrong (assuming you do get the same result).
Just to update, it works fine with a 128 bits key. I didn't realize 2^64 was such a small number beyond depth 11. Plus, the perf hit for a 128 bits hash is irrelevant, so might as well work with that regardless, maybe even 256.