TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Ed Trice

Joined: 19 Sep 2014
Posts: 98

Post subject: Re: Checkers Is Strongly-Solved for 8-pieces    Posted: Wed Feb 15, 2017 2:50 pm

 Rein Halbersma wrote: I would be interested in learning why DTW computations for checkers are inherently more complicated than for say chess. Can you elaborate?

The details emerge once you are actually writing the code and getting results. You soon find out that "chess logic" for DTW does not apply to checkers. Not only that, once you figure out the checkers logic, it's not apparent if your routine will ever terminate. Then, finally, the "light bulb moment" occurs, and everything falls into place.

In chess, for example, you place the pieces on every possible square, and look for checkmates for the side to move. Every such position is a "loss in 0." Next, every move possible by the side-not-to-move must create a "win in 1." I am oversimplifying, leaving out illegal "still in check" moves and the fact that the mated side might also have winning chances, etc. This process repeats for loss in 2, win in 3, loss in 4, etc.

In checkers, you have to look at every position with each iteration, and not just "increment" the win/loss ply counters.

Example from the 9-piece database:

Here the red checker starts at the bottom and crowns to a king on squares 29, 30, 31, or 32. It must travel up the board.

You can see if it were white to move, 16-12 threatens to win the checker on square 8 trivially. One might then think 8-12 is forced for red to move, keeping the red checker safe. But 8-12 throws away the win and white draws with 14-10 12x19 15x24x31. Recall an iterator only sees 1-move ahead at a time, and the values written are a function of the number of times a position is visited.

The correct winning move for red is 21-25! which can ignore 16-12? since that in turn loses to 25-22! which is a killer shot. It seems to throw away material pointlessly, but red wins after either 12x3 1-6! 18x25 6-10 14x7 2x11x18 and white to move loses in 28-ply, or 18x25 1-6 12x3 6-10 14x7 2x11x18.

So all this turmoil must first be examined, iteration after iteration, and we still don't have the optimal response for white to move after 21-25!

In chess endgames you don't have to deal with this.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Ed Trice Sun Feb 12, 2017 6:13 pm
Gerd Isenberg Mon Feb 13, 2017 1:04 pm
Sven Schüle Mon Feb 13, 2017 1:43 pm
Álvaro Begué Mon Feb 13, 2017 2:45 pm
Vladimir Medvedev Mon Feb 13, 2017 1:52 pm
Ed Trice Mon Feb 13, 2017 4:11 pm
Gerd Isenberg Mon Feb 13, 2017 7:46 pm
Ronald de Man Mon Feb 13, 2017 8:08 pm
Ed Trice Mon Feb 13, 2017 8:24 pm
Ronald de Man Mon Feb 13, 2017 8:30 pm
Sven Schüle Mon Feb 13, 2017 10:22 pm
Ronald de Man Mon Feb 13, 2017 11:51 pm
Ed Trice Tue Feb 14, 2017 2:26 am
Álvaro Begué Tue Feb 14, 2017 2:42 am
Ed Trice Tue Feb 14, 2017 12:02 am
Dann Corbit Tue Feb 14, 2017 12:26 am
Sven Schüle Tue Feb 14, 2017 9:57 am
Ed Trice Tue Feb 14, 2017 12:53 pm
Sven Schüle Tue Feb 14, 2017 2:55 pm
Ronald de Man Wed Feb 15, 2017 1:23 am
Sven Schüle Wed Feb 15, 2017 12:36 pm
J. Wesley Cleveland Wed Feb 15, 2017 6:08 pm
Ronald de Man Wed Feb 15, 2017 8:05 pm
Ed Trice Wed Feb 15, 2017 4:11 am
Sven Schüle Wed Feb 15, 2017 12:45 pm
Rein Halbersma Tue Feb 14, 2017 3:13 pm
Ed Trice Wed Feb 15, 2017 3:55 am
Rein Halbersma Wed Feb 15, 2017 9:03 am
Ed Trice Wed Feb 15, 2017 2:50 pm
Re: Checkers Is Strongly-Solved for 8-pieces Ed Trice Wed Feb 15, 2017 2:50 pm
Rein Halbersma Wed Feb 15, 2017 7:20 pm
Ed Trice Thu Feb 16, 2017 4:38 am
Rein Halbersma Thu Feb 16, 2017 7:25 am
Ronald de Man Wed Feb 15, 2017 8:00 pm
Rein Halbersma Wed Feb 15, 2017 8:14 pm
Ronald de Man Wed Feb 15, 2017 8:31 pm
Ed Trice Thu Feb 16, 2017 4:20 am
Rein Halbersma Thu Feb 16, 2017 7:16 am
Ed Trice Thu Feb 16, 2017 8:23 am
Rein Halbersma Thu Feb 16, 2017 11:55 am
Sven Schüle Thu Feb 16, 2017 3:00 pm
Álvaro Begué Thu Feb 16, 2017 3:13 pm
Rein Halbersma Thu Feb 16, 2017 3:48 pm
Ed Trice Thu Feb 16, 2017 3:55 pm
Rein Halbersma Thu Feb 16, 2017 4:18 pm
Ronald de Man Thu Feb 16, 2017 7:27 pm
Ed Trice Thu Feb 16, 2017 9:47 pm
Ed Trice Sat Feb 18, 2017 5:23 am
Ronald de Man Sat Feb 18, 2017 3:58 pm
Ed Trice Sat Feb 18, 2017 4:49 pm
J. Wesley Cleveland Sat Feb 18, 2017 5:56 pm
Roch Manilla Sun Feb 19, 2017 12:32 am
Ed Trice Sun Feb 19, 2017 5:44 pm
Greg Simpson Sun Feb 19, 2017 9:04 pm
Rein Halbersma Sun Feb 19, 2017 9:27 pm
Greg Simpson Sun Feb 19, 2017 10:10 pm
Martin Sedlak Sun Feb 19, 2017 11:17 pm
Ed Trice Mon Feb 20, 2017 2:35 am
Ed Trice Mon Feb 20, 2017 5:31 am
Daniel Anulliero Mon Feb 20, 2017 8:21 am
Richard Delorme Mon Feb 20, 2017 2:13 pm
Jon Fredrik Åsvang Mon Feb 20, 2017 5:10 pm
Ed Trice Mon Feb 20, 2017 5:34 pm
Ed Trice Mon Feb 20, 2017 5:37 pm
Ed Trice Mon Feb 20, 2017 5:51 pm
Alvaro Cardoso Thu Feb 23, 2017 1:04 am
Ed Trice Thu Feb 23, 2017 6:14 pm
Alvaro Cardoso Thu Feb 23, 2017 11:52 pm
Ed Trice Fri Feb 24, 2017 4:19 am
Alvaro Cardoso Sat Feb 25, 2017 1:20 am
Ed Trice Sun Feb 26, 2017 4:56 am
Alvaro Cardoso Sun Feb 26, 2017 1:21 pm
Ed Trice Tue Feb 28, 2017 5:58 pm
Ed Trice Thu Mar 23, 2017 11:21 pm
Alvaro Cardoso Fri Mar 24, 2017 4:23 pm
Ed Trice Mon Mar 27, 2017 3:31 pm
Michael B Fri Mar 31, 2017 3:39 am
Ed Trice Thu Apr 06, 2017 10:10 pm
Rein Halbersma Mon Feb 27, 2017 2:58 pm
Ronald de Man Sat Feb 18, 2017 8:33 pm
Ed Trice Mon Mar 05, 2018 2:54 am
Rein Halbersma Mon Mar 05, 2018 7:23 am
Ronald de Man Mon Mar 05, 2018 4:34 pm
Rein Halbersma Mon Mar 05, 2018 5:18 pm
Ronald de Man Mon Mar 05, 2018 5:34 pm
Rein Halbersma Sat Feb 18, 2017 4:16 pm
Ed Trice Thu Feb 16, 2017 4:06 pm
Álvaro Begué Thu Feb 16, 2017 4:10 pm
Ed Trice Thu Feb 16, 2017 9:51 pm
Ronald de Man Wed Feb 15, 2017 1:10 am
Sven Schüle Wed Feb 15, 2017 12:29 pm
Ronald de Man Wed Feb 15, 2017 8:12 pm
Álvaro Begué Tue Feb 14, 2017 2:43 am
Ed Trice Tue Feb 14, 2017 3:03 am
Alvaro Cardoso Mon Feb 13, 2017 9:21 pm
Ed Trice Mon Feb 13, 2017 11:50 pm
Ed Trice Tue Feb 14, 2017 2:08 am
Krzysztof Grzelak Tue Feb 14, 2017 2:37 pm
Ed Trice Sat Feb 17, 2018 7:16 pm

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumChess Players ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum