Why Checkers is NOT easier than Chess

[Chexhero]

Haha, I found the draw!

11-7, 26-31, 21-17, 31-26, 17-13, 26-22, 6-2, 18-23, 9-6, 22-18, 13-9 or 14-9! Now white can just play back and forth, no chance for red to break in! Not sure if that is the continuation giving, but red does not have enough time to break in. Wow, what a great problem! I am assuming 11-7 is crucial in order to maintain the fortress?

[MostFamousDane]

Haha, I found the draw!

11-7, 26-31, 21-17, 31-26, 17-13, 26-22, 6-2, 18-23, 9-6, 22-18, 13-9 or 14-9! Now white can just play back and forth, no chance for red to break in! Not sure if that is the continuation giving, but red does not have enough time to break in. Wow, what a great problem! I am assuming 11-7 is crucial in order to maintain the fortress?

Yep you got it - all though 14-9 won't do it has to be 13-9. There is more on this kind of position in Bolands Masterpieces page 154.

What is interesting to note is that the search tree for these kinds of positions is infinite. What are you supposed to do with this kind of position when you attempt to solve checkers by searching ? The answer is there is nothing you can do - no matter how much hardware you have available it is logically impossible to perform an infinite search!

You are forced to cut off at some point and just assume that the position is a draw. So how many moves do you search forward 100 moves, 200 ? You have to know beforehand what is the maximal number of moves required to win a position. The only way you can have this information is if you all ready have solved checkers!

[liam stephens]

Copy to University of Alberta (Dr Schaeffer)

[Bernard Coll]

Nice one Sune.

[Palomino]

This problem is reminiscent of Brian Hinkle's Bear Claw problem.

A series of articles from Bob Newell.
(Checker Maven Dec 10, 2005)
http://www.bobnewell.net/nucleus/nucleu ... itemid=166
(Checker Maven FEb. 25, 2006)
http://www.bobnewell.net/nucleus/nucleu ... itemid=232
(Checker Maven Mar. 11, 2006)
http://www.bobnewell.net/nucleus/nucleu ... itemid=248
(Checker Maven Apr. 15, 2006)
http://www.bobnewell.net/nucleus/nucleu ... itemid=263
(Checker Maven July 1, 2006)
http://www.bobnewell.net/nucleus/nucleu ... itemid=264
(Checker Maven Sept. 30, 2006)
http://www.bobnewell.net/nucleus/nucleu ... itemid=337
Solution: (Checker Maven Nov. 18, 2006)
http://www.bobnewell.net/nucleus/checke ... tured+Bear

This is now the draw formation attributed to Dr. T. J. Brown in Ben Boland's Masterpieces in the Game of Checkers, p. 155, diagram C.

[Bill Salot]

I know we are off-topic, but you fellows seem to enjoy checker problems. So why don't you try composing one?

[George Hay]

Sune, the "checker fortress" problem by Dr. Brown fooled Cake and Wincheck!
I was able to draw those programs on this problem, recognizing the theme.
I was familiar with the theme thanks to Bob Newell, a.k.a. chipschap, a.k.a. the Checker Maven.
His Ein Feste Burg (A Mighty Fortress) 06/09/12 column had a a similar problem by O. H. Richmond.
In fact Dr. Brown's problem, well essentially the same problem, is the lead problem
in that column.

(Checker Maven June 9, 2012)
http://www.bobnewell.net/nucleus/checke ... itemid=249

The "checker fortress" problem reminds me of castling in chess, and I can say that is my first impression!
I am impressed with Chexhero solving the problem cross-board!
--George Hay

[Chexhero]

Solving a problem is a lot easier when you know the idea your looking for. I would have never solved that was it not for Sune's clues. Heck, I was not even willing to attempt it at first lol. That is something you just don't look for on a checkerboard

[chipschap]

As I recall from back then, both Cake and KingsRow couldn't solve the fortress; I'll have to try it again with the latest KingsRow and 10-piece database, though I don't expect anything different.

[Chexhero]

I agree with Liam, I think we should send it to Schaeffer and see if Chinook can solve it. Just this one problem could actually prove if Chinook solving checkers is real or not. There were also problems in Bill's problem contests that kingsrow or cake could not solve, I think due to another fortress or giant block idea, I forget the problems, but it certainly seems there are certain types of problems programs can't solve.

[chipschap]

Originally (again if I recall correctly) Cake and KingsRow wouldn't solve huge block problems*, but I remember Martin going back and putting logic in Cake for that. But the fortress remains outside the solving ability of these engines. I don't see why Chinook would be different, because the move search functions (which have to be similar for all three engines) prune out the "starting move" and never go down that branch.

I tried KingsRow again this morning (9 September 2012) on the problem in this thread and after an hour (i.e. just about forever) it still thought Black wins.

What does this say about checkers being "solved"? It's maybe not the right question. Checkers was proven to be a draw but it certainly wasn't solved over its entire solution space.

*See "Remarkable Block Problem", Checker Maven, Feb 19, 2005, http://www.bobnewell.net/nucleus/checkers.php?itemid=48

[Alex_Moiseyev]

Sune position is nice as many other Dr. Brown similar problems. But it doesn't demostrate any complexity of game, only curiousity

And also programs probaly don't have loaded important WCDF tournament rules of "3 (4,5 ... whatever) times repeated draw" and "40 moves" rule which allows normal end of game and breaks "infinite". There are also "positional draws" in chess where one side with big material advantage can't make any progress.

Having these rules install, program evaluation number will automatically drop to -1 as soon as search depth reach 50 moves (100 plies) or some position during search gets repeated 3 times.

No programs are perfect today until programmers build 24 pieces ranking ending database However ... for 7 years since Kigsrow was delivered to public, I made to it's opening book ONLY 2 corrections when program gets into lost with ALL BEST moves. Ed Gilbert corrected this by interventing and extending manually extra and deeper generator search. Not too bad number - 2 corrections to 2 million positions. It maybe still a few more somwhere. I also suggested Ed to review positions at the very end of each variation

In addition I also pointered out Ed attention to one class of positions, where it's evaluation number should be changed and increased manually by adding extra factor. Ed followed my suggestion, made alot of testing and finally little bit changed code which improved program search and allowed it to win more positions with more accurate play.

Jim Loy also find more corrections to Kingsrow GOOD moves.

So, the only thing we really proved so far - noone and nothing is perfect (including programs), but this fact was well known to human society more than 2000 years ago when Bible war written !

Sincerely yours,
Alex Moiseyev

[MostFamousDane]

And also programs probaly don't have loaded important WCDF tournament rules of "3 (4,5 ... whatever) times repeated draw" and "40 moves" rule which allows normal end of game and breaks "infinite". There are also "positional draws" in chess where one side with big material advantage can't make any progress.

Having these rules install, program evaluation number will automatically drop to -1 as soon as search depth reach 50 moves (100 plies) or some position during search gets repeated 3 times.

That is just silly these are practical rules are geared toward humans playing in a tournament and are completely irrelevant in this context. When you generate the endgame databases you find lots and lots of positions that take more than 50 moves to achieve progress if you applied this rule while generating the endgame databases they would be completely worthless.

No programs are perfect today until programmers build 24 pieces ranking ending database However ... for 7 years since Kigsrow was delivered to public, I made to it's opening book ONLY 2 corrections when program gets into lost with ALL BEST moves. Ed Gilbert corrected this by interventing and extending manually extra and deeper generator search. Not too bad number - 2 corrections to 2 million positions. It maybe still a few more somwhere. I also suggested Ed to review positions at the very end of each variation

In addition I also pointered out Ed attention to one class of positions, where it's evaluation number should be changed and increased manually by adding extra factor. Ed followed my suggestion, made alot of testing and finally little bit changed code which improved program search and allowed it to win more positions with more accurate play.

Jim Loy also find more corrections to Kingsrow GOOD moves.

So, the only thing we really proved so far - noone and nothing is perfect (including programs), but this fact was well known to human society more than 2000 years ago when Bible war written !

Sincerely yours,
Alex Moiseyev

I didn't assume that I had proven anything - my starting point was that chinook has not solved checkers and that this had been established a long time ago. I agree with you that Kingsrows best move is probably quite close to being perfect - but just because you have not been able to find many flaws in it doesn't mean that Mac wouldn't be able to find lots - or that I wouldn't .

Sune

[Alex_Moiseyev]

it doesn't mean that Mac wouldn't be able to find lots - or that I wouldn't .

All my findings I shared with Ed, he corrected book and released to public - all I know. Same thing did Jim Loy. No sure if you, Max or anyone else find anything - not my business and don't care of.

Kingsrow program is a free public product, not our enemy, and it is OUR responsibility to improve it and make close to perfect. Ed Gilbert can't do this alone.

[Alex_Moiseyev]

Sune,

thought more about this class of positions in checkers. It is quite possible that with existing, not 100% accurate algorythm to build ending databases, even in 24 pieces EDB (ending database) this position will be still rated as lost or ... missed !!! WOW