From: pjj+@cs.cmu.edu (Peter Jansen)
Subject: Re: Pawnless endgames and databases
Organization: School of Computer Science, Carnegie Mellon
Date: Tue, 25 Aug 1992 22:02:27 GMT

[Another post that feel between the cracks a month ago...]

In article <1293@rand.mel.cocam.oz.au>, shaneb@auzodt3.mel.cocam.oz.au
(Shane Booth) wrote:

>A crude indicator of a pawnless endgame is whether it is generally
>won, lost or drawn.  We know K + R vs K and K + Q vs K + R are
>generally won for the stronger side, whereas K + R vs K + B is
>normally drawn.  Now we have databases for all 5 piece pawnless
>endings and several 6 piece endings (due to Lewis Stiller)
>containing statistics like the percentage of white to move and win
>positions or black to move and draw or win positions.  (I will
>assume White is always the stronger side).
>
>    It would be nice to classify the endgames into one of the three
>categories given above based on the database statistics alone.  The
>first idea that comes to mind is to say that if the percentage of
>white to move and win positions is larger than a certain figure,
>the ending is won, otherwise it is drawn.  This seems to work well
>for five piece endings, we can say that KRBKR is generally drawn,
>while KBBKN and KQKBB are generally won.  The drawn endings seem
>to have white to move and win percentages below 50%, while the won
>endings have figures above 75%.  But for six piece endings, I'm
>not so sure.  I would say that KRBKNN is generally won, since
>it has a 96% white to move and win percentage, and the maximin
>position seems so unfavourable to the KRB combination.  However,
>KQNKRR seems to have an 86% white to move and win percentage (I
>could be wrong here though), but the maximin position has the
>Black king (the one with the two rooks) on the edge of the board,
>so I would have to assume that it would be in general drawn with
>a more favourable Black king position.
>
>    So, we have an ending that is probably drawn but has a fairly
>high white to move and win percentage.  Would anyone suggest a
>better figure to use to make an overall assessment about pawnless
>endgames, or does the general concept of generally won endgames no
>longer apply for 6 piece and greater endgames?

>    Assuming that we can still talk about generally won endgames,
>I would imagine that using both White to move and win and the
>Black to move and draw or win figures could be useful to classify
>the endgame.  (However, I haven't seen the latter figures for any
>6 piece endgame).  But how much are these likely to get distorted
>upwards by each side having many positions where piece wins are
>possible immediately or very soon?  Of course, this problem must
>increase as the number of pieces on the board increase.
[...]

Nice analysis, and good observations!

I'd like to add the following points, which are based on a study
of random games.

1) Instead of 3 classes, I use 2 for each player: win and non-win.
   A game can be a win for both players, a win for one side or
   a win for neither.
   In a 'win', most positions are winning positions (for the winning
   side to move).

2) The distinction between 'win' and 'non-win' is very sharp:
   either almost all positions are winning (KQKR, for example),
   or a large number are not, in which case most of the winning
   positions are very shallow (e.g. KRKN). There are virtually no
   games 'in between'. This is true for random games with constant
   branching factor, which are surprisingly good models for simple
   pawn-less chess endgames.

3) Whether a game is a win or non-win is determined by the branching
   factor and the total number of immediate wins (*).
   When the branching factor is large, the number of immediate wins
   required for a 'won' endgame constitutes a rather large portion of
   the whole domain.
   So, as you seem to suggest, it might indeed make more sense to compute
   the proportions of winning and drawing positions without counting
   the number of immediate wins, which can (and will) be large even for
   games that are 'non-wins'.

4) Another way to distinguish the two categories of (pawnless) endgames
   is to look at the *density* of positions over depth (i.e. how many
   positions there are that require D moves to win, for each D).
   For a non-win the density is unimodal (with a sharp peak for lower
   depths). For a win, the density is roughly bi-modal: a large portion
   of winning positions are deep.

-----
(*) For better correspondence with the random-game model, this should
    include positions in which the King can be taken.


>-- 
>Shane Booth: shaneb@auzodt3.mel.cocam.oz.au
>Co-Cam Computer Group, Abbotsford, Vic.
>


-- Peter