Computer Draughts, Past Present and Future

Discussion about development of draughts in the time of computer and Internet.
Post Reply
BertTuyt
Posts: 1344
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: 793
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

Post Reply