CFP: Originality and Creativity

[hyatt]

I don't get the distinction in this case (Null move). We were USING null-move in 1989 WCCC as were at least a couple of others (LaChex comes to mind first). The deep Thought guys also reported on their results using it, and was the place where I first saw the TT avoid-null-move trick mentioned as well. This was not a 1995 thing. It was already well-known by then.

Yes, first published 1975 in English by the Kaissa authors:
Georgy Adelson-Velsky, Vladimir Arlazarov and Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs. Artificial Ingelligence, Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702. Reprinted (1988) in Computer Chess Compendium

2. The Order of Move Considerations:
A less trivial idea was that sometimes an extension of the game tree by introducing of dummy move can lead to a reduction of the search tree. In positions with material advantage (with respect to limits) it was permitted to try a so-called "blank" move in which ones own pieces are not moved. Certainly in positions with "Zugzwang" (the side to move must weaken his position) this may lead to errors.

On Lachex, it appears in the WCCC 1989 booklet under program descriptions with null move mentioned (pp 15), but not in the table of participants and Lachex did not play in Edmonton (it played 1986 in Cologne and 1992 Madrid).
http://archive.computerhistory.org/proj ... 028.sm.pdf

Didn't Cray Blitz already use null move in 1983, according to your 1996 rgcc post? I mean that is no contradiction CB used null move in 1989 as well, but one then assumes 1989 was the first occurrence using null move.
http://groups.google.com/group/rec.game ... dc1ec60967

Null Move was used in 1983, because I used it in the program that won the world computer chess championship that year. They aren't particularly new ideas at all ...

I don't think what they do is based on the "Null Move assumption" as defined by Beal. You can find a 1974 or so paper about my original Blitz program that talked about using a null-move. But it was used to deal with threats. I played a null-move, and let the tactical component of my search find the best tactical shot (if present). I could then fairly safely assume I could remove THAT threat by playing a real move. If the opponent had ANOTHER tactical shot, then I was in trouble and needed more search. Not the same as the null-move observation to refute anything. In fact, my null-move search didn't fail high or low in Blitz IV (very selective program as was common in early 70's). But I had a "causality function" (similar to Berliner's idea described in his "Chess as problem solving, the development of ..." paper. It could take a PV and figure out what was wrong, but it needed a PV to workon. This was a cheap way to detect the opponent's threats in the days when FORTRAN was not even close to being recursive.

[Gerd Isenberg]

I don't get the distinction in this case (Null move). We were USING null-move in 1989 WCCC as were at least a couple of others (LaChex comes to mind first). The deep Thought guys also reported on their results using it, and was the place where I first saw the TT avoid-null-move trick mentioned as well. This was not a 1995 thing. It was already well-known by then.

Yes, first published 1975 in English by the Kaissa authors:
Georgy Adelson-Velsky, Vladimir Arlazarov and Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs. Artificial Ingelligence, Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702. Reprinted (1988) in Computer Chess Compendium

2. The Order of Move Considerations:
A less trivial idea was that sometimes an extension of the game tree by introducing of dummy move can lead to a reduction of the search tree. In positions with material advantage (with respect to limits) it was permitted to try a so-called "blank" move in which ones own pieces are not moved. Certainly in positions with "Zugzwang" (the side to move must weaken his position) this may lead to errors.

On Lachex, it appears in the WCCC 1989 booklet under program descriptions with null move mentioned (pp 15), but not in the table of participants and Lachex did not play in Edmonton (it played 1986 in Cologne and 1992 Madrid).
http://archive.computerhistory.org/proj ... 028.sm.pdf

Didn't Cray Blitz already use null move in 1983, according to your 1996 rgcc post? I mean that is no contradiction CB used null move in 1989 as well, but one then assumes 1989 was the first occurrence using null move.
http://groups.google.com/group/rec.game ... dc1ec60967

Null Move was used in 1983, because I used it in the program that won the world computer chess championship that year. They aren't particularly new ideas at all ...

I don't think what they do is based on the "Null Move assumption" as defined by Beal.

Whom do you mean with they? Kaissa programmers?

You can find a 1974 or so paper about my original Blitz program that talked about using a null-move. But it was used to deal with threats. I played a null-move, and let the tactical component of my search find the best tactical shot (if present). I could then fairly safely assume I could remove THAT threat by playing a real move. If the opponent had ANOTHER tactical shot, then I was in trouble and needed more search. Not the same as the null-move observation to refute anything. In fact, my null-move search didn't fail high or low in Blitz IV (very selective program as was common in early 70's). But I had a "causality function" (similar to Berliner's idea described in his "Chess as problem solving, the development of ..." paper. It could take a PV and figure out what was wrong, but it needed a PV to workon. This was a cheap way to detect the opponent's threats in the days when FORTRAN was not even close to being recursive.

What about Cray Blitz of 1983? Was it NM threat detection or also already (non recursive) NM refutation?

[hyatt]

Correct on the first one. The Kaissa guys used a null (as did Botvinnik) in a way similar to what I was doing.

1983 CB was not using null-move at all. Blitz version V (5) and beyond were chess 4.x-like full-width searchers. About the only thing we did differently at that point was that we had a full search, a q-search, and in between the two a 4-ply "threat only search" that tried to make sure we were not overlooking tactics near the ends of the PV where we would drop into a capture-only search that could make mistakes. The threat detection was last used at the 1977 WCCC in Toronto (the event where the ICCA was formed, in fact). The next year, we were an exhaustive search, going from 100K lines of Fortran to about 10K in one year. Not to mention adding a significant amount of strength, of course.

My first null-move search program (null-move as used today) was 1989. Burt Wendroff (Lachex) and I used to talk regularly, and a couple of months prior to the 1989 WCCC in Edmonton, we met up at Los Alamos for our annual "chess get-together" and he showed me two papers. One was Beal's null-move idea, the other was Hsu's singular extension idea. We both added the null-move search idea in a couple of hours (Initially, we did R=1, and just one null on any single path, later that last restriction was removed although no version of Cray Blitz ever played with R=2 although we did test with it a bit).

[Gerd Isenberg]

Correct on the first one. The Kaissa guys used a null (as did Botvinnik) in a way similar to what I was doing.

1983 CB was not using null-move at all. Blitz version V (5) and beyond were chess 4.x-like full-width searchers. About the only thing we did differently at that point was that we had a full search, a q-search, and in between the two a 4-ply "threat only search" that tried to make sure we were not overlooking tactics near the ends of the PV where we would drop into a capture-only search that could make mistakes. The threat detection was last used at the 1977 WCCC in Toronto (the event where the ICCA was formed, in fact). The next year, we were an exhaustive search, going from 100K lines of Fortran to about 10K in one year. Not to mention adding a significant amount of strength, of course.

My first null-move search program (null-move as used today) was 1989. Burt Wendroff (Lachex) and I used to talk regularly, and a couple of months prior to the 1989 WCCC in Edmonton, we met up at Los Alamos for our annual "chess get-together" and he showed me two papers. One was Beal's null-move idea, the other was Hsu's singular extension idea. We both added the null-move search idea in a couple of hours (Initially, we did R=1, and just one null on any single path, later that last restriction was removed although no version of Cray Blitz ever played with R=2 although we did test with it a bit).

In CPW
https://chessprogramming.wikispaces.com ... tory-Hyatt
I referred your 1996 post:
https://groups.google.com/forum/?fromgr ... nGHtzYzDwJ[1-25]

Hashing was used in Mac Hack, in the 60's... it was used in every
version of my program dating back to 1972. Null Move was used in
1983, because I used it in the program that won the world computer
chess championship that year. They aren't particularly new ideas
at all, particularly hashing...

Now, with your current statement I am a bit confused

[BB+]

Call for paper for a Special Issue of the journal Entertainment Computing (Elsevier)
Topic of the special issue: "Originality and creativity in designing software for games"

The issue has now been published

The Preface by Paolo Ciancarini is available at:
http://www.sciencedirect.com/science/ar ... 2114000172

It describes the 3 papers therein.

[BB+]

I guess even the Preface is behind a paywall. Here is what is says in part.

This special issue includes three papers, which were submitted together with others after an open Call for Papers. The papers were all reviewed by at least three people. The papers discuss most of the current arguments in favour and against cloning in games.

1. Plagiarism in Game Programming Competitions, by H. Jaap van den Herik, Aske Plaat, David Levy, and Daniel Dimov. The paper describes how the ICGA arrived to disqualify the Rybka program and its author after a charge of undisclosed cloning. The main argument is that undisclosed cloning is against the rules of the WCCC.

2. What makes a Chess program original? Revisiting the Rybka case, by Soren Riis. The paper reviews the Rybka case taking the side of the defense. The main argument is that the program is original, as proved by the fact that at the time of accusations it was the strongest one, so how could it be copied?

3. Move similarity analysis in chess programs, by Don Dailey, Adam Hair, and Mark Watkins. The paper discusses a technique called move similarity testing, useful to compare two programs and decide if they are clones. Sadly, the first author of this paper deceased in 2013 after an improvvise illness.

We believe that these papers cover satisfactorily both the technological and the agonistic issues of the Rybka case, so that the reader can reach his or her own conclusions.

Furthermore, it seems that the relevant authors of the papers can make them freely available for 50 days.

To help you access and share your article, we are providing you with the following personal article link, which will provide free access to your article, and is valid for 50 days, until August 14, 2014

http://authors.elsevier.com/a/1PFel6gYiZJvxn

Please use this link to download a personal copy of your article for your own archive. You're also welcome to email the link to your co-authors and colleagues, or post the link on your Facebook, Google +, Twitter or other social media profile, to tell your network about your new publication. Anyone who clicks on the link until August 14, 2014, will be taken to the final version of your article on ScienceDirect for free. No sign up or registration is needed - just click and read!

[BB+]

Here are the Abstracts of the papers.

In June 2011, the International Computer Games Association (ICGA) disqualified Vasik Rajlich and his Rybka chess program for plagiarism and breaking their rules on originality in their events from 2006 to 2010. One primary basis for this came from a painstaking code comparison, using the source code of Fruit and the object code of Rybka, which found the selection of evaluation features in the programs to be almost the same, much more than expected by chance.

In his brief defense, Rajlich indicated his opinion that move similarity testing was a superior method of detecting misappropriated entries. Later commentary by both Rajlich and his defenders reiterated the same, and indeed the ICGA Rules themselves specify move similarity as an example reason for why the tournament director would have warrant to request a source code examination.

We report on data obtained from move-similarity testing. The principal dataset here consists of over 8000 positions and nearly 100 independent engines. We comment on such issues as: the robustness of the methods (upon modifying the experimental conditions), whether strong engines tend to play more similarly than weak ones, and the observed Fruit/Rybka move-similarity data.

On June 28, 2011 the International Computer Games Association (ICGA) disqualified and banned the program Rybka and its programmer Vasik Rajlich from previous and future World Computer Chess Championships (WCCC). The ICGA had conducted an investigation into allegations that, in the chess program Rybka, two other programs were plagiarized: Crafty and Fruit. It was found that the allegations were true, and that the ICGA tournament rules had been broken. The investigation, the report of the investigation, and the verdict that Rajlich was guilty of the plagiarism took place in the form of a version of Crowdsourced Online Dispute Resolution (CODR). The above sentence was determined by the Board of the ICGA. This article describes, amongst other things, the background, the ICGA rules, the rules for fair play in competitions, CODR, and the future of clones. Finally, in the conclusions, the question is addressed whether the application of the ICGA rules has been fair and lawful.

In this article I will consider the controversial Rybka case, which created a considerable stir in the computer chess community in 2011. Rybka was, from its initial public release in 2005 until it was surpassed in 2010, by far the strongest chess engine ever seen. The question of whether Rybka was substantially or slightly copied from other sources, or a completely original work, is still passionately being debated on forums and blogs. Since the actual source code was not available the determination of whether or not the program was original is complex and involves technical topics such as reverse engineering, program analysis, the abstraction–filtration–comparison test and black box testing such as ponder-hit analysis. The question relates to practices for software development, legal issues like copyright law and touches on innovation and market leadership.

Drawing on this array of topics we review the question if and to what extent Rybka was a clone/derivative.

The main conclusion is that the view computer experts take on this question is colored by two different views of software development, one that fits programming in an academic environment, one that fits programming in an industry environment.

This article is party based on my four part ChessBase article, but includes some new analysis.

And here are the "highlights" from two of the 3 papers (the third seems lacking):

• We use move similarity techniques to explore creativity and originality in computer chess programs.
• We apply the results to the specific case of Rybka and Fruit.
• The move similarity data is also of interest to questions of “style” of engines.

• On June 28, 2011 the program Rybka was disqualified from 4 World Computer Chess Championship titles.
• An investigation found that chess program Rybka plagiarized two other programs: CRAFTY and FRUIT.
• The investigation took place in the form of a version of Crowdsourced Online Dispute Resolution.
• This article describes the background, the ICGA rules, and the rules for fair play in competitions.
• The article also addresses the future of clones and whether the application of the ICGA rules is fair.

[hyatt]

BTW, for me, I do not believe I did null-move in 1983. My recollection is as follows.

Somewhere circa 1988 Burt Wendroff (Lachex) mentioned two papers he had seen. He said something like "null-move is easy to do, but the other one (which happened to be the first paper on singular extensions) is very messy." I am not 100% certain whether I added null-move in 1988 or in 1989. But it was somewhere in that range. Not sure why I would have said 1983 unless it was just a memory lapse or possibly a typo. In looking at the dates of papers on the above, I believe I did this in 1988. If that was the Orlando ACM tournament (I think it was but my files are at the office) then that was the year null-move was added. R=1, non-recursive (only 1 null move in any path). Within a year or two that restriction was dropped (I think in 1989 however) so that with R=1, it could do multiple null-moves, just not two in a row.

Unfortunately, all I have left from those days are a couple of printed listings that are impossible to read they have faded so much. Without any actual source files, I can't find when it was added. There is a 1989 or so era version of Cray Blitz source on the internet, but it simply uses the classic R=1 recursive form mentioned above (more than one allowed, but not two in a row).

I can only plead "old age" now. I really didn't even remember the recursive null-move until someone pointed out it was in the released source version someone dug up for me. The program was retired 20 years ago, so a memory lapse is not that surprising I suppose.

The only other thing I just remembered was that in 1989, I was in the middle of rewriting the search (from Fortran to cray ASM) and got pretty aggravated at a position where it failed high and then low. When I disabled null-move it went away. Of course it ran a lot slower so I did not remove it. That was early Summer, 1989 getting ready for the WCCC in Edmonton that year. So it was certainly in prior to 1989, and I am almost certain the first (non-recursive form) was added about a year earlier.