Draughts has not been solved, can a chess programmer solve it ?

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
mvanthoor
Posts: 1784
Joined: Wed Jul 03, 2019 4:42 pm
Location: Netherlands
Full name: Marcel Vanthoor

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by mvanthoor »

dangi12012 wrote: Tue Nov 16, 2021 8:30 pm Is there a draught engine in existence on github?
I don't know, but Chinook has been unbeatable for all intents and purposes since about 1994; and AFAIK, while it was running on a powerful computer for that time, it wasn't even a purpose-built supercomputer such as Deep Blue.

Draughts / Checkers have limited opening theory compared to chess.
Massive opening books and table bases (even compared to chess) exist, but I don't know if there are any for free. I assume so.
The rules are simpler than those of chess, and there are many positions with only one legal move: if you _can_ capture, you _must_ capture, and if there are multiple capture possibilities, the one capturing the most pieces _must_ be played.

As there are very large opening books and table bases, the computer only has to survive a relatively short, super-tactical middle game, which is right up its alley. IMHO, for all practical purposes, checkers / draughts is solved. You play it because you want to, not because there's ever a chance you could beat a computer at it.

Heck, even chess is "solved". Following GothamChess on YouTube, I see him, as a 2350 player, make opening preparations up to 20 moves and getting frazzled if the opponent plays something he didn't prepare for. Sometimes he says "this position is practically lost", and he's just at move 21. Also he sometimes says: "This position has been reached many times before...." (At move 30+...)

There are table bases of up to 7 pieces now. So even in chess, the computer has to only survive a relatively short middle game, so even chess is "solved" for practical purposes... but the one thing we can still learn from computers is that (opening) positions that were deemed unplayable actually ARE playable.

I see GothamChess play openings that were ... not a thing ... when I learned to play chess in the 80's. If I'd had a teacher back then and I would play some of the current-day openings, he'd be swiping the pieces off the board because of "idiotic play"... but today, computers have proven these lines to be perfectly playable, and now they're theory. Since I've been writing my chess engine I've also started to play chess more, against weaker engines (sub-2000 CCRL Elo), and I _really_ have to update my opening repertoire when I make opening books from games played after 2010. If I make opening books from games played after 2015-2016, I'm in danger of getting my eyes crossed... permanently. Some of that stuff is unreal to someone who has been playing chess only intermittently in the last 20 years (with a max rating up to 2000 Elo, around the year 2000).
Last edited by mvanthoor on Tue Nov 16, 2021 11:06 pm, edited 1 time in total.
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL
Madeleine Birchfield
Posts: 512
Joined: Tue Sep 29, 2020 4:29 pm
Location: Dublin, Ireland
Full name: Madeleine Birchfield

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by Madeleine Birchfield »

dangi12012 wrote: Tue Nov 16, 2021 8:30 pm Is there a draught engine in existence on github?
For international draughts:

https://github.com/rhalbersma/scan

For English draughts or American checkers:

https://github.com/jonkr2/GuiNN_Checkers
Chessqueen
Posts: 5685
Joined: Wed Sep 05, 2018 2:16 am
Location: Moving
Full name: Jorge Picado

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by Chessqueen »

Madeleine Birchfield wrote: Tue Nov 16, 2021 11:05 pm
dangi12012 wrote: Tue Nov 16, 2021 8:30 pm Is there a draught engine in existence on github?
For international draughts:

https://github.com/rhalbersma/scan

For English draughts or American checkers:

https://github.com/jonkr2/GuiNN_Checkers

Based on this information Scan 3.1 was the 5th best Draughts engine. https://www.uwccpi2021.draughtsprograms ... usion.html . For Chess Players who wants to try their luck, they can play on https://lidraughts.org/ like this IM who wanted to know if he can become good at Draught Eric Rosen is an IM in Chess

An IM like Eric got lucky against Magnus Carlsen by Eric Rosen ==>
Last edited by Chessqueen on Tue Nov 16, 2021 11:48 pm, edited 3 times in total.
User avatar
mvanthoor
Posts: 1784
Joined: Wed Jul 03, 2019 4:42 pm
Location: Netherlands
Full name: Marcel Vanthoor

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by mvanthoor »

Quite some people from the Netherlands again.

I always wondered why there are so many Dutch, German and English chess programmers; at least, there were in the 80's and 90's. Or maybe I'm just biased an remember them better than others.
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL
dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by dangi12012 »

mvanthoor wrote: Tue Nov 16, 2021 11:44 pm Quite some people from the Netherlands again.

I always wondered why there are so many Dutch, German and English chess programmers; at least, there were in the 80's and 90's. Or maybe I'm just biased an remember them better than others.
Thats racist.
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
User avatar
mvanthoor
Posts: 1784
Joined: Wed Jul 03, 2019 4:42 pm
Location: Netherlands
Full name: Marcel Vanthoor

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by mvanthoor »

dangi12012 wrote: Wed Nov 17, 2021 12:24 am Thats racist.
WTH? I am a _racist_ because I seem to remember more Dutch, German and English programmers from the 80's/90's than I do programmers from other nationalities and now for noticing that there are more than a few Dutch draughts programmers as well on that page? Cool. You must then want to hang me for knowing lots of Swedish pop music but none from Romania. I'm also of the opinion that Nightwish and some other symphonic metal bands are the *** because Floor Jansen is the lead singer... oh. Damn. She _happens_ to be Dutch. Hang me twice. And _all_ of the martial arts I practiced in the past are from Japan or South-Korea. The Chinese, and many others, must now be very upset with me...

Enough said. I'm not going to spend time replying to this subject any further.
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL
Chessqueen
Posts: 5685
Joined: Wed Sep 05, 2018 2:16 am
Location: Moving
Full name: Jorge Picado

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by Chessqueen »

dangi12012 wrote: Tue Nov 16, 2021 8:30 pm
Chessqueen wrote: Mon Nov 15, 2021 8:31 pm Draughts has not been solved, can a chess programmer solve it ? Only 8x8 checkers has been solved by Chinook, but not this version of international Draughts, which could be as complicated as chess with 10x10 Draughts board. I believe that this will be the next challenge to solve Draughts. Anyway here is an IM Chess player who just learned how to play Draughts ==>

Here is Eric Rosen Fide Ratings in Chess, but he is only rated over 1700 in Draughts ==> https://ratings.fide.com/profile/2032562
So that this doesnt derail into a discussion of chess vs draughts which you stated that you do not want.
Let me ask this:
Is there a draught engine in existence on github?
What is the known branching factor?

From a computer standpoint I can say that only 50 squares are used so a position would fit into 2 computer registers. Also with very simple rules so I guess only 2-3 instructions are needed per possible move so you could literally do trillions of moves/s on a gpu.

If its a 8x8 board its literally 32 squares with 24 pieces. That sounds infinitely more solvable especially since a gpu is a 32 bit machine.

That leaves retrograde analysis starting from 0 pieces and building a tablebase until you arrive at 40 man tablebase. I think in chess the tablebase uses less than 1 bit per position on average.
Also most of you do NOT even noticed that some of these Draughts programmers programmed Chess engines that are above 2550 CCRL rating for instance:

Joost Buijs programmer of Ares NNUE Draughts also programmed Nightmare Chess engine
The program was created in the end of june 2020, the first version of Ares in the NNUE [Event "WCRCC 2013"]

[Site "Internet Chess Club"]
[Date "2013.07.20"]
[Round "6"]
[White "Nightmare"]
[Black "Arasan"]
[Result "1/2-1/2"]

1.e4 c6 2.d4 d5 3.e5 Bf5 4.Nf3 e6 5.Be2 Nd7 6.O-O Bg6 7.Nbd2 Ne7 8.Nh4 c5
9.c3 Qb6 10.Ndf3 Be4 11.dxc5 Qxc5 12.Nd4 Nc6 13.Be3 Qe7 14.f3 Qxh4 15.Bf2
Qg5 16.fxe4 dxe4 17.Qa4 Ncxe5 18.Nb5 Qd8 19.Qxe4 a6 20.Bg3 Qb6+ 21.Kh1 axb5
22.Bxe5 Qc6 23.Qe3 Nxe5 24.Qxe5 f6 25.Rxf6 gxf6 26.Qxf6 Rg8 27.Bh5+ Rg6
28.Bxg6+ hxg6 29.Rf1 Kd7 30.Qf7+ Kd6 31.Rd1+ Ke5 32.h4 Rc8 33.Rd4 Bh6
34.Qxg6 Rh8 35.Rb4 Kd6 36.Qf6 Qe8 37.a4 Be3 38.Re4 Ba7 39.Qe5+ Kd7 40.Qxb5+
Kc8 41.Qe5 Qd8 42.Rc4+ Kd7 43.g3 Qb8 44.Qg7+ Kd6 45.Rb4 Qf8 46.Qxf8+ Rxf8
47.Rxb7 e5 48.Rxa7 e4 49.b3 e3 50.Ra6+ Kd5 51.c4+ Ke5 52.Ra5+ Ke4 53.Ra6 Rf1+
54.Kg2 e2 55.Re6+ Kd3 56.g4 e1=Q 57.Rxe1 Rxe1 58.h5 Ke3 59.b4 Kf4 60.b5 Re2+
61.Kf1 Kf3 62.a5 Ra2 63.Ke1 Ke3 64.Kf1 Rf2+ 65.Kg1 Kf3 66.b6 Rg2+ 67.Kf1 Ra2
68.Ke1 Ke3 69.Kd1 Kd3 70.Kc1 Kc3 71.Kd1 Kd3 72.Kc1 Kc3 73.Kd1 Kd3 1/2-1/2


Fabien Letouzey Scan 3.1 in Draughts also created this chess programs Fruit [2], Chess-64 [3] and Senpai,
Fruit is rated above 2700 by CCRL, therefore, when you look at Fruit 2 and compare it with Scan 3.1 in Draughts rated around 2450 by Draughts ratings, it is not so easy to program a Draughts engine that can beat the World Draughts human Champion https://www.fruitchess.com/
https://www.chessprogramming.org/Fabien_Letouzey
Chessqueen
Posts: 5685
Joined: Wed Sep 05, 2018 2:16 am
Location: Moving
Full name: Jorge Picado

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by Chessqueen »

Chessqueen wrote: Wed Nov 17, 2021 4:35 am
dangi12012 wrote: Tue Nov 16, 2021 8:30 pm
Chessqueen wrote: Mon Nov 15, 2021 8:31 pm Draughts has not been solved, can a chess programmer solve it ? Only 8x8 checkers has been solved by Chinook, but not this version of international Draughts, which could be as complicated as chess with 10x10 Draughts board. I believe that this will be the next challenge to solve Draughts. Anyway here is an IM Chess player who just learned how to play Draughts ==>

Here is Eric Rosen Fide Ratings in Chess, but he is only rated over 1700 in Draughts ==> https://ratings.fide.com/profile/2032562
So that this doesnt derail into a discussion of chess vs draughts which you stated that you do not want.
Let me ask this:
Is there a draught engine in existence on github?
What is the known branching factor?

From a computer standpoint I can say that only 50 squares are used so a position would fit into 2 computer registers. Also with very simple rules so I guess only 2-3 instructions are needed per possible move so you could literally do trillions of moves/s on a gpu.

If its a 8x8 board its literally 32 squares with 24 pieces. That sounds infinitely more solvable especially since a gpu is a 32 bit machine.

That leaves retrograde analysis starting from 0 pieces and building a tablebase until you arrive at 40 man tablebase. I think in chess the tablebase uses less than 1 bit per position on average.
Also most of you do NOT even noticed that some of these Draughts programmers programmed Chess engines that are above 2550 CCRL rating for instance:

Joost Buijs programmer of Ares NNUE Draughts also programmed Nightmare Chess engine
The program was created in the end of june 2020, the first version of Ares in the NNUE [Event "WCRCC 2013"]

[Site "Internet Chess Club"]
[Date "2013.07.20"]
[Round "6"]
[White "Nightmare"]
[Black "Arasan"]
[Result "1/2-1/2"]

1.e4 c6 2.d4 d5 3.e5 Bf5 4.Nf3 e6 5.Be2 Nd7 6.O-O Bg6 7.Nbd2 Ne7 8.Nh4 c5
9.c3 Qb6 10.Ndf3 Be4 11.dxc5 Qxc5 12.Nd4 Nc6 13.Be3 Qe7 14.f3 Qxh4 15.Bf2
Qg5 16.fxe4 dxe4 17.Qa4 Ncxe5 18.Nb5 Qd8 19.Qxe4 a6 20.Bg3 Qb6+ 21.Kh1 axb5
22.Bxe5 Qc6 23.Qe3 Nxe5 24.Qxe5 f6 25.Rxf6 gxf6 26.Qxf6 Rg8 27.Bh5+ Rg6
28.Bxg6+ hxg6 29.Rf1 Kd7 30.Qf7+ Kd6 31.Rd1+ Ke5 32.h4 Rc8 33.Rd4 Bh6
34.Qxg6 Rh8 35.Rb4 Kd6 36.Qf6 Qe8 37.a4 Be3 38.Re4 Ba7 39.Qe5+ Kd7 40.Qxb5+
Kc8 41.Qe5 Qd8 42.Rc4+ Kd7 43.g3 Qb8 44.Qg7+ Kd6 45.Rb4 Qf8 46.Qxf8+ Rxf8
47.Rxb7 e5 48.Rxa7 e4 49.b3 e3 50.Ra6+ Kd5 51.c4+ Ke5 52.Ra5+ Ke4 53.Ra6 Rf1+
54.Kg2 e2 55.Re6+ Kd3 56.g4 e1=Q 57.Rxe1 Rxe1 58.h5 Ke3 59.b4 Kf4 60.b5 Re2+
61.Kf1 Kf3 62.a5 Ra2 63.Ke1 Ke3 64.Kf1 Rf2+ 65.Kg1 Kf3 66.b6 Rg2+ 67.Kf1 Ra2
68.Ke1 Ke3 69.Kd1 Kd3 70.Kc1 Kc3 71.Kd1 Kd3 72.Kc1 Kc3 73.Kd1 Kd3 1/2-1/2


Fabien Letouzey Scan 3.1 in Draughts also created this chess programs Fruit [2], Chess-64 [3] and Senpai,
Fruit is rated above 2700 by CCRL, therefore, when you look at Fruit 2 and compare it with Scan 3.1 in Draughts rated around 2450 by Draughts ratings, it is not so easy to program a Draughts engine that can beat the World Draughts human Champion https://www.fruitchess.com/
https://www.chessprogramming.org/Fabien_Letouzey

Fabien wrote:
After a few years in computer draughts, I am back to chess for a little while. I see too many draws at top level, and am afraid that it will be too late in a couple of years. Big hardware and large opening books are also not helping IMO.

So I'm here to announce Senpai 2.0. The code looks all different because I started from my draughts program Scan, but it's actually still Senpai inside. I prefer having a consistent codebase for multiple games (also Shogi and Othello)
https://github.com/B4dT0bi/senpai/releases/tag/2.0
Jjaw
Posts: 78
Joined: Thu Jul 29, 2021 4:48 pm
Full name: Joe Louvier

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by Jjaw »

Guenther , Don't waste your time on the ChessFairy , he is in love with himself & oblivious to anything else ...
Chessqueen
Posts: 5685
Joined: Wed Sep 05, 2018 2:16 am
Location: Moving
Full name: Jorge Picado

Re: Draughts has not been solved, can a chess programmer solve it ?

Post by Chessqueen »

Jjaw wrote: Wed Nov 17, 2021 5:16 am Guenther , Don't waste your time on the ChessFairy , he is in love with himself & oblivious to anything else ...
Yes Guenther, Do NOT waste your time, trying to stop some troll on this forum, since they do NOT care what you say as long as they can keep a topic interesting for the other 98% of the members :roll: :mrgreen: :roll: