KPK bitbase

[lucasart]

Why not just generate the bitbase by retrograde analysis?

It's exactly what I'm doing!

I managed to get to that point, after which any further iteration doesn't resolve any more unknown positions

Code: Select all

ILLEGAL: 30932
UNKNOWN: 16717
DRAW: 37677
WIN: 111282

I already have reached the exact number of wins, but some draws have not been detected (unknown i/o draw).
I need to look into these unknown positions, and see what's missing in my static rules to initialize the process correctly.

I'm almost there! Going to bed now...

[hgm]

It is pointless to have initial rules for draws. In retrograde analysis all positions that remain unknown after you propagated the wins and losses are draws. Typically you would need very many rules to define all draws that you can be forced to, as in most draws you cannot force anything at all. They are just positions where you cannot make progress. I.e. they are a group of positions that are bounded by obvious draws (like in KPK stalemates and loss of the Pawn), but within which you can roam around freely.

E.g. did your draw rules capture distant oppositions (Ke2, Pe2, Ke7, btm)? Black cannot force the white King to approach him, and take regular opposition, or force white to advance his Pawn, so he can step in front of it. There is no reason why drawn positions can be forced from other drawn positions. But from any win-in-N you should be able to force a win-in-(N-1), or it would not have been a win-in-N. Therefore all wins are retrogradely reachable from win-in-0 = checkmates. For draws there is no such rule.

[tpetzke]

Unknown: 0
Invalid: 30932
Win: 62642
Loss: 49052
Draw: 53982

Hard to imagine those positions where white loses against a lone black king anyway.

Thomas...

[hgm]

That is because they are in reality positions where black loses when he has the move.

[sje]

Code: Select all

Summary for TB/KPK.tbw (WTM):

Score        Sp        Sp/unfold Tp        Tp/unfold Ap        Ap/unfold
------------ --------- --------- --------- --------- --------- ---------
Even             19184     38368      1338      2676     20522     41044
MateIn28             3         6         0         0         3         6
MateIn27             7        14         0         0         7        14
MateIn26            19        38         0         0        19        38
MateIn25            64       128         0         0        64       128
MateIn24           144       288         0         0       144       288
MateIn23           343       686         0         0       343       686
MateIn22           562      1124         0         0       562      1124
MateIn21           606      1212         0         0       606      1212
MateIn20           558      1116         0         0       558      1116
MateIn19           658      1316         0         0       658      1316
MateIn18           871      1742         0         0       871      1742
MateIn17          1066      2132         0         0      1066      2132
MateIn16          1154      2308         0         0      1154      2308
MateIn15          1065      2130         0         0      1065      2130
MateIn14          3829      7658         0         0      3829      7658
MateIn13          6719     13438         0         0      6719     13438
MateIn12          8178     16356         0         0      8178     16356
MateIn11          8601     17202         0         0      8601     17202
MateIn10          8395     16790         0         0      8395     16790
MateIn9           7541     15082         0         0      7541     15082
MateIn8           5647     11294         0         0      5647     11294
MateIn7           3121      6242         0         0      3121      6242
MateIn6           1636      3272         0         0      1636      3272
MateIn5            915      1830         0         0       915      1830
MateIn4            422       844         0         0       422       844
MateIn3            219       438         0         0       219       438
MateIn2             97       194         0         0        97       194
MateIn1             40        80         0         0        40        80
Bust             27704     55408     20366     40732     48070     96140

Entry count: 131072
Entry count (unfolded): 262144

Longest mate score (WTM): MateIn28
Sample WTM longest mating position: 8/8/8/6k1/8/8/1P4K1/8 w - - 0 1

Optimal move sequence from the above WTM longest mating position:

1. Kg3 Kf5 2. Kf3 Ke5 3. Ke3 Kd5 4. Kd3 Kc5 5. Kc3 Kb5 6. Kb3 Ka5 {Ka6 Kc5 Kc6}
7. Kc4 Kb6 8. Kb4 Ka6 {Ka7 Kc6 Kc7} 9. Kc5 Kb7 10. Kb5 Ka7 11. Kc6 Ka8 12. Kb6
{b4} Kb8 13. b3 {b4} Ka8 {Kc8} 14. b4 Kb8 15. b5 Kc8 16. Ka7 Kc7 {Kd7 Kd8} 17.
b6+ Kc6 {Kd6 Kd7} 18. b7 Kd5 19. Kb6 {b8=Q} Kd4 {Ke4 Ke5 Ke6} 20. Kc6 {b8=Q}
Kc3 {Kc4 Kd3 Ke3 Ke4 Ke5} 21. Kd5 {b8=Q} Kb4 {Kd2 Kd3} 22. Kd4 {b8=Q+} Kb5 23.
b8=Q+ Kc6 24. Qd8 Kb5 25. Qc7 {Qd6 Qd7+ Qf6} Ka4 {Ka6 Kb4} 26. Kc4 {Qb6 Qb7
Qb8} Ka3 27. Qh2 Ka4 28. Qa2#

No WTM non-transition lose positions exist.

Summary for TB/KPK.tbb (BTM):

Score        Sp        Sp/unfold Tp        Tp/unfold Ap        Ap/unfold
------------ --------- --------- --------- --------- --------- ---------
Even             47876     95752       996      1992     48872     97744
Bust             12690     25380      7724     15448     20414     40828
Checkmated           0         0        42        84        42        84
LoseIn1              9        18        55       110        64       128
LoseIn2             23        46       140       280       163       326
LoseIn3             64       128       342       684       406       812
LoseIn4            153       306       668      1336       821      1642
LoseIn5            332       664      1366      2732      1698      3396
LoseIn6            812      1624      2312      4624      3124      6248
LoseIn7           2089      4178      3752      7504      5841     11682
LoseIn8           4226      8452      3377      6754      7603     15206
LoseIn9           7180     14360       930      1860      8110     16220
LoseIn10          7857     15714         0         0      7857     15714
LoseIn11          7215     14430         0         0      7215     14430
LoseIn12          5843     11686         0         0      5843     11686
LoseIn13          4185      8370         0         0      4185      8370
LoseIn14          2501      5002         0         0      2501      5002
LoseIn15          1026      2052         0         0      1026      2052
LoseIn16          1194      2388         0         0      1194      2388
LoseIn17           902      1804         0         0       902      1804
LoseIn18           711      1422         0         0       711      1422
LoseIn19           597      1194         0         0       597      1194
LoseIn20           436       872         0         0       436       872
LoseIn21           565      1130         0         0       565      1130
LoseIn22           430       860         0         0       430       860
LoseIn23           292       584         0         0       292       584
LoseIn24           109       218         0         0       109       218
LoseIn25            31        62         0         0        31        62
LoseIn26            14        28         0         0        14        28
LoseIn27             4         8         0         0         4         8
LoseIn28             2         4         0         0         2         4

Entry count: 131072
Entry count (unfolded): 262144

No BTM non-transition mate positions exist.

Longest lose score (BTM): LoseIn28
Sample BTM longest losing position: 8/8/8/7k/8/7K/1P6/8 b - - 0 1

Optimal move sequence from the above BTM longest losing position:

1... Kg5 2. Kg3 Kf5 3. Kf3 Ke5 4. Ke3 Kd5 5. Kd3 Kc5 6. Kc3 Kb5 7. Kb3 Ka5 {Ka6
Kc5 Kc6} 8. Kc4 Kb6 9. Kb4 Ka6 {Ka7 Kc6 Kc7} 10. Kc5 Kb7 11. Kb5 Ka7 12. Kc6
Ka8 13. Kb6 {b4} Kb8 14. b3 {b4} Ka8 {Kc8} 15. b4 Kb8 16. b5 Kc8 17. Ka7 Kc7
{Kd7 Kd8} 18. b6+ Kc6 {Kd6 Kd7} 19. b7 Kd5 20. Kb6 {b8=Q} Kd4 {Ke4 Ke5 Ke6} 21.
Kc6 {b8=Q} Kc3 {Kc4 Kd3 Ke3 Ke4 Ke5} 22. Kd5 {b8=Q} Kb4 {Kd2 Kd3} 23. Kd4
{b8=Q+} Kb5 24. b8=Q+ Kc6 25. Qd8 Kb5 26. Qc7 {Qd6 Qd7+ Qf6} Ka4 {Ka6 Kb4} 27.
Kc4 {Qb6 Qb7 Qb8} Ka3 28. Qh2 Ka4 29. Qa2#

[Don]

Exploiting the symmetry of the problem, we assume without restriction that white has the pawn, and the pawn is within [A2..D7] rectangle. So there are N = 64*64*24*2 elements in the bitbase (2 for side to move).

Out of these, how many draws are there ?

I need a unit test to validate my code -- like assert(nb_draws == ...). Nb of draws seems like a good unit test, just like perft values are a good unit test for board/movegen code. If everyone agrees on that number, it's likely to be correct. If it's not a good unit test as such, perhaps the number of draws for each of the 6 values of rank(white pawn) or something like that.

Also regarding rules used to initialize the generation, are these rules 100% correct at detecting a draw ? (even if the white pawn is on the 2nd rank and/or on a rook file)

• Black king directly in front of the pawn, white king directly behind it, black to move.
• Black king directly in front of the pawn, white king diagonally behind the pawn, white to move.

Some rules were produced 20 or so years ago which solve KPK perfectly - they can be substituted for a bitbase and are 100% correct. I don't have a source but they do exist somewhere.

It can be proved trivially that any bitbase can be replaced by a set of rules that will return the same result. The most trivial "rule" is to perform a search to find the answer. But can any or most databases be replaced with a decision tree or set of rules that execute quickly while representing a substantial space savings? I think the answer is "probably"

I think the rule for Rook and King vs King is that it's a win always unless black is stalemated or the rook is immediately subject to capture (and not defended by the king.) It wouldn't surprise me if there is some exception to what I just stated, it's maddeningly difficult to produce a perfect set of rules.

Don