TalkChess.com
Hosted by Your Move Chess & Games

Author Message
H.G.Muller

Joined: 10 Mar 2006
Posts: 21881
Location: Amsterdam

Post subject: Re: How to implement KPK ?    Posted: Thu Mar 21, 2013 6:36 pm

I see KPK quite often.

Anyway, to further the public-domain cause, the following code actually runs, and prints some numbers that seem to make sense (like the number of stalemates, which matches what I calculated by hand). I even put in the initial double-push, which is important for rule-of-squares situations.

Btw, this is the dumb algorithm, which does not use any unmoves. It just attempts regular moving from all not-yet-decided positions, to look for a move to a won position for white, and to a non-lost position for black.

 Code: /* Public-domain KPK bitbase code by H.G. Muller */ #define WTM 0 #define BTM 1 char dtc[2][64][64][64]; // 512 KB char bitbase[2*64*64*3]; char steps[] = {1, -1, 16, -16, 15, -15, 17, -17}; // 0x88 King steps void Init () { /* 3 = bK captured, 2 = can capture bK, 1 = won, 0 = undecided, -1 = broken or wK captured */   int wk, bk, p;   for(wk=0; wk<64; wk++) for(p=0; p<64; p++) for(bk=0; bk<64; bk++) {     if(bk == wk) dtc[BTM][wk][p][bk] = 3, dtc[WTM][wk][p][bk] = -1; else     if(wk == p) dtc[BTM][wk][p][bk] = dtc[WTM][wk][p][bk] = -1; else     if(bk ==  p) dtc[BTM][wk][p][bk] = -3; else // with WTM black just captured P     if(p >= 56) dtc[WTM][wk][p][bk] = 1; // promoted and on move = win   } } void Pass (int stm, int first, int def, int esc) {   int wk, bk, p, d;   for(wk=0; wk<64; wk++) for(p=0; p<64; p++) for(bk=0; bk<64; bk++) {     int k = stm == WTM ? wk : bk;     int O88 = (k & 070) + k; // 0x88 square number of King     if(dtc[stm][wk][p][bk]) continue; // already decided     dtc[stm][wk][p][bk] = def;  // assume lost if btm, undecided if wtm     if(bk != p && stm == WTM) { // pawn not captured, so can move       if(p+8 != bk && (dtc[BTM][wk][p+8 ][bk] > first || p < 16 &&          p+16 != bk && dtc[BTM][wk][p+16][bk] > first))  { dtc[WTM][wk][p][bk] = esc; continue; }       if(p+7 == bk && (p & 7) != 0)  { dtc[WTM][wk][p][bk] = 2; continue; }       if(p+9 == bk && (p & 7) != 7)  { dtc[WTM][wk][p][bk] = 2; continue; }     }     for(d=0; d<8; d++) {       int to = O88 + steps[d];       if(to & 0x88) continue; // off board       to -= to>>1 & 070;       if(stm == WTM ? dtc[BTM][to][p][bk] > first : dtc[WTM][wk][p][to] <= first)       { dtc[stm][wk][p][bk] = esc; break; }     }   } } void Pack () {   int wk, bk, p, i;   for(wk=0; wk<64; wk++) for(p=8; p<56; p+=2) for(bk=0; bk<64; bk++) { // calculate probe address and bit     int index = (bk >> 3) + 8*wk + 8*64*(p-8>>1);     bitbase[2*index] |= (dtc[WTM][wk][p][bk] > 0) << (bk & 7);     bitbase[2*index+1] |= (dtc[BTM][wk][p][bk] > 0) << (bk & 7);   } } void Build () {   int i;   Init();   Pass(WTM, 2, 0, 2); Pass(BTM, 1, -2, 0); // calculate King captures and stalemates   for(i=0; i<25; i++) // won't take more than 25 moves     Pass(WTM, 0, 0, 1), Pass(BTM, 0, 1, 0);   Pack(); }

Printing the stats of the positions with the Pawn on rank 2-7 afterwards gives:

 Code: white to move: 124960+, 41044=, 6096-, 0 stalemate, 24508 K-capture black to move: 97604+, 89866=, 6066-, 18 stalemate, 0 K-capture

where + means won to white, = means draw, - illegal by white's fault or black stalemated. (White stalemates are not separately identified, they count with the other draws.)
 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
Re: How to implement KPK ? 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
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