Shatranj tablebases

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

Shatranj tablebases

Postby h.g.muller » Wed Aug 20, 2008 8:13 pm

I did generate some Shatranj tablebases. That was an interesting exercise, because in Shatranj there is a 'bare-King-loses' rule, which does not exist in Chess. So 3-men end-games are by definition 100% won, even KNK and the weaker pieces Ferz and Elephant (KFK and KEK). The effect of this propagates to the larger tablebases, e.g. KNNKN is a general win, while in Chess it is of course a dead draw.

The baring rule has the complication that a bare King does not lose if on the next move he can bare the opponent as well. If he can, it is draw. So trading the last piece does not help, you really have to win it. I implemented this by declaring all wtm positions where black has a bare King, and white not, as 'in-check' positions, before generating the btm checkmated predecessor positions. So btm positions where the black King is bare, and it cannot capture the last white piece, are labeled as checkmates. From that point on the tablebase is built as normal (except that I do not weed out stalemates, as in Shatranj being stalemated also counts as a loss.

Below is the summary of my efforts.
_____________________________________________________________________

Shatranj end-games:

Due to the bare-King-equals-loss rule, all 3-men endings are 100% won.
This has important effects on the larger endings, e.g. KNKP would be
an easy draw for black in normal Chess, but in Shatranj it is usually lost,
as losing the Pawn is fatal. For 4-men endings where the strong side has a
Rook, it makes no difference, though, as KRK is also 100% won if black cannot
capture the Rook on the first move. So the baring rule adds no wins, and only
a very slight difference due to a few stalemate positions now being wins remains.

Of the 4-men endings (always 2+2, of course) only KRKF and KRKE are generally won:

Code: Select all
Won for white with btm:

4-MEN                White
black      R       N       F       E
   R       0.47%
   N       9%      2.9%            0.26%
   F      73%     16%    7%/9%   3.3%/0.9%
   E      75%     10%    8%/11%

Won wtm:

4-MEN                White
black      R       N       F       E
   R      50%
   N      63%     32%             25%
   F      99.86%  54%   41%/38%  37%/26%
   E      99.83%  49%   40%/38%

wtm King capture:

4-MEN                White
black      R       N       F       E
   X      29%     18%   15%/15%   14%


Notes: F and E are color-bound, so if there are more of them, the cases
where they are on like or unlike color are treated separately.

The wtm King capture percentage gives an indication how likely
it is a black piece will be attacked. As the probability that it is
undefended by its own King is ~90% (and even then it might be doubly
attacked), you have to multiply it by 1.9 to get the fraction of positions
that are trivially won to white with wtm. E.g. in KRKN about 55% of the
positions is won by capturing K or R on the first move. So only about 7%
of the positions is won the hard way. This is reflected in the low fraction
of btm positions that are won to white: only 0.5%. Typically the number of
wtm positions won to white is about 10x larger than the brm position, as each
btm position can be reached by many white moves.

So the fact that KRKN lists 63% wins with wtm should not be taken as evidence
that there is a good chance to win this end-game. It is a dead draw, and you
need to capture the opponen't hanging Knight on the first move, or create
a skewer, to win this end-game. If an end-game is won, it typically has 99%+
won positions for wtm, and a fraction as low as 63% indicates it is almost
never won. With btm it is the opposite: even in totally-won end-games, there is
a large fraction of positions (25-50%) where black starts capturing our King or
an undefended piece.

End-games with Ferzes are special, because an isolated Ferz can be hunted down
by a King. So there are always a large number of initial positions where the
Ferz is born in a sector of the board where it is doomed, unless it can be
defended from a distance by a Rook.

5-men, 2+1:

Here a Knight advantage is enough to subdue another Knight or Ferz (KNNKN,
KNFKF), but in the presence of Rooks (KRNKR) it is not enough. The Rook only
needs the tiniest help to beat a Knight, (KRFKN and even KREKN), where alone
(KRKN) could not do it. Presumably the mere presence of the auxilary piece,
making an R vs N trade a win through the baring rule, is what swings the odds.

Code: Select all
       wtm                     btm
KFFKE  95.67%/91.95%/31%   60%/56%/2.4%
KFFKF  95.75%/94.49%/45%   58%/59%/13%
KFEKF  73%/53%/63%/44%     29%/16%/23%/13%
KNFKF  99.37%/99.16%         67%/70%
KFFKN  35%/36%              1.6%/1.4%
KNFKN  42%                     2.3%
KNNKN  99.40%                 60%
KREKN  99.43%                 63%
KRFKN  99.55%                 63%
KRFKR  58%                     2.7%
KRNKR  64%                     4.4%


Notes: An extremely small fraction of KNNKN wins take more than 50 moves (upto 60).
Of the KFFKF wins with two unlike Ferzes against one, about 0.4% takes between 50
and 73 moves. Note that KFFKF is generally won ith all Ferzes on the same color
(first number), as well as with an unlike pair vs a single one, but not with two
like Ferzes against a Ferz on the opposite color (third number). The same holds for
KFFKE. The comparatively low win fraction for a generally won endgame in KFFKF and
KFFKE (~95% in stead of 99%+) is due to one of the Ferzes being hunted down.

KFFKE with unlike Ferzes is surprisingly enough easier to defend than KFFKF,
although an Elephant is in general weaker than a Ferz. This is because a King can
hunt down an isolated Ferz, but not an Elephant (because the latter outruns it).

The wins in KFEKF are likely due to the possibility of hunting down the lone Ferz
with the King, but there is a fair number of cases where you can do that. And a
single move cannot easily save an isolated Ferz from danger, like in the end-games
that depend on tactics to win them. If the Ferz in these endigs can find shelter
with its King, it is draw. The same holds for KFFKF with like vs unlike. In KFFKE,
where the black piece cannot be chased, the btm win probability drops to a normal
value (~3%) for drawn end-games.

One lesson is that it seems not to matter so much if your Ferzes are of like or
unlike color, as long as the opponent's Ferz or Elephant is not on the other color.
But a like Ferz and Elephant do better than unlike.

5-men, 1+2:

Code: Select all
          wtm          btm
KRKFE 94.45%/94.68%  52%/52%
KRKFF 85%/88%        37%/48%
KNKFE 22%/23%       1.4%/1.9%
KNKFF 23%/24%       1.3%/2.6%


Notes: KRKFF seems to do pretty well, but in fact this is just due to the large number of targets tthat are potentially hanging on the first move. The check probability with K+R is 28%, and each of the Ferzes has a similar probability to be target. And if one of them falls, the remaining KRKF is generally won. To this we must add the probability that one of the Ferzes is cut off from its allies, and can be hunted down by the King. Of the won btm positions, 60% is lost within 3 moves, 80% within 6. This is the typical timescale of Ferz chases.

Only KRKFE is generally won. (I did not do KRKEE, because there would be too many unnatural combinations of Elephants to make that meaningfull. With 8-fold symmetry reduction, there are still 2 different kinds of Elephants, only one of which can occur in a Shatranj game. So even with only one Elephant, the results are contaminated by 50% impossile positions. I have not made an attempt to filter those out, yet.)
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Shatranj tablebases

Postby syzygy » Sat Aug 23, 2008 7:31 pm

h.g.muller wrote:(I did not do KRKEE, because there would be too many unnatural combinations of Elephants to make that meaningfull. With 8-fold symmetry reduction, there are still 2 different kinds of Elephants, only one of which can occur in a Shatranj game. So even with only one Elephant, the results are contaminated by 50% impossile positions. I have not made an attempt to filter those out, yet.)

Could you not just mark those impossible positions as broken positions?
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: Shatranj tablebases

Postby h.g.muller » Tue Aug 26, 2008 6:39 am

My code does not mark broken positions. They are just never reached. The most efficient way to handle it would be to build a filter, and use it on the positions that are initially declared wins (i.e. the black-in-check and black-bare wtm positions), to leave them undecided when Elephants are on an impossible relative position. (It should be able to figure that out by doing some XOR operations on bits of their rank and file numbers.) Then the tablebase would get very sparse, and that would save a lot of time in building it. The impossible positions would just never be accesses, and as they form contiguous memory blocks, that saves a lot of access time.

But the point is that I would have to do some programming, and that it is questionable if that is worth it. I have not identified any 4-men end-games where adding a second Elephant might make a difference. And I would not be able to do 6-men anyway. It might be more useful to add the capability to handle Pawns to the tablebase generator.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Shatranj tablebases

Postby byakuugan » Tue Aug 30, 2011 1:55 am

h.g.muller wrote:I did generate some Shatranj tablebases. That was an interesting exercise, because in Shatranj there is a 'bare-King-loses' rule, which does not exist in Chess. So 3-men end-games are by definition 100% won, even KNK and the weaker pieces Ferz and Elephant (KFK and KEK). The effect of this propagates to the larger tablebases, e.g. KNNKN is a general win, while in Chess it is of course a dead draw.

The baring rule has the complication that a bare King does not lose if on the next move he can bare the opponent as well. If he can, it is draw. So trading the last piece does not help, you really have to win it. I implemented this by declaring all wtm positions where black has a bare King, and white not, as 'in-check' positions, before generating the btm checkmated predecessor positions. So btm positions where the black King is bare, and it cannot capture the last white piece, are labeled as checkmates. From that point on the tablebase is built as normal (except that I do not weed out stalemates, as in Shatranj being stalemated also counts as a loss.

Below is the summary of my efforts.
_____________________________________________________________________

Shatranj end-games:

Due to the bare-King-equals-loss rule, all 3-men endings are 100% won.
This has important effects on the larger endings, e.g. KNKP would be
an easy draw for black in normal Chess, but in Shatranj it is usually lost,
as losing the Pawn is fatal. For 4-men endings where the strong side has a
Rook, it makes no difference, though, as KRK is also 100% won if black cannot
capture the Rook on the first move. So the baring rule adds no wins, and only
a very slight difference due to a few stalemate positions now being wins remains.

Of the 4-men endings (always 2+2, of course) only KRKF and KRKE are generally won:

Code: Select all
Won for white with btm:

4-MEN                White
black      R       N       F       E
   R       0.47%
   N       9%      2.9%            0.26%
   F      73%     16%    7%/9%   3.3%/0.9%
   E      75%     10%    8%/11%

Won wtm:

4-MEN                White
black      R       N       F       E
   R      50%
   N      63%     32%             25%
   F      99.86%  54%   41%/38%  37%/26%
   E      99.83%  49%   40%/38%

wtm King capture:

4-MEN                White
black      R       N       F       E
   X      29%     18%   15%/15%   14%


Notes: F and E are color-bound, so if there are more of them, the cases
where they are on like or unlike color are treated separately.

The wtm King capture percentage gives an indication how likely
it is a black piece will be attacked. As the probability that it is
undefended by its own King is ~90% (and even then it might be doubly
attacked), you have to multiply it by 1.9 to get the fraction of positions
that are trivially won to white with wtm. E.g. in KRKN about 55% of the
positions is won by capturing K or R on the first move. So only about 7%
of the positions is won the hard way. This is reflected in the low fraction
of btm positions that are won to white: only 0.5%. Typically the number of
wtm positions won to white is about 10x larger than the brm position, as each
btm position can be reached by many white moves.

So the fact that KRKN lists 63% wins with wtm should not be taken as evidence
that there is a good chance to win this end-game. It is a dead draw, and you
need to capture the opponen't hanging Knight on the first move, or create
a skewer, to win this end-game. If an end-game is won, it typically has 99%+
won positions for wtm, and a fraction as low as 63% indicates it is almost
never won. With btm it is the opposite: even in totally-won end-games, there is
a large fraction of positions (25-50%) where black starts capturing our King or
an undefended piece.

End-games with Ferzes are special, because an isolated Ferz can be hunted down
by a King. So there are always a large number of initial positions where the
Ferz is born in a sector of the board where it is doomed, unless it can be
defended from a distance by a Rook.

5-men, 2+1:

Here a Knight advantage is enough to subdue another Knight or Ferz (KNNKN,
KNFKF), but in the presence of Rooks (KRNKR) it is not enough. The Rook only
needs the tiniest help to beat a Knight, (KRFKN and even KREKN), where alone
(KRKN) could not do it. Presumably the mere presence of the auxilary piece,
making an R vs N trade a win through the baring rule, is what swings the odds.

Code: Select all
       wtm                     btm
KFFKE  95.67%/91.95%/31%   60%/56%/2.4%
KFFKF  95.75%/94.49%/45%   58%/59%/13%
KFEKF  73%/53%/63%/44%     29%/16%/23%/13%
KNFKF  99.37%/99.16%         67%/70%
KFFKN  35%/36%              1.6%/1.4%
KNFKN  42%                     2.3%
KNNKN  99.40%                 60%
KREKN  99.43%                 63%
KRFKN  99.55%                 63%
KRFKR  58%                     2.7%
KRNKR  64%                     4.4%


Notes: An extremely small fraction of KNNKN wins take more than 50 moves (upto 60).
Of the KFFKF wins with two unlike Ferzes against one, about 0.4% takes between 50
and 73 moves. Note that KFFKF is generally won ith all Ferzes on the same color
(first number), as well as with an unlike pair vs a single one, but not with two
like Ferzes against a Ferz on the opposite color (third number). The same holds for
KFFKE. The comparatively low win fraction for a generally won endgame in KFFKF and
KFFKE (~95% in stead of 99%+) is due to one of the Ferzes being hunted down.

KFFKE with unlike Ferzes is surprisingly enough easier to defend than KFFKF,
although an Elephant is in general weaker than a Ferz. This is because a King can
hunt down an isolated Ferz, but not an Elephant (because the latter outruns it).

The wins in KFEKF are likely due to the possibility of hunting down the lone Ferz
with the King, but there is a fair number of cases where you can do that. And a
single move cannot easily save an isolated Ferz from danger, like in the end-games
that depend on tactics to win them. If the Ferz in these endigs can find shelter
with its King, it is draw. The same holds for KFFKF with like vs unlike. In KFFKE,
where the black piece cannot be chased, the btm win probability drops to a normal
value (~3%) for drawn end-games.

One lesson is that it seems not to matter so much if your Ferzes are of like or
unlike color, as long as the opponent's Ferz or Elephant is not on the other color.
But a like Ferz and Elephant do better than unlike.

5-men, 1+2:

Code: Select all
          wtm          btm
KRKFE 94.45%/94.68%  52%/52%
KRKFF 85%/88%        37%/48%
KNKFE 22%/23%       1.4%/1.9%
KNKFF 23%/24%       1.3%/2.6%


Notes: KRKFF seems to do pretty well, but in fact this is just due to the large number of targets tthat are potentially hanging on the first move. The check probability with K+R is 28%, and each of the Ferzes has a similar probability to be target. And if one of them falls, the remaining KRKF is generally won. To this we must add the probability that one of the Ferzes is cut off from its allies, and can be hunted down by the King. Of the won btm positions, 60% is lost within 3 moves, 80% within 6. This is the typical timescale of Ferz chases.

Only KRKFE is generally won. (I did not do KRKEE, because there would be too many unnatural combinations of Elephants to make that meaningfull. With 8-fold symmetry reduction, there are still 2 different kinds of Elephants, only one of which can occur in a Shatranj game. So even with only one Elephant, the results are contaminated by 50% impossile positions. I have not made an attempt to filter those out, yet.)


How did you accomplish all this? I've been wanting to learn how to change the meaning of a "win" for study purposes. The fact that a rook trade cannot be forced in RN vs R can be useful in normal chess.
byakuugan
 
Posts: 40
Joined: Tue May 18, 2010 4:36 am

Re: Shatranj tablebases

Postby h.g.muller » Sun Oct 23, 2011 5:18 pm

Sorry for the late reply; I have not visited this forum in ages!

The way I did it was by modifying my simple tablebase generator (posted on my website) in the mentioned way: adding a single pass through it where I mark all positions which satisfy a certain condition on material (namely non-bare vs bare), and then run it for all the mentioned end-games.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam


Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 3 guests