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
Computational Challenge ... Endgame Passes
Re: Computational Challenge ... Endgame Passes
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.guyhaw wrote: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)].
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
Re: Computational Challenge ... Endgame Passes
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.guyhaw wrote: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?
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
-
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: Computational Challenge ... Endgame Passes
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.
-
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
Re: Computational Challenge ... Endgame Passes
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
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
-
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: Computational Challenge ... Endgame Passes
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:
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.
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
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.
Last edited by h.g.muller on Thu Mar 20, 2008 4:09 pm, edited 2 times in total.
-
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: Computational Challenge ... Endgame Passes
Note I had to cut out part of the stats, or the forum software would not allow me to post it.
-
- Posts: 223
- Joined: Mon Feb 19, 2007 8:24 am
- Sign-up code: 0
- Location: Amsterdam
- Contact:
Re: Computational Challenge ... Endgame Passes
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.
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.
-
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
Re: Computational Challenge ... Endgame Passes
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
g