Author Topic: 3-Piece Musketeer Chess Endgame Tablebases Solved  (Read 369 times)

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #30 on: January 24, 2018, 09:28:03 pm »
1. Lf7 Kd7
2. Kb7 Ke7
3. Le5 Ke6
4. Lc4 Kf5
5. Kc6 Ke4
6. Kc5 Kf4
7. Kd4 Kf5
8. Le5

Mate in 10


HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #31 on: January 25, 2018, 01:27:07 pm »
For Cannon I have a mate in 15, which differs from your data.

Code: [Select]
8  K O . . . . . .
7  . . . . . . . .
6  . . k . . . . .
5  . . . . . . . .
4  . . . . . . . .
3  . . . . . . . .
2  . . . . . . . .
1  . . . . . . . .

   a b c d e f g h

The 3-piece endgame: King + Cannon vs. King has a win in 029-ply (015 moves for white) with white to move.

The 3-piece endgame: King + Cannon vs. King has no wins for black to move.

The 3-piece endgame: King + Cannon vs. King has no losses when it is white to move.


8  K O . . . . . .
7  . . . k . . . .
6  . . . . . . . .
5  . . . . . . . .
4  . . . . . . . .
3  . . . . . . . .
2  . . . . . . . .
1  . . . . . . . .

   a b c d e f g h

The 3-piece endgame: King + Cannon vs. King has a loss in 030-ply (015 moves for black) with black to move.

I suspect we use a different move for the Cannon. I use King + (0,2) + sideway Knight (KDsN in Betza notation). This piece can drive a King to checkmate against the side edges all by itself, making the mate very fast. I don't even need a tablebase to see that in the last position above the mate is much faster than 15 moves. When I let Fairy-Max analyze the position it sees it as 'mated in 9' (18 ply) within 6 sec (first mate score in 1.9 sec, but that is not the fastest mate):

 21      #-9    12.0M     0:22.26   Kc6 2. Ca7 Kb5 3. Kb8 Kb4 4. Cc6 Kc3 5. Cd5 Kd2 6. Ce4 Ke1 7. Cd3 Kf1 8. Cd1 Kg1 9. Ce1 Kh1 10. Cf1
 20      #-9    5.20M     0:09.73   Kc6 2. Ca7 Kb5 3. Kb8 Kb4 4. Cc6 Kc3 5. Cd5 Kd2 6. Ce4 Ke1 7. Cd3 Kf1 8. Cd1 Kg1 9. Ce1 Kh1 10. Cf1
 19      #-9    2.94M     0:05.42   Kc6 2. Ca7 Kb5 3. Kb8 Kb4 4. Cc6 Kc3 5. Cd5 Kd2 6. Ce4 Ke1 7. Cd3 Kf1 8. Ce3
 18    #-10    1.52M     0:02.71   Kc6 2. Ca7 Kb5 3. Kb8 Kb4 4. Cc6 Kc3 5. Cd5 Kd2 6. Ce4
 17    #-10    1.07M     0:01.87   Kc6 2. Ca7 Kb5 3. Kb8 Kb4 4. Cc6 Kc3 5. Cb5
 16    -8.28    681953   0:01.17   Kc6 2. Cb7 Kc5 3. Kb8 Kc4 4. Cd6 Kd3 5. Ce5 Kd2 6. Ce4 Ke1 7. Ce3

Once the Cannon can check on the same rank the end is very quick, so black is forced to evade towards the first rank on every check to prevent that. But eventually the board ends in that direction too.

Are you sure you included the Knight moves? Without Knight moves I get a mate-in-15 worst case too.
 
« Last Edit: January 25, 2018, 02:05:59 pm by HGMuller »

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #32 on: January 25, 2018, 04:35:46 pm »
I suspect we use a different move for the Cannon. I use King + (0,2) + sideway Knight (KDsN in Betza notation). This piece can drive a King to checkmate against the side edges all by itself, making the mate very fast. I don't even need a tablebase to see that in the last position above the mate is much faster than 15 moves. When I let Fairy-Max analyze the position it sees it as 'mated in 9' (18 ply) within 6 sec (first mate score in 1.9 sec, but that is not the fastest mate)

Are you sure you included the Knight moves? Without Knight moves I get a mate-in-15 worst case too.

A cannon does not have "all" of the knight's capabilities:



You can see which Knight-like destinations do not appear on this diagram. That is how I encoded it in the move generator. Let me double check the moves anyway based on your info. Thanks H.G.

Edit: I found the bug! My "for loop" only went from 1-12 instead of 1-16 for examining each move vector!

So basically I did not generate the last 4 moves which were the outermost reaches of the Knight, the north north west, north north east, south south west, and south south east knight moves. So it was a cannon with only one wheel spinning I guess :)
« Last Edit: January 25, 2018, 04:45:19 pm by GothicChessInventor »

ebinola

  • Jr. Member
  • **
  • Posts: 77
  • Location: nowhere in particular
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #33 on: January 25, 2018, 04:58:07 pm »
8. ...Ke6
Chess player, amateur writer and on the side shitposter extraordinaire.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #34 on: January 25, 2018, 05:52:44 pm »
Edit: I found the bug! My "for loop" only went from 1-12 instead of 1-16 for examining each move vector!
OK, it had to be something like that, the difference was much too big to be some subtle bug in a generator that works OK for most pieces. (My own generator failed when the royal piece had a sliding move, however, as I discovered last week, because of a short-cut I had used which wasn't valid for sliders.)

At the moment my generator does not support limited-range sliding moves, so I cannot do some of the other Musketeer pieces. I usually just replace the limited slides by direct leaps, as in a 3-men end-game there is hardly any obstruction, and it would be extremely unlikely it depended on that whether the end-game is a general win or not. But for the statistics, and longest forced mate it is likely to matter.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #35 on: January 25, 2018, 08:00:45 pm »
1. Lf7 Kd7
2. Kb7 Ke7
3. Le5 Ke6
4. Lc4 Kf5
5. Kc6 Ke4
6. Kc5 Kf4
7. Kd4 Kf5
8. Le5 Ke6
9. Ke4

Mate in 9 (you're still playing perfectly according to this tablebase)



GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #36 on: January 25, 2018, 08:30:09 pm »
At the moment my generator does not support limited-range sliding moves, so I cannot do some of the other Musketeer pieces. I usually just replace the limited slides by direct leaps, as in a 3-men end-game there is hardly any obstruction, and it would be extremely unlikely it depended on that whether the end-game is a general win or not. But for the statistics, and longest forced mate it is likely to matter.

I wrote a move generator that looks like this:

Code: [Select]
#define PAWN 0
#define KNIGHT 1
#define BISHOP 2
#define ROOK 3
#define QUEEN 4
#define HAWK 5
#define UNICORN 6
#define LEOPARD 7
#define ELEPHANT 8
#define CANNON 9
#define FORTRESS 10
#define SPIDER 11
#define ARCHBISHOP 12
#define CHANCELLOR 13
#define DRAGON 14
#define KING 15

#define TOTAL_DIRECTIONS 16

for(piece_loop = PAWN; piece_loop <= KING; piece_loop++)
for (square_loop = A8; square_loop <= H1; square_loop++)
{
global_piece_move_generator[piece_loop][square_loop].number_of_different_directions = 0;
for (direction_loop = 0; direction_loop < TOTAL_DIRECTIONS; direction_loop++)
{
global_piece_move_generator[piece_loop][square_loop].all_moves_for_this_piece_on_this_square[direction_loop].number_of_moves_in_this_direction = 0;
for (each_direction = 0; each_direction < TOTAL_DIRECTIONS; each_direction++)
{
global_piece_move_generator[piece_loop][square_loop].all_moves_for_this_piece_on_this_square[direction_loop].all_moves_in_this_direction[each_direction] = 0;
}
}
}

/****************/
/* KNIGHT ON A1 */
/****************/
which_piece = KNIGHT;
which_square = A1;
which_direction = 0;
which_move_in_this_direction = 0;

global_piece_move_generator[which_piece][which_square].number_of_different_directions = 2;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].number_of_moves_in_this_direction = 1;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = B3;

which_direction++;

global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].number_of_moves_in_this_direction = 1;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = C2;

/****************/
/* KNIGHT ON B1 */
/****************/
which_piece = KNIGHT;
which_square = B1;
which_direction = 0;
which_move_in_this_direction = 0;

global_piece_move_generator[which_piece][which_square].number_of_different_directions = 3;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].number_of_moves_in_this_direction = 1;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = A3;

which_direction++;

global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].number_of_moves_in_this_direction = 1;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = C3;

which_direction++;

global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].number_of_moves_in_this_direction = 1;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = D2;

/****************/
/* BISHOP ON A1 */
/****************/
which_piece = BISHOP;
which_square = A1;
which_direction = 0;
which_move_in_this_direction = 0;

global_piece_move_generator[which_piece][which_square].number_of_different_directions = 1;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].number_of_moves_in_this_direction = 7;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = B2;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = C3;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = D4;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = E5;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = F6;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = G7;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = H8;

/****************/
/* BISHOP ON B1 */
/****************/
which_piece = BISHOP;
which_square = B1;
which_direction = 0;
which_move_in_this_direction = 0;

global_piece_move_generator[which_piece][which_square].number_of_different_directions = 2;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].number_of_moves_in_this_direction = 6;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = C2;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = D3;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = E4;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = F5;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = G6;
which_move_in_this_direction++;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = H7;

which_direction++;
which_move_in_this_direction = 0;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].number_of_moves_in_this_direction = 1;
global_piece_move_generator[which_piece][which_square].all_moves_for_this_piece_on_this_square[which_direction].all_moves_in_this_direction[which_move_in_this_direction] = A2;

This way I can hard-code for loops to stop "sliding" after a constant number of moves that will vary by piece square without having to test "out of bounds" conditions all of the time.
« Last Edit: January 25, 2018, 08:43:00 pm by GothicChessInventor »

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #37 on: January 26, 2018, 03:19:29 am »
In my generator I defined macros for move generation, so that in places where I need to generate moves the code can look like this, hiding the details. (EGT[] is the array holding the tablebase, the '1' bit indicating whether the position is won with white to move):

Code: [Select]
static int Escape(int sq, int index)
{ // try black King moves (assumed to be valid as both capts and non-capts!)
  FOR_ALL_MOVES(firstCapts[3], sq, index, 3)
    if(!(EGT[nwind] & 1)) return 1;
  NEXT_MOVE
  return 0;
}

The macro looks as follows:

Code: [Select]
// loop through all moves of given piece. capts indicates which captures will be accepted

#define FOR_ALL_MOVES(movelist, from, index, capts) \
  { int r, f;                                       \
    for(r=movelist; f=flags[r]; r++) {              \
      int v=steps[r], to=from, nwind=index;         \
      while(b[to+=v] <= capts) {                    \
nwind += isteps[r];                         \

#define NEXT_MOVE               \
if(b[to] || f&4) break; \
      }                         \
    }                           \
  }

The pieces are described by the lists steps[] (step on a 0x88 board), isteps[] (index step in the EGT) and flags[] (indicating if it can slide or not through the '4' bit), and a zero value in the flags[] is used as a sentinel to indicate the end of the list of moves for that piece. In principle this is easy to adapt for limited range, by counting the number of steps n in the inner loop, and replacing the test f&4 by the more gradual test n < range[r].

The annoyance is that range[r] then would have to be defined for every move of every piece. Currently de pieces are defined in the program as a quite large number of arrays of initialized data, such as

Code: [Select]
// sample piece descriptions: (mode, delta_x, delta_y) triples, where mode 4=leaper, 2=non-capt, 1=capt
int king[]   = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 0};
int knight[] = {7,1,2, 7,1,-2, 7,-1,-2, 7,-1,2, 7,2,1, 7,-2,1, 7,2,-1, 7,-2,-1, 0};
int bishop[] = {3,1,1, 3,-1,-1, 3,-1,1, 3,1,-1, 0};
int archbsp[]={3,1,1, 3,-1,-1, 3,-1,1, 3,1,-1, 7,1,2, 7,1,-2, 7,-1,-2, 7,-1,2, 7,2,1, 7,-2,1, 7,2,-1, 7,-2,-1, 0};
which specifies each move by a triple (flags, x_step, y_step). If that would have to change to quadruples, in order to also include specification of a range, I would have to completely rewrite every move in the entire list.

But the lists of the selected pieces are interpreted by an initialization routine to fill the flags[], step[] and istep[] arrays, and I guess I could piggyback the range specification as a higher-order digit on what is now the flag specification. This is 0 for all existing definitions, which the initialization routine could then interpret as 1 or infinite, depending on if the lowes digit defined the move as a leap or a slide, and use the specified value as range when non-zero.



GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #38 on: January 26, 2018, 03:48:04 am »

The annoyance is that range[r] then would have to be defined for every move of every piece. Currently the pieces are defined in the program as a quite large number of arrays of initialized data...

That is true, but you know what the funny part is? It is actually easier to write fprintf() statements in a big loop that writes all of that C code for you :)

Then you just open up the text file and copy/paste the code into your program.

I learned that the first time I solved the 10-piece database for the game of checkers. There was no way I was going to write all of that code to put every type of material distribution into every possible legal configuration.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #39 on: January 26, 2018, 05:33:48 am »
In WinBoard (and the JavaScript for the interactive diagram) I facilitated specifying of moves by writing a 'compiler' for Betza notation. This just takes the Betza notation of the string, e.g. fBbR , and then generates the list with step vectors, ranges and move capabilities (capture, non-capture, hop...) from that. I might equip future versions of Fairy-Max with that too, it makes definition of the moves so much simpler.

Anyway, I now made the necessary modifications to specify finite range to my 3-men generator. This gave the following results:

Leopard:

        mated    mate
King captures 63348
mates     396         ( 0.00 sec)
in-1       64    4508 ( 0.00 sec)
in-2      408     432 ( 0.01 sec)
in-3      216    1472 ( 0.01 sec)
in-4      844    1248 ( 0.01 sec)
in-5      784    2564 ( 0.01 sec)
in-6     1580    3092 ( 0.01 sec)
in-7     1964    4388 ( 0.01 sec)
in-8     3628    5008 ( 0.01 sec)
in-9     3704    8708 ( 0.03 sec)
in-10    7884    7284 ( 0.03 sec)
in-11   16480   14236 ( 0.03 sec)
in-12   26524   26944 ( 0.05 sec)
in-13   36196   38096 ( 0.06 sec)
in-14   43368   40728 ( 0.08 sec)
in-15   40312   21256 ( 0.09 sec)
in-16   14540    5748 ( 0.09 sec)
in-17    2748     924 ( 0.11 sec)
in-18       0       0 ( 0.11 sec)
won:     249984 (100.0%)
lost:    201640 ( 80.7%)
avg:       13.1 moves


Spider:

        mated    mate
King captures 73948
mates     556         ( 0.00 sec)
in-1     1012    6824 ( 0.01 sec)
in-2     2460    3608 ( 0.01 sec)
in-3     5040    7444 ( 0.01 sec)
in-4     8236   11592 ( 0.03 sec)
in-5    12320   15992 ( 0.05 sec)
in-6    17348   20556 ( 0.08 sec)
in-7    30692   26780 ( 0.09 sec)
in-8    41644   36952 ( 0.14 sec)
in-9    45476   31852 ( 0.17 sec)
in-10   32424   13452 ( 0.20 sec)
in-11    4272     984 ( 0.20 sec)
in-12       0       0 ( 0.20 sec)
won:     249984 (100.0%)
lost:    201480 ( 80.6%)
avg:        7.7 moves


Fortress:

        mated    mate
King captures 70140
mates      76         ( 0.00 sec)
in-1      280     724 ( 0.00 sec)
in-2      888    1884 ( 0.00 sec)
in-3     1008    3376 ( 0.00 sec)
in-4     1920    4468 ( 0.00 sec)
in-5     2660    6588 ( 0.00 sec)
in-6     5748    8912 ( 0.02 sec)
in-7     7824   13732 ( 0.02 sec)
in-8    13004   16716 ( 0.03 sec)
in-9    18476   21292 ( 0.03 sec)
in-10   27396   25428 ( 0.05 sec)
in-11   34816   28028 ( 0.06 sec)
in-12   41600   28536 ( 0.08 sec)
in-13   35164   16828 ( 0.09 sec)
in-14   10164    3232 ( 0.09 sec)
in-15     448     100 ( 0.09 sec)
in-16       0       0 ( 0.09 sec)
won:     249984 (100.0%)
lost:    201472 ( 80.6%)
avg:       10.7 moves


This seems in agreement with your results on these pieces.
« Last Edit: January 26, 2018, 06:11:55 am by HGMuller »

ebinola

  • Jr. Member
  • **
  • Posts: 77
  • Location: nowhere in particular
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #40 on: January 26, 2018, 01:23:15 pm »
9.... Ke6
Chess player, amateur writer and on the side shitposter extraordinaire.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #41 on: January 26, 2018, 07:53:59 pm »
9.... Ke6

1. Lf7 Kd7
2. Kb7 Ke7
3. Le5 Ke6
4. Lc4 Kf5
5. Kc6 Ke4
6. Kc5 Kf4
7. Kd4 Kf5
8. Le5 Ke6
9. Ke4 (still waiting)

I have your King on e6 already. Let me know if we need to redo a move.

ebinola

  • Jr. Member
  • **
  • Posts: 77
  • Location: nowhere in particular
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #42 on: January 28, 2018, 06:43:32 pm »
Yeah, I meant Ke7.
Chess player, amateur writer and on the side shitposter extraordinaire.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #43 on: January 29, 2018, 12:16:34 pm »
1. Lf7 Kd7
2. Kb7 Ke7
3. Le5 Ke6
4. Lc4 Kf5
5. Kc6 Ke4
6. Kc5 Kf4
7. Kd4 Kf5
8. Le5 Ke6
9. Ke4 Ke7
10. Kd5

Mate in 8




ebinola

  • Jr. Member
  • **
  • Posts: 77
  • Location: nowhere in particular
    • View Profile
Re: 3-Piece Musketeer Chess Endgame Tablebases Solved
« Reply #44 on: February 06, 2018, 06:14:21 pm »
10.... Ke8
Sorry for the delay.
Chess player, amateur writer and on the side shitposter extraordinaire.