TalkChess.com

[H.G.Muller]

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.