hash collisions

[bob]

Then show a list of bugs “that have been there for a while”.

Do you not realize how silly that sounds? If they can't show a list, the program is therefore proven correct? Pick up ANY software engineering textbook and read the chapter on testing.

Having a list of bugs fixed in the last year does not show the program is now bug free, nor does it show it is not bug free. It just shows that all detected bugs have been fixed. The set of all existing bugs is guaranteed to be a super-set that includes the set of known bugs). The problem is finding those in the super-set but not in the known set. Hard to find that which can't be seen, until they produce an artifact that can be seen. Just because you can't see an obstruction in a dead straight road does not mean you can drive your Lambo at 200 miles per hour for an hour with no problem. You can see about 7 miles ahead due to curvature of the earth. What bugs lie beyond your line of sight? How can you know until you actually _get there_?

I doubt you can find a single chess programmer that is actively working on their chess program, who has not discovered an unknown bug in their code while looking for something unrelated. Multiple times in a year. Bugs that have had zero impact on the program (so far as we knew prior to discovering the bug). This is just a part of writing complex software. Shoot, even the "almighty" could not produce a bug-free program in our DNA. If he could not, we certainly can not.

[Ovyron]

Having a list of bugs fixed in the last year does not show the program is now bug free, nor does it show it is not bug free. It just shows that all detected bugs have been fixed.

Yes, and those bugs were shipped with Stockfish 10. I really don't know from where chrisw got the idea that every Stockfish release has been bug-free

[Michel]

This whole discussion is silly. About the only hard requirement of a chess program is that it plays legal moves when given a legal position. So a "bug" in a chess program is mostly an undefined concept.

A pv must be sensible? Some people here will argue that a pv is only "cosmetics"... Endgame trolling (Leela)? Only cosmetics...

[mar]

The only difference between H.G.M’s method and That of Stockfish is that I think H.G.M’s is better since it is cheaper. And who knows maybe even the occasional errors will enhance the search. You might think I am joking but the errors might lead to the same positive effect that you can get by randomise the evaluations a little in that the search will favour lines with more options in them. It might also be that H.G.M’s method is better because the erroneous positions might be more erroneous on average thus cheaper to refute.

Maybe HGM's method is indeed faster/better, but you would have to implement and compare both. Claims are cheap.

I'm not sold on the idea that searching an unintended move somewhere deep in the tree with very low probability is beneficial.
I think it will have no impact at all in fact.

I guess that you are not a programmer.

before you call Chris a non-programmer, look up Chess System Tal

[hgm]

Beware that my method might not be better for Stockfish: what is best will depend on the engine. I heard that Stockfish uses a very short hash signature (like 16 bits), so collisions will be very frequent, and time wasted on searching some garbage line after a collision will add up. My engines, however, typically use 32 bits of signature, and try only 3 or 4 entries per hash probe, so collision rate will be less than 1 in a billion. (Most of my engines are not SMP, so that I don't have to worry about hash corruption by memory races there.)

Not all key collisions would result in a dummy search of a faulty hash move (a large fraction of entries do not contain a hash move at all, because they were fail lows), and for those that do the depth of that search would be the average depth of the nodes in a typical tree (as all nodes stand an equal chance to collide). This will be below 1 (as d=0 QS nodes will be over-represented), or when you do not store QS somewhere between 1 and 2. But the relevant quantity is the average size of the sub-tree for the garbage search. I you calculate how large on average the sub-tree is hanging from a randomly chosen node of a given tree, each depth will contribute about equal (the size of the sub-tree will be inversely proportional to the frequency of the nodes with such a tree), and the average number of nodes in the sub-tree is the depth of the total tree. So we are talking about 100 nodes max, once in a billion times, or an overhead of 0.00001%. (Not sure how you would want to measure that.) As we heard, pseudo-legality testing can take on the order of 0.7%, so even with error margins of several orders of magnitude, there is no doubt at all as to what is faster for my engines. But if the signature is only 16 bits...

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.)

If you want entries much larger than 8 byte, so that economizing on signature length will not get you down to 8, you can still make sure the hash move resides in the same atomically accessed part as the signature, and only place non-critical (i.e. crash-safe) data in the potentially race-corrupted part. Wrong score, depth, bound-type, age should be harmless as far as crashing is concerned.

[chrisw]

It has not been suggested here yet, but a consideration to look at for hash collision testing is the Hamming Distancehttps://www.chessprogramming.org/Popula ... gDistance .

Some programs like Crafty and Fruit use preset hash keys, but other engines are generating random numbers for every new instance of their engine. If the hamming distance of the zobrist keys are zero, then there is a likelihood of hash key failure, especially with lock-less hashing. This can be tested with:

hamming distance = popcount(a ^ b);

Prompted me to test mine (64*6*2 time seeded random numbers at engine initialisation). left it running, exhaustively testing all five-way xor combinations, except any of self with self, so far after about 700,000,000,000,000 combinations tested, minimum popcount = 5, and maximum = 56. Not sure if that's good, bad or merely indifferent. Or why the popcounts are not balanced.

Well, that got to 4 min and 56 max. So now leaving it overnight doing a six-way xor of all with all.

17924800000000 6-way xor tests overnight: min popcount 4, max popcount 56 and obviously no xors to zero result. Good enough, maybe.

[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.

Please educate us all, by showing us YOUR 100% bugfree chess engine.

Oh, you don't write code? What a surprise…

Probably when you were still in nappies, kid.
Code writing is basic literacy nowadays, and it’s also not much of a deal to claim to be a “coder”, programmers are just another set of skilled workers, the real talent is how to think, how to design, how to include factors from other skill sets, and is found in those who generate whole systems, whole products that work. Those people will be “coding” much as they speak English, its just another aspect of literacy, and they’ll be just as likely supervising programmers, because they have management talents also.
Have a nice day, and remember your manners next time.

[hgm]

Hamming distance in the basis keys has no correlation with key independence, or even a negative one. This has been discussed many times before. E.g. for a set of three 48-bit keys (plus 0) the set FFFFFFFF0000, FFFF0000FFFF and 0000FFFFFFFF (hex) have hamming distance 32, but XOR any two of those, and you get the third. If you take 1, 2 and 4, they would have Hamming distances of 2 (or distance 1 to 0), but they would be independent. There exists a mathematical recipe for generating a set with maximum Hamming distance, and it works by generating each next element by XOR-ing two that were already in the set, i.e. the worst dependence you could have without using more copies of the same key.

BTW, the most efficient way to test dependence is to store all XORs of a number of keys (say 3) in a hash table; as soon as you get a collision in this table, (i.e. same XOR result for a different set of 3 keys) you have detected a dependence of double that number of keys (so 6). For detecting (say) 5-way dependencies you would (hash-)tabulate all combinations of 2 keys, and then probe them for all combinations of 3.

Also note that not all 64*6*2 keys need to be independent. Because you know there will be only a single King of each color, you can generate a set of 64 King keys from just 6 independent keys (one for each bit in the square number, XOR-ing those for the 1 bits together). The set of 64 will then have very high (3-way) dependency: the XOR of any two will produce another key in the set. But you don't care, as only a single key of the set will be used in the total board key. If you don't care about super-numerary pieces, you can affort the sets of 64 keys for N,B,R and Q (it is probably save to make accomodations for 2 Queens) to contain 4-way dependencies, etc. By having the keys for the individual pieces be dependent in a way that doesn't hurt, they will span a smaller section of the total key space, leaving more room for avoiding collisions between keys of different pieces.

[chrisw]

Then show a list of bugs “that have been there for a while”.

Do you not realize how silly that sounds?

Still on the NPD put-downs? Can't help yourself?

And no, it doesn't sound silly at all. Someone said there's a list of bugs, so I responded, ok show us the list of bugs. Why would you think that was "silly", when it's just a request for actual evidence of an assertion? Well, it isn't silly, but you needed to get a rudeness/put-down into your first sentence, we've spoken about this on your part in the past, I think?

If they can't show a list, the program is therefore proven correct? Pick up ANY software engineering textbook and read the chapter on testing.

You can stop the patronising telling me to read XYZ as well. Is just another gratuitous put-down, and you know what those mean about you.

If there's no list (it was asserted a few posts ago that there is a huge list) then that is good evidence for 100% bug free over the time the list was compiled. Stockfish is a remarkably solid program, and that's down to management and attitude and testing.

Having a list of bugs fixed in the last year does not show the program is now bug free, nor does it show it is not bug free. It just shows that all detected bugs have been fixed. The set of all existing bugs is guaranteed to be a super-set that includes the set of known bugs). The problem is finding those in the super-set but not in the known set. Hard to find that which can't be seen, until they produce an artifact that can be seen. Just because you can't see an obstruction in a dead straight road does not mean you can drive your Lambo at 200 miles per hour for an hour with no problem. You can see about 7 miles ahead due to curvature of the earth. What bugs lie beyond your line of sight? How can you know until you actually _get there_?

I doubt you can find a single chess programmer that is actively working on their chess program, who has not discovered an unknown bug in their code while looking for something unrelated. Multiple times in a year.

Obviously. When something is being worked on there will be bugs of one sort or another. By the time its considered finished and been through QC and testing through to release, the goal, the requirement is 100% no bugs. That's entirely doable for something (a chess program) relatively simple that's come out of a long history of computer chess. No excuse at all for anything to be broken. That's the publishing requirement, and those of us who have worked to 100% no bug contracts know how to deliver.

Bugs that have had zero impact on the program (so far as we knew prior to discovering the bug). This is just a part of writing complex software. Shoot, even the "almighty" could not produce a bug-free program in our DNA. If he could not, we certainly can not.

[Rebel]

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]