ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

How to implement KPK ?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Sven Schüle



Joined: 15 May 2008
Posts: 3445
Location: Berlin, Germany

PostPost subject: Re: How to implement KPK ?    Posted: Sun Mar 31, 2013 9:02 am Reply to topic Reply with quote

hgm wrote:
Well, it depends on the depth. I don't think it will be possible without King term if you restrict the search depth to 1 ply, for instance. In situations other than a simple rule-of-squares race, you need more King moves than Pawn moves to win against best defence. E.g. with Ke4, Pe3 vs Ke6 (btm) after Kd6 both Kf5 and Kf4 are winning, but only Kf5 is progress. So if because of move-gen ordering it happens to prefer Kf4, it would never make progress. Relying on rep-draw code to force progress is a tricky thing, because it also often backfires; In the given example you might think that the second time it would play Kf5 because it now recognizes Kf4 as a draw, but in fact there won't be a second time, because after Kd6, Kf4, Ke6 the only winning move Ke4 is now tainted as rep-draw, so it will accept that the position is drawn now, and pick a random drawing move.

Restricting the search to 1 ply might seem a bit extreme, but it is of course exactly what you do if you want to build a recognizer for this end-game.

In my view the typical application of a KPK recognizer that uses a bitbase is the normal search which also has repetition detection. None of these problems should occur there: in the given example the search will prefer Kf5 after 4 iterations.

Iteration 1 might return 1.Kf4 as PV move, as you say.
Iteration 2: 1.Kf4 Ke6 (win).
Iteration 3: 1.Kf4 Ke6 2.Ke4 (win).
Iteration 4: 1.Kf4 Ke6 2.Ke4 Kd6 (rep draw). But now it still finds 1.Kf5 (e.g. Ke7 2.Ke5 Kd7) as new PV at the root.

Restricting the search to 1 ply is not "typical" in my eyes. A perfect recognizer that you can use in a 1-ply search would be based on a DTM tablebase, not a bitbase, so that you always select among those moves which have the shortest path to mate. Using a bitbase together with a complex evaluation does not make much sense to me.

In many practical cases where a KPK position is reached within a deeper search of a "bigger" endgame you will not need the complex evaluation part at all since the "win" or "draw" information itself will already lead to a cutoff.

Sven
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
How to implement KPK ? Chan Rasjid Thu Mar 21, 2013 3:43 am
      Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 7:46 am
            Re: How to implement KPK ? Chan Rasjid Thu Mar 21, 2013 8:27 am
                  Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 10:07 am
                        Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 10:33 am
                        Re: How to implement KPK ? Chan Rasjid Thu Mar 21, 2013 6:10 pm
                              Re: How to implement KPK ? Don Dailey Tue Apr 02, 2013 6:56 pm
            Re: How to implement KPK ? Lucas Braesch Thu Mar 21, 2013 11:03 am
                  Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 11:52 am
                        Re: How to implement KPK ? Lucas Braesch Thu Mar 21, 2013 12:04 pm
                        Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 6:36 pm
                              Re: How to implement KPK ? H.G.Muller Thu Mar 21, 2013 9:00 pm
                              Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 8:15 am
                                    Re: How to implement KPK ? Evert Glebbeek Sat Mar 30, 2013 8:42 am
                                          Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 12:12 pm
                                                Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 12:20 pm
                                                      Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 12:42 pm
                                                            Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 2:03 pm
                                                                  Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 6:29 pm
                                                      Re: How to implement KPK ? Wylie Garvin Sat Mar 30, 2013 12:50 pm
                                                            Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 1:53 pm
                                                Re: How to implement KPK ? Evert Glebbeek Sat Mar 30, 2013 2:03 pm
                                                      Re: How to implement KPK ? H.G.Muller Sat Mar 30, 2013 2:26 pm
                                                            Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 6:38 pm
                                                                  Re: How to implement KPK ? H.G.Muller Sat Mar 30, 2013 8:13 pm
                                                                        Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 8:58 pm
                                                                              Re: How to implement KPK ? H.G.Muller Sat Mar 30, 2013 10:58 pm
                                                                                    Re: How to implement KPK ? Sven Schüle Sat Mar 30, 2013 11:51 pm
                                                                                          Re: How to implement KPK ? H.G.Muller Sun Mar 31, 2013 7:35 am
                                                                                          Re: How to implement KPK ? Sven Schüle Sun Mar 31, 2013 9:02 am
                                                                                          Re: How to implement KPK ? H.G.Muller Sun Mar 31, 2013 9:09 am
                                                                                          Re: How to implement KPK ? Sven Schüle Sun Mar 31, 2013 9:13 am
                                                                                          Re: How to implement KPK ? Steven Edwards Mon May 13, 2013 2:14 am
                                                                                          Re: How to implement KPK ? Don Dailey Mon May 13, 2013 2:20 am
                                          Re: How to implement KPK ? Chan Rasjid Sat Mar 30, 2013 12:18 pm
                                    Re: How to implement KPK ? H.G.Muller Sat Mar 30, 2013 9:08 am
      Re: How to implement KPK ? Chan Rasjid Sun May 12, 2013 10:27 pm
            Re: How to implement KPK ? Ronald de Man Sun May 12, 2013 11:11 pm
                  Re: How to implement KPK ? Chan Rasjid Mon May 13, 2013 7:39 am
            Re: How to implement KPK ? Don Dailey Mon May 13, 2013 2:14 am
            Re: How to implement KPK ? Steven Edwards Tue May 14, 2013 7:19 am
                  Re: How to implement KPK ? Chan Rasjid Tue May 14, 2013 2:45 pm
                        Re: How to implement KPK ? Chan Rasjid Tue May 14, 2013 2:50 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
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




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads