TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Sven Schüle

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

Post subject: Re: How to implement KPK ?    Posted: Sun Mar 31, 2013 9:02 am

 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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Chan Rasjid Thu Mar 21, 2013 3:43 am
H.G.Muller Thu Mar 21, 2013 7:46 am
Chan Rasjid Thu Mar 21, 2013 8:27 am
H.G.Muller Thu Mar 21, 2013 10:07 am
H.G.Muller Thu Mar 21, 2013 10:33 am
Chan Rasjid Thu Mar 21, 2013 6:10 pm
Don Dailey Tue Apr 02, 2013 6:56 pm
Lucas Braesch Thu Mar 21, 2013 11:03 am
H.G.Muller Thu Mar 21, 2013 11:52 am
Lucas Braesch Thu Mar 21, 2013 12:04 pm
H.G.Muller Thu Mar 21, 2013 6:36 pm
H.G.Muller Thu Mar 21, 2013 9:00 pm
Chan Rasjid Sat Mar 30, 2013 8:15 am
Evert Glebbeek Sat Mar 30, 2013 8:42 am
Sven Schüle Sat Mar 30, 2013 12:12 pm
Chan Rasjid Sat Mar 30, 2013 12:20 pm
Sven Schüle Sat Mar 30, 2013 12:42 pm
Chan Rasjid Sat Mar 30, 2013 2:03 pm
Sven Schüle Sat Mar 30, 2013 6:29 pm
Wylie Garvin Sat Mar 30, 2013 12:50 pm
Chan Rasjid Sat Mar 30, 2013 1:53 pm
Evert Glebbeek Sat Mar 30, 2013 2:03 pm
H.G.Muller Sat Mar 30, 2013 2:26 pm
Sven Schüle Sat Mar 30, 2013 6:38 pm
H.G.Muller Sat Mar 30, 2013 8:13 pm
Sven Schüle Sat Mar 30, 2013 8:58 pm
H.G.Muller Sat Mar 30, 2013 10:58 pm
Sven Schüle Sat Mar 30, 2013 11:51 pm
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
H.G.Muller Sun Mar 31, 2013 9:09 am
Sven Schüle Sun Mar 31, 2013 9:13 am
Steven Edwards Mon May 13, 2013 2:14 am
Don Dailey Mon May 13, 2013 2:20 am
Chan Rasjid Sat Mar 30, 2013 12:18 pm
H.G.Muller Sat Mar 30, 2013 9:08 am
Chan Rasjid Sun May 12, 2013 10:27 pm
Ronald de Man Sun May 12, 2013 11:11 pm
Chan Rasjid Mon May 13, 2013 7:39 am
Don Dailey Mon May 13, 2013 2:14 am
Steven Edwards Tue May 14, 2013 7:19 am
Chan Rasjid Tue May 14, 2013 2:45 pm
Chan Rasjid Tue May 14, 2013 2:50 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