On Crafty...

[Dann Corbit]

Here's the problem, "there is NO public domain code in either program."

So it means you hold copyright on bubble sort in Crafty?
Interesting, I thought the very same implementation of bubble sort you copied verbatim from Knuth...
Clearly you are lying (since there is obviously quite a bit of PD code in Crafty), so why would anyone trust you when you make your usual baseless accusations?

I hold the copyright on _the_ bubble sort in crafty, yes. Not on the bubble sort idea, but on that specific code, along with everything else in there that I wrote. That was simple, wawsn't it. What PD code was in the Crafty that was copied into Fruit? Today's crafty certainly has Pradu's magic move generation code, attributed to him in the comments. The version copied and used in Rybka certainly did not. Please identify any PD code in Crafty, by specific source file name and line numbers, for the 19.0 version used as the basis for Rybka's bitboard code...

ball is in your court... You certainly ought to be able to go to "sorting and searching" by Knuth and cite the exact page where the code was copied "verbatim", correct? Actually, if you look carefully, Crafty uses _TWO_ different types of sorts, depending on whether it is a full-width node or a quiiece-only node. And the code looks nothing like the code you claim I copied "verbatim".

But, your turn...

BTW, you are now trying to justify your "Robolito/etc/Houdini is legal" on the real "stretch" that all Houdart copied into Houdini was the sort code from Crafty? Are you sure that code is in Robolito? Did you see my _explicit_ reference to the bitboard code (particularly the initialization) that is in Robolito?

We've done been down this road once in the Fruit / Rybka discussion. Same lame arguments Each was disproved, over time, by massive evidence. Houdini's day will come, too. Yuri has already commented on it. But don't let that disturb your thinking... Nor any of the other posts concerning Robo and Houdini. Hang on to that dream for as long as you can...

It can be safely said that Crafty's code is beyond reproach.
All contributed code is clearly documented. The historical commentary found in main.c is the example for all programmers to follow.

It would be a benefit to mankind if not just every computer chess program but every program in general were programmed and documented in this way.

As far as the implementation of bubble sort, it is also obvious that Dr. Hyatt has copyright on his own implementation. Failure to understand this is failure to understand what "copyright" means.

Yes, I am a Dr. Hyatt fan, I freely admit. However, that has nothing to do with my opinion on this matter.

The shocking fact is that someone is using bubble sort
Is Crafty using bubble sort or this is one the gazillion Byzantine discussions we see in CCC?
I bet the latter.

Miguel

Crafty uses insertion sort in next.c (2 places I think). It uses a plain bubble sort, but with an early exit (if no two values are exchanged it terminates rather than going for N-1 iterations regardless...

The use of bubble sort in crafty is one of those little ironies...

Bubble sort has a single case where it performs well. That case is where the data is very nearly sorted to start with. In the case of the spot in crafty where it is used, that is indeed the case in point. Despite my well intentioned attempts to improve crafty via insertion sort, it turned out actually inferior, and so the code was reverted back to bubble sort.

[Dirt]

Following your conclusions, there is no verbatim copy of Fruit or Crafty code in Rybka so there is no basis for any complaint against Vas. Similar thing is valid for Rybka/Ippo or Ippo/Houdini issue.
So why is all the fuss then?

Because verbatim copying isn't necessary for copyright infringement. Finding Crafty bugs in Rybka is very damning. There might be a logical explanation aside from copying, but it looks unlikely.

Copyright works at all levels. You could translate a program from C to Pascal and still infringe copyright. At that level it would be harder to prove, but not impossible.

[Milos]

The use of bubble sort in crafty is one of those little ironies...

Bubble sort has a single case where it performs well. That case is where the data is very nearly sorted to start with. In the case of the spot in crafty where it is used, that is indeed the case in point. Despite my well intentioned attempts to improve crafty via insertion sort, it turned out actually inferior, and so the code was reverted back to bubble sort.

It is trivial to prove that insertion sort is more efficient (less swaps) than bubble sort for nearly sorted lists. So it is literally impossible for bubble sort to perform better. If testing showed this, then testing is faulty. As simple as that.

[Milos]

So then it means this investigation of Rybka-Crafty/Fruit is only through functional equivalence of "large swath" of assembly codes. Still such large swath of code equivalence is suspicious - if the blocks are too "large" for comfort.

So we have to let a panel of expert to pronounce. This is how the real world works.

But ...remember how the professional rating agencies rated Lehman Brother's...

I completely agree on that.

[Milos]

Because verbatim copying isn't necessary for copyright infringement. Finding Crafty bugs in Rybka is very damning. There might be a logical explanation aside from copying, but it looks unlikely.

Copyright works at all levels. You could translate a program from C to Pascal and still infringe copyright. At that level it would be harder to prove, but not impossible.

This is all very fine but where you draw the line for copyright?
If I take Knuth's code and translate it to C (and change variable names in the process) do I then hold a copyright? Yes, no? What if change change data types so I compare pointers instead of numbers. Is that enough to claim my own copyright? What if I swap both key and value instead of just value? Is it now sufficient? How can anyone tell when it is?
If original code contained a bug (for example doesn't make swaps in last iteration), and my also contains it, but I made all the changes (translation, changing data types, changing swapping, changing sort direction, changing sort index bounds) does this invalidates my copyright?
You think a court judge would have consistent opinion on that?

[Houdini]

Classic bubble sort. I see _nothing_ verbatim there. I am sorting _two_ values, not just one. I have a value, and a move. I am sorting the moves, but I am using the value as the sort key. So I move both around. Is Knuth doing that? Of course not. Code is different.
I have not said "this is not a bubble sort, it is something original I wrote."
I have said that "this is a bubble-sort that is my original code, it was not copied from _anywhere_."
And that statement stands, and you have not contradicted it in the least.

Thank you for making the statement in bold (my emphasis). It makes the delicate but useful distinction between writing "something original" and writing "my original code".
I'm also glad that everyone agrees that your code is an original, copyrightable version of the bubble sort algorithm.

I'll certainly bookmark this discussion for future use.

Robert

[Sven]

Classic bubble sort. I see _nothing_ verbatim there. I am sorting _two_ values, not just one. I have a value, and a move. I am sorting the moves, but I am using the value as the sort key. So I move both around. Is Knuth doing that? Of course not. Code is different.
I have not said "this is not a bubble sort, it is something original I wrote."
I have said that "this is a bubble-sort that is my original code, it was not copied from _anywhere_."
And that statement stands, and you have not contradicted it in the least.

Thank you for making the statement in bold (my emphasis). It makes the delicate but useful distinction between writing "something original" and writing "my original code".

Simple use of propositional logic proves your sentence wrong. The statement

I have not said "not(A) AND B"

is equivalent to

(I have not said "not(A)") OR (I have not said "B")

but NOT, as you tried to imply:

(I have not said "not(A)") AND (I have not said "B")

So Bob's sentence "I have not said ..." does NOT imply "I have not said it is something original I wrote", therefore the difference you put into his mouth simply does not exist.

Sven

[Sven]

The key point of this quite unimportant "bubble sort" issue from my viewpoint is:

The Donald Knuth book "The Art of Computer Programming" shows, explains, discusses, and teaches algorithms. A large percentage of software worldwide uses algorithms that have been learned from such a book at some time (actually that Knuth book in many cases), which is also the intended goal of such books. Algorithms usually are expressed in "pseudocode", even if - as in the given case - a special language (MIXAL) is used for it. But that expression is not an "implementation" in the sense of something intended to compile and run. (Considering even the existence of an integrated MIXAL development environment does not change anything.)

A textbook like the Knuth book does not contain copyrightable code that implements sorting algorithms but merely the algorithms themselves. It is essential to get that distinction right. So the Knuth book has no code that could be copied, implying that it also does not have "PD" code, implying in turn that the BubbleSort implementation in Crafty - as in any other computer program - is NOT "PD code taken from somewhere". PD (Public Domain) software is software that is not copyrighted, see here and here for instance.

Anyone implementing such an algorithm based on the Knuth book creates an original, copyrightable work thereby. There is zero doubt about that for Crafty, as for all other programs. We are certainly not attempting to redefine copyright here. A book is a book but not a program. (It may have a CD with copyrighted software attached, which would make a different case of course.)

Apart from bursting bubbles, a lot more interesting issue is which chess related pieces of code have been silently used where. I would highly recommend to put more effort into that area than into "bubbles". Overusing the "bubbles" topic leaves me with the impression that some people might want to draw off the attention from something else. Just an impression, though.

Sven

[tomgdrums]

Classic bubble sort. I see _nothing_ verbatim there. I am sorting _two_ values, not just one. I have a value, and a move. I am sorting the moves, but I am using the value as the sort key. So I move both around. Is Knuth doing that? Of course not. Code is different.
I have not said "this is not a bubble sort, it is something original I wrote."
I have said that "this is a bubble-sort that is my original code, it was not copied from _anywhere_."
And that statement stands, and you have not contradicted it in the least.

Thank you for making the statement in bold (my emphasis). It makes the delicate but useful distinction between writing "something original" and writing "my original code".
I'm also glad that everyone agrees that your code is an original, copyrightable version of the bubble sort algorithm.

I'll certainly bookmark this discussion for future use.

Robert

Rather smug from a person who at best answers questions in legally opaque sound bites. You have a long way to go to reach Dr. Hyatt's level of transparency.

[Dirt]

This is all very fine but where you draw the line for copyright?
If I take Knuth's code and translate it to C (and change variable names in the process) do I then hold a copyright? Yes, no? What if change change data types so I compare pointers instead of numbers. Is that enough to claim my own copyright? What if I swap both key and value instead of just value? Is it now sufficient? How can anyone tell when it is?
If original code contained a bug (for example doesn't make swaps in last iteration), and my also contains it, but I made all the changes (translation, changing data types, changing swapping, changing sort direction, changing sort index bounds) does this invalidates my copyright?
You think a court judge would have consistent opinion on that?

Personally, I think the bubble sort is too short for copyright of the object code. It's been implemented thousands of times, and most simple variations have all been tried. In other words, I'd put in the public domain unless there was something very unusual about it. In the source code, though, if you used non-simple variable names it might be copyrightable.

Every byte of Crafty is in the public domain, but not every sequence of bytes. For instance, I'll bet there is an 'A' in Crafty but I can use that snippet all I like: AAA. No violation. At some point the expression of an idea, whether in source, object or general plan, becomes so unlikely to think of independently that it becomes copyrightable. Borderline cases take a judge to decide, and he will listen to experts. At some point it's a crapshoot, though.