Computational Challenge ... Endgame Passes

[guyhaw]

Let E be some endgame in chess. Let 'P' be a set of positions where (say) White has a win.
Let 'DP' be the set of positions that are currently wins for White but would be draws if all the positions in 'P' were defined as draws [in a Chess Variant called Chess(P)]. DP is a set of 'dependant positions' - 'dependant' because their wins depend on some position(s) in P being theoretical wins.

Of course, P =< DP for all P, and so the 'Pass Factor' |DP|/|P| >= 1.

Now for the computational challenges. Given an endgame 'E', what set of positions 'P' maximises the Pass Factor |DP|/|P|, and what endgame 'E' has the greatest Pass Factor?

guy

[jkominek]

Let 'DP' be the set of positions that are currently wins for White but would be draws if all the positions in 'P' were defined as draws [in a Chess Variant called Chess(P)].

How about: let 'SC' be the set of positions that are currently draws for White but would be wins if all the positions in 'P' were defined as wins.

SC = stalemate captures

I wonder how the tablebases would change - and chess strategy - were the game to once again be played with deadly stalemate? It would make the passed pawn itself a more potent combatant, I believe, rather than merely a potentially powerful piece, to be gently nursed across the field.

john

[jkominek]

Now for the computational challenges. Given an endgame 'E', what set of positions 'P' maximises the Pass Factor |DP|/|P|, and what endgame 'E' has the greatest Pass Factor?

Oh yes, to your question then. While I am not a CS theoretician, this sounds like a variant of the minimal set coverage question. Which is an NP complete problem as far as I can recall. You won't find a sub-exponential algorithm for it.

But a heuristic search may find an approximate solution.
1. scan for all mate-in-1 positions. Call this set S1.
2. select the subset of S1 s.t. only one move leads to mate-in-0 (all other moves are value shedding). Call this S11.
3. separately: for each element in S11, set the successor position from mi0 to drawn.
4. apply retrograde analysis to compute the modified endgame table (having one terminal node altered at the start).
5. count the number of wins. subtract this from the original number wins to get |DP|. Since |P|=1, the pass ratio = |DP|.
6. select the position with the highest ratio (or randomly select one if there is a tie).
7. repeat, incrementally adding positions one at a time to P. This is so-called "greedy" optimization. It is known to be suboptimal.
Comment: is S11 is empty then go for positions that have two mi0 successors, S12, etc.

This algorithm is O(N) in the size of S1. But each iteration is humongous!

john

[h.g.muller]

Just an intuitive guess: If I could pick both the end-game and the positions I would pick KBNK, and declare all checkmates in the corner as draw. I expect that to turn this generally won endgame into a generally drawn one, producing a huge factor.

[guyhaw]

I like the KBNK idea.
More generally, if P = all positions with DTC(onversion) = m, then wins with DTC > m must have their winning lines passing through P.
So we could look for endgames with some significantly small set of positions for some value of DTC.
For KBNK, the smallest number of positions is for "Black lost in 2" ... 37. So the whole edifice of 'White wins in dtc > 2' and 'Black loses in dtc > 2' rests on these positions.
So, KBNK, P = "Black loses in 2" is our 'leader in the clubhouse'. Thank you.
g

[h.g.muller]

I encountered an extreme DTC bottleneck in one of the 5-men fairy end-games I calculated: King + Bishop + Commoner against King + Nightrider. The stats for this end-game are:

Code: Select all

KBM_KH.dtc

WON.wtm        879,668,832
K capture      278,156,480
imm.conv.      469,199,456
other          410,469,376
            0  731,929,356

            0   65,626,988
            1      896,664
            2      268,028
            3      155,080
            4      122,900
            5      124,704
            6      120,892
            7      123,168
            8      121,744
            9      118,088
           10      117,920
           11      112,816
           12      109,440
           13      100,492
           14       99,780
           15       95,136
           16       96,992
           17       97,340
           18       99,396
           19      107,572
           20      119,656
           21      131,564
           22      137,048
           23      142,068
           24      143,928
           25      144,848
           26      133,756
           27      123,152
           28      114,728
           29      112,080
           30      110,368
           31      108,136
           32       98,352
           33       90,064
           34       81,288
           35       66,320
           36       53,976
           37       51,912
           38       53,576
           39       56,728
           40       57,280
           41       60,248
           42       64,000
           43       63,312
           44       62,208
           45       52,440
           46       46,144
           47       44,448
           48       41,176
           49       36,188
           50       30,296
           51       28,160
           52       23,104
           53       16,952
           54       13,072
           55        8,512
           56        6,404
           57        5,392
           58        4,320
           59        4,136
           60        3,584
           61        3,576
           62        2,904
           63        2,752
           64        2,232
           65        2,824
           66        4,320
           67        4,608
           68        5,256
           69        5,632
           70        6,512
           71        8,080
           72       10,032
          100       35,072
          120      185,528
          140       72,248
          160       43,168
          180       44,560
          200       84,956
          220      499,428
          240    1,210,036
          260    2,516,044
          280    8,922,756
          300      288,592
          301      117,912
          302       41,816
          303       16,256
          304        5,296
          305        1,272
          306          216
          307           40

WON.btm        347,224,148
stalemate              560
W check        143,965,980
LEGAL          770,975,460
TOTAL          914,941,440

As can be seen, 96% of all pseudo-legal positions is won with white to move, so this is a generally won end-game. As usual, the number of positions won for white with btm is much smaller than this (only 38%). In the other positions white is in check (illegal) or loses its Commoner through a trivial tactic (e.g. a Nightrider fork or skewer, leading to loss or trade), or has a hanging Bishop. But the wtm positions have a similar number of trivial wins, where a black piece was hanging, or the position was outright illegal (black was in check).

Of the positions that white can win with btm, about 7% are checkmates or immediate conversions (e.g. where black is in check, and its Nightrider is hanging). Almost none of those can be forced: the number of conversion-in-1 positions is 80 times lower.

The remarkable thing about this end-game is that there are only 2,232 DTC=64 positions, while 98% of the non-trivial wins with btm (i.e. DTC >= 1) has DTC > 64. The longest win has DTC=307, while the average DTC (of the non-trivially won btm positions) is 264.5 (220 if you count the trivial wins).

The DTC=64 positions thus form a very spectacular bottleneck; the number of positions that they would cut off from a win is 140,000 times their own number for btm positions, and about as much wtm positions on top of it.

[h.g.muller]

Note I had to cut out part of the stats, or the forum software would not allow me to post it.

[h.g.muller]

To get back to KBNK: I still think my original idea of deleting checkmates would give a larger pass factor than deleting the DTM=2 poitions. Although there are more checkmates than DTM=2, most of them are mates on the edge or in the wrong corner, and such mates cannot be forced even from the DTM=1.btm level (similar to the mates in KNNK). There are only 80 mates that can be forced (10 irreducible positions). Without those 80, all DTM>0 positions would turn into draws. There are about 16M x 2 of those. This would give a pass factor 400,000.

This might even be larger than the pass factor through the DTC=64 positions of the KBMKH end-game. To know that for sure, I would have to calculate that factor more precisely. (Especially the WTM positions.) Of course it might happen there too tht not all of the DTC=64 positions have to be deleted as wins, because some of them are unforcible from the DTC=65 level. Or that the optimal barrier is not along constant DTC.

[guyhaw]

hgm - I'm sure you are right - but it's not obvious how to organise the inveestigation of reducing the set of positions to increase the 'dependancy factor'.
g