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 

End-game evaluation
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 12776
Location: Amsterdam
PostPost subject: Re: End-game evaluation    Posted: Mon Nov 07, 2011 7:28 pm Reply to topic Reply with quote
I wrote some code to automatically identify drawish end-games by retrograde material analysis (for cases where white needs to be discounted):

Code:
#define MAX 1000
#define NTYP 5

int pVal[2*NTYP] = { 1,3,3,5,9, 1,3,3,5,9 };
int maxN[2*NTYP] = { 8,2,2,2,1, 8,2,2,2,1 };

char status[MAX];
char endgame[MAX][2*NTYP] = { // initialized with some elementary draws
  {0,0,0,0,0, 0,0,0,0,0}, // KK
  {0,1,0,0,0, 0,0,0,0,0}, // KNK
  {0,0,1,0,0, 0,0,0,0,0}, // KBK
  {0,0,0,1,0, 0,1,0,0,0}, // KRKN
  {0,0,0,1,0, 0,0,1,0,0}, // KRKB
  {0,2,0,0,0, 0,0,0,0,0}, // KNNK
};

int ptr = 6;

void Print(char *cur)
{
   static char pieceID[2*NTYP] = "PNBRQpnbrq";
   int i, j;
   for(i=NTYP-1; i>=0; i--) for(j=0; j<cur[i]; j++) printf("%c", pieceID[i]);
   printf("-");
   for(i=NTYP-1; i>=0; i--)  for(j=0; j<cur[i+NTYP]; j++) printf("%c", pieceID[i+NTYP]);
   printf("\n");
}

int FindStatus(char *cur)
{
   int i, j;
   for(i=0; i<ptr; i++) {
       for(j=0; j<2*NTYP; j++) if(cur[j] != endgame[i][j]) break;
       if(j == 2*NTYP) return status[i];
   }
   return -1; // not found
}

void build()
{
   int i, j, k, m, wp, bp;
   char cur[2*NTYP];

   for(i=0; i<ptr; i++) {
       if(status[i] == 0) { // drawish, predecessors not yet generated. Do it now
      int imbalance = 0;
      for(j=0; j<2*NTYP; j++) imbalance += (j<NTYP ? 1 : -1) * pVal[j] * (cur[j] = endgame[i][j]); // copy and sum
      for(wp=-1; wp<NTYP; wp++) { // choose white piece to add (-1 = nothing)
          if(wp >= 0 && endgame[i][wp] >= maxN[wp]) continue; // already saturated for this piece type
          if(wp >= 0) cur[wp]++, imbalance += pVal[wp]; // add white piece
          if(cur[4]+2*cur[3] <= 2 && cur[0] < 3) // with more majors than Q or RR, or more than 2 Pawns, opponent never has easy draw
          for(bp=0; bp<NTYP; bp++) {
         if(endgame[i][bp+NTYP] >= maxN[bp+NTYP]) continue; // already saturated
         // we now have identified a piece pair (wp,bp) we could add to create predecessor
         if(pVal[bp+NTYP] < pVal[wp]) continue; // black piece must at least equal for black to force trade
         if(wp==0 && bp==0) continue;           // Pawn trade can in general not be forced
         if(imbalance - pVal[bp+NTYP] + cur[0]*3/2 <= 0) continue; // white cannot possibly be ahead
         // found predecessor that could be drawish (for white)
         cur[bp+NTYP]++;
         if(FindStatus(cur) == 0) goto escape; // this predecessor was already found before, no need to do it again
         if(wp >= 0 && pVal[bp+NTYP] == pVal[wp]) {       // we added equal pair: white can pick how he trades
             for(k=0; k<NTYP; k++) {
            if(cur[k] == 0) continue;     // white doesn't have this
            for(m=0; m<NTYP; m++) {
                int stat;
                if(cur[m+NTYP] == 0) continue; // black doesn't have this
                if(k==0 && m==0) continue;     // Pawn trade can in general not be forced
                if(pVal[k] < pVal[m+NTYP]) continue; // white can only trade/sac stronger or equal piece
                cur[k]--; cur[m+NTYP]--;  // trade
                stat = FindStatus(cur);
                cur[k]++; cur[m+NTYP]++;  // restore
                if(stat < 0) goto escape; // white trade not listed as drawish
            }
             }
         }
         // white could not find any trade into non-drawish, or black can sac into drawish
         for(k=0; k<2*NTYP; k++) endgame[ptr][k] = cur[k];
         status[ptr++] = 0;
         Print(cur);
         if(ptr >= MAX) printf("table overflow\n"), exit(0);
            escape:
         cur[bp+NTYP]--;
          }
          if(wp >= 0) cur[wp]--, imbalance -= pVal[wp]; // remove white piece
      }
       }
   }
}

main()
{
   build();
}


I have some doubt as to the validity of the output, in partcular w.r.t. the treatment of the N-pair. One of the assumptions going into the analysis is that you can add a minor, R or Q on each side of a drawish end-game without disturbing the draw. This based on the observation that R+minor vs R and Q+minor vs Q are still draws.

But it might not be true for NN. Does anyone happen to know if KRNNKR and KQNNKQ are still drawish, i.e. if the threat of trading R or Q is a sufficiently powerful defense plan to secure a draw? And how is it with KBNNKB? Can white force N vs B trade and then win KBNK? (With unlike Bishops black can hardly avoid that, I guess.)

So how should I fix this? Never declare an end-game where you are two minors ahead drawish, unless it is really NN and no additional piece material at all? I guess KBNNKR is still a draw (black perpetually harrassing the B for a RxB sac), although you are technically ahead more than a minor (2 minors > R). So perhaps I should put the limit as being above +4. Or is this a special case, and is KRBNNKRRand KQBNNKQR hopelessly lost to black?
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
End-game evaluation H.G.Muller Tue Oct 04, 2011 11:44 am
      Re: End-game evaluation Evert Glebbeek Tue Oct 04, 2011 1:02 pm
            Re: End-game evaluation H.G.Muller Tue Oct 04, 2011 2:20 pm
      Re: End-game evaluation Oliver Uwira Tue Oct 04, 2011 1:59 pm
      Re: End-game evaluation Jon Dart Tue Oct 04, 2011 2:10 pm
            Re: End-game evaluation Jon Dart Tue Oct 04, 2011 2:13 pm
      Re: End-game evaluation Kevin Hearn Tue Oct 04, 2011 8:19 pm
            Re: End-game evaluation Pawel Koziol Wed Oct 05, 2011 10:46 am
      Re: End-game evaluation H.G.Muller Mon Oct 10, 2011 8:09 am
            Re: End-game evaluation H.G.Muller Mon Oct 10, 2011 9:00 am
                  Re: End-game evaluation Evert Glebbeek Mon Oct 10, 2011 1:04 pm
                  Re: End-game evaluation Ed Schroder Mon Nov 07, 2011 10:15 pm
            Re: End-game evaluation H.G.Muller Wed Oct 19, 2011 10:16 am
                  Re: End-game evaluation Michael Hoffmann Wed Oct 19, 2011 11:48 am
                        Re: End-game evaluation H.G.Muller Wed Oct 19, 2011 1:24 pm
                              Re: End-game evaluation Michael Hoffmann Wed Oct 19, 2011 2:53 pm
                                    Re: End-game evaluation Volker Annuss Wed Oct 19, 2011 4:53 pm
                                    Re: End-game evaluation H.G.Muller Wed Oct 19, 2011 4:54 pm
                                          Re: End-game evaluation H.G.Muller Sat Oct 22, 2011 5:29 pm
                                                Re: End-game evaluation H.G.Muller Mon Nov 07, 2011 7:28 pm
                                                      Re: End-game evaluation Evert Glebbeek Mon Nov 07, 2011 8:33 pm
                                                            Re: End-game evaluation Evert Glebbeek Mon Nov 07, 2011 9:02 pm
                                                                  Re: End-game evaluation H.G.Muller Mon Nov 07, 2011 9:40 pm
                                                            Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 11:16 am
                                                                  Re: End-game evaluation Evert Glebbeek Tue Nov 08, 2011 5:50 pm
                                                                        Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 8:16 pm
                                                                              Re: End-game evaluation Evert Glebbeek Tue Nov 08, 2011 8:52 pm
                                                                                    Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 10:14 pm
                                                      Re: End-game evaluation Karlo Bala Jr. Mon Nov 07, 2011 11:59 pm
                                                            Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 7:30 am
                                                                  Re: End-game evaluation Kevin Hearn Tue Nov 08, 2011 9:58 am
                                                                        Re: End-game evaluation H.G.Muller Tue Nov 08, 2011 12:40 pm
                                                                              Re: End-game evaluation Evert Glebbeek Tue Nov 08, 2011 5:53 pm
      Re: End-game evaluation Mark Lefler Mon Oct 10, 2011 4:08 pm
            Re: End-game evaluation H.G.Muller Mon Oct 10, 2011 9:09 pm
                  Re: End-game evaluation H.G.Muller Mon Oct 10, 2011 9:58 pm
                  Re: End-game evaluation H.G.Muller Tue Oct 11, 2011 8:50 am
                        Re: End-game evaluation H.G.Muller Tue Oct 18, 2011 6:36 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