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.
chrisw
Posts: 3745
Joined: Tue Apr 03, 2012 2:28 pm

Re: hash collisions

Post by chrisw » Tue Feb 18, 2020 7:30 pm

Ovyron wrote:
Tue Feb 18, 2020 6:21 pm
chrisw wrote:
Tue Feb 18, 2020 5:40 pm
Alayan wrote:
Tue Feb 18, 2020 4:01 pm
With a moderately large definition of bug...

Bugs shipped with SF11 and fixed since then :
https://github.com/official-stockfish/S ... dd694a3cec
https://github.com/official-stockfish/S ... 655300ce64
Bugs shipped with SF10 and fixed in SF11 :
https://github.com/official-stockfish/S ... 352a288f07
https://github.com/official-stockfish/S ... 2a0b0e618a
https://github.com/official-stockfish/S ... 0b750b3dda
https://github.com/official-stockfish/S ... 51cf6cacf5
https://github.com/official-stockfish/S ... c005b03df9
https://github.com/official-stockfish/S ... 6d3abc3cbc
https://github.com/official-stockfish/S ... dc1268e4c6
https://github.com/official-stockfish/S ... 86354bf9ae
https://github.com/official-stockfish/S ... a773f82595

Anybody familiar with the Stockfish's development process knew that the claim of no bug in release versions was ridiculous.
Cool. Some data points.
That refute everything you were saying about it. Any other example of "bug-free software" besides Stockfish?
You really don't get it, do you?

petero2
Posts: 610
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

Re: hash collisions

Post by petero2 » Tue Feb 18, 2020 7:36 pm

Ovyron wrote:
Tue Feb 18, 2020 7:26 pm
Oh.

In that case the chess equivalent might be Sting, an engine based on Stockfish 2.1.1 where all known Stockfish 2.1.1 bugs would have been fixed so any bug that it'd have would need to have survived since that version.

So a bug-free version might be possible, but at what cost? (in this case, no improvements from 2.1.1 to version 11.)
Indeed, the cost for TeX was really high. Feature freeze was 30 years ago. The program was written by one of the greatest computer scientists in the world. He set up a bounty system to encourage everyone to report bugs to earn money and fame.

And still, 24 years after feature freeze he had to fix a bug in his program.

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

Re: hash collisions

Post by chrisw » Tue Feb 18, 2020 7:38 pm

bob wrote:
Tue Feb 18, 2020 6:49 pm
chrisw wrote:
Tue Feb 18, 2020 11:48 am
bob wrote:
Tue Feb 18, 2020 2:37 am
So, as usual, you want to just hand-wave the discussion away.
I prefer it to Bob dense paragraph waving. My rule for which has been, for a long time now, the longer you post and the more examples using cars included, the more is the one central point (being usually lost by then anyway) wrong.

This is a major problem. The entire field of software engineering sprang up to make progress. And today, the best SE can do is REDUCE the number of bugs that slip by. It is impossible to eliminate them completely.
your argument is circular. You assume there are always more bugs, therefore you can never get to none. Is like the maths proof about infinity and largest number. If I say N, you say N+1.
If I say N+2, you say N+3 and so on.

There are not an infinite number of bugs in a developing chess engine, obviously. What you are trying to tell us is just wrong, you are telling us that we can’t sit down and methodically test a finite engine of relatively low complexity in a bounded 64 square environment, finding and removing bugs one by one until we found them all. All N of them.

I say it is possible. Signed contracts to do it. Created the infrastructure to do it. Done it. Seen others do it. Got product through the most destructive possible testing environments. Many times.

If we could, that would be the holy grail of computer science.
misuse of concept. You just mean it would be a good thing if stuff worked.

Do some reading. Learn some facts. Then you will begin to understand the problems.
Here we go again. You just can’t stop yourself with the NPD put downs, can you?
Is there a technical argument anywhere that exists where you are not personally insulting the person who technically argues with you?

Having some foreign hot-shot come and yell is NOT going to eliminate all bugs.
actually, it did, and it provided the model by which we did it ourselves. Japanese style quality control. Which created Value, proven by Market.
Only way to do that is to eliminate all programmers, which would then eliminate all programs, which is the only way to eliminate all bugs.
You see anything about cars in my post?

I have not said there is an infinite number of bugs. I have said there is a LARGE number of potential bugs. And there are a significant number of bugs that slip past any type of testing you can throw at it reasonably and be able to complete it without taking years or decades to complete the testing.

What in the above is insulting. You obviously are not familiar with the discipline of software engineering.

Here are a few famous quotes from software engineering:

1. It’s hard enough to find an error in your code when you’re looking for it; its even harder when you’ve ASSUMED your code is ERROR-FREE. (sound familiar?) --Steve McConnell

2. Even the best planning is not so omniscient as to get it right the first time. -- Fred Brooks

3. Program testing can be used to show the presence of bugs, but never to show their absence! --Edsger Dijkstra

4. Before software can be reusable it first has to be usable. --Ralph Johnson

5. Every big computing disaster has come from taking too many ideas and putting them in one place. --Gordon Bell

6. Hiring people to write code to sell is not the same as hiring people to design and build durable, usable, dependable software. --Larry Constantine

7. If you don't know that a bug exists yet, is it still a bug? You seem to think "no" here... I do not.

8. Bottom line: Can you write "Bug free software"? NO Anyone who tells you otherwise is clueless. (note that is ANOTHER quote, not MY words). I presume you will call that an insult. I call it a quote and statement of fact.

9. There is no such thing as a perfect software. Zero bug development is a myth that should be dispensed with.

I found an interesting discussion about bugs. You run on computing hardware. That can have bugs. (remember the pentium floating point divide fiasco for just one example?) You run on an operating system that can have bugs that affect your program. You use multiple programming libraries (IE C library) that can have bugs. You use a compiler to convert your source code to an executable binary. That can have bugs. And, of course YOUR code will always have bugs, particularly if you use threads which adds several more orders of magnitude of potential bugs.

Now, to the above quotes, from some GIANTS of computer science, software development, and software engineering. You seem to believe that you know more than all/any of them. Think about that for a minute, and it might sink in. The GIANTS agree that bug-free software is a dream, not a reality.

Your statement "actually it did..." is utter nonsense. EVERYONE (but you, apparently) agrees that testing can only discover bugs, not prove that they don't exist. To believe otherwise is naive given all the evidence supporting this concept.

I do realize that actual data seems to you to always be an insult, because that is the only way you can escape from a discussion with you having zero supporting evidence to support you other than "your statements. Which have to be factual since you wrote em?" As I said, you should stop, read a bit, and get a better grasp on what is going on. Right now you are "way out there" compared to a bunch of people I have very high respect for.

For your request about EPD testing, _I_ did it. I have code that tests for everything I could think of. No more than 9 queens + pawns, no more than 10 knights, rooks and bishops + pawns. Valid EP status. Valid castling status (at least rooks/kings on original squares, no way to know if they have moved previously and moved back. Side not on move can't be in check. Total pawns + pieces can not be > 15. I ran millions of lines of EPD through my EPD input, then examined the resulting board positions to be sure they were valid, AFTER the EPD input code had checked for every possible error I could think of. And testing showed a couple I missed and had to fix. But once again, testing can not prove the absence of bugs, it can only prove their presence. So I won't claim that my FEN parsing is bug-free. I can only claim that massive testing found no bugs. I know of no holes, but can not guarantee there is a special case I missed. I will add that this checking caused lots of user complaints. They had test positions with 9 queens + 3 or more rooks or other pieces plus pawns still on board. I elected to ignore the complaints and treat EPD as a purely legal position description rather than something off-the-wall. But that is a TINY piece of code compared to the complex parts of Crafty. TINY.

So many of us DO try to test our code as thoroughly as possible. But no code will ever be perfect.
You're not getting it. Read Dann Corbitt. Then try looking for the metaphorical message.

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

Re: hash collisions

Post by Ovyron » Tue Feb 18, 2020 8:13 pm

chrisw wrote:
Tue Feb 18, 2020 7:30 pm
You really don't get it, do you?
No, explain it like I'm 5.

The fact is that shows Stockfish 11 was shipped with 2 bugs, and by the looks of it at least 7 more bugs will have been found until Stockfish 12, unknown bugs that were shipped with the engine's release. And Stockfish 12 will be released with at least 9 bugs that will have been found and fixed on its way to Stockfish 13. And so on, never a bug-free Stockfish in sight as that'd require a code freeze.

Actually, they could do it like Rybka 2.3.2a, have a branch with Stockfish 11 with no improvements and just bug fixes, then we'd have Stockfish 11.2 with no improvements and just the 2 bug fixes and probably the regression code removed. But who would use that if it was weaker than Stockfish dev? We have two kind of users, the ones that are happy with Stockfish 11 despite those bugs, and the ones that aren't, so they want the strongest thing available, and they'll download Stockfish dev with the bleeding edge of improvements that they can get (if an improvement gives 2 elo and it has a bug that hurts 1 elo they'd rather have it than a bug-free one.)

There's no user that would care for a bug-free Stockfish (try it; you can produce it yourself and give them the choice of your bug-free Stockfish and a Stockfish dev with improvements that plays stronger, and nobody would choose your compile.)

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

Re: hash collisions

Post by chrisw » Tue Feb 18, 2020 8:35 pm

Ovyron wrote:
Tue Feb 18, 2020 8:13 pm
chrisw wrote:
Tue Feb 18, 2020 7:30 pm
You really don't get it, do you?
No, explain it like I'm 5.

The fact is that shows Stockfish 11 was shipped with 2 bugs, and by the looks of it at least 7 more bugs will have been found until Stockfish 12, unknown bugs that were shipped with the engine's release. And Stockfish 12 will be released with at least 9 bugs that will have been found and fixed on its way to Stockfish 13. And so on, never a bug-free Stockfish in sight as that'd require a code freeze.

Actually, they could do it like Rybka 2.3.2a, have a branch with Stockfish 11 with no improvements and just bug fixes, then we'd have Stockfish 11.2 with no improvements and just the 2 bug fixes and probably the regression code removed. But who would use that if it was weaker than Stockfish dev? We have two kind of users, the ones that are happy with Stockfish 11 despite those bugs, and the ones that aren't, so they want the strongest thing available, and they'll download Stockfish dev with the bleeding edge of improvements that they can get (if an improvement gives 2 elo and it has a bug that hurts 1 elo they'd rather have it than a bug-free one.)

There's no user that would care for a bug-free Stockfish (try it; you can produce it yourself and give them the choice of your bug-free Stockfish and a Stockfish dev with improvements that plays stronger, and nobody would choose your compile.)
I read you, I understand what you are saying. The inverse isn't the case. You have a literal/metaphorical processing unit between your ears. Work out what you think is the other side's message.

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

Re: hash collisions

Post by Ovyron » Tue Feb 18, 2020 9:11 pm

chrisw wrote:
Tue Feb 18, 2020 8:35 pm
You have a literal/metaphorical processing unit between your ears. Work out what you think is the other side's message.
I guess that's your blanket message for when you fail to express what you want to say?

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

Re: hash collisions

Post by chrisw » Tue Feb 18, 2020 9:22 pm

Ovyron wrote:
Tue Feb 18, 2020 9:11 pm
chrisw wrote:
Tue Feb 18, 2020 8:35 pm
You have a literal/metaphorical processing unit between your ears. Work out what you think is the other side's message.
I guess that's your blanket message for when you fail to express what you want to say?
No, it’s a rule to never explain to those who misunderstand. It’s better for them to work it out themselves, albeit unlikely, and they’re likely misunderstanding for social reasons (social group) which will still remain.

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

Re: hash collisions

Post by Ovyron » Tue Feb 18, 2020 9:43 pm

I think it's supercilious to assume that when someone misunderstands what you say, it's their fault, and that they can get it if they try hard enough, when perhaps they'd do it if you explained better.

So let me guess: are you saying that there's literal bugs and metaphorical bugs, all the Stockfish bugs are literal, so it's metaphorically bug-free? Because that's my best guess.

(and no, I'm not going to pretend that Dann Corbit is on your side and that you're saying what he's saying. You said with enough effort you can get bug-free software, he said "If your code base has half a million lines in it, there will definitely be bugs", which contradicts your statement, so he's on my side)

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

Re: hash collisions

Post by Alayan » Tue Feb 18, 2020 9:58 pm

chrisw wrote:
Tue Feb 18, 2020 9:22 pm
No, it’s a rule to never explain to those who misunderstand. It’s better for them to work it out themselves, albeit unlikely, and they’re likely misunderstanding for social reasons (social group) which will still remain.
You're trying to weasel your way out of admitting that you repeated multiple time "100% no bug" in a way that left no room for ambiguity - it didn't mean trying to minimize bugs, it meant zero bug.

You repeated multiple times how according to you chess engines are so simple a piece of software that they should be completely bug-free, and would be if only their programmers were not lazy slouches ; and wrongly used Stockfish as an example of software that would have bug-free releases.

It was bad enough when you pretended that anybody that doesn't think your 100% no-bug theory is workable would be lazy irresponsible programmers that would oppose decent QA practices. Now, you're pretending those who don't get the "metaphorical message" that would somehow make your wrong claims right are idiots.

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 » 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.
Down with the shit: vote for SHID!

Post Reply