End-game evaluation
Moderators: hgm, Rebel, chrisw
-
- Posts: 411
- Joined: Thu Dec 30, 2010 4:48 am
Re: End-game evaluation
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.
-
- Posts: 27988
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: End-game evaluation
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.Evert wrote: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).
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).
-
- Posts: 27988
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: End-game evaluation
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.kbhearn wrote: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.
This is a bit tricky to implement, though. You would not want to avoid polluting the hash with 50-move-dependent scores.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: End-game evaluation
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).hgm wrote: 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.
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.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.
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.
Yes, that's true.So the real problem is stalemate, and when stalemate would be a win, as in Xiangqi, two Knights would win easily.
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).Any color-alternator would have that problem, but also color-bound simple leapers like Ferz (which is a 'higher-order' color-alternator).
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.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!)
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: End-game evaluation
hgm wrote: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.kbhearn wrote: This is a bit tricky to implement, though. You would not want to avoid polluting the hash with 50-move-dependent scores.
-
- Posts: 27988
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: End-game evaluation
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.Evert wrote: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.
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).
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: End-game evaluation
Ok, that's useful information.hgm wrote: 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).
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.
-
- Posts: 27988
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: End-game evaluation
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:
The beginning of this does not really differ spectacularly from what you see with Camel + Wazir, though:
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:
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.)
[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
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
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
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.)