hash collisions

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 24877
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: hash collisions

Post by hgm » Wed Feb 19, 2020 8:13 am

I once spent a full day debugging a program for doing a convolution, because it failed my test for the surface area under the convolution result being the product of the surface area of the input curves, but was instead about 50% larger. I just couldn't see what I was doing wrong, so I started simplifying the program as much as I could by stripping away parts in a way that would preserve the error. I was finally left with a one-line program:

writeln(1.000e-26);

The output of this program was

1.486542e-26

When I complained about this to our IT department theys said the floating-point printing code issued by the Pascal compiler took some shortcuts 'for efficiency'...
Down with the shit: vote for SHID!

Dann Corbit
Posts: 11621
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: hash collisions

Post by Dann Corbit » Wed Feb 19, 2020 8:17 am

Alayan wrote:
Wed Feb 19, 2020 12:49 am
Rebel wrote:
Wed Feb 19, 2020 12:14 am
The compiler you use creates 100% bug free code.

So bug free complicated programs do exist.
You mean to say that the compiler itself is bug-free ?

Compilers are very refined software, because it's one area were high-quality is mandatory and they are the focus of a lot of attention.

But compilers are not bug-free.

Here is GCC's C++ bug tracker. Several (potential) bugs are reported here every day.

Now, depending at which level you decide to call something "complicated" and how much time talented people spend looking at the code over and over after a total feature freeze, you might get something that is bug-free. You won't be able to prove it to be so, though, unless you put the threshold for "complicated" really low. And actually succeeding becomes exponentially unlikely with the complexity of the program. Which, once again, doesn't mean that proper QA practice to catch issues, and to fix known issues, are not useful.
Note that they have something called a "bug tracker" which implies not only that they take note of program flaws, but it's also have a methodology to actually address these problems. Now, this is a product that is given away for free. That shows it can be done. Even in a free software environment.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

User avatar
hgm
Posts: 24877
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: hash collisions

Post by hgm » Wed Feb 19, 2020 9:09 am

chrisw wrote:
Tue Feb 18, 2020 11:35 pm
hgm wrote:
Tue Feb 18, 2020 10:47 pm
I think the main problem is that you take what he says seriously, as if it would be part of a rational discussion, rather than just incoherent rambling.

haha! But not funny, really. I think you ought to know that an authority figure (mod), encouraging mobbing behaviour, is a psychopathy tick box. We can carry on the wild abuse on CTF if you like, it's kind of tolerated over there.
On the contrary, I try to prevent mobbing by making potential mobbers aware that whatever nonsense you write and false accusations you make are only worth to be laughed at. Rather than something to be taken seriously and get so worked up about that they feel would feel the urge to refute it, so that they would get drawn into your spiral of aggressive verbal abuse.

The quoted posting should be seen as a plea to the author of the preceding posting to just drop the issue and go away (which he wisely did), thus dispersing the mob, as in the eyes of an unbiased reader the issue has been solved long since.

I can add that your trolling now has completely hijacked this thread, which originally was a serious question about treatment of hash collisions by an active engine developer. If trolling was a violation of the charter, I would have had to ban you already...
Down with the shit: vote for SHID!

chrisw
Posts: 3745
Joined: Tue Apr 03, 2012 2:28 pm

Re: hash collisions

Post by chrisw » Wed Feb 19, 2020 11:43 am

bob wrote:
Wed Feb 19, 2020 3:07 am
Now there's a joke. :) Care to come back to reality and the actual discussion???

UAB police have this ugly concept where they notify anyone that gets a formal complaint filed. Care to guess what _I_ got from them? Nada.

Again, dishonest and posting crap.
Well, that's a challenge.

UABPD Case 201207676
UAB Police Department
Criminal Investigation Division
102F Police Headquarters Building
1117 14th Street South

NEVER threatened anyone with any sort of violence on the RF either.
Well, you did once. Maybe the Criminal Complaint worked if you've not done it again.


And neither do I have abuse fantasies.
Your posts contain far too many abusive fecal references, despite multiple complaints, you don't seem able to get it into your head just how disgusting your language actually is. Not to mention utterly inappropriate. This is a computer chess forum where one would have assumed a certain minimum of manners would apply, you go regularly through any minimum level and into the sewers like its a natural place for you to be.
About the only thing I fantasize about is that maybe one day you will participate in a legitimate discussion,
You mean like positing that chess engines are not sufficiently complex for 100% bug elimination to be a thing? That acceptance of, or excuse of, bugs in chess engines is a question of attitude. Or that "chess engine complexity" is on a pedestal here. Seem entirely legitimate viewpoints. But I see that anyone disagreeing with you is automatically "illegitimate".

offer real data, and maybe learn something in the process. But is clearly a fantasy, it would seem...

chrisw
Posts: 3745
Joined: Tue Apr 03, 2012 2:28 pm

Re: hash collisions

Post by chrisw » Wed Feb 19, 2020 12:06 pm

hgm wrote:
Wed Feb 19, 2020 9:09 am
chrisw wrote:
Tue Feb 18, 2020 11:35 pm
hgm wrote:
Tue Feb 18, 2020 10:47 pm
I think the main problem is that you take what he says seriously, as if it would be part of a rational discussion, rather than just incoherent rambling.

haha! But not funny, really. I think you ought to know that an authority figure (mod), encouraging mobbing behaviour, is a psychopathy tick box. We can carry on the wild abuse on CTF if you like, it's kind of tolerated over there.
On the contrary, I try to prevent mobbing by making potential mobbers aware that whatever nonsense you write and false accusations you make are only worth to be laughed at. Rather than something to be taken seriously and get so worked up about that they feel would feel the urge to refute it, so that they would get drawn into your spiral of aggressive verbal abuse.

The quoted posting should be seen as a plea to the author of the preceding posting to just drop the issue and go away (which he wisely did), thus dispersing the mob, as in the eyes of an unbiased reader the issue has been solved long since.

I can add that your trolling now has completely hijacked this thread, which originally was a serious question about treatment of hash collisions by an active engine developer. If trolling was a violation of the charter, I would have had to ban you already...
Well, I tracked back the thread to the first piece of personal commenting, and it came from YOU.

"Then writing chess programs is the wrong buiseness for you." The inversion of actual reality is a clear personal insult there. And the comment, along with various others, is actually a shot at social group exclusion. You also use of a lot of “we” language, as if there is an in-group and an “other”. Later, you use words like: paranoia, delusion, rambling. Bob chimes in with dishonest and so on. That's authority figures (mods) not only becoming personal *first* in the thread, but also giving the green light for mobbing, and it’s motivation, plus plenty later continuation green lights for continued mobbing, and mobbing there was, for sure.

The accusation “trolling” and the implied threat is another continuation and encouragement of mobbing behaviour with exclusion objective. It is not "trolling" to take a minority position. The consensus view that chess engines are by necessary definition hiding unknown bugs is unproven. The consensus view that the number of possible bugs in a chess engine is intractably large is not proven. Have a nice day.

User avatar
Ovyron
Posts: 4393
Joined: Tue Jul 03, 2007 2:30 am

Re: hash collisions

Post by Ovyron » Wed Feb 19, 2020 1:43 pm

chrisw wrote:
Wed Feb 19, 2020 1:24 am
Chess engines are on a continuum of simple-complex, nobody really knows the point where bugs get “inevitability” status no matter what
I think I do: it's at the point at which the cost of being bug-free becomes higher than what you can improve in the program.

The only way to kill all bugs is to dedicate time to finding and fixing current ones, and stop new code from entering that could have bugs. That'd require some code freezing.

Chess is an exponential problem, so to keep improving a program you need exponential improvements. Stockfish's development has been amazing! Adding about 50 ELO per year, on top of the strongest A/B engine available, with no sign of stopping, unlike chess programs of the past that had linear growth, that even gave the illusion of being close to maxing out potential progress because they were plateauing.

It is the greatest chess example of what community collaboration can achieve, and they've made the right decisions in many areas as shown by their feats, and they decided that the cost of being bug-free wasn't worth it, and that releasing a buggy Stockfish was fine, because the improvements that chess requires don't allow you a single second of code freezing to squash bugs, because if you don't increase exponentially, your improvement flat-lines.

Bugs aren't inevitable, but whoever is willing to pay the price for bug freedom will never reach the top.

If you were in charge of Stockfish, with your attitude towards bugs, it could never have gotten off the ground.

User avatar
hgm
Posts: 24877
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: hash collisions

Post by hgm » Wed Feb 19, 2020 1:54 pm

Well, there is no telling what crazy people might consider insults or not.

Fact is that all chess programs of any significance (strength-wise) use approximate and heuristic techniques, known to be prone to failure. One can mention null move (fails in the presence of zugzwang), transposition hashing (can cause failure of repetition detection), most forward-pruning techniques, too short hash keys (inviting key collisions and possible blunders)... Reject all of those as bugs, because their manifestation "damages the reputation of your brand", and you would not be able to reach any strength.

So no, not an insult at all, just a dry, clean fact: those not willing to use the best we have because it is not perfect, better not take up chess-engine programming. You don't have to agree with that, and you can even argue against it, but you cannot whine 'insult' because of it. To tell a Flat Earther the Earth is a sphere is NOT an insult.

If there is any insult here, it is self-inflicted. By taking a stance that so obviously conflicts with reality, you made a fool of yourself. It is not the person who points out the discrepancy of between what you confess and what you actually do who delivers the insult. Such a person just exposes the insult that you prepared for yourself.

Defending a minority POV is not trolling. Constantly changing such a view, denying that you ever had it, accompanied by nasty remarks against people that pointed out you had it, totally misrepresenting the views of people that argued against your views... Yes, in my book that is trolling.
Down with the shit: vote for SHID!

Alayan
Posts: 422
Joined: Tue Nov 19, 2019 7:48 pm
Full name: Alayan Feh

Re: hash collisions

Post by Alayan » Wed Feb 19, 2020 5:07 pm

Dann Corbit wrote:
Wed Feb 19, 2020 8:17 am
Note that they have something called a "bug tracker" which implies not only that they take note of program flaws, but it's also have a methodology to actually address these problems. Now, this is a product that is given away for free. That shows it can be done. Even in a free software environment.
This was not debated as far as I can tell ; it's proper software development practice.

chrisw
Posts: 3745
Joined: Tue Apr 03, 2012 2:28 pm

Re: hash collisions

Post by chrisw » Wed Feb 19, 2020 8:18 pm

hgm wrote:
Wed Feb 19, 2020 1:54 pm
Well, there is no telling what crazy people might consider
still insulting? actually it’s pretty much my opinion of you, not without actual quotable cause either. I’ll ask the psychotherapist next time I see her, but “crazy” would not be the diagnosis, sorry about that. Disagreeing with the National Union of Chess Programmers and whatnots is not “crazy”, and the stronger the counter reaction from the entrenched interests, the more likely the disagreement is correct.

insults or not.

Fact is that all chess programs of any significance (strength-wise) use approximate and heuristic techniques, known to be prone to failure. One can mention null move (fails in the presence of zugzwang), transposition hashing (can cause failure of repetition detection), most forward-pruning techniques, too short hash keys (inviting key collisions and possible blunders)... Reject all of those as bugs,
if you need to invent the opposition’s position it’s usually a sign of, never mind. Pointless.

because their manifestation "damages the reputation of your brand", and you would not be able to reach any strength.

So no, not an insult at all, just a dry, clean fact: those not willing to use the best we have because it is not perfect, better not take up chess-engine programming.
well, both you and Bob, for sone reason, perhaps you are similar, are often insulting people’s core identity. How does it sound if you’re told “you’re unsuited and shouldn’t be in the business of being an academic”? Is not good, is it? Or as Bob tells lawyers they are not real lawyers, or programmers they are not real programmers. You do have form here, you realise?
You don't have to agree with that, and you can even argue against it, but you cannot whine 'insult' because of it. To tell a Flat Earther the Earth is a sphere is NOT an insult.
to tell an academic he should not be an academic is an insult. I tell you why is not the same as flat-earthers. First is unlikely it’s their core identity, second it’s a belief, they can choose. As an insult it’s not in same league.

If there is any insult here, it is self-inflicted. By taking a stance that so obviously conflicts with reality, you made a fool of yourself.
you just can’t stop can you?
I offered you to continue the personal attack fest over on CTF but seems you really prefer polluting here instead,
It is not the person who points out the discrepancy of between what you confess and what you actually do who delivers the insult. Such a person just exposes the insult that you prepared for yourself.

Defending a minority POV is not trolling. Constantly changing such a view, denying that you ever had it, accompanied by nasty remarks against people that pointed out you had it,
I remind you again, YOU initiated the personal abuse. YOU signalled in multiple ways to initiate a mobbing. You’re still at it.

totally misrepresenting the views of people that argued against your views...
hahahahaha! Exactly what you do. Projection.
Yes, in my book that is trolling.
I’ll think up a suitable expression for a weak person who recruits mobbers and then encourages them.

Have a nice day and why not just shut up?

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: hash collisions

Post by bob » Wed Feb 19, 2020 8:59 pm

Dann Corbit wrote:
Wed Feb 19, 2020 8:17 am
Alayan wrote:
Wed Feb 19, 2020 12:49 am
Rebel wrote:
Wed Feb 19, 2020 12:14 am
The compiler you use creates 100% bug free code.

So bug free complicated programs do exist.
You mean to say that the compiler itself is bug-free ?

Compilers are very refined software, because it's one area were high-quality is mandatory and they are the focus of a lot of attention.

But compilers are not bug-free.

Here is GCC's C++ bug tracker. Several (potential) bugs are reported here every day.

Now, depending at which level you decide to call something "complicated" and how much time talented people spend looking at the code over and over after a total feature freeze, you might get something that is bug-free. You won't be able to prove it to be so, though, unless you put the threshold for "complicated" really low. And actually succeeding becomes exponentially unlikely with the complexity of the program. Which, once again, doesn't mean that proper QA practice to catch issues, and to fix known issues, are not useful.
Note that they have something called a "bug tracker" which implies not only that they take note of program flaws, but it's also have a methodology to actually address these problems. Now, this is a product that is given away for free. That shows it can be done. Even in a free software environment.
I don't follow the above. What is the "it" in "it can be done?" The implication is you are talking about the compiler, but I suspect I am wrong. And again, detecting and fixing bugs is only a part of the problem that can be solved. The rest of the problem is "detecting the REST of the bugs that testing doesn't expose."

Post Reply