End-game evaluation

[Volker Annuss]

* How do you handle the exchange ? especially if you classify
"being ahead" (i am thinking of constellations like: KRPP - KBNPP).
My feeling and my observations are, that the side with the rook
has the better play in many cases. :?:

My statistics show only a 32.1% score for the rook side.

[hgm]

You can also scale the complete evaluation (not only the material value), and store a flag in your material table when you like to do so.

That is what I do now. (And what Fruit does.)

If you think of opposite bishops for example, even with 2 connected passers ahead
it often will be draw (if they can be easily blocked for example).

This is also already in: I consider the two Bishops different piece types in the material index (so there are 4 Bishop states per side, rather than 3), so that I can put in different scaling flags for like and unlike Bishops. Fruit does not make this distinction in its material key, but it sets a flag for B vs B (+ suitable numbers of pawns) in the table contents to trigger explicit testing of the B colors in the evaluation.

* How do you handle the exchange ? especially if you classify
"being ahead" (i am thinking of constellations like: KRPP - KBNPP).
My feeling and my observations are, that the side with the rook
has the better play in many cases.

Conventional piece-value wisdom has it that the side with the two minors is ahead here. But with two Pawns, Fruit considers neither of those as drawish. At least not as more drawish than the regular additive eval score would suggest. Apart from unlike B with an imbalance of upto 2 Pawns, (but an arbitrary number of them), Fruit only discounts combinations with 0 or 1 Pawn.

In my simplified system I now discount (apart from the unlike Bishops case) with the following imbalances (meaning there can be more material than the mentioned if it is balanced, and neither side has two majors):

Code: Select all

1) one light piece ahead
  a) without Pawns and none of my light pieces has mating potential by itself (otherwise I would trade until that piece is left)
  b) with one Pawn and just two Knights (as he can sac my Pawn away with his minor)
2) exchange ahead
  a) only without Pawns (he cannot afford to sac anything for a Pawn)
3) equal light pieces
  a) without Pawns
  b) with one Pawn if none of my light pieces has mating potential by itself (he can sac a piece for my Pawn to get into (1a))
  c) with two Pawns if I have just a pair of Knights (he can afford to sac both minors for my Pawns).
4) exchange behind
  a) without Pawns (but I cannot be ahead in that case?)
  b) with one Pawn *
5) one light piece behind
  a) without Pawns (but again, we cannot be ahead here?)
  b) with one Pawn (he can sac one of his pieces, to convert to (3a)
  c) with two Pawns, when none of my light pieces has mating potential by itself (a piece-for-paw sac converts to (3b))
6) Rook vs two light pieces
  a) without Pawns
  b) with one Pawn (piece-for-pawn sac converts to (2a))
7) two light pieces vs Rook
  a) without Pawn, unless two of my light pieces have mating potential by themselves. (A Rook sac on a single piece with mating potential gives (1a))
  b) with one Pawn and two Knights (Rook sac for the Pawn destroys my mating potential)

The case marked by * has some exceptions. If there are other light pieces, he can sac one of them for the Pawn, to get to (7a). (The exception there is for Spartan Chess, and should thus also be made in (4b).) If there are no other pieces, he might have to sac the Rook for the Pawn, which he can still afford if my light piece has no mating potential.

KBBKN (and KBBKNP?) should be an exception to case (1). In my current system I can only make that exception by not discounting it at all, because the default multiplier for Pawnless material is 1/8. Fruit gives it 1/2 (which seems deserved by the fact that most wins would exceed the 50-move rule). So I might extend my system with some special codes to discount both sides by 1/2 irrespective of their number of Pawns.

I am not sure how to treat overwhelmingly won end-games that contain fortress draws. I guess they should still be discounted by default. Because when you are in a fortress, the search would stay their irrespective of search depth, while a lost position would at some depth find the winning conversion, and the score would be corrected accordingly. In end-games like KQKBN most won positions would be won at reasonably low depth. Perhaps these would also be good candidates for the unconditional 1/2 reduction.

[hgm]

I programmed all these exceptions into Spartacus, for FIDE Chess as well as Spartan, but it remains a lot of knowledge that has tobe added by hand to the engine. I would hate to have to repeat it fore very future variant I would add (e.g. all the Chess with Different Armies sub-variants). So Ihave been looking for a way to automate it. It seems that retrograde analysis (buildig sort of a 'material tablebase') could be a way to do that:

I start with the knowledge that some end-games are draw (for FIDE that could be KK, KBK, KNK and KNNK, but also KRKB and KRKN). Then I start to construct drawish predecessors, by adding pieces, accordig to the following rules:

1) I add single pieces or pairs of opposite color, because I assume most conversions willoccur by trading.
2) Available pieces are subdivided into 'classes'. For leapers these would be pawns, 'weak' pieces with 4 move targets, 'light' pieces with 8 move targets, 'medium' with 12 targets, etc. Sliders would be added to the classes depending on their empirical value (which must be an input to the program anyway): weak ~150, light ~300, medium ~450... So Bishops are light, Rooks are medium, or perhaps just above medium in a class of their own.
3) The added pairs do not have to be balanced: the side that seeks the draw (whose opponent will get a discount) can have a piece from a higher class, (or be the only one to receive a piece), as long as that doesn't put him in the lead with certainty. E.g. to KBK the pre-decessor KBNKR (by adding (N,R)) will be considered. Such an imbalanced predecessor will always be considered drawish, because the side that seeks the draw needs to sac a stronger piece for a weaker piece (her R for N), and because the piece is stronger it is assumed he can pick its target (the Rook will perpetually harrass the Knight). KBKP will also be an allowed predecessor of KBK according to this rule.
4) When a balanced pair is added (two pieces from the same class), it is not assumed the side seeking the draw can convert at will, but that the side going for the win is allowed to pick which equal trade he will allow. So the KBNKB predecessor of KBK (obtained by adding (N,B)) is only a candidate drawish end-game, and has to be verified by considering all equal trades (after selected sacrifices). In this case these are an (N,B) and a (B,B) trade, which convert to KBK and KNK respectively. Both are already marked as draw, so there is no escape for the strong side, and KBNKB is marked drawish.
5) If there is an equal trade to a non-drawish end-game (i.e. not yet marked), verification failed, and the predecessor is not marked. This would for instance happen in Spartan Chess, where there is an additional KLK marked as draw. Adding a balanced pair (C,B) would produce KLCKB, which has to be verified for the (C,B) and (L,B) equal trades. Now the first one is of course OK because it brings us back to the staring point, but the second would convert to KCK, which was not on the list (and will never be; C has mating potential). So KLCKB isnot drawish. Adding (C,R), however, would produce KLCKR, where the Rook now can select its victim, and will of course go for the C.
6) A natural limit will be put on the number pieces of any given type. I.e. if your material table does not consider compositions with 3 Knights, you cannot add N to the side that already has two. You can make additional rules that you will not discount end-games with too many majors, because the mating potential that floats around there is so large that it could be easily won without conversion.
7) In calculating if the side seeking the draw still could be behind, you consider Pawns of the opponent as 250, and its own Pawns as 100. So to KNNPKB, marked as drawish as predecessor of KNNK through a (P,B) sac, you will never add (P,Q), because even when P=250 NNPP will be only 1100, while QP is 1200. KNNPPKRB will be drawish (for both sides actually, as it is also a predecessor of KNPKR, which is again predecessor of KNKR, a primordial draw.)

When exceptions to the assumptions are known from tablebases (e.g. that KBBKN is a win, despite the fact it can only convert by trading to KBK), you can assign that end-game an initial non-drawish state,which cannot be overruled. But even without input only from 3and 4-men tablebases, you would already do a pretty good job.

[hgm]

I wrote some code to automatically identify drawish end-games by retrograde material analysis (for cases where white needs to be discounted):

Code: Select all

#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&#40;i=NTYP-1; i>=0; i--) for&#40;j=0; j<cur&#91;i&#93;; j++) printf&#40;"%c", pieceID&#91;i&#93;);
	printf&#40;"-");
	for&#40;i=NTYP-1; i>=0; i--)  for&#40;j=0; j<cur&#91;i+NTYP&#93;; j++) printf&#40;"%c", pieceID&#91;i+NTYP&#93;);
	printf&#40;"\n");
&#125;

int FindStatus&#40;char *cur&#41;
&#123;
	int i, j;
	for&#40;i=0; i<ptr; i++) &#123;
	    for&#40;j=0; j<2*NTYP; j++) if&#40;cur&#91;j&#93; != endgame&#91;i&#93;&#91;j&#93;) break;
	    if&#40;j == 2*NTYP&#41; return status&#91;i&#93;;
	&#125;
	return -1; // not found
&#125;

void build&#40;)
&#123;
	int i, j, k, m, wp, bp;
	char cur&#91;2*NTYP&#93;;

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

main&#40;)
&#123;
	build&#40;);
&#125;

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?

[Evert]

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?

I don't know, but you could try a 6-man tablebase (I've used http://www.k4it.de/index.php?topic=egtb&lang=en to browse tablebases, though I wouldn't check this by hand).

I've been thinking about endgame (and piece-value evaluation) in Sjaak as well, and it's not clear to me how to do it except by manual input (which I don't want to do). So far I've come up with different piece properties to look at, colour bound being an obvious one. Another one is the ability to perform a tempo-move, which I suspect is needed to be able to mate a lone king (hence why you can't with two knights), but I don't know how valid such generatlisations are (I'd need a tablebase to test). I haven't really pushed that further though.
Maybe monte-carlo analysis could help here too (maybe that's too slow)?

[Evert]

I had a quick look at a few positions from KRNNKR, which seemed to be generally won. The strategy seems to be to drive the defending king to the edge with the king, knights and rook, at which point mate-threats will force the loss of the black rook.

[hgm]

OK, I found .tbs files at Kirill's website, and they support your conclusion. Same with KQNNKQ and KNNNKN. So KNNK is really the exception, and any material you add makes the two-minor advantage decisive. No .tbs files for KRBNNKRR, of course... Fortunately such end-games never occur!

So I will add the test

Code: Select all

			if(imbalance - pVal[bp+NTYP] - cur[0] + cur[NTYP] > 4) continue; // more than minor ahead not drawish

It still generates 377 end-games.

[Rebel]

http://www.top-5000.nl/authors/rebel/ch ... tm#ENDGAME

Maybe this will help.

Just a 256 bytes table, perhaps it fits in your famous matchbox version

[Karlo Bala]

I wrote some code to automatically identify drawish end-games by retrograde material analysis (for cases where white needs to be discounted):

Code: Select all

#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&#40;i=NTYP-1; i>=0; i--) for&#40;j=0; j<cur&#91;i&#93;; j++) printf&#40;"%c", pieceID&#91;i&#93;);
	printf&#40;"-");
	for&#40;i=NTYP-1; i>=0; i--)  for&#40;j=0; j<cur&#91;i+NTYP&#93;; j++) printf&#40;"%c", pieceID&#91;i+NTYP&#93;);
	printf&#40;"\n");
&#125;

int FindStatus&#40;char *cur&#41;
&#123;
	int i, j;
	for&#40;i=0; i<ptr; i++) &#123;
	    for&#40;j=0; j<2*NTYP; j++) if&#40;cur&#91;j&#93; != endgame&#91;i&#93;&#91;j&#93;) break;
	    if&#40;j == 2*NTYP&#41; return status&#91;i&#93;;
	&#125;
	return -1; // not found
&#125;

void build&#40;)
&#123;
	int i, j, k, m, wp, bp;
	char cur&#91;2*NTYP&#93;;

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

main&#40;)
&#123;
	build&#40;);
&#125;

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?

I'm not sure that your logic is good. For example:
NNPP-nnpppp
NNPP-bnpppp
NNPP-bbpppp

It looks to me that all those endgames are lost for white. Did I miss something?

[hgm]

Well, it depends on the Pawns. A 7th-rank passer is worth more than two Pawns in their initial position. So with two connected 7th-rank passers the naive evaluation could still think white is ahead. The table only means to indicate that in such a case the imagined advantage is not much more than wishful thinking, and should be corrected towards draw score. Because it is compratively easy for black to sac his Knights for the two passers, and then you are left with a material combination without mating potential.

So the table lists allend-games where white could conceivably be considered ahead. It would not list things as KNNKQ, because no matter what the board position is, the naive evaluation would never think white is ahead. Of course it could be listed for black as drawish. I am not sure how KQKNN fares. For end-games with fortress draws it probably pays to have recognizers. KQKP also falls in this class. You could of course also rely on bitbases for that.