hash collisions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Dann Corbit
Posts: 11221
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: hash collisions

Post by Dann Corbit » Wed Feb 19, 2020 9:07 pm

bob wrote:
Wed Feb 19, 2020 8:59 pm
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."
What I was referring to was a free project {the GCC compiler} that is managed rationally. They have a database to track errors and manage the correction of the errors. Workers remove defects while improving the project's functionality at the same time.

Even though you will never remove all the bugs from a very large process, that does not mean that you should not attempt to remove the well known errors that are potentially harmful and that are easy to fix.

It is possible to write perfect code through program proving. But it is so expensive that nobody does it (that I know of).
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.

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

Re: hash collisions

Post by bob » Wed Feb 19, 2020 9:07 pm

Ovyron wrote:
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.
I have to disagree here. If you stop development on some program right now, and continue to test and fix bugs for the next 10 years, will it then become "bug free"? My favorite quote here is "Program testing can be used to show the presence of bugs, but never to show their absence! --Edsger Dijkstra" I don't see any way to show the absence of bugs until you do the ultimate testing, which is to execute every possible path within a program with every possible value of the inputs. That is quite a chore once you reach 1000 lines of code, much less 10K, 20K, etc. And, again, this ignores the basic impossibility of testing parallel code exhaustively because now you need to try every combination of instructions against the instructions of the other thread, also in every combination of timing. Talk about computationally intractable...

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

Re: hash collisions

Post by bob » Wed Feb 19, 2020 9:10 pm

Dann Corbit wrote:
Wed Feb 19, 2020 9:07 pm
bob wrote:
Wed Feb 19, 2020 8:59 pm
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."
What I was referring to was a free project {the GCC compiler} that is managed rationally. They have a database to track errors and manage the correction of the errors. Workers remove defects while improving the project's functionality at the same time.

Even though you will never remove all the bugs from a very large process, that does not mean that you should not attempt to remove the well known errors that are potentially harmful and that are easy to fix.

It is possible to write perfect code through program proving. But it is so expensive that nobody does it (that I know of).
I would agree with that. In my case, EVERY detected bug is fixed. Sometimes a one line change. Sometimes a 1K line rewrite. But those are the only ones I can fix, the ones I have identified. And note that some are identified by looking over the code from time to time to detect unknown bugs that have yet to cause a problem that could be noticed during a game.

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

Re: hash collisions

Post by Ovyron » Wed Feb 19, 2020 9:55 pm

bob wrote:
Wed Feb 19, 2020 9:07 pm
I have to disagree here. If you stop development on some program right now, and continue to test and fix bugs for the next 10 years, will it then become "bug free"?
My point was that even if doing so allowed you to become "bug free" it wouldn't be worth the cost.
bob wrote:
Wed Feb 19, 2020 9:07 pm
I don't see any way to show the absence of bugs until you do the ultimate testing
Being bug free doesn't equal knowing about it. It's possible you find all the bugs and kill them, and since your code is frozen you're not introducing new ones. But you wouldn't know, so you could expect that someone will find a bug in the future, they won't because you're done, but there's no way to know.

User avatar
hgm
Posts: 24651
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 10:12 pm

Crazy people can see insults in everything. Their lack of rational behavior both sees to that and earns them the label. That is just a fact of life, and not an insult, certainly not to anyone in particular.

You apparently see insults in the most innocent things, and cannot help to shout it from the roofs. That surely will make people think...

He who habitually behaves like an idiot, is by definition an idiot. Again, not an insult, but a fact. Calling such a person an idiot is not an insult, but a diagnosis...
chrisw wrote:
Wed Feb 19, 2020 8:18 pm
Have a nice day and why not just shut up?
You are not very good at taking your own medicine, hey? It is always others that are mean to you, never your own fault, right?

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

Re: hash collisions

Post by chrisw » Wed Feb 19, 2020 10:44 pm

hgm wrote:
Wed Feb 19, 2020 10:12 pm
Crazy people can see insults in everything. Their lack of rational behavior both sees to that and earns them the label. That is just a fact of life, and not an insult, certainly not to anyone in particular.

You apparently see insults in the most innocent things, and cannot help to shout it from the roofs. That surely will make people think...

He who habitually behaves like an idiot, is by definition an idiot. Again, not an insult, but a fact. Calling such a person an idiot is not an insult, but a diagnosis...
chrisw wrote:
Wed Feb 19, 2020 8:18 pm
Have a nice day and why not just shut up?
You are not very good at taking your own medicine, hey? It is always others that are mean to you, never your own fault, right?
Let's just make it quite clear, since you misinterpret everything. I am not complaining on my behalf about your insults. I can look after myself, thank you. I am pointing to the fact that YOU are an insulter as a matter of course, that YOU encourage mobbing, that YOU initiated the insults, that there is something wrong with YOU, That YOU built the thread to defcon insult level 3 or whatever. And YOU are still doing it. Is that clear now? Insult away, it's not important, who are you? Actually? Why should anyone be concerned with yet another internet whatever it is you are? Really, just shut up your cowardly trolling from safety position. Have a nice day.

User avatar
Rebel
Posts: 5351
Joined: Thu Aug 18, 2011 10:04 am

Re: hash collisions

Post by Rebel » Wed Feb 19, 2020 10:45 pm

hgm wrote:
Wed Feb 19, 2020 10:12 pm
Crazy people can see insults in everything. Their lack of rational behavior both sees to that and earns them the label. That is just a fact of life, and not an insult, certainly not to anyone in particular.

You apparently see insults in the most innocent things, and cannot help to shout it from the roofs. That surely will make people think...

He who habitually behaves like an idiot, is by definition an idiot. Again, not an insult, but a fact. Calling such a person an idiot is not an insult, but a diagnosis...
chrisw wrote:
Wed Feb 19, 2020 8:18 pm
Have a nice day and why not just shut up?
You are not very good at taking your own medicine, hey? It is always others that are mean to you, never your own fault, right?
Next time say that into his face.
90% of coding is debugging, the other 10% is writing bugs.

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

Re: hash collisions

Post by bob » Thu Feb 20, 2020 1:43 am

I would be more than happy to. What's the point here???

lauriet
Posts: 197
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: hash collisions

Post by lauriet » Thu Feb 20, 2020 6:02 am

To Chrisw.

Here is my spec for a computer chess program from my client.

1: It should except legal moves.
2: It should make legal moves.
3: It should not lock up or crash in any way.
4: It should play to the highest ELO.

If spec 1,2,3 are taken care of, then spec 4 is the priority.
My client wants you to pay attention to spec 4 especially, since it sells more units.

My client knows nothing about programming, or programming languages, or team management, or algorithms, or compilers, or testers, or managers,
or academics, or programming philosophy........he only wants spec 1,2,3,4 met.

He will only pay you if you meet spec 1,2,3,4..........especially spec 4.
If he gets a phone call from 1 customer in every 10,000,000 units sold about strange behaviour that can't be reproduced, he will accept this and pay you for your work.
You have 3 months to complete the project, and satisfy spec 1,2,3,4.

Over to you.....................

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

Re: hash collisions

Post by hgm » Thu Feb 20, 2020 8:40 am

Rebel wrote:
Wed Feb 19, 2020 10:45 pm
Next time say that into his face.
Then what? What response do you expect him to exhibit that would make that an interesting experiment? Explain yourself!

Post Reply