Computer Program Weaknesses with Problems

Discussion and analysis about certain positions.

Computer Program Weaknesses with Problems

Postby Bill Salot on Sun Sep 08, 2013 1:22 pm

Sune Thrane's "Teasers" have demonstrated that complicated positions can baffle computers for a long time.

An earlier discussion indicated that most computer programs are unable to solve "fortress" problems.

My little "Checkerboard: Cake 1.85" has always struggled with "block" problems.

And the latest disappointment for me is that my program insists that "Payne's Single Corner Draw" is a win.

By that I mean when I set up "Payne's Single Corner Draw", with White being a piece down, the program gives the Red position a value in the +140's. And when I give it "infinite" time to think on it, it decides, after about 80 seconds, to make an aimless move while still valuing the Red position in the +140's. This continues indefinitely until I finally lose my patience with its stupidity.

My questions are 1) Do other programs have the same opinion about "Payne's Single Corner Draw", and 2) If not, what determines when they concede that a perpetual draw is really a draw?
Bill Salot
 
Posts: 341
Joined: Sat Dec 15, 2007 10:57 am

Re: Computer Program Weaknesses with Problems

Postby George Hay on Mon Sep 09, 2013 1:10 pm

Hi Bill, Payne's Single Corner Draw (aka Payne's Draw) is still a draw with cake! I put it on auto and ran at least 40 moves without a capture or the move of a man, and cake still draws. I ran it on 10 seconds per move. I am not sure what is happening with the numbers! It is my impression that a perfectly even position would be at zero. Until now I was also under the (false) impression that a winning position would always be about 100.

KingsRow got the same result as cake, a draw. The regular (English) KingsRow may be downloaded (free) to CheckerBoard fairly easily from:

http://edgilbert.org/Checkers/KingsRow.htm

Even simplech draws, although eacych is not advanced enough for Payne's Draw.

Wincheck will draw even after 40 moves, and will accept a draw when offered (I could have saved a few steps ha ha). Wincheck is available (free) from:

http://alemanni.pagesperso-orange.fr/index.html

The work of Dr. T.J. Brown of Limerick is very interesting. He had the first Fortress Problem for English Draughts, as seen on page 70 of Checkers Improved by S.T. Livermore. Dr. Brown also composed First Position in Embryo, and the Adam Problem. Dr. Brown is featured in Midget Problems by W.T. Call, as well as G.H. Slocum and Dr. A. Schaefer (who is not to be confused with Dr. Jonathan Schaeffer). In 1871 Dr. Brown even claimed to prove checkers is a draw if "properly played" as reported by W.T. Call in Vocabulary Of Checkers, under the entry Improving the board.
--George Hay
George Hay
 
Posts: 808
Joined: Sat Jan 01, 2011 7:41 am
Location: Grand Rapids, Michigan, USA

Re: Computer Program Weaknesses with Problems

Postby john reade on Tue Sep 10, 2013 1:14 am

Colossus gives a draw for the Payne position too.
john reade
 
Posts: 513
Joined: Tue Jan 24, 2006 12:50 pm

Re: Computer Program Weaknesses with Problems

Postby Bill Salot on Sun Sep 15, 2013 2:01 pm

George and John,

Are you saying that the value set by any of these programs is untrustworthy for the purposes of adjudicating a game, and that we must set it on automatic and wait for 40 moves before declaring that Payne's Draw is a draw?

Isn't there a program that can recognize or analyze the draw without making a move?

Isn't that what a perfect database is supposed to do?
Bill Salot
 
Posts: 341
Joined: Sat Dec 15, 2007 10:57 am

Re: Computer Program Weaknesses with Problems

Postby George Hay on Mon Sep 16, 2013 11:41 am

Hi Bill, I let the computer play out to a legal draw of 40 moves on each side without a man moving or a capture.
That way I am pretty sure the position is a draw. For Payne's Draw, I don't think the pieces are moving aimlessly, at least not the side playing defense! This is in contrast to a fortress problem, where the computer flat out misses the draw and never forms the fortress, leading to a loss for the defense! I don't have a 10 piece database, but it would take a 24 piece database to strongly solve checkers! Chinook has a limitation, so far, in its opening analysis. From the Chinook webpage index you can go to Checkers Solution where a after an application run a set up checkerboard appears with notes about win or draw for each move. (You can view the moves in "Tree" or "Flat", with "Flat" working better for me!) If these Single Corner moves are played, 11-15 22 18, 15x22, 25x18, 8-11 29 25, 4-8 25 22, the last move in that sequence is "unresolved." So one of the earliest and most published Single Corner opening sequences is "unresolved" by Chinook by white's fourth move (25 22).
http://webdocs.cs.ualberta.ca/~chinook/

--George Hay
George Hay
 
Posts: 808
Joined: Sat Jan 01, 2011 7:41 am
Location: Grand Rapids, Michigan, USA

Re: Computer Program Weaknesses with Problems

Postby Bill Salot on Mon Sep 16, 2013 4:57 pm

Hi George,

Did you miss my point? I was not trying to prove that Payne's Draw is a draw. We all know that it is. I was just trying to make my computer concede that it is.

Sure it will play 40 moves automatically without making progress. If you call it a draw at that point, it is you, not the computer, calling it a draw.

I set my computer on automatic, 15 seconds per move, and let it go for hours, hundreds of moves, and it made no difference. It obviously thought for 15 seconds, then made a move without having reached a conclusion, and repeated the process ad infinitum. For Heaven's sake, I can play that way without a computer.

I also let the computer have infinite time to make a move. It crashed without making a single move.

My computer can claim a win in some positions, so why can't it claim a known draw without wasting my time waiting for nothing?

Is there a computer program that can do better?

Is the only correct interpretation this: when my computer can't claim a win, it is a draw that the computer will never concede?

Come on you computerphiles, defend yourselves!
Bill Salot
 
Posts: 341
Joined: Sat Dec 15, 2007 10:57 am

Re: Computer Program Weaknesses with Problems

Postby liam stephens on Tue Sep 17, 2013 7:56 am

Hi Bill,

With the Wyllie program and 8 piece database my computer sees that Payne's single corner position is a draw, but on account of that does not try to win with the strong side and soon sacrifices a piece to make it a 2 X 2 draw.

Position - Black: 13, K: 14, 15, White: K: 22, 26. White to play and draw.
Computer plays: 26-23, 14-17, 22-25, 17-21, 25-22, 13-17, draw.

Similarly in the Oldbury problem in Move Over, page 70, diagram 46:

Position - Black: K: 13, 16, White 18, 28, K: 5. Black to play.

Computer plays: 16-11, 5-1, 13-9, 18-15, draw.

It appears that in man down draws, once the program sees that it is a draw it will not bother to try and win with the strong side but will soon sacrifice a piece to a simple drawn ending.

Regards - Liam.
liam stephens
 
Posts: 912
Joined: Sun Nov 27, 2005 2:56 pm
Location: Ireland

Re: Computer Program Weaknesses with Problems

Postby Chexhero on Tue Sep 17, 2013 12:46 pm

Liam is correct. A program with a 5 piece endgame database and up will instantly know Payne's single corner draw is indeed a draw. The endgame database will never win or lose in a position it knows is a draw. I agree however, computer programs do have weaknesses, even though there isn't many. I have found they can struggle with complicated block problems that involve a lot of sacrifices. There was also a problem by Melvin Green which involved about 12 to 13 consecutive forced jumps that the computer was unable to solve, 24 pieces on the board and I am not even sure if the position was legal, though it still stumped the computer, even at 2 min per move.
Chexhero
 
Posts: 561
Joined: Sat Jan 08, 2011 10:11 pm
Location: PA

Re: Computer Program Weaknesses with Problems

Postby George Hay on Tue Sep 17, 2013 2:28 pm

Hi Bill, I did misunderstand about the computer conceding a draw. Wincheck will offer a draw in very simple draw situations after some repetition. A box will appear "Wincheck asks for draw Press OK to accept." In more advanced draws, such a Payne's Draw (at or close to the set-up position) it will accept a draw if offered by clicking the "Offer draw" box. If the computer accepts the draw a box will appear "Match Null !" The only drawback (no pun intended) is that the "Offer draw" box is not on the 2-D board, although it is possible to switch to a 3-D board to offer the draw!
http://alemanni.pagesperso-orange.fr/index.html
--George Hay
George Hay
 
Posts: 808
Joined: Sat Jan 01, 2011 7:41 am
Location: Grand Rapids, Michigan, USA

Re: Computer Program Weaknesses with Problems

Postby George Hay on Mon Sep 23, 2013 2:58 pm

Image

I am once again surprised going on Al Lyman's Checkerworld!
http://www.checkerworld.com/

There, on the home page, the above position is described as "Payne's Single Corner Draw."
I looked it up in my ECCO Print Edition of An Introduction To The Game Of Draughts by William Payne (1756).
The position is white to move and draw, a familiar theme. It is "First situation" in "Critical situations to draw Games."
The draw is given as 15 11 3-8, 11 7 8-12, 7 11 &c.

When I play against the cake computer program, I play 15 11 and cake replies 3-8. I then play 11 7 and cake replies 8-12
with a message: Cake claims a database draw.

This very simple draw is not the same a the standard position Payne's Draw, as positioned by Liam in his above post from
Tue Sep 17, 2013.

--George Hay
George Hay
 
Posts: 808
Joined: Sat Jan 01, 2011 7:41 am
Location: Grand Rapids, Michigan, USA

Re: Computer Program Weaknesses with Problems

Postby jimloy on Tue Jul 25, 2017 10:06 am

Concerning Payne's Draw, if I have the extra piece, whether I concede the draw or not depends on who I am playing. I may play on just to see if you have studied that ending. Programs play on, even when they know it's a draw, for similar practical reasons. If you can make the program show you the numerical evaluation of the position, you may see that the program does know it's a draw. Programming a checker program to offer draws, to accept draws, or to resign is very difficult, and most programmers have found it not worth the effort. By the way, the program may accept a draw if it is at some disadvantage.

Programs with an eight-piece database will evaluate all endings with eight or fewer pieces correctly. Instead of calculating the value of the position, the program just takes the value (win, loss, or draw) from a table (essentially) of all such positions. And some programs have ten-piece databases, or incomplete ten-piece databases (just the 5x5 endings).
jimloy
 
Posts: 428
Joined: Wed Dec 07, 2005 12:20 am
Location: Bozeman, Montana


Return to Positions

Who is online

Users browsing this forum: No registered users and 1 guest

cron
class=