Clone Conflict

Discussion about development of draughts in the time of computer and Internet.
BertTuyt
Posts: 1303
Joined: Wed Sep 01, 2004 19:42

Clone Conflict

Post by BertTuyt » Sun Aug 21, 2016 22:09

Thanks to the Internet, and the willingness of many programmers to share source, the question arises what remains original or not.

To give a few examples.
* Very recently Ed shared not only the 8p Databases but also the sources for the DB-handler.
* Perft() discussions revealed many details to construct a bitboard MoveGenerator.
* Sources for the Search are available from Scan, Moby Dam, and Damage.
* Complete Engine sources are available from Moby Dam and Scan.

So what do we consider in the future as original?.
Is a Bitboard based Engine , with the general available alpha-beta search with the known enhancements (like bad move pruning, Late Move reductions, PVS, .....), an evaluation table copied from Scan, and DBs from ED, something which is acceptable?

I expect that in the next year tools will become avaialbe for ML, so all can generated the eval tables based upon the ideas of Fabien.
So whats orginal, and how to differentiate?

Anyway, Computer Draughts is still fun, even when Moore Law comes to an end :)

Bert

Joost Buijs
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Clone Conflict

Post by Joost Buijs » Mon Aug 22, 2016 08:01

Bert,

Indeed cloning is a big problem, to be honest I more or less came to this forum because I was getting sick of the level of cloning going on in the computer-chess world. And what is worse is that most people from the computer-chess community find this quite acceptable.

I've been programming zero-sum games for 40 years now, with an absence of 10 years, just as a hobby, not because I want to gain something with it or to get recognition for it, but just for the fun of programming.
And sometimes it hurts when somebody with hardly any experience beats your program with a clone or derivative.

Since I have to leave now I will get back at this later.

Joost
Last edited by Joost Buijs on Mon Aug 22, 2016 11:02, edited 1 time in total.

Rein Halbersma
Posts: 1625
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Clone Conflict

Post by Rein Halbersma » Mon Aug 22, 2016 08:04

BertTuyt wrote:Thanks to the Internet, and the willingness of many programmers to share source, the question arises what remains original or not.
It seems to me that this is at the moment a largely hypothetical issue. I also don't expect it to be a real issue any time soon. The market for commercial draughts programs is so tiny (ask Ed or Michel if they even recover their electricity bills) that fraud seems hardly profitable :)
To give a few examples.
* Very recently Ed shared not only the 8p Databases but also the sources for the DB-handler.
* Perft() discussions revealed many details to construct a bitboard MoveGenerator.
* Sources for the Search are available from Scan, Moby Dam, and Damage.
* Complete Engine sources are available from Moby Dam and Scan.
I somehow missed that you published your search, could you repost that link?
So what do we consider in the future as original?.
Is a Bitboard based Engine , with the general available alpha-beta search with the known enhancements (like bad move pruning, Late Move reductions, PVS, .....), an evaluation table copied from Scan, and DBs from ED, something which is acceptable?[
I think in the old days everyone used the same 6 piece databases that Harm's Dam 2.2 did, generated by Michel's DragonDraughts, and Scan still uses those. The situation is the same in computer chess.
I expect that in the next year tools will become avaialbe for ML, so all can generated the eval tables based upon the ideas of Fabien.
So whats orginal, and how to differentiate?

Anyway, Computer Draughts is still fun, even when Moore Law comes to an end :)

Bert
I think that Michel's experiments with "blindly" copying the Scan eval weights in one's own program shows that this still leaves a large margin for further optimization. It's a bit like Formula 1: you can buy/get engines and tires, but tuning and a good driver still make a difference.

In case of disputes, just require every tournament participant to fully open source their engine ;) I think the ICGA has some audit procedure for such cases.

Rein Halbersma
Posts: 1625
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Clone Conflict

Post by Rein Halbersma » Mon Aug 22, 2016 08:29

Rein Halbersma wrote:
I somehow missed that you published your search, could you repost that link?
Found it, link from 2013: viewtopic.php?f=53&t=4013&start=95
Note your own words there, Bert: "The YBWC algorithm is mostly based on the work of Glaurung/Stockfish" ;)

BertTuyt
Posts: 1303
Joined: Wed Sep 01, 2004 19:42

Re: Clone Conflict

Post by BertTuyt » Mon Aug 22, 2016 10:25

Rein, you are right , but at least I admitted this, and anyone could examine my search code :) .
The pope is holy, we are human.......
Also In my case before I generated the 7P DBs myself, I used the DBs as provided by Harm.
So therefore also my question......

Bert
Last edited by BertTuyt on Mon Aug 22, 2016 10:30, edited 1 time in total.

BertTuyt
Posts: 1303
Joined: Wed Sep 01, 2004 19:42

Re: Clone Conflict

Post by BertTuyt » Mon Aug 22, 2016 10:29

Rein, another comment.
I think it would be an interesting thought indeed, that after every tournamant we share sources.
So all could read and examine each others inventions, and work another year in open or secret on new ideas...

Bert

Joost Buijs
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Clone Conflict

Post by Joost Buijs » Mon Aug 22, 2016 11:53

It is very difficult to distinguish between what is a clone, a derivative or not.
Most search techniques have been known for many years now, with the latest addition probably being LMR. I think using these techniques is fine, but plain copying of code, or parameters is not.

For instance the SMP routine in my chess program resembles YBWC because that is one of the easiest ways to do this, but the whole implementation and coding is done by me without looking at other programs how to do this.
This took me 2 to 3 months (mainly working during weekends) before I found out how to do it and to have all the nasty race-conditions and bugs resolved, and in the end it gave me a lot of satisfaction because I developed everything myself.
I don't think that using the YBW concept is cloning, but more or less using the implementation from another program is.
The same holds for many other techniques, using a technique or an idea is fine, but copying code or using the same implementation or parameters is not. At least this is my feeling about it.

At the moment you will find many chess programs using exact the same LMR reduction-tables as stockfish does, and there are several using the same evaluation function and parameters, this is a very unhealthy trend.
This development is mainly the reason that I didn't touch my chess program for 2.5 years and that I decided to switch to draughts in the hope that there is more originality within this community.
It is not so difficult to grab everything from stockfish and make a very strong chess-program, but somehow this doesn't feel right.

Joost

Rein Halbersma
Posts: 1625
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Clone Conflict

Post by Rein Halbersma » Mon Aug 22, 2016 22:30

BertTuyt wrote:Rein, you are right , but at least I admitted this, and anyone could examine my search code :) .
The pope is holy, we are human.......
Also In my case before I generated the 7P DBs myself, I used the DBs as provided by Harm.
So therefore also my question......

Bert
Bert, of course I didn't mean it as an accusation.

Implementing YBW from Glauring/Stockfish is something that can hardly be done with plain "cloning". You need to adapt your own data structures and search engine to this, finetune it again for performance. Same for the eval.

Even Ed's endgame database driver requires substantial tuning (hint: in particular of the conditional lookup ("cl") parameter to egdb_lookup()) before it will give optimal performance during an engine search. The particular implementation will depend on the relative sizes/speeds of RAM / SSD / regular hard drive, as well as on the speed ratio of your search/qsearch/eval functions. So yes, you can copy Ed's driver, but you won't get Kingsrow performance without a lot of additional work.

Rein Halbersma
Posts: 1625
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Clone Conflict

Post by Rein Halbersma » Mon Aug 22, 2016 22:54

Joost Buijs wrote:It is very difficult to distinguish between what is a clone, a derivative or not.
Most search techniques have been known for many years now, with the latest addition probably being LMR. I think using these techniques is fine, but plain copying of code, or parameters is not.
I think there are various degrees of cloning/copying/reusing.

1) renaming a binary program to your own and selling it/playing with it in a tournament (plain fraud/theft)
2) recompiling a program's source code with your own optimized compiler settings (this is what Jim Ablett provides as a valuable service to chess program authors, basically like an automobile tune-up)
3) copying a substantial portion of a strong open source program (data structures, search, eval, egdb drivers, opening book) and fitting it into your own program. Some authors (Ed, Ronald/Jeroen in chess) even provide such portions (egdb, opening book) as freely usable plugins.
4) reading source code / journal articles about new ideas / techniques and implementing these from scratch

I think that in practice there is little difference between 3/4, or at the very least that they form a very broad and grey spectrum. Sure, 4 is more noble, and you'll certainly learn more, but is 3 really that bad? For some techniques there is very little discretion for an individual programmer (OK, some people will even find a dozen ways to locate 1-bits in a bitboard), for others it greatly matters. In all cases, you need lots of finetuning.

Also, where to draw the line? I am a big fan of using (C++) libraries such as the Standard Library and Boost. Some data structures and algorithms from these libraries are very sophisticated and can for some parts of a chess program give substantial performance benefit, simplify your program, or both. Why write your own sorting routine instead of std::sort from the C++ STL? Why implement your own hash table instead of std::unordered_map, or an optimized one from Boost?

My own (still pre-alpha) DCTL library (tomorrow 4 years ago!, see viewtopic.php?t=3910) aims to provide general usable data structures and algorithms for draughts engines. It's open source because a) I don't care if someone copies my stuff and b) if they do, I hope they find it useful.
For instance the SMP routine in my chess program resembles YBWC because that is one of the easiest ways to do this, but the whole implementation and coding is done by me without looking at other programs how to do this.
This took me 2 to 3 months (mainly working during weekends) before I found out how to do it and to have all the nasty race-conditions and bugs resolved, and in the end it gave me a lot of satisfaction because I developed everything myself.
That's very impressive!
I don't think that using the YBW concept is cloning, but more or less using the implementation from another program is.
The same holds for many other techniques, using a technique or an idea is fine, but copying code or using the same implementation or parameters is not. At least this is my feeling about it.

At the moment you will find many chess programs using exact the same LMR reduction-tables as stockfish does, and there are several using the same evaluation function and parameters, this is a very unhealthy trend.
A few years ago, I studied the Stockfish code very thoroughly. It's basically the cleanest open source program, so very readable. Still, even if I could, copying the raw weights (eval, LMR) to any other program is not going to give the same performance. It all depends on the relative speeds of eval/search, the complex interactions between different reductions etc. Maybe as a starting point they work OK, but it's never going to be a global maximum for any program optimization.

Anyway, the draughts community is so small, that the "shame" factor is enough to keep fraudsters out. Plus there is no money involved.

Rein Halbersma
Posts: 1625
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Clone Conflict

Post by Rein Halbersma » Mon Aug 22, 2016 23:03

Joost Buijs wrote: This development is mainly the reason that I didn't touch my chess program for 2.5 years and that I decided to switch to draughts in the hope that there is more originality within this community.
Joost
There is certainly a large amount of originality in draughts. But there is not enough discussion about it, and the discussions that do happen have far too little code in them for me to be interesting. I like to see concrete code how an idea works, to fully understand it, and to try and improve it is for me a big part of the fun. When someone states he has solved problem X but doesn't want to discuss the implementation, what is exactly shared?

I like tinkering with different implementations, and abstractions to see what works fast, what works cleanly (as an interface) etc. It's just a way of expressing yourself precisely enough that a computer will follow you :) The a chess author (and C++ expert as well) Bo Persson formulated it like this a long time ago:
To me, finding the right abstractions is also part of the fun. Getting classes
like Piece, Square, Move, Bitboard, MoveGenerator, etc to work together without
them knowing each other's internal representation (and without get/set
functions), is great fun to me. Feels almost as good as seeing the piece images
make good moves on the screen...
This was during one of the early endless C vs C++ debates on CCC. The exact topic has changed of course, but the philosophy is a big part of what motivates me as well.

Joost Buijs
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Clone Conflict

Post by Joost Buijs » Tue Aug 23, 2016 08:18

Rein Halbersma wrote: 3) copying a substantial portion of a strong open source program (data structures, search, eval, egdb drivers, opening book) and fitting it into your own program. Some authors (Ed, Ronald/Jeroen in chess) even provide such portions (egdb, opening book) as freely usable plugins.
4) reading source code / journal articles about new ideas / techniques and implementing these from scratch

I think that in practice there is little difference between 3/4, or at the very least that they form a very broad and grey spectrum. Sure, 4 is more noble, and you'll certainly learn more, but is 3 really that bad? For some techniques there is very little discretion for an individual programmer (OK, some people will even find a dozen ways to locate 1-bits in a bitboard), for others it greatly matters. In all cases, you need lots of finetuning.
In many cases 3 is bad, in some cases you can not avoid to have small parts of your program resemble another one like for instance a board-structure or parts of a search() algorithm, but plain copying of a substantial portion of a strong open-source program is in my opinion not done.

The strength of an engine is largely determined by the evaluation features and the accompanying values, for a single person it takes an enormous amount of time to tune all these features.
In the case of stockfish there are many people working on this, just grabbing these features, putting them in your own engine and pretending that your engine is original is not very honest towards colleague programmers who don't take this shortcut.

When you write a chess engine from scratch it will take you many years of fine-tuning before you reach an acceptable level, nowadays I see many people without any experience creating >3000 Elo engines in just a few months, mostly by copying large portions of other strong engines.
I have no respect for people doing this, I have more respect for people like Henk van den Belt who is struggling to get his engine at an amateur level, but at least he created the thing himself.

I'm afraid that the same thing is going to happen here as well, shame factor or not.

Joost

Joost Buijs
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Clone Conflict

Post by Joost Buijs » Thu Aug 25, 2016 09:54

Joost Buijs wrote: For instance the SMP routine in my chess program resembles YBWC because that is one of the easiest ways to do this, but the whole implementation and coding is done by me without looking at other programs how to do this.
This took me 2 to 3 months (mainly working during weekends) before I found out how to do it and to have all the nasty race-conditions and bugs resolved, and in the end it gave me a lot of satisfaction because I developed everything myself.
Rein Halbersma wrote: That's very impressive!
The time I did this was in 2000 or 2001, there were only a few smp chess-programs, and there wasn't much knowledge about it besides some articles in the ICCA journal.
Nowadays it is a lot easier, compiler support is better, and there is a lot more knowledge about smp in general.
If I had to do it today I would also peek at other programs to get an idea, but that doesn't mean copying code.

Joost Buijs
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Clone Conflict

Post by Joost Buijs » Thu Aug 25, 2016 20:37

Rein Halbersma wrote: There is certainly a large amount of originality in draughts. But there is not enough discussion about it, and the discussions that do happen have far too little code in them for me to be interesting. I like to see concrete code how an idea works, to fully understand it, and to try and improve it is for me a big part of the fun. When someone states he has solved problem X but doesn't want to discuss the implementation, what is exactly shared?
It is indeed disappointing that there is hardly any discussion going on here, sometimes there is not a single post in days.

Personally I don't have a problem with posting ideas and code snippets, but posting complete implementations goes a little bit far.
Computer-chess and computer-draughts is competitive in nature, when everybody shares everything there is not much of a competition anymore.

BertTuyt
Posts: 1303
Joined: Wed Sep 01, 2004 19:42

Re: Clone Conflict

Post by BertTuyt » Thu Aug 25, 2016 21:13

I tend to agree that we miss some Brothers in Arms....
Im sure that Ed, Michel, Harm, Fabien, Jelle, Jan-Jaap, Ron, Klaas and others have zillions of ideas.
Also Gerard is absent for some time.
And altough Ton, Frank, Leo are Computer Draughts programmers from the early days I dont recall seeing them recently.
Not to forget Stef and Adri who are also lost in traffic.

So guys come on, ... :)

Bert

Joost Buijs
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Clone Conflict

Post by Joost Buijs » Fri Aug 26, 2016 06:47

Recently I spoke a few times with Gijsbert Wiesenekker by email and by telephone.
He was a little bit disappointed by the last results of GWD which he thinks is due to a bad evaluation function and the lack of SMP.
Probably his interest was renewed by talking to me because he told me lately he now has SMP working.
Hopefully we will see him more often here as well.

Joost

Post Reply