End-game evaluation

[kbhearn]

KQKNN is a general draw unless the queen can seperate one of the Ns from the king immediately. KQKNB and KQKBB on the other hand the Q wins except for a single fortress setup near a corner.

[hgm]

So far I've come up with different piece properties to look at, colour bound being an obvious one. Another one is the ability to perform a tempo-move, which I suspect is needed to be able to mate a lone king (hence why you can't with two knights), but I don't know how valid such generatlisations are (I'd need a tablebase to test).

Well, you could use the tablebase generator I released last week. Building a 4-men EGT typically takes less than half a minute, so testing pairs of minors for mating potential should be easy. Testing a single piece for mating potential is a sub-second job.

The problem with NN is not so much tempo-moves, as well as the inability of the Knight to switch in one move from attacking c1 (so that checking the bare King on b1 would force him to step into the corner) to attacking a1 to perform the checkmate. And you must do that in a single move, or you would stalemate him. Tempo is not a problem (like it would be in 8/8/8/8/8/p7/k1K1N3/8 w - - 0 1), because the King can 'triangulate', by playing Kb3-c2 when the bare King is on a1, effectively null-moving because the new positions is symemtry-equivalent to the old one. So the real problem is stalemate, and when stalemate would be a win, as in Xiangqi, two Knights would win easily.

Any color-alternator would have that problem, but also color-bound simple leapers like Ferz (which is a 'higher-order' color-alternator). Dababba could do it, but is too weak to be of use in driving the bare King towards the corner exactly for the high-order color-biding that makes the mating move possible. So the color of the deadly corner seems to be not so much determined by color-binding, as well as the ability to step from c1 to a1 in 3 moves. The (color-bound) Bishop can do that, but the equally color-bound Ferz ((1,1) leaper) can not. The piece that plays the role of Knight in the Clobbers army of Chess with Different Armies (a (1,0) + (2,2) compound leaper) can do it. To force checkmate with that plus a color-bound (2,2) + (3,3) leaper compound (a sub-set of the Bishop!), you have to do it in the corner of opposite color of the latter. Because with (2,2) + (3,3) jumps you can not go from c1 to a1 in 3 moves, like you would have to do in your 'own corner', and neither can the piece cover a1 and c1 at the same time, as would be needed for an edge mate on b1. (Also note the piece can lose a tempo in 5 moves!)

For divergent pieces the '3-moves rule' must be replaced by '2 captures + 1 non-capture'. A pair of (1,0) capturers + (1,1) non-capturers can thus force a corner mate, while (1,1) capturers + (1,0) non-capturers can force an edge mate (cover a1 and c1 at once, while the other switches from c1 to b1 in 2 captures +1 non-capture).

[hgm]

KQKNN is a general draw unless the queen can seperate one of the Ns from the king immediately. KQKNB and KQKBB on the other hand the Q wins except for a single fortress setup near a corner.

OK, thanks. This could be seen as a very big fortress, and it would probably be wrong to discount this end-game indiscriminatorily as drawish, as the statistical probability that one of the Kights will be separated from the King is appreciable. An alternative for such draws is to discount them based on the 50-move counter: the longer you stay in the end-game, the more likely it is that you are facing a fortress, because if you were not, you probably already would have gobbled up the Knight, and in the mean time the opponent gets more opprtunity to build up his defenses.

This is a bit tricky to implement, though. You would not want to avoid polluting the hash with 50-move-dependent scores.

[Evert]

Well, you could use the tablebase generator I released last week. Building a 4-men EGT typically takes less than half a minute, so testing pairs of minors for mating potential should be easy. Testing a single piece for mating potential is a sub-second job.

I downloaded it, but didn't do more with it so far than look whether I could compile my own version (since I don't have Windows).

The problem with NN is not so much tempo-moves, as well as the inability of the Knight to switch in one move from attacking c1 (so that checking the bare King on b1 would force him to step into the corner) to attacking a1 to perform the checkmate.

Hmm... my thinking was that you'd want to be able to make a waiting move so that the defending king has to yield terrain and walk into the corner. You can always do that in KRK (and KQK, but that's not interesting), KBBK and KBNK, but not in KNNK (except with the king, as you pointed out, but then your own king may be giving up terrain that you need to controlled; the correct statement would have been that I expect you want two pieces that can triangulate). Of course it's always good to have the ability to triangulate in case you need it, without saying that you do need it.
Should be easy to test though whether it makes a difference: just allow the side with the knights to null-move and see whether it can do it. I might try that at some point just for fun.

So the real problem is stalemate, and when stalemate would be a win, as in Xiangqi, two Knights would win easily.

Yes, that's true.

Any color-alternator would have that problem, but also color-bound simple leapers like Ferz (which is a 'higher-order' color-alternator).

Yes, a Ferz can't do a triangulation (the intersection of it's 1-move attack set and it's 2-move attack set is 0).

To force checkmate with that plus a color-bound (2,2) + (3,3) leaper compound (a sub-set of the Bishop!), you have to do it in the corner of opposite color of the latter. Because with (2,2) + (3,3) jumps you can not go from c1 to a1 in 3 moves, like you would have to do in your 'own corner', and neither can the piece cover a1 and c1 at the same time, as would be needed for an edge mate on b1. (Also note the piece can lose a tempo in 5 moves!)

That's an interesting point, and different from what I assume right now in Sjaak. Of course most if that is mostly ad-hoc generalisations from normal chess and similar-enough variants, which can be improved for more general cases. At some point.

[Evert]

This is a bit tricky to implement, though. You would not want to avoid polluting the hash with 50-move-dependent scores.

I don't allow hash cutoffs in the last 20 plies before reaching the 50-move limit (which is the point where I also start dragging the evaluation closer to 0). Seems to do the trick.

[hgm]

Hmm... my thinking was that you'd want to be able to make a waiting move so that the defending king has to yield terrain and walk into the corner. You can always do that in KRK (and KQK, but that's not interesting), KBBK and KBNK, but not in KNNK (except with the king, as you pointed out, but then your own king may be giving up terrain that you need to controlled; the correct statement would have been that I expect you want two pieces that can triangulate). Of course it's always good to have the ability to triangulate in case you need it, without saying that you do need it.
Should be easy to test though whether it makes a difference: just allow the side with the knights to null-move and see whether it can do it. I might try that at some point just for fun.

That triangulation is not needed can already be seen from the fact that there are many pairs of non-triagulating pieces that can force mate. In fact, simple leapers (i.e. with only a single step vector, like (1,2) for N, symmetrized to all directions) can never triangulate: they are either color alternatorsorcolor-bound, and when they are color-bound you can consider their color as a 45-degrees rotated grid checkered by meta-colors, and then they have to be meta-color alternating ormeta-color-bound, and so on, untilin the end evry piece is meta-(meta-...)colr alternating.

But almost any combination of (an inhomogeneous pair of) Ferz (1,1), Wazir (1,0), Knight (1,2), Camel (1,3) and Zebra (2,3) can force checkmate, except F+W, F+N and another that I forgot (F+C, because they are both color-bound?). Even N+W can do it. W and F with only 4 moves are significantly weaker than the others, which have 8 moves, but even an 8-move plus a 4-move piece have little trouble driving a King into the corner.

Another indication is that there are no mate-in-2 positions at all in KNNK, not even when the King is already trapped on a1-b1 by Kb3 + Ne2, while the other Knightis free to roam the board to get in position. And that KNNKX with X slow and far away usually has longer mates (I think that KNNKN has some mate-in-6 positions, and KNNKW even much longer), beause the X breaks the stalemate. And apparently you don't even need zugzwang. When the piece can be blocked until needed, you can even have >50-move wins (KNNKP).

[Evert]

But almost any combination of (an inhomogeneous pair of) Ferz (1,1), Wazir (1,0), Knight (1,2), Camel (1,3) and Zebra (2,3) can force checkmate, except F+W, F+N and another that I forgot (F+C, because they are both color-bound?). Even N+W can do it. W and F with only 4 moves are significantly weaker than the others, which have 8 moves, but even an 8-move plus a 4-move piece have little trouble driving a King into the corner.

Another indication is that there are no mate-in-2 positions at all in KNNK, not even when the King is already trapped on a1-b1 by Kb3 + Ne2, while the other Knightis free to roam the board to get in position. And that KNNKX with X slow and far away usually has longer mates (I think that KNNKN has some mate-in-6 positions, and KNNKW even much longer), beause the X breaks the stalemate. And apparently you don't even need zugzwang. When the piece can be blocked until needed, you can even have >50-move wins (KNNKP).

Ok, that's useful information.
I guess I won't need to investigate this further. There may still be some sort of advantage to having the option of a triangulation (or at least knowing which pieces can do it, for the purpose of deciding whether we allow a null-move search), but I guess it won't help for determining mating potential.
I'd like to do it with static analysis (when starting a new game) but I might be able to get away with doing a quick retrograde analysis starting from a mate position. It would only be needed for pairs of pieces that can't mate on their own.

[hgm]

For 4 pieces a complete retrograde analysis on 8x8, even just for the first few moves, is probably too costly. Reason is that there are usually lots of edge mates, almost all non-forcible, and even just identifying these mates takes a significant fraction of the time needed to build the entire EGT. But I guess it would be good enough for the first few iterations to only consider positions with the white King on a3,b3,c3, the black King on c2,c1,b1,a1,a2,a3, and the white pieces everywhere. That should tell you if the pieces in principle are able to perform the final mating steps. You would find that two Dababbas can do it, though:

[d]6R1/8/8/8/K7/8/8/k5R1 w
Mate in 11 with 2 Dababbas

1. Kb3 Kb1 2. De1 {closes the trap} Ka1 3. Dc1+ Kb1 4. Dc3 Ka1 5. De8 Kb1 6. Dc8 Ka1 7. Da8 Kb1 8. Da6 Ka1 9. Kb2! {triangulates} Ka2 10. Da4+ Ka1 11. Da3#

But as you can see from the complete statistics only 680 out of 2M btm positions are won:

Code: Select all

KDD_K

                 like          unlike
WON.wtm   346220     371840
K capture   346220     368584
other            0       3256
  0.       1823704    1881164
 10.             0         16
 11.             0          8
 12.             0         16
 13.             0         32
 14.             0        176
 15.             0         52
 16.             0        240
 17.             0         32
 18.             0         96
 19.             0          4
 20.             0          8
WON.btm          0        680
stalemate      456        348
W check      51712      54192
LEGAL      1824160    1882192
TOTAL      1875872    1936384

The beginning of this does not really differ spectacularly from what you see with Camel + Wazir, though:

Code: Select all

KCW_K

WON.wtm    3781436
K capture   809720
other      2971716
  0.        737536
 10.            84
 11.            18
 12.            26
 13.           122
 14.           172
 15.           396
 16.           308
 17.           730
 18.          1048
 19.          1492
 20.          1121
 21.          1267
 22.           698
 23.          1109
 24.           936
 25.          1001
 26.          1441
 27.          1231
 28.          1490
 29.          1500
 30.          1267
 31.          1178
 32.          1146
 33.          1232
 34.           563
 35.           608
 36.           809
 37.          1499
 38.          1177
 39.           560
 40.           248
 41.           199
 42.           404
 43.           440
 44.           154
 45.           330
 46.           264
 47.           210
 48.           514
 49.           410
 50.           720
 51.          1224
 52.          2450
 53.          2650
 54.          3470
 55.          4504
 56.          5796
 57.          9145
 58.         11572
 59.         14216
 60.         20626
 61.         32617
 62.         47723
 63.         63105
 64.         91688
 65.        127635
 66.        175735
 67.        225274
 68.        271017
 69.        301921
 70.        310095
 71.        285314
 72.        238836
 73.        177634
 74.        111629
 75.         64539
 76.         33995
 77.         16270
 78.          8608
 79.          5433
 80.          3632
 81.          2056
 82.          1071
 83.           473
 84.           214
 85.           112
 86.            30
 87.            10
WON.btm    2702441
stalemate     1937
W check     370342
LEGAL      3441914
TOTAL      3812256

There are still only 154 mate-in-34 positions (counting starts at 10 in my generator for technical reasons), and at that point it is not clearat all this is a generally won end-game. What you saw upto then is a lengthy and cumbersome drive of the bare King from the wrong corner into the right one. (Camel is color-bound, neither Wazir or Camel can move from c1 to a1 in 3 moves, but Camel can attack a1 and c1 at the same time in its own corner, while Wazir can move from c1 to b1 in 3 moves, so an edge-mate is possible there, and only there.) That you can drive the bare King to the edge at all turns out only later, and requires another 25 moves or so. But in the end 70% of all btm and 99% of all wtm positions is won.

Compare that to Zebra+Ferz:

Code: Select all

KZF_K

WON.wtm     832447
K capture   754740
other        77707
  0.       3670601
 10.            53
 11.            40
 12.            25
 13.            48
 14.            96
 15.           124
 16.           179
 17.           272
 18.           428
 19.           410
 20.           820
 21.           832
 22.           910
 23.           748
 24.           596
 25.           876
 26.          1064
 27.           792
 28.           592
 29.           311
 30.           412
 31.           499
 32.           294
 33.           326
 34.           361
 35.           258
 36.           148
 37.           142
 38.            97
 39.            90
 40.            90
 41.           162
 42.           290
 43.           322
 44.           704
 45.           592
 46.          1636
 47.           661
 48.          1166
 49.           392
 50.           596
 51.           159
 52.           214
 53.            35
 54.            81
 55.             6
 56.             6
WON.btm      18955
stalemate     1602
W check     121098
LEGAL      3691158
TOTAL      3812256

Here there are 159 mate-in-41 positions, and what happened until then does not seem so different from the KCWK case. But unlike the latter,it quickly peters out after that, and not even 0.5% of all btm positions is won. It is really not possible to tell the C+W can do the drive before the system becomes super-critical after 38 iterations, and that Z+F cannot do it before you reach iteration 45...

So I guess there is no shortcut for building the entire tablebase. It should be possible to do that significantly faster than the released version does it. (But the highly optimized version, which could do a 4-men in about 2 sec, was a DTM generator not supporting slider/leaper compouds.)