Computer Draughts, Past Present and Future

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

Computer Draughts, Past Present and Future

Post by BertTuyt » Sun Nov 03, 2019 14:44

On a rainy day in Switzerland, Im further working on my draughts program Damage.

As some know, I already started with this hobby (or addiction) in the 1970-1980 period.
Staring with a CPU development kit (Z80) , which I used to program in hex a draughts move generator.
The first program around 1977-1978, programmed in Fortran on a PDP11.
And at the end of the 1980 decade the first version of Damage (Damage 1.0) on a Amiga 500, where I never succeeded in realizing the 1000 nodes/second.

When I write this my program is running between 60M - 70M nodes/second, on a 6-core Intel i7 8700K.
Building on the shoulders of giants.
A draughts program consist of several components, and many have supported to get where we are today.

MoveGenerator, think all (or at least the majority) use a bitboard based version. And the Perft competition (started by Ed) has helped to stretch limits never thought possible.

Search, from minimax to alpha beta, and all kinds of search enhancements (mainly developed within the active Chess community), have resulted in search-depths beyond the 20 ply. And for all who want to learn all techniques, just examine Stockfish or the Scan code from Fabien.
Next to that to utilize the power of multi-core one can rely on algorithms like YBWC or (maybe the better solution for hyper number of cores) Lazy SMP.

Evaluation, where initially only experienced draughts players dominated computer chess ( Stef Keetman Truus, Adri Vermeulen Flits), the approach developed and shared by Fabien (although Michel Grimminck with Dragon might be the first) seem now the only way forward. To my knowledge now at least 2 other programs (next to Scan and Dragon) have implemented this technique (Kingsrow and Maximus).

Endgame Databases, the retrograde algorithm is quite old, but since Ed provided free of charge his egdb-driver and 8p DBs, there is basically no need to generate them separately by yourself.

Opening book, this remains a time consuming task, but also here the example you should apply is drop-out expansion (to my knowledge at least used by Ed).

And to compare engines with each others we can now all benefit from the DXP communication standard as developed by Frank Mesander.

In my case (= Damage), Im now generating many games (plan around 1M) to also enter the group of ML learned evaluation patterns. Here I really should thank Ed who shared with me some source code, so I could make a jump start.
So Damage will join the ML team (some day :D).

As written quite some times, the top programs (Scan, Kingsrow) now all play almost always a draw with normal match game settings ( > 10 minutes), and the real difference only become obvious with ultra fast bullet time settings (and limiting the search to 1 core).

So as we all will disappear in the draw black hole, what is left.
To my opinion we could further built upon the work of AlphaZero, so the combination of MCTS and neural networks, or use this network to find the optimal features.

For now the modern ML based evaluation functions are based upon lineair features (like men value, left right balance, first king, multi kings, ...) and boolean features, like a specific pattern is present or not.
The current feature set (example for Scan) seems to work extremely well, but most likely the optimum is not yet reached.

So no reason for Computer Draughts to retire yet...... :D

Bert

Krzysztof Grzelak
Posts: 927
Joined: Thu Jun 20, 2013 17:16
Real name: Krzysztof Grzelak

Re: Computer Draughts, Past Present and Future

Post by Krzysztof Grzelak » Sat Dec 21, 2019 08:59

Hi Bert.

I have a request for you. How to make your draughts engine, please make it so that you can use it for the processor AMD.

Krzysztof

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

Re: Computer Draughts, Past Present and Future

Post by BertTuyt » Sun Feb 23, 2020 11:30

Krzysztof, re reading my older emails.

I will issue a version which works on your 16 Core Threadripper.
As you can read in other posts, Im now working on getting closer to Kingsrow/Scan.
Based on the simulations (DXP Matches), I guess Damage 15.3 is around 10 ELO points weaker compared with these (famous) 2.
Maybe even more when Ed releases his next HUB Version.
So first I will try to optimize the evaluation.

Next to that, further big improvements will become more and more difficult as there is most likely no simple magic ELO bullet, which increases performance with 10 points.

In that case one need 10 smaller improvements, who each bring you 1 ELO point with a statistical significance of 6-sigma.
Which means testing with many games to make sure all works.....

As I go on holiday (if not stopped by Corona) end March, I will issue a version for the community before my departure.

Bert

Krzysztof Grzelak
Posts: 927
Joined: Thu Jun 20, 2013 17:16
Real name: Krzysztof Grzelak

Re: Computer Draughts, Past Present and Future

Post by Krzysztof Grzelak » Mon Feb 24, 2020 12:47

Thank you for the information Bert.

Sidiki
Posts: 177
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: Computer Draughts, Past Present and Future

Post by Sidiki » Fri Feb 28, 2020 11:45

BertTuyt wrote:
Sun Feb 23, 2020 11:30
Krzysztof, re reading my older emails.

I will issue a version which works on your 16 Core Threadripper.
As you can read in other posts, Im now working on getting closer to Kingsrow/Scan.
Based on the simulations (DXP Matches), I guess Damage 15.3 is around 10 ELO points weaker compared with these (famous) 2.
Maybe even more when Ed releases his next HUB Version.
So first I will try to optimize the evaluation.

Next to that, further big improvements will become more and more difficult as there is most likely no simple magic ELO bullet, which increases performance with 10 points.

In that case one need 10 smaller improvements, who each bring you 1 ELO point with a statistical significance of 6-sigma.
Which means testing with many games to make sure all works.....

As I go on holiday (if not stopped by Corona) end March, I will issue a version for the community before my departure.

Bert
Thank Bert,
We are waiting for this release, so even at this time, Scan refuse to lose?
10 Elo weaker than another program it's more visible with many thousand of games. Isn't ?

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

Re: Computer Draughts, Past Present and Future

Post by BertTuyt » Fri Feb 28, 2020 17:12

Sidiki, to quantify ELO differences like 10, you need indeed far more games.
However when multiple matches show the same pattern, I'm confident that Damage 15.3 is still weaker as Scan 3.1, ballpark figure 10 ELO.
I will further try to optimize the evaluation function, and will certainly before end of March issue the new version including GUI.

Bert

Sidiki
Posts: 177
Joined: Thu Jan 15, 2015 16:28
Real name: Coulibaly Sidiki

Re: Computer Draughts, Past Present and Future

Post by Sidiki » Fri Feb 28, 2020 22:54

BertTuyt wrote:
Fri Feb 28, 2020 17:12
Sidiki, to quantify ELO differences like 10, you need indeed far more games.
However when multiple matches show the same pattern, I'm confident that Damage 15.3 is still weaker as Scan 3.1, ballpark figure 10 ELO.
I will further try to optimize the evaluation function, and will certainly before end of March issue the new version including GUI.

Bert
Thank again Bert for these explainations,
So gain 1 Elo isn't a little thing.
That's clear that eval has a big effect on draughts program strenght.
Just to say that, an deep eval with an agressive goal will be very hard to beat. The best defense it's attack.

Sidiki

Krzysztof Grzelak
Posts: 927
Joined: Thu Jun 20, 2013 17:16
Real name: Krzysztof Grzelak

Re: Computer Draughts, Past Present and Future

Post by Krzysztof Grzelak » Sat Aug 01, 2020 08:09

I found such a history of the Damage program in the Internet.

The development of Damage started somewhere around 1974-1975 when I wrote a hypothetical Move-generator for Draughts (10 *10). A nowadays obsolete computer language (ECOL ?) was used, which was only meant as an educational tool for students.

Later (1978-1979) I made, together with a friend (Rob van Ommering), DAM11, probably one of the first Draughts programs. The language was FORTRAN and the computer a Digital PDP 11/03. Although the system speed was very slow, measured by todays standards, the program managed to win on a regular basis. This to the disbelief of the victims and/or spectators who were quite sure that this was almost impossible. How could an advanced calculator win from the combined intellect and the creativity of the human brain? Parallels with L'affaire Dreyfus and more recently Kasparov are obvious.

After my study and military service, I restarted (1987) with this Computer draughts addiction and developed a new program Damage. The name is in fact a combination of Dam which is dutch for Draughts and age referring to the author! The programming language was C with 68000 Assembly, the computer a Commodore Amiga 500 (Damage 1.x). Later I switched to a more powerful Amiga 2000, equipped with a 25MHz Motorola 68040 and 16MByte memory (Damage 2.0 - 3.10). At this time I also started participating in draughts tournaments, with (I hate to admit it) moderate success, so Damage despite his frightening name mostly hurts itself and therefor his creator.

In 1995 I stopped with Draughts program development for the Amiga platform because Commodore could no longer offer a cost-effective alternative to the PC in terms of raw-speed, programming tools, etc. From that moment onwards I joined the PC camp. Due to the problems I had encountered with updating and associated debugging I abandoned the Assembly and restricted myself to C. In 1996 I was ready with the port from Amiga to PC. Because I had little PC-knowledge at that time, the program (Damage 4.0) had a relatively simple ASCII user-interface (but it worked !).

From 1996 onwards I concentrated on a Windows95 implementation of my program. The Freeware beta-release (Damage 5.0) will become general available in April-May 1998. After user feedback the final release can be expected before the end of this year. Because the main Draughts-engine is relatively unchanged since 1995, my first priority is the improvement of the evaluation function in future releases. Improving the search-process further has less priority, due to diminishing returns for additional search.

Post Reply