On Crafty...

[bob]

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.

Says the voice of authority. # of swaps is not the only issue. # of loop iterations is just as important. But you wouldn't know or understand that anyway...

[bob]

So which is it? You originally said "verbatim." which has a specific meaning. Now you say "functionally equivalent" which means the two "ideas" are the same, They are certainly not "semantically equivalent." I have already explained why.

Nope, I originally said copyright. Agian you are changing subject and topic as it suits you. For claiming your own copyright it's not enough to just change variable names and you know it. You are just playing dumb.

So I just imagined this direct quote from the first post in this specific thread:

Interesting, I thought the very same implementation of bubble sort you copied verbatim from Knuth...

That "verbatim" is my imagination???

It would have been quite a trick, since Crafty would have to have a MIX interpreter since Knuth writes all of his algorithms in MIX.

Minor detail. Details or facts don't matter in this discussion...

[bob]

It can be safely said that Crafty's code is beyond reproach.
All contributed code is clearly documented.

I don't think that's really true. As an easy example, the Random32() function STILL doesn't have attribution, even though it's been brought up a zillion times before...

Then what is this:

Code: Select all

/*
 *******************************************************************************
 *                                                                             *
 *  A 32 bit random number generator. An implementation in C of the algorithm  *
 *  given by Knuth, the art of computer programming, vol. 2, pp. 26-27. We use *
 *  e=32, so we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which  *
 *  is implicitly done by unsigned arithmetic.                                 *
 *                                                                             *
 *******************************************************************************
 */
unsigned int Random32(void) {

That is taken from utility.c, starting at line #2991.

This is in Crafty version 20.0, same source file:

Code: Select all

/*
 A 32 bit random number generator. An implementation in C of the algorithm
 given by Knuth, the art of computer programming, vol. 2, pp. 26-27. We use
 e=32, so we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which
 is implicitly done by unsigned arithmetic.
 */

unsigned int Random32(void)
{

Or this in version 17.0, same file:

Code: Select all

/*

A 32 bit random number generator. An implementation in C of the algorithm given by
Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
done by unsigned arithmetic.

*/

unsigned int Random32(void) {

So care to explain _exactly_ what you are talking about???

Seems like a perfect citation to ma, page number, title of book, author, etc. Sheesh, are you now trying to emulate Milos?

As far as the "this has been brought up a zillion times before" wouldn't you call that just "a bit of an exaggeration"? It has been brought up exactly zero times...

Just for the record, from Crafty 11.13 that played in the WMCCC in 1996, which anyone can find in that specific source file:

Code: Select all

*

A 32 bit random number generator. An implementation in C of the algorithm given by
Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
done by unsigned arithmetic.

*/

unsigned int Random32(void)
{

All I can say is "ahem... better check your facts before writing nonsense, don't you think?"

[bob]

It can be safely said that Crafty's code is beyond reproach.
All contributed code is clearly documented.

I don't think that's really true. As an easy example, the Random32() function STILL doesn't have attribution, even though it's been brought up a zillion times before...

I have long been of the opinion that writing any computer program should be exactly the same as writing a reference book. By this I mean that every external piece of information should have a citation complete with original author, etc.

I remember my excitement when I heard about "literate programming" since I supposed that my intended approach might be what was described, but it turns out not to be the case, and WEB is a pain in the posterior {*}.

Let me amend my claim concerning Crafty:
Of the hundreds of chess programs for which I have read the source code, Crafty, by leaps and bounds, is the most careful and complete as far as proper citations for original material is concerned.

I am not surprised that the goal has fallen short of perfections and I would also be very keen to see a program which was better documented as far as historical sources and modification history.

{*} IMO-YMMV

You should have simply looked at the source. See my reply to Zach. This function has been properly cited dating back to the 1996 WMCCC event version...

[bob]

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.

Nope, you are sorting only one value sort_value. You have only one comparison. You are however swapping 2 values, but that's just irrelevant. You seams not to understand the difference between sorting (comparing) and swapping. Maybe you didn't copied the code, maybe Vas also didn't copy the code. However, concerning presented evidence and your reasoning (definition of verbatim copying) none of it is provable. So it's again forcing ppl to believe just because you are some kind of authority. Sorry, not good enough.

Now that is 2 out of the 4 sorts you find in Crafty. Do we go through the other two as well. Again. _nothing_ has been copied.

So you say. Vas says the same. Judging by the authority (since there is nothing else left, since none did verbatim copying by your own definition) by the success of the program he should be believed first since all of his programs are far more successful than any of yours.

There is a lot that you don't know. Did you know that the old Xerox sigma 6, 7 and 9 computers had pointers? if the high order bit of something used as an address was set, then that indicated that the value was "indirect" and had to be dereferenced. And it was recursive. Lot you don't know.

Thanks for the lesson in prehistoric computer "design". If I needed one, I would go to technology museum. So how is that relevant to anything in the discussion?

In assembly language, most of us consider this a pointer:

mov eax, [ebx]

where this is a simple value:

mov eax, ebx.

Yes, it is also called "register indirect". It's a pointer. The register doesn't contain the value, it contains the address of the value. That's a pointer.

Most of you is you and ppl you blindly follow your authority. For others there is a referent literature. And this one says differently.
You are well known for trying to dispute the common facts and definitions in AI/CS field and introduce your own. However, that doesn't make you any more special, just more weird.

I don't create definitions, but I do tend to like to use accepted ones, whether I think they are the best choice or not...

I don't even want to guess what you are talking about. But it is certainly technically irrelevant and incorrect, so there's no point in trying to figure it out.

You have no other argument but to call on your authority. Sorry, but that one does not really exist in the real world outside of this forum and even here is not unanimous.

Not a "hunch". It is more correctly called "experimental testing." Feel free to rip the insertion sort out of next.c and copy it into quiesce.c. It will plug in perfectly. See what happens. No guesswork. No wondering. Just run a 2 billion node search with each and see which one is faster. Then you don't need a hunch. I certainly didn't need one.

You cannot measure reliably (with sufficiently small error margin) this kind of difference by measuring time. So simply speaking, I don't know what you've tested and how you've tested it, but that's simply BS.

So _you_ don't know how to measure something that small? I do. Measure it a zillion times. A zillion times a small number suddenly becomes a bigger number that _can_ be measured. I can measure the speed difference of a single poorly-constructed if statement. Sorry if you don't know how to do that...

On the other hand there is quite accurate math in Knuth's book that says you have no clue what you are talking about.

Knuth's "math" doesn't take into account branch prediction issues, cache line loading issues, pipeline stall issues, etc... All of that says _you_ are the one with no clue...

I'm not changing _anything_. In our analysis of Rybka, we showed several complete functions from Rybka. Compared directly to the same functions in Crafty. The code was _identical_. You compile your "knuth code" and compare the compiler output to my sort and see how "identical they are." Then you can join the argument intelligently.

The code might have been identical by one of your custom handy definitions of identical but not by your own definition of verbatim. Since you are frequently using verbatim with respect to Rybka/Fruit/Crafty issue you are simply slandering.

"verbatim" is your issue, not mine. We (the entire group) have said all along that all of the code could _not_ be copied verbatim. Because he copied Fruit's search and evaluation, which don't mesh with my bitboard code he copied. So both had to be changed in some places (but not in all places). So please, go away, and come back once you are up-to-date on what has transpired. We have now gone from "I copied verbatim" (which was a complete crock as you apparently now accept) to "Vas didn't copy everything verbatim" which we have never claimed he did...

First things first. Still waiting on your "verbatim copy from Knuth to Crafty." Am also still waiting on your "lots of PD code in Crafty." Lest you try to forget, intentionally:

You are the one who first started claiming Robbo contains code from Crafty. I simply say that's BS and you are slandering because your ego is hurt.
That's evident to anyone who has sufficient emotional intelligence.
And since you haven't provided any evidence the point is moot. The truth is, there is zero copyrightable Crafty code in Robbo. End of story.

I'll take the time to list side-by-side, when I have the time. But you are right, the story is at an end. As always, you finish second-best. Because you don't do your homework.

[bob]

Verbatim could be said of Rybka only when there are exact binary matches with other binaries. Is this not how they run the show? Did not the ICGA team found "large swath" of codes in Rybka that match exactly the assembly codes produced by compiling Crafty/Fruit. ONLY IF there are such exact assembly matches can it be said "Rybka has Crafty/Fruit codes in it...".

Having exact binary match is impossible. You would need to have exactly the same source code (not just the function you are comparing but all the surrounding code), exactly the same version of compiler (with exactly the same libraries) and exactly the same compiler switches. If you really believe they (ICGA) managed to reproduce all of that, than there is only one word left to describe you - naive.

You are likely one of the most ignorant people I know, that is capable of putting up a "front" that appears legitimate. In Rybka 1.6.1, there are _identical_ chunks of assembly language hundreds of instructions long. I do mean _identical_. Wonder exactly how that happened? One such function was "EvaluateWinner()" in Crafty's evaluation. Others include "NextMove", "NextEvasion". Not much need to go any further. If you find _identical_ assembly language, what does that tell you??? You got it...

More precisely, verbatim copy test would be for example take N bytes (and you put some reasonable minimum on N, like 1000) of binary A, take N bytes of binary B and calculate CRC on both. If CRC doesn't match they are not verbatim copies, plain and simple.

Shows your complete lack of understanding. They would never match, because if you don't copy _everything_ the addresses will be different, even if the code is the same. Different addresses mean the instructions that reference a direct address won't match.

Do you know _anything_ about assembly language programming and computer architecture, or are you just one giant source of hot air???

[bob]

Verbatim could be said of Rybka only when there are exact binary matches with other binaries. Is this not how they run the show? Did not the ICGA team found "large swath" of codes in Rybka that match exactly the assembly codes produced by compiling Crafty/Fruit. ONLY IF there are such exact assembly matches can it be said "Rybka has Crafty/Fruit codes in it...".

Having exact binary match is impossible. You would need to have exactly the same source code (not just the function you are comparing but all the surrounding code), exactly the same version of compiler (with exactly the same libraries) and exactly the same compiler switches. If you really believe they (ICGA) managed to reproduce all of that, than there is only one word left to describe you - naive.

I have to accept your authority on this unless some other authority refutes it.

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

Rasjid.

What we used, and what has been explained about a thousand times, is the concept of "semantic equivalence". Since we have C on one side (Crafty or Fruit) and assembly language on the rybka side from IDA Pro disassembly, one matches them up and determines which assembly language statements match up _precisely_ with a specific C statement. When done, if there are no assembly language statements left over, and no C statements left over, then those two pieces of code are called "semantically equivalent."

Please ignore Milos, as a prime example of someone that talks a reasonable game but has absolutely no understanding of the topic being discussed...

Any person familiar with compilers and assembly language will tell you the same thing I did above. Ask them. They know. _not_ Milos.

[bob]

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

This has nothing to do with your outright copying of Robo* family code, of course...

[Chan Rasjid]

I do expect there could be assembly code matches if there have been any cut_and_paste; we could try the common compiler options/switches and there are the common compilers in use.

Rasjid

[Houdini]

Bob, repeating the same personal attack 1000 times is hardly interesting... why don't you comment on the substance?

Like I said, you've established a convincing argument for claiming the originality and/or copyrightability of your bubble sort code.
The following demonstrates that you didn't copy any code:

Different variable names. No "swap()" function. Loops are done differently (he uses simple counter, I use a pointer). In other words. not even close.

And the following quote is about copyright infringement:

Does the code in the wiki look _exactly_ like the code in Crafty? Not to me, so how can I sue them for copyright infringement when they didn't copy my code exactly? You can't copyright "ideas".

Two questions:
1) If somebody else on this forum would make the same argument as you did in this thread, using similar wording, wouldn't you be the first to crucify the poor fellow?

2) Why don't you apply your own logic to the rotated bitboard code you claim Robbo (but you probably mean Ippo) copied from Crafty? Is the code _exactly_ the same? If it isn't, can you claim copyright?

Cheers,
Robert