Life In 19x19

Some of you may find this interesting: it's about the charges of plagiarism against the creator of the strong chess engine Rybka. The author argues that they are unwarranted. http://marginalrevolution.com/marginalr ... tions.html (this is a blog post discussing the original piece, but it has all three links in one place).

This issue almost single handedly brought the computer chess community to it's knees. In fact, the computer chess community split into at least two groups over a similar issue about the supposed cloning of Rybka.

Unless an algorithm is patented, I call it open season for reverse engineering. The entire game industry (where I work as a programmer) is 100% reliant on reimplementing what the other guy is doing in your own engine. And really that's 99% of the work anyway. Clever algorithms are nice and all, but unless someone sits down to write the code it's just an idea. And the Devil's always in the details.

Even if you had the other guy's source code in front of you, getting it to even build and compile is usually more effort than it's worth, let alone trying to make it work with your own code base in any meaningful way. Source code plagiarism is really a fundamentally silly concept.

Numsgil wrote:Unless an algorithm is patented, I call it open season for reverse engineering.

Huh? What about copyright? Only patents count for you? Can you explain why?

Huh? What about copyright? Only patents count for you? Can you explain why?

It's not only IP law that matters. Tournaments have rules. These generally forbid using someone else's work without permission.

kirkmc wrote:

Numsgil wrote:Unless an algorithm is patented, I call it open season for reverse engineering.

Huh? What about copyright? Only patents count for you? Can you explain why?

As a mathematician, I don't think an algorithm CAN be patented, nor an algorithm CAN have copyright. I know reality differs in a lot of countries, but this is nonsense. In mathematics, like Newton said, we stand in the shoulders of giants. If we allow algorithms to be patented and not allow them to be used and built upon, we will be licking midget's feet in the future.

So maybe reverse engineering is not the adequate issue, but re-implementing the same algorithm is.

RBerenguel wrote:

kirkmc wrote:

Numsgil wrote:Unless an algorithm is patented, I call it open season for reverse engineering.

Huh? What about copyright? Only patents count for you? Can you explain why?

As a mathematician, I don't think an algorithm CAN be patented, nor an algorithm CAN have copyright. I know reality differs in a lot of countries, but this is nonsense. In mathematics, like Newton said, we stand in the shoulders of giants. If we allow algorithms to be patented and not allow them to be used and built upon, we will be licking midget's feet in the future.

So maybe reverse engineering is not the adequate issue, but re-implementing the same algorithm is.

Agreed, Imagine in mathematics if every conjecture or theorem was copyrighted or patented, The field would grind to a complete halt.

I think having some way to cite sources (a la published journals) is a great idea, I think calling it plagiarism is a stretch.

I'm the owner of a software patent on an algorithm (via a previous company), and I also think they're complete bunk.

I think some misunderstanding of the issues.

An algorithm can't be copyright or patented but I believe you can patent the application of an algorithm to some particular task. However that's not what "reverse engineering" is all about.

a) The creators of a program do not have to disclose what algorithms they are using. If they do not, they do not have to allow anybody to look at the code to figure that out. They can make one of the conditions of obtaining a copy "don't look at the code".

b) Just knowing the algorithms (these might be known) does not necessarily make writing your implementation of them cheap and easy. Some of us are better at devising clever implementations than others so it's not at all unusual to see different implementations of an algorithm done by different people with an order of magnitude difference in performance. Or even more. Back in my working days that's one of the things I did, rewrite programs to improve perfomance. Admittedly there had to be something clumsy about the way the existing production program was written to cause its poor performance to come to my attention but usually I could get an order of magnitude improvement and in a few instance ~50 times!

BTW, "reverse engineering" isn't cheap or easy either. A few times I was called upon to disassemble a routine to replace lost source code. The tools can give you something you can recompile but not something you can easily maintain (modify). To convert from what the tools give you to what makes for human readablity takes a bit of skill and experience. Tedious work.

Just for the record, you can't copyright OR patent an algorithm, since EVERY chess program contains an Alpha-Beta, SEE, Pruning of some sort, etc. But that's NOT the problem and that's not what allegedly happened in the Rybka case. What allegedly happened in the Rybka case was Rybka's author, Vasik Rajlich, took the open source chess program Fruit, which was open source but GPL'ed and copied significant portions of code.

One argument against the copying case is that Rybka was a bitboard program and Fruit was a mailbox program. Dr. Hyatt, an expert in the computer chess field headed a panel, of experts, that decompiled the earliest versions of Rybka. What they found was that Rybka's author copied significant portions of Crafty (Dr. Hyatt's program), and contained even the same exact bugs, mixed with significant portions of Fruit, most notably the Fruit PST's.

Like I said, this issue has just about brought the computer chess community to it's knees. Whether or not Rybka copied code now is a moot point since the ICGA has banned Vasik Rajlich and Rybka for life. Keep in mind, that there are still debates over this issue in the computer chess community.

Suji, http://en.wikipedia.org/wiki/Software_patents The fact that an algorithm can not be patented does not detract from the fact that it happens. Did you know that Amazon tried (and succeded)to patent 1-click buying?

The United States Patent and Trademark Office (USPTO) issued US 5960411 for this technique to Amazon.com in September 1999.
On May 12, 2006, the USPTO ordered a reexamination[1] of the "One-Click" patent, based on a request filed by Peter Calveley.[2] Calveley cited as prior art an earlier e-commerce patent and the Digicash electronic cash system.
On October 9, 2007, the USPTO issued an office action in the reexamination which confirmed the patentability of claims 6 to 10 of the patent.[3] The patent examiner, however, rejected claims 1 to 5 and 11 to 26. In November 2007, Amazon responded by amending the broadest claims (1 and 11) to restrict them to a shopping cart model of commerce. They have also submitted several hundred references for the examiner to consider.[4] In March 2010, the revised patent was confirmed.[5][6][7]

As a regular reader of Slashdot in the past, I've seen a lot of cases, this is the most flagrant I remember. Maybe 1-click is not an algorithm, but the patentability of something in the US (and starting soon, in Europe) is quite absurd.

The RSA algorithm was patented in the US (and prior to the end of that patent, all cryptographic programs like PGP asked if you were in the US or outside, it was not patented in most of the rest of the world), for the record: http://en.wikipedia.org/wiki/RSA_(algorithm)

The point is, in the US you can patent a "method for X" which uses algorithm Y. When someone else wants to do X using Y (and Y is not patented) you are infringing this patent.

It may be a stretch to say that I can patent a "method for determining the zeros of a function", use Newton's algorithm and get rich: there is prior art. But as the RSA case shows, you can stretch the algorithm patentability as much as you want

Just read part 4 of the series at http://www.chessbase.com/newsdetail.asp?newsid=7813

I'm not familiar with programming, but if the claims about the side-by-side comparison are true then they certainly bring up disturbing questions about the entire investigation.

RBerenguel wrote:Suji, http://en.wikipedia.org/wiki/Software_patents The fact that an algorithm can not be patented does not detract from the fact that it happens. Did you know that Amazon tried (and succeded)to patent 1-click buying?

The United States Patent and Trademark Office (USPTO) issued US 5960411 for this technique to Amazon.com in September 1999.
On May 12, 2006, the USPTO ordered a reexamination[1] of the "One-Click" patent, based on a request filed by Peter Calveley.[2] Calveley cited as prior art an earlier e-commerce patent and the Digicash electronic cash system.
On October 9, 2007, the USPTO issued an office action in the reexamination which confirmed the patentability of claims 6 to 10 of the patent.[3] The patent examiner, however, rejected claims 1 to 5 and 11 to 26. In November 2007, Amazon responded by amending the broadest claims (1 and 11) to restrict them to a shopping cart model of commerce. They have also submitted several hundred references for the examiner to consider.[4] In March 2010, the revised patent was confirmed.[5][6][7]

As a regular reader of Slashdot in the past, I've seen a lot of cases, this is the most flagrant I remember. Maybe 1-click is not an algorithm, but the patentability of something in the US (and starting soon, in Europe) is quite absurd.

The RSA algorithm was patented in the US (and prior to the end of that patent, all cryptographic programs like PGP asked if you were in the US or outside, it was not patented in most of the rest of the world), for the record: http://en.wikipedia.org/wiki/RSA_(algorithm)

The point is, in the US you can patent a "method for X" which uses algorithm Y. When someone else wants to do X using Y (and Y is not patented) you are infringing this patent.

It may be a stretch to say that I can patent a "method for determining the zeros of a function", use Newton's algorithm and get rich: there is prior art. But as the RSA case shows, you can stretch the algorithm patentability as much as you want

I am indeed aware that it can happen. For chess programs, however, patents don't come into play. This is because of the nature of chess programs. Every program uses alpha-beta searching, SEE, MVV-LVA, LMR, etc. There are multiple 0x88 programs out there as well as bitboard programs. However, if I GPL my program and someone uses my code they are required to release the code to my program, along with the modifications they did.

That is what was at play in the Rybka case.

illluck wrote:Just read part 4 of the series at http://www.chessbase.com/newsdetail.asp?newsid=7813

I'm not familiar with programming, but if the claims about the side-by-side comparison are true then they certainly bring up disturbing questions about the entire investigation.

Yes, Chessbase has all four of the parts and I encourage everyone to read them, along with this, this, and this and all the corresponding links and come up with your own conclusions.

Where the charge is using open source code the situation is much more complicated. It is not an infringement for a commercial product to use something that comes from open source provided a number of conditions are met. Since these conditions would be of no interest to end users I won't bother describing.

Mike Novack wrote:It is not an infringement for a commercial product to use something that comes from open source provided a number of conditions are met.

I agree with the preceding statement, however, Fruit had the GPL license applied to it. The issue then becomes, did Rybka copy code? If so, then as per the GPL, Rybka would then have to be open source regardless of being commercial or not.

Thanks for the articles, they were pretty interesting.

What I am curious after reading them, is if there is an overlap to Go computer programs as well.
I wonder if running the same sort of playing similarity tests on current computer go programs would produce as interesting a linkage graph as the one on the article.