How could Checkers be solved in 2007 when .............

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

Moderators: hgm, Rebel, chrisw

Chessqueen
Posts: 5685
Joined: Wed Sep 05, 2018 2:16 am
Location: Moving
Full name: Jorge Picado

Black to play and Win (Checkers!)

Post by Chessqueen »

Sorry I do NOT have a graphical interface for Checkers, and I do NOT know where there is a Talkcheckers forum similar to this Talkchess forum. I am a terrible Chess player but I recently beat a Checker player rated 2150 playing Black. Since I do NOT have ant Checkers interface I am using Arena for chess. See if you can find the winning combination for Black to play and win ? I will give you the solution in 1 hour if you can NOT find it. This was playing the American checkers, NOT the British Checkers version. :roll:
[d]8/K5p1/1p5P/2P1k3/8/8/8/K1p1p1K1 b - - 0 1

Sorry for posting this here, I just found a great Checkers GUI, but NOT a Checker Forum similar to Talkchess Forum https://3dkingdoms.com/checkers.htm
Russian believe that they are special, that they can Kill thousands of Ukranian civilians, but cry like babies when a few Russian...
Chessqueen
Posts: 5685
Joined: Wed Sep 05, 2018 2:16 am
Location: Moving
Full name: Jorge Picado

Did Kingsrow reached the level of Chinook ?

Post by Chessqueen »

Chessqueen wrote: Sat May 18, 2024 6:43 pm Sorry I do NOT have a graphical interface for Checkers, and I do NOT know where there is a Talkcheckers forum similar to this Talkchess forum. I am a terrible Chess player but I recently I beat a Checker player rated 2150 playing Black. Since I do NOT have a Checkers interface I am using Arena for chess. See if you can find the winning combination for Black to play and win ? I will give you the solution in 1 hour if you can NOT find it. This was playing the American checkers, NOT the British Checkers version. :roll:
[d]8/K5p1/1p5P/2P1k3/8/8/8/K1p1p1K1 b - - 0 1

Sorry for posting this here, I just found a great Checkers GUI, but NOT a Checker Forum similar to Talkchess Forum https://3dkingdoms.com/checkers.htm
Did Kingsrow reached the level of Chinook in Checkers?


NOTE: Eureka I just found the best Checker Forum for Beginner player like myself, since I tried hard to become good at Chess and could never achieved it, I am having a better chance at Checker http://playground.usacheckers.com/forum/index.php
Russian believe that they are special, that they can Kill thousands of Ukranian civilians, but cry like babies when a few Russian...
Chessqueen
Posts: 5685
Joined: Wed Sep 05, 2018 2:16 am
Location: Moving
Full name: Jorge Picado

How could Checkers be solved in 2007 when .............

Post by Chessqueen »

How could Checkers be solved in 2007 when according to this article Chinook can definitely still lose a game.
In fact, in a match of indefinite length against a genuine oracle it would definitely lose. Currently the KingsRow program (Ed Gilbert) is stronger than Chinook - it's phenomenal - though still far from perfect.
https://www.google.com/search?q=Is+King ... s-wiz-serp
Russian believe that they are special, that they can Kill thousands of Ukranian civilians, but cry like babies when a few Russian...
User avatar
hgm
Posts: 27926
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: How could Checkers be solved in 2007 when .............

Post by hgm »

To solve a game you need to search until you reach a tablebase position. Which then gives you an exact score (distance to win, or a draw). So you won't need the heuristic evaluation of the engine. Under conditions where the search cannot be deep enough to reach the tablebases, the quality of play is determined by the heuristic evaluation, though.
User avatar
hgm
Posts: 27926
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: How could Checkers be solved in 2007 when .............

Post by hgm »

[Moderation] Checkers is somewhat off topic for TalkChess; it is not a chess variant.

It is true that from the viewpoint of engine programming chess and checkers are very similar, though. And in fact we have several long-time members who are checkers/draughts programmers.

I doubt whether there can be much useful interaction between users of chess and checkers engines, though, and publishing Checkers problems might be pointless here. But I don't think a single thread about Checkers would cause too much annoyance for those who hate the game, if the title cearly warns them off. So I will allow posting on Checkers as long as it stays limited to this thread.
User avatar
hgm
Posts: 27926
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: How could Checkers be solved in 2007 when .............

Post by hgm »

It is possible to post Checkers diagrams, but I had to resort to off-site images for the stones. And of course the Diagram's AI won't work, as it is not aware that capturing is mandatory.
theme=MV firstRank=1 graphicsDir=*/graphics.dir/alfaerieSVG/
graphicsType=svg
whitePrefix=b
blackPrefix=w
promoChoice=K
symmetry=none
checker::fmFfcafm(afcafm)F::c1,e1,b6,g7,,c5,h6
king::mFcafm(acafm)F:checkerking:e5,,a1,g1,a7
BTW, the WinBoard Alien Edition does support Checkers.
User avatar
Ajedrecista
Posts: 1986
Joined: Wed Jul 13, 2011 9:04 pm
Location: Madrid, Spain.

Re: Did KingsRow reached the level of Chinook?

Post by Ajedrecista »

Hello:
Chessqueen wrote: Sat May 18, 2024 7:29 pmDid Kingsrow reached the level of Chinook in Checkers?


NOTE: Eureka I just found the best Checker Forum for Beginner player like myself, since I tried hard to become good at Chess and could never achieved it, I am having a better chance at Checker http://playground.usacheckers.com/forum/index.php
AFAIK, the 2007 solution of checkers was a weak solving in the sense that Chinook was unbeatable if playing from the starting position with the standard, official rules. It is different than being a 24-piece DTM EGDB (distance-to-mate end game database) at any given position. It is true that both KingsRow and Cake improved a lot, to the point that there was a time that the challenge was not to lose any game —which was trivial—, but to reduce the time to not to lose any game. For example, a big difference would be if one engine needed 1 second/move to not lose while the other needed 10 seconds/move.

Furthermore, the thumbnail of the video shows a 10×10 checkerboard of International draughts with flying kings and men can capture backwards, which is a different variant than the 8×8 American checkers / British draughts without flying kings and men can not capture backwards that was weakly solved in 2007. The search space complexity of the game of nxn checkers was already a subject at TalkChess in 2016 and later confirmed outside TalkChess in 2017. You can see the difference of the search space complexity between an 8×8 checkerboard with 24 pieces (an upper bound of circa 5*10^20) and a 10×10 checkerboard with 40 pieces (an upper bound of circa 2.3*10^33).

There is an equivalent forum to TalkChess dedicated to 10×10 International draughts (and sometimes to other variants) here. The USA Checkers forum posted by you is the well-known forum of ACF (American Checkers Federation), that is, one of the 8×8 variants.

------------
hgm wrote: Sun May 19, 2024 10:39 am [Moderation] Checkers is somewhat off topic for TalkChess; it is not a chess variant.

It is true that from the viewpoint of engine programming chess and checkers are very similar, though. And in fact we have several long-time members who are checkers/draughts programmers.

I doubt whether there can be much useful interaction between users of chess and checkers engines, though, and publishing Checkers problems might be pointless here. But I don't think a single thread about Checkers would cause too much annoyance for those who hate the game, if the title cearly warns them off. So I will allow posting on Checkers as long as it stays limited to this thread.
Thanks Müller for allowing a checkers thread once in a blue moon. :-)

Regards from Spain.

Ajedrecista.
User avatar
hgm
Posts: 27926
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: How could Checkers be solved in 2007 when .............

Post by hgm »

I am not even sure the fact that the weak prove exists implies that Chinook could not be beaten. Proving a game is won or drawn could in theory be done by having an engine search to the very end of the game. And I think Fairy-Stockfish is indeed able to do this for some mini-variants that are won, such as Kyoto Shogi. Analyze the start position for a few weeks, and you get a mate score. (Of course having EGTs, so that you only have to search until you enter those, rather than to the checkmate, can greatly speed up the process, but it is not essential.)

That doesn't mean it would always win when it has to play faster than one move a month. The tree that would prove the win might be way too large to store it anywhere. Even the winning opening lines might overflow available storage before they are long enough to reach the mate (or EGT) when it gets out of book. If it has a poor evaluation it might then very well blunder the game away.
User avatar
Ajedrecista
Posts: 1986
Joined: Wed Jul 13, 2011 9:04 pm
Location: Madrid, Spain.

Re: Black to play and win (Checkers!).

Post by Ajedrecista »

Hello:
Chessqueen wrote: Sat May 18, 2024 6:43 pm Sorry I do NOT have a graphical interface for Checkers, and I do NOT know where there is a Talkcheckers forum similar to this Talkchess forum. I am a terrible Chess player but I recently beat a Checker player rated 2150 playing Black. Since I do NOT have ant Checkers interface I am using Arena for chess. See if you can find the winning combination for Black to play and win ? I will give you the solution in 1 hour if you can NOT find it. This was playing the American checkers, NOT the British Checkers version. :roll:
[d]8/K5p1/1p5P/2P1k3/8/8/8/K1p1p1K1 b - - 0 1

Sorry for posting this here, I just found a great Checkers GUI, but NOT a Checker Forum similar to Talkchess Forum https://3dkingdoms.com/checkers.htm
Ratings are relative, not absolute. The important thing is the rating difference between players, not the number itself. 2150 out of context could be an average player in a site where ratings are inflated. For example, top human players at Lichess are rated 3100+ in bullet games, and there are more blunders there than in 2700+ Elo FIDE human games at classical time controls. Sure, the longer time control improves the quality of the games and reduces the amount of blunders, despite the seemingly lower ratings.

AFAIK, American checkers and English draughts are exactly the same regarding the rules of play. There might be small differences of style like black pieces in England being red in USA; and the colours of the squares.

First of all, here is a comparison since chess and checkers have different notations:

Code: Select all

In chess, white starts the game and it is shown in the bottom half of the chessboard.
In American checkers / English draughts, black starts the game and it is shown in the bottom half of the checkerboard.

                  CHESS                            AMERICAN CHECKERS / ENGLISH DRAUGHTS

                  Black                                            White
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
| a8 | b8 | c8 | d8 | e8 | f8 | g8 | h8 |        |    | 32 |    | 31 |    | 30 |    | 29 |
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
| a7 | b7 | c7 | d7 | e7 | f7 | g7 | h7 |        | 28 |    | 27 |    | 26 |    | 25 |    |
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
| a6 | b6 | c6 | d6 | e6 | f6 | g6 | h6 |        |    | 24 |    | 23 |    | 22 |    | 21 |
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
| a5 | b5 | c5 | d5 | e5 | f5 | g5 | h5 |        | 20 |    | 19 |    | 18 |    | 17 |    |
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
| a4 | b4 | c4 | d4 | e4 | f4 | g4 | h4 |        |    | 16 |    | 15 |    | 14 |    | 13 |
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
| a3 | b3 | c3 | d3 | e3 | f3 | g3 | h3 |        | 12 |    | 11 |    | 10 |    |  9 |    |
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
| a2 | b2 | c2 | d2 | e2 | f2 | g2 | h2 |        |    |  8 |    |  7 |    |  6 |    |  5 |
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
| a1 | b1 | c1 | d1 | e1 | f1 | g1 | h1 |        |  4 |    |  3 |    |  2 |    |  1 |    |
+----+----+----+----+----+----+----+----+        +----+----+----+----+----+----+----+----+
                  White                                          Red / Black
The checkers notation might seem weird or strange, but if you flip the board to show white in the bottom half of the checkerboard, you get:

Code: Select all

   AMERICAN CHECKERS / ENGLISH DRAUGHTS

                Red / Black
+----+----+----+----+----+----+----+----+
|    |  1 |    |  2 |    |  3 |    |  4 |
+----+----+----+----+----+----+----+----+
|  5 |    |  6 |    |  7 |    |  8 |    |
+----+----+----+----+----+----+----+----+
|    |  9 |    | 10 |    | 11 |    | 12 |
+----+----+----+----+----+----+----+----+
| 13 |    | 14 |    | 15 |    | 16 |    |
+----+----+----+----+----+----+----+----+
|    | 17 |    | 18 |    | 19 |    | 20 |
+----+----+----+----+----+----+----+----+
| 21 |    | 22 |    | 23 |    | 24 |    |
+----+----+----+----+----+----+----+----+
|    | 25 |    | 26 |    | 27 |    | 28 |
+----+----+----+----+----+----+----+----+
| 29 |    | 30 |    | 31 |    | 32 |    |
+----+----+----+----+----+----+----+----+ 
                  White
Which is more user-friendly for left-to-right, top-to-bottom readers.

------------------------

I have the CheckerBoard GUI. If I set up the position and analyze with KingsRow 1.19b (which is not the latest version) and 8-man EGDB:

A first search with Multi-PV enabled at low depths retrieved than only 18-14 (e5-f4) would be a probable win for black (evals around 66, where 100 is a man and usually enough to win), but higher depths output drawish scores:

Code: Select all

depth 33,  1046.2s,  18-14,1  18-22,1  24-27,1  18-15,1  3-7,-1  2-7,-1  25-30,-1  25-29,-1  3-8,-2668  2-6,-2670  18-23,-3900
Positive scores are better for black and negative scores are better for white. The range of evaluations goes between -4000 and 4000 (-3999 means a mate in 1 ply for white).

------------------------

A second search with Multi-PV disabled also outputs a draw:

Code: Select all

value>1,  depth 37/5.0/5, 124.2s,  5006 kN/s,  pv 18-15 19x10 2-6 28x19 6x24
Such low values of selective search and mean depth values denote that EGDB positions are found. In this case, the mainline quickly goes down to a 3 vs 3 endgame (6 pieces after 4 captures: e5-d4 c5xe3, e1-f2 a7xc5, f2xd4xb6), thus covered by the 8-man EGDB.

------------------------
hgm wrote: Sun May 19, 2024 11:27 am It is possible to post Checkers diagrams, but I had to resort to off-site images for the stones. And of course the Diagram's AI won't work, as it is not aware that capturing is mandatory.
theme=MV firstRank=1 graphicsDir=*/graphics.dir/alfaerieSVG/
graphicsType=svg
whitePrefix=b
blackPrefix=w
promoChoice=K
symmetry=none
checker::fmFfcafm(afcafm)F::c1,e1,b6,g7,,c5,h6
king::mFcafm(acafm)F:checkerking:e5,,a1,g1,a7
BTW, the WinBoard Alien Edition does support Checkers.
Well done! The pieces are not shown to me, unfortunately, neither in the quote of your post, nor if I copy and paste your post without quoting. OTOH, I can see the pieces in your original post.

Regards from Spain.

Ajedrecista.
User avatar
hgm
Posts: 27926
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: How could Checkers be solved in 2007 when .............

Post by hgm »

Because I used off-site piece images the Diagram description contains a URL. The forum software corrupts that if you have not ticked the checkbox "Do not automatically parse URLs" when submitting the posting. I did that in my posting, but when you copy / quote it to a posting that didn't the corruption surfaces again, and the image URLs are mutilated to the point where they do not show up.

[Edit] It appears I already built in a solution for that, which I completely forgot about: a leading * in the graphicsDir specification is taken to mean the chessvariants.com domain, from which I took the piece images. Using that the forum software no longer recognizes the spec as a URL, and leaves it intact even without ticking the box. I now changed my Diagram and your quote of it accordingly.