hash collisions

[mar]

As to the corruption by races, the solution I consider best is an 8-byte (i.e. atomic) entry with a shortened key signature to make it fit (e.g. 24 bit), plus a signature extension in the first word of the hash bucket (e.g. 8 bit), so that this first word alone will (in almost all cases) be enough to conclude there is no hit within this bucket. The distribution of the key over different words will reduce the number of undetected race corruptions by the size of the smallest key part (i.e. by 256 in the 8-bit case). The overhead for such a 'divided key' is not an extra XOR, but the fact that the signature comparison has to be done in two parts. But in the overwhelming majority of cases the second comparison would not have to be done, because the first (the signature extension) already failed to match, and the fact that the signature extension for all entries is in the same word should more than make up for that. (Most hash probes are misses, and these would otherwise have to compare the key in all the eligible entries of the bucket, waiting for them to arrive from memory.)

This seems like an interesting idea, not sure if I understand it correctly:
So you propose to use 8 bytes in the bucket to store 8-bit parts of the zobrist key for each stored entry (at a specific position in the key), let's say such bucket can store 7 8-byte actual entries plus this merged extended signature.
So you extract the 8 bytes first (merged extended signatures), extract the extended signature from the zobrist key for the position a compare
(7 times using shifts+masks) to see if there's a potential hit in the bucket without accessing the individual entries yet?

I mean, you know the extended signature for the position you're probing, you don't know where it is in the merged extended signature key in the bucket (if at all), so a single comparison won't really work here (that is, unless I completely misunderstood your idea) - maybe some SIMD magic might work

EDIT: now that I think about it, you could actually use a 9-bit extension (this would give you 33-bit signature in TT), only wasting 1 bit per bucket. I still miss however how to do an efficient comparison of the probing signature, because you don't know the index in the bucket in the case of a hit

[Dann Corbit]

You don't like it when your stupidity receives extra attention?

Hahahaha! 100% no bugs for chess engines is entirely possible, the mechanics of moving the six pieces in defined ways over 64 squares and performing recursive search are quite trivial. Programmers who won’t work to 100% bug free methods are a liability and unemployable. Yes, that’s my opinion and it’s pretty much all I wrote on the topic. Somehow this has tripped your ego and you resort to silly put downs, well okay, I’m well used to dealing with that too.

The goal is not necessarily writing bug free code, for instance by program proving, because it is quite expensive and difficult to do that. The goal is to remove serious known bugs so that the program operates safely.

Failure to perform the above is simple incompetence.

[hgm]

This seems like an interesting idea, not sure if I understand it correctly:
So you propose to use 8 bytes in the bucket to store 8-bit parts of the zobrist key for each stored entry (at a specific position in the key), let's say such bucket can store 7 8-byte actual entries plus this merged extended signature.

Exactly. Something like

Code: Select all

typedef struct {
  uint32 keyAndDepth; // packed 3 bytes signature and 1 byte depth
  uint16 moveAndBoundType;
  uint16 score;
} HashEntry;

typedef struct {
  uint8 ext[7];
  uint8 aging; // filler, possibly used for aging bits
  HashEntry e[7];
} HashBucket;

So you extract the 8 bytes first (merged extended signatures), extract the extended signature from the zobrist key for the position a compare
(7 times using shifts+masks) to see if there's a potential hit in the bucket without accessing the individual entries yet?

Well, I was thinking in terms of byte memory accesses to hashTable[index].ext[ i], but I guess shift & mask when defining ext as an uint64 instead of an array of uint8 would be competative as well.

I mean, you know the extended signature for the position you're probing, you don't know where it is in the merged extended signature key in the bucket (if at all), so a single comparison won't really work here (that is, unless I completely misunderstood your idea) - maybe some SIMD magic might work

True; but this is always the case. You have to compare with the signature of all entries in the bucket where the sought position could potentially have been stored. So this will also hold for the signature extension. But if an extension does not match, you don't have to bother testing the remaining part of the signature.

And you are right: SIMD could do this. I had not even thought of that. But old-fasioned MMX should be able compare 8 bytes at a time, and deliver a word with eight all-0 or all-1 masks depending on the outcome. So just MMX-compare with (hashKey>>56)*0x0101010101010101ULL. If that entire word is 0, (the common case!) you can exclude a hit immediately, without waiting for the cache-line fill to complete. Otherwise you can use the standard bit-extraction techniques to find the 1 bits (and then strip those 8 at the time) to check out the potential hits.

EDIT: now that I think about it, you could actually use a 9-bit extension (this would give you 33-bit signature in TT), only wasting 1 bit per bucket. I still miss however how to do an efficient comparison of the probing signature, because you don't know the index in the bucket in the case of a hit

Indeed you could, if you use shift & mask anyway. But not with SIMD.

Using "shallowest-of-7" replacement is usually overdoing it, although the possibility to identify the hit in a single SIMD test certainly makes it more attractive. I would prefer to use the first entry (immediately after the extension word) as a dedicated always-replace entry, though, rather than just replacing the lowest depth of the seven. So replace the lowest depth of entry 2-7 if we equal or exceed it, (possibly counting stale entries as having depth 0), and replace entry 1 if not.

That means the most common case (a complete miss) would do the SIMD compare of the extensions only. The somewhat less frequent case of a hit would see an extension match in entry 1, the first word to be loaded from memory after the extension word, compare the remaining bits of the signature there, probably find a match (as it would be rather unlikely that the extension matched by accident), and conclude the hit. Only very rarely you would have a hit (or a potential hit because of an accidental match of the signature extension) on one of the later (depth-preferred) entries, needing to examine words that arrive late in the cache-fill burst. An accidental extension match in one of the 7 entries should occur only in 2.8% of the probes.

[mar]

So just MMX-compare with (hashKey>>56)*0x0101010101010101ULL. If that entire word is 0, (the common case!) you can exclude a hit immediately, without waiting for the cache-line fill to complete. Otherwise you can use the standard bit-extraction techniques to find the 1 bits (and then strip those 8 at the time) to check out the potential hits.

I thought along the same lines and came up with this. Not sure it would work, but if it does then you can do even without SIMD:

Code: Select all

uint64_t unpack_ext_sig(uint64_t sig)
{
    sig >>= 64-8;
    sig *= 0x10101010101010101ull;
    return sig;
}

bool match(uint64_t bhash, uint64_t psig)
{
    auto xunp = unpack_ext_sig(psig);
    bhash ^= xunp;
    bhash &= bhash >> 32;
    bhash &= bhash >> 16;
    bhash &= bhash >> 8;
    return bhash == 0;
}

the idea is to unpack first, then xor. this will produce a zero 8 bits somewhere (if it's present), then you squash it with ands + shifts (if it works).
at the end, if the squashed value is zero, then you have a potential hit in the bucket.

[chrisw]

You don't like it when your stupidity receives extra attention?

Hahahaha! 100% no bugs for chess engines is entirely possible, the mechanics of moving the six pieces in defined ways over 64 squares and performing recursive search are quite trivial. Programmers who won’t work to 100% bug free methods are a liability and unemployable. Yes, that’s my opinion and it’s pretty much all I wrote on the topic. Somehow this has tripped your ego and you resort to silly put downs, well okay, I’m well used to dealing with that too.

The goal is not necessarily writing bug free code, for instance by program proving, because it is quite expensive and difficult to do that. The goal is to remove serious known bugs so that the program operates safely.

Failure to perform the above is simple incompetence.

Well, this is true, but.
If you want to publish, say through a Japanese publisher (because they have the most rigorous QC imaginable), then you have to make sure 100% no possibility your product will hang their hardware to cause an end user to do a power on power off restart. For Sony (eg) that is totally unacceptable and they won’t accept your product. They’ll put your product through every imaginable thing an end user could do, and I had one fail once because play test turned every piece into a Queen, asked for a move, and the search got so lost into extensions it didn’t return quick enough. For them that’s a bug. Well, we fixed it and product was accepted, but huge scene with the intermediary wrap-into-graphics-game publisher who was now under reputational threat by Sony for submitting buggy product and tried stopping final payment. Lawyers, two court hearings, I won plus costs, but even so, it’s the final publisher who owns the gold and who gets to define “bug” and what constitutes 100% no bugs.
By the time you’ve done some work with high-QC customers, on of whom even sent their managers in to mine to oversee our first work for them, programmer sat on day after day by manager who checked and tested everything he did, until no bugs. Can be done, programmers used to being a little careless and not being checked too much really don’t like it, but it works.

[bob]

Definition of a bug - A bug is when the engine doesn't follow the intention of the programmer.

When a programmer can't stand losing a game he will make the engine crash after a losing score.

It's NOT a bug.

[/troll]

No, a bug is when a program does not follow the specifications 100% of the time. Most of us don't have specifications. So we consider bugs to be behavior that we did not intend to happen, as you said. But that is not the formal definition. BTW some bugs do not have any harmful effect. For example, an evaluation test where you are looking to see if a pawn is supported, and on the 2nd rank you look for supporting pawns on the first rank. Is that a bug? Will it affect the program's performance in any way? Would you fix it anyway? I would answer yes, no and yes. There are many such cases that get overlooked because they don't have any harmful effect. Some are intentional. For example, I don't try to recognize hash collisions, even though I know that they have a potential to affect the program's performance. Is that a bug? In a parallel search I know I am going to search nodes that the serial search would not. Does that affect performance? Yep. Is it undesirable? yes. Can it be eliminated? Yes. But at a huge cost. A cost so high that it would be worse than the extra search overhead. So there are lots of types of bugs. Those that cause crashes. Those that call incorrect analysis. Those that impact performance. And some that we are willing to accept because the cure is worse than the disease.

The first two are almost guaranteed to exist in any engine. The current version of Crafty has played over 100 million games on the cluster. I STILL just found a bug that did not change any analysis at all, other than wasting some time that MIGHT have changed the analysis output had it not been wasted. Is that a bug? To me, yes.

I believe it was Dennis Richie (C programming language with Ken Thompson) that wrote "Everyone knows that debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it?" Food for thought.

And finally, before you can claim a program has no bugs, you have to test for 100% of all possible bugs. Finding just one proves it is not bug free. Finding exactly zero proves it is. This latter is simply impossible to do. Automated verification tools? Not a chance. Sufficient test cases? Not a chance. And test cases do not even begin to find all parallel search bugs. The probability of having a bug-free program of the complexity of a chess engine is not zero. But it can be approximated by 1 / infinity. Pretty close to zero.

[bob]

You don't like it when your stupidity receives extra attention?

Hahahaha! 100% no bugs for chess engines is entirely possible, the mechanics of moving the six pieces in defined ways over 64 squares and performing recursive search are quite trivial. Programmers who won’t work to 100% bug free methods are a liability and unemployable. Yes, that’s my opinion and it’s pretty much all I wrote on the topic. Somehow this has tripped your ego and you resort to silly put downs, well okay, I’m well used to dealing with that too.

The goal is not necessarily writing bug free code, for instance by program proving, because it is quite expensive and difficult to do that. The goal is to remove serious known bugs so that the program operates safely.

Failure to perform the above is simple incompetence.

Well, this is true, but.
If you want to publish, say through a Japanese publisher (because they have the most rigorous QC imaginable), then you have to make sure 100% no possibility your product will hang their hardware to cause an end user to do a power on power off restart. For Sony (eg) that is totally unacceptable and they won’t accept your product. They’ll put your product through every imaginable thing an end user could do, and I had one fail once because play test turned every piece into a Queen, asked for a move, and the search got so lost into extensions it didn’t return quick enough. For them that’s a bug. Well, we fixed it and product was accepted, but huge scene with the intermediary wrap-into-graphics-game publisher who was now under reputational threat by Sony for submitting buggy product and tried stopping final payment. Lawyers, two court hearings, I won plus costs, but even so, it’s the final publisher who owns the gold and who gets to define “bug” and what constitutes 100% no bugs.
By the time you’ve done some work with high-QC customers, on of whom even sent their managers in to mine to oversee our first work for them, programmer sat on day after day by manager who checked and tested everything he did, until no bugs. Can be done, programmers used to being a little careless and not being checked too much really don’t like it, but it works.

OK, so NOW you change the definition of a bug and limit it to the case where it can't hang or crash the machine? Nothing wrong with that goal, but that is NOT the definition of a bug that almost 100% of the programmers would accept. What about generating an extra king and rook when you make/unmake a castling move when the king and rook have moved from their original squares? Will that crash the program? If so it is a bug? What if the program continues to play? Is it now not a bug? I can recall the 1976 ACM event where a program pushed a pawn to the 8th rank but did not promote it. Program didn't crash. Didn't blow up the game since the opponent considered the pawn a queen, but the first program just let it sit there. David ruled that the game would continue until this caused a problem that prevented the game from continuing. Was that a bug? To me, absolutely. Based on the "crashes state" it would be no.

I don't think anyone agrees that some third party can define what 100% no bugs means. A bug has a precise definition (violates program specifications in any no matter how small). So once again, we are discussing something where you have a non-traditional definition of a word, and you want to use that non-traditional definition to argue about bugs. How can a resolution EVER be reached? So back to the ACTUAL definition of "bug". In the case of an SMP program, an expectation could legitimately be that N processors produce the same result as the one processor search (which takes T time) but in T/n time. No SMP program meets that specification. So we change the specification to not require T/N speed, but at least something less than the original T. Can't meet that goal either because an occasional search will take greater than T time. Not very often. So we are back to the definition of bug once again. Is this a bug? Can it be fixed? Should it be fixed? first answer is "yes". Second answer is "yes, but at a great performance loss for all the OTHER more normal positions." Third answer "no". Is it reasonable to fix the specifications so that a behavior now doesn't fall outside them? No doubt. But given the original specifications, there is definitely a bug present.

I am MUCH more concerned about all the bugs that likely exist in Crafty that DO affect moves played (and hence effect Elo) that I do NOT know about. Because if I don't know about 'em, I have no idea how they affect the games being played. THOSE are the bugs I am addressing. Not the obvious things. Crafty does a pure minimax search to order root moves. Give it a position with 9 queens on each side and that ordering search might take over a minute. Bug? probably since it would appear to hang in a game/1 minute time control, and would lose on time. Something I am going to fix? No. It is an unnatural position that won't ever occur in a real game.

Your turn.

[hgm]

He even considers it a bug, and reason to be fired over, if someone comes up with a more efficient algorithm than he himself would have used.

[hgm]

So just MMX-compare with (hashKey>>56)*0x0101010101010101ULL. If that entire word is 0, (the common case!) you can exclude a hit immediately, without waiting for the cache-line fill to complete. Otherwise you can use the standard bit-extraction techniques to find the 1 bits (and then strip those 8 at the time) to check out the potential hits.

I thought along the same lines and came up with this. Not sure it would work, but if it does then you can do even without SIMD:

Code: Select all

uint64_t unpack_ext_sig(uint64_t sig)
{
    sig >>= 64-8;
    sig *= 0x10101010101010101ull;
    return sig;
}

bool match(uint64_t bhash, uint64_t psig)
{
    auto xunp = unpack_ext_sig(psig);
    bhash ^= xunp;
    bhash &= bhash >> 32;
    bhash &= bhash >> 16;
    bhash &= bhash >> 8;
    return bhash == 0;
}

the idea is to unpack first, then xor. this will produce a zero 8 bits somewhere (if it's present), then you squash it with ands + shifts (if it works).
at the end, if the squashed value is zero, then you have a potential hit in the bucket.

I don't think this works. You can also get zero during squashing when all key extensions differ from the sought one, but all in different bits. So you would get a lot of false potential hits.

I often regret that there doesn't exist something like a 'logical multiply', which does a binary multiplication using OR on the partial products instead of adding them. A logical multiply of the signature-key XOR with 0xFF would then only leave 0 on the 0x8080808080808080ull bits if the corresponding byte was all 0 (i.e. a match). It could be emulated by

Code: Select all

bhash ^= xunp;
bhash |= bhash << 1;
bhash |= bhash << 2;
bhash |= bhash << 4;
return (bhash & 0x8080808080808080ull) != 0x8080808080808080ull;

[chrisw]

He even considers it a bug, and reason to be fired over, if someone comes up with a more efficient algorithm than he himself would have used.

You two mutually massaging each other is funny.