Pairwise Analysis of Chess Engine Move Selections

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Rebel, chrisw

Adam Hair
Posts: 3226
Joined: Wed May 06, 2009 10:31 pm
Location: Fuquay-Varina, North Carolina

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Adam Hair »

Sven Schüle wrote:
Graham Banks wrote:
Adam Hair wrote:........ so it seems to me the fairest thing would be to test every engine above 2600 Elo (CCRL). Unfortunately, that is not proving to be possible at the moment.
Well your analysis has certainly changed my opinion to a degree.
In light of the fact that it seems that many engines might have heavily borrowed ideas from strong open source engines, I'm more amenable now to the the idea of testing Houdini as the Ippo family representative, and also to continuing testing Naraku.
It would seem pretty difficult now to tar one or two engines without having lingering doubts about others.
Must have a think about all this.
I must admit that this analysis is indeed very interesting, and I highly appreciate the effort. But I don't see how it changes anything substantial for the "engine origins" discussion (and as I understand Adam's statements this was also not his main intention). The key point of this analysis is that certain engines behave similar to each other regarding their move selection. There are several possible explanations for this similarity. A common explanation is that these engines are partially based on the same ideas and algorithms.

Some people may think that selecting the same moves as another engine means that code must have been copied from that other engine. But "borrowing ideas" should not be mixed up with "borrowing implementation (code)", and it is important to understand that selecting the same moves as another program *may* imply reuse of algorithms but *does not* imply reuse of code. (And, for those not being familiar with formal logic, it is also important to understand the meaning of "to imply" ;-) )

The former, "borrowing ideas", is fully o.k., even to a high extent, although one could argue that having two engines sharing the same ideas but implementing them differently is somewhat less "interesting" than having two engines with different ideas.

The latter, "borrowing implementation", is o.k. as long as copyright and license are not violated.


If your rule of thumb were that there should be only one representative from a "family" being included into testing activities, and if it is defined that an engine B belongs to the "family" of another (original) engine A if it is based on at least a certain percentage X of ideas and algorithms taken from A, then you would face these two problems:

- you would have to define the value of X, which is practically impossible;

- you would have to exclude a lot of engines from testing, including all Ippo* engines, Houdini, Fire, Strelka, Rybka, but - according to the data presented here - perhaps also Onno, Loop, Critter, Thinker, Delfi, Naraku, TwistedLogic, SmarThink, Hamsters, Pupsi, Daydreamer, Philou, Cyrano, ... - which obviously goes into the wrong direction.

Another problem would be, for consistency you would also have to exclude those open source engines which are legally derived from another engine in full GPL compliance, like Toga. But for which reason? Legally sharing implementation does of course imply sharing ideas and algorithms. This shows that the notion of "borrowing ideas" does not qualify as a guideline to decide about testing or not testing an engine.


In my opinion a better rule of thumb would be to continue concentrating on the cases where copyright/license violation is proven - difficult enough as it is, but looking more consistent to me at least.

This rule does not help much for the Ippolit case itself, though, since there is no clear agreement yet about the question whether heavily reusing code by reverse engineering a commercial program is considered as a copyright violation, and also whether such a heavy code reuse actually happened in case of Ippolit. In my opinion both get a "yes" but certainly others disagree.

As a second rule, I would still insist on not testing engines by anonymous authors.

Sven
Thanks for the response Sven. My main focus is just a discussion on
issues, knowing that there will be no resolution of anything. I agree with
everything that you wrote.
Adam Hair
Posts: 3226
Joined: Wed May 06, 2009 10:31 pm
Location: Fuquay-Varina, North Carolina

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Adam Hair »

Graham Banks wrote:
Adam Hair wrote:........ so it seems to me the fairest thing would be to test every engine above 2600 Elo (CCRL). Unfortunately, that is not proving to be possible at the moment.
Well your analysis has certainly changed my opinion to a degree.
In light of the fact that it seems that many engines might have heavily borrowed ideas from strong open source engines, I'm more amenable now to the the idea of testing Houdini as the Ippo family representative, and also to continuing testing Naraku.
It would seem pretty difficult now to tar one or two engines without having lingering doubts about others.
Must have a think about all this.

Cheers,
Graham.
:wink:

That has been my feeling, for the most part, for a while now. Though
I have waffled some :)
Dann Corbit
Posts: 12542
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Dann Corbit »

Graham Banks wrote: {snip other stuff}
I didn't mean to imply any copying of code by any of these engine authors. I agree that the use of ideas is obviously fine.
The main point that I was trying to make was that I now find it difficult to single out one or two engines in particular, given that Adam's analysis seems to show that the implementation of ideas from open source engines is fairly widespead.
Please correct me if you think I'm wrong in this assumption.

Cheers,
Graham.
In my opinion, there is nothing at all bad implied from using ideas from Fruit and Glaurung/Stockfish (so long as the borrowing of ideas is done legally). In fact, it is even virtuous to do so. What is the purpose of open source software if it is not to share ideas? If, in fact, you have an open source program and someone uses one of your algorithms and then you feel miffed, I puzzle at your attitude. Why open source then?

There is clearly virtue in sharing ideas. This can be through code, or through papers or discussions on chess programming boards or conversations at events or many other methods.

There is also nothing wrong with keeping your ideas to yourself. When the source is closed, it is up to the author to decide if:
1. He is going to expose his source code to the world
2. He is going to discuss his chess ideas with the world
3. He is going to keep things private for himself
4. He is going to give the engine away for free
5. He is going to sell the engine
etc.

On the other hand, there are right ways to do things and wrong ways to do things. There is nothing at all wrong with reading code, understanding the idea, and then making your own version [*]. There is something wrong with taking or using code in a way that specifically violates the license of the code. In my opinion, it is very hard to tell if this was done in a specific case since algorithms are not protected.

Specifically, this is NOT protected:

al·go·rithm [ álgə rìəm ] (plural al·go·rithms)

noun

Definition:

1. problem-solving procedure: a logical step-by-step procedure for solving a mathematical problem in a finite number of steps, often involving repetition of the same basic operation

[*] OK, patents, but fortunately, I do not know of any chess authors who have patented their ideas.

Now, with the so-called controversial engines, it is possible that the authors *may* have done something wrong. However, I think that we should abide by the principle "innocent until proven guilty" for all of them. We are not a formal body entrusted with power of law.

On the other, other hand, I do think that it is possible to form our own *opinions* about whether someone has *probably* done something wrong. There is nothing wrong with that either. So I can dictate my own personal choices according to opinions (guesses) that I have formed if I feel that they are factual enough to have merit. But if I tell others to do the same as my choice, I think that is an error.

IMO-YMMV
Adam Hair
Posts: 3226
Joined: Wed May 06, 2009 10:31 pm
Location: Fuquay-Varina, North Carolina

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Adam Hair »

To help visualize the data, here is a tree using 60 of the engines I
tested. I do not claim this to be definitive, just a tool to help interpret
the results.

Image
Jan Brouwer
Posts: 201
Joined: Thu Mar 22, 2007 7:12 pm
Location: Netherlands

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Jan Brouwer »

Interesting picture (partly because my program is in it)!
If I understand this picture correctly, then the length of the lines between any two programs is a measure for how different they are in move selection.
Is there something like an objective origin in this picture (I mean a point which you can consider the root of a tree), or is that a nonsensical thing here?
Adam Hair
Posts: 3226
Joined: Wed May 06, 2009 10:31 pm
Location: Fuquay-Varina, North Carolina

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Adam Hair »

Jan Brouwer wrote:Interesting picture (partly because my program is in it)!
If I understand this picture correctly, then the length of the lines between any two programs is a measure for how different they are in move selection.
Is there something like an objective origin in this picture (I mean a point which you can consider the root of a tree), or is that a nonsensical thing here?
Hi Jan,

The length of the branches is a measure of the difference in move selection, and the tree does not have a root.

This tree was formed using the neighbor-joining cluster method:
http://en.wikipedia.org/wiki/Neighbor_joining
http://mbe.oxfordjournals.org/content/4/4/406.long

Adam
Michel
Posts: 2272
Joined: Mon Sep 29, 2008 1:50 am

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Michel »

To bad GnuChess was not included. As far as I can tell 5.07 is an independent codebase (although it probably includes ideas from early Crafties).

In my improvement to the codebase I have also implemented some ideas from Fruit and Stockfish. I am kind of curious if this would show in the similarity analysis.

My latest released version of GnuChess seems to be about 350 Elo stronger than the FSF version
(see here http://computerchess.org.uk/ccrl/404/cg ... +opponents )

(my development version is another 50Elo stronger).
Adam Hair
Posts: 3226
Joined: Wed May 06, 2009 10:31 pm
Location: Fuquay-Varina, North Carolina

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Adam Hair »

Michel wrote:To bad GnuChess was not included. As far as I can tell 5.07 is an independent codebase (although it probably includes ideas from early Crafties).

In my improvement to the codebase I have also implemented some ideas from Fruit and Stockfish. I am kind of curious if this would show in the similarity analysis.

My latest released version of GnuChess seems to be about 350 Elo stronger than the FSF version
(see here http://computerchess.org.uk/ccrl/404/cg ... +opponents )

(my development version is another 50Elo stronger).
Hi Michel,

First of all, thank you for your branches of Polyglot and GnuChess. Your version
of Polyglot has been very useful to me. As far as GnuChess goes, I was the one
who tested the latest release for the CCRL 40/4 list :)

I was unable to get GnuChess to successfully run with the sim tool. At the moment,
I do not remember the details. So, I will make another attempt and let you know
what occurs.

Adam
Michel
Posts: 2272
Joined: Mon Sep 29, 2008 1:50 am

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Michel »

First of all, thank you for your branches of Polyglot and GnuChess. Your version
of Polyglot has been very useful to me. As far as GnuChess goes, I was the one
who tested the latest release for the CCRL 40/4 list Smile
Hey thanks! Of course I was not aware of this!
I was unable to get GnuChess to successfully run with the sim tool. At the moment,
That's interesting. Was it the original version of GnuChess that did not
work? That is a winboard engine, and even then its implementation of
the winboard protocol is quite flaky.
Adam Hair
Posts: 3226
Joined: Wed May 06, 2009 10:31 pm
Location: Fuquay-Varina, North Carolina

Re: Pairwise Analysis of Chess Engine Move Selections

Post by Adam Hair »

I used the latest version that you released: GnuChess 5.07 1705b

However, this time I had no problems. I downloaded WB2UCI again
and everything is working better with winboard engines.

Here is an updated tree ( added Bobcat, CuckooChess, and GnuChess)

Image

I'll post updated numbers later.