Can someone explain to me how a tablebase (e.g., supposedly deciding
all positions with seven pieces or less as wins for one player or the
other, or as draws) can fulfill this function given, for example, the
Fifty Move Rule? Does a position contain all that is necessary to
decide the outcome, when in fact the history might affect it as well?
For example, say that some endgame position is analyzed as containing a
forced mate in three for White (to move). But what if that position
was reached in a game with 49 previous moves qualifying under the Fifty
Move Rule, such that any move made by White would result in a draw if
the rule were invoked by Black?

For that matter, has it been proven that all theoretical endgame
positions are reachable under applicable anti-repetition and
anti-stasis rules?

Mark Adkins

schrieb:
Can someone explain to me how a tablebase (e.g., supposedly deciding
all positions with seven pieces or less as wins for one player or the
other, or as draws) can fulfill this function given, for example, the
Fifty Move Rule? Does a position contain all that is necessary to
decide the outcome, when in fact the history might affect it as well?
For example, say that some endgame position is analyzed as containing a
forced mate in three for White (to move). But what if that position
was reached in a game with 49 previous moves qualifying under the Fifty
Move Rule, such that any move made by White would result in a draw if
the rule were invoked by Black?

For that matter, has it been proven that all theoretical endgame
positions are reachable under applicable anti-repetition and
anti-stasis rules?

Mark Adkins



Hi,

if you want to know more about tablebases, the following address might
be of some interest for you: http://www.aarontay.per.sg/Winboard/egtb.html

As far as I know, some endgame positions can only be won in more than
50 moves against the best defence.

Best regards,

Bruno

schrieb:
Can someone explain to me how a tablebase (e.g., supposedly deciding
all positions with seven pieces or less as wins for one player or the
other, or as draws) can fulfill this function given, for example, the
Fifty Move Rule? Does a position contain all that is necessary to
decide the outcome, when in fact the history might affect it as well?
For example, say that some endgame position is analyzed as containing a
forced mate in three for White (to move). But what if that position
was reached in a game with 49 previous moves qualifying under the Fifty
Move Rule, such that any move made by White would result in a draw if
the rule were invoked by Black?

The tablebases do not consider the 50-move rule.

wrote:
Can someone explain to me how a tablebase (e.g., supposedly deciding
all positions with seven pieces or less as wins for one player or the
other, or as draws) can fulfill this function given, for example, the
Fifty Move Rule?

The six-man tablebases are not, to the best of my knowledge, complete
yet, let alone seven-man.

I think but am not absolutely certain, that tablebases work like this.
The tablebase gives a score to each position with each player to move.
That score is positive if White wins, negative if Black wins and zero
if the position is drawn. In the case where the score is non-zero, it
is the number of moves (ply?) to checkmate. To use the tablebase, the
program looks up the score of the position after each legal move and
makes the move (or a move) with the best score which, for White, is
the lowest positive score or the most negative score, if there are no
scores of =0 (this corresponds to making Black find the longest
mate).

The tablebase does not actually store *all* positions but exploits
symmetry -- left/right reflection of the board, swapping colours and
possibly even more if there are no pawns on the board. So, for
example, the KP vs P tablebase only needs to consider the cases where
White has a pawn on the queenside. Positions where White's pawn is on
the kingside are just reflections and positions where Black has the
pawn are reflections with the colours swapped.


Does a position contain all that is necessary to decide the outcome,
when in fact the history might affect it as well? For example, say
that some endgame position is analyzed as containing a forced mate
in three for White (to move). But what if that position was reached
in a game with 49 previous moves qualifying under the Fifty Move
Rule, such that any move made by White would result in a draw if the
rule were invoked by Black?

This cannot happen. Whether or not we are in the tablebase depends
only on the material on the board. So, if the current position is in
the tablebases and the previous position was not, then the last move
must have been a capture or a pawn promotion, and the 50-move counter
is reset in both cases. The only possibility is that the last capture
or pawn more was 49 moves ago, from which point the tablebase said
`mate in 53 with best play by Black.' White may as well continue
playing from there because, if Black makes a sub-optimal move, White
might get to checkmate before the 50-move rule kicks in. I suppose
that tablebases with sufficient material in them will start to say
`And now White must make a pawn move for the sole purpose of avoiding
the 50-move rule.' (Which is to say, all moves apart from pawn moves
and captures will score zero to indicate that the opponent can just
claim a draw.)

Also, notice that the tablebases do not explicitly know about the
threefold repetition rule. They do know about it implicitly, though:
the fastest route to mate cannot involve repeating a position and if
you're trying to draw, repetitions are good for you.


For that matter, has it been proven that all theoretical endgame
positions are reachable under applicable anti-repetition and
anti-stasis rules?

It's easy to prove that they can't: consider the case where White has
pawns on a2, a3 and b2.


Dave.

--
David Richerby Accelerated Apple (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ tasty fruit but it's twice as fast!

David Richerby wrote:
wrote:
Can someone explain to me how a tablebase (e.g., supposedly deciding
all positions with seven pieces or less as wins for one player or the
other, or as draws) can fulfill this function given, for example, the
Fifty Move Rule?

The six-man tablebases are not, to the best of my knowledge, complete
yet, let alone seven-man.

Very well, then in responding to recent assertions in this newsgroup
about the abilities of tablebases, those assertions were erroneous.


I think but am not absolutely certain, that tablebases work like this.
The tablebase gives a score to each position with each player to move.
That score is positive if White wins, negative if Black wins and zero
if the position is drawn. In the case where the score is non-zero, it
is the number of moves (ply?) to checkmate. To use the tablebase, the
program looks up the score of the position after each legal move and
makes the move (or a move) with the best score which, for White, is
the lowest positive score or the most negative score, if there are no
scores of =0 (this corresponds to making Black find the longest
mate).

The tablebase does not actually store *all* positions but exploits
symmetry -- left/right reflection of the board, swapping colours and
possibly even more if there are no pawns on the board. So, for
example, the KP vs P tablebase only needs to consider the cases where
White has a pawn on the queenside. Positions where White's pawn is on
the kingside are just reflections and positions where Black has the
pawn are reflections with the colours swapped.


Does a position contain all that is necessary to decide the outcome,
when in fact the history might affect it as well? For example, say
that some endgame position is analyzed as containing a forced mate
in three for White (to move). But what if that position was reached
in a game with 49 previous moves qualifying under the Fifty Move
Rule, such that any move made by White would result in a draw if the
rule were invoked by Black?

This cannot happen. Whether or not we are in the tablebase depends
only on the material on the board. So, if the current position is in
the tablebases and the previous position was not, then the last move
must have been a capture or a pawn promotion, and the 50-move counter
is reset in both cases. The only possibility is that the last capture
or pawn more was 49 moves ago, from which point the tablebase said
`mate in 53 with best play by Black.' White may as well continue
playing from there because, if Black makes a sub-optimal move, White
might get to checkmate before the 50-move rule kicks in. I suppose
that tablebases with sufficient material in them will start to say
`And now White must make a pawn move for the sole purpose of avoiding
the 50-move rule.' (Which is to say, all moves apart from pawn moves
and captures will score zero to indicate that the opponent can just
claim a draw.)

Who says that the previous position was not in the tablebase? For
that matter, who says that the "previous position" wasn't reachable
from other games than the one in question?

The point remains: a tablebase cannot decide the outcome of a game
based solely on information present in a current position. And
tablebase statistics are often used in arguments claiming that chess is
solvable (and especially those which imply that it might be possible
for chess to be a win for either position from move 1 no matter what
the other side does). I have other reasons for believing this to be
false, and may post them at a future date.

Mark Adkins

schrieb:

The point remains: a tablebase cannot decide the outcome of a game
based solely on information present in a current position. And
tablebase statistics are often used in arguments claiming that chess is
solvable (and especially those which imply that it might be possible
for chess to be a win for either position from move 1 no matter what
the other side does). I have other reasons for believing this to be
false, and may post them at a future date.

The question *if* chess is solvable is not a question of belief:
1) In any state of the game, either side only has a limited number of
legal moves available.
2) In any state of the game, both sides have full information about it.
3) There is a precisely defined finite set of final states.

Therefore, chess is solvable, although we're talking about an impressive
amount of calculation and possibilities.

wrote:
David Richerby wrote:
Whether or not we are in the tablebase depends only on the material
on the board. So, if the current position is in the tablebases and
the previous position was not, then the last move must have been a
capture or a pawn promotion, and the 50-move counter is reset in
both cases. The only possibility is that the last capture or pawn
more was 49 moves ago, from which point the tablebase said `mate in
53 with best play by Black.' White may as well continue playing
from there because, if Black makes a sub-optimal move, White might
get to checkmate before the 50-move rule kicks in. I suppose that
tablebases with sufficient material in them will start to say `And
now White must make a pawn move for the sole purpose of avoiding
the 50-move rule.' (Which is to say, all moves apart from pawn
moves and captures will score zero to indicate that the opponent
can just claim a draw.)

Who says that the previous position was not in the tablebase?

I suggest you re-read my post. I covered the two possibilities,
namely that the previous position was in the tablebase (in which case,
the tablebase `knows' the value of the 50-move counter) and the case
in which it wasn't (where it knows the value of the 50-move counter is
zero because the last move was either a capture or a pawn promotion).


The point remains: a tablebase cannot decide the outcome of a game
based solely on information present in a current position.

Yes it can, as long as it is used properly. The proper use of a
tablebase is to start using it immediately when the material on the
board allows it. Let's imagine we're playing a game and I'm cheating
by using 3-man tablebases. I must start to use the tablebase as soon
as we get into a position where I have KP vs your K because, if I
don't, the tablebase might tell me to make a move that gives
three-fold repetition or I might have spent so long messing around
that I run over the fifty-move limit. However, if I started using the
tablebases as soon as we got to a position of KP vs K, they will work
perfectly.

Let's see why that is. Suppose the tablebase is used for the first
time to decide Black's move number N. It must be that White's move
number N was either a capture or a pawn promotion because, if it was
neither of these things, then White's Nth move would also have been
determined by tablebase lookups because the same material would have
been on the board. Now, in either case, capture or promotion, the
fifty-move counter is reset to zero (because it is fifty moves from
the last capture or pawn move) and there is no possibility that a
position from before White's Nth move can ever occur again because the
material on the board is different.

So, every time we are using tablebases, we know that the exact number
of moves since the last capture or pawn promotion and we know exactly
what positions have been seen before and might come up again. These
are, respectively, the number of moves since this tablebase was
entered and the set of positions that have been seen since this
tablebase was entered.


And tablebase statistics are often used in arguments claiming that
chess is solvable (and especially those which imply that it might be
possible for chess to be a win for either position from move 1 no
matter what the other side does). I have other reasons for
believing this to be false, and may post them at a future date.

If you are prepared to have a reasonable discussion on the matter, I
will happily explain to you why chess is, theoretically at least,
solvable. However, the last time we attempted to have such a
discussion, you became abusive, accusing me of being a `pseudo-
sentient' and stating that I `lie compulsively and habitually, from a
pathological contrarianism.'[1] Needless to say, I won't be wasting my
time again if we end up there.


Dave.

[1] http://tinyurl.com/b4l4j [--http://groups.google.com/...]

--
David Richerby Generic Chicken (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ farm animal but it's just like all
the others!

Mr. Richerby, thank you for your most informative posts on chess
ending tablebases. We could do with way more posts like yours
around here! 8)

David Richerby wrote:
I suggest you re-read my post. I covered the two possibilities,
namely that the previous position was in the tablebase (in which case,
the tablebase `knows' the value of the 50-move counter) and the case
in which it wasn't (where it knows the value of the 50-move counter is
zero because the last move was either a capture or a pawn promotion).

The point remains: a tablebase cannot decide the outcome of a game
based solely on information present in a current position.

Yes it can, as long as it is used properly. The proper use of a
tablebase is to start using it immediately when the material on the
board allows it. Let's imagine we're playing a game and I'm cheating
by using 3-man tablebases. I must start to use the tablebase as soon
as we get into a position where I have KP vs your K because, if I
don't, the tablebase might tell me to make a move that gives
three-fold repetition or I might have spent so long messing around
that I run over the fifty-move limit. However, if I started using the
tablebases as soon as we got to a position of KP vs K, they will work
perfectly.

Let's see why that is. Suppose the tablebase is used for the first
time to decide Black's move number N. It must be that White's move
number N was either a capture or a pawn promotion because, if it was
neither of these things, then White's Nth move would also have been
determined by tablebase lookups because the same material would have
been on the board. Now, in either case, capture or promotion, the
fifty-move counter is reset to zero (because it is fifty moves from
the last capture or pawn move) and there is no possibility that a
position from before White's Nth move can ever occur again because the
material on the board is different.

So, every time we are using tablebases, we know that the exact number
of moves since the last capture or pawn promotion and we know exactly
what positions have been seen before and might come up again. These
are, respectively, the number of moves since this tablebase was
entered and the set of positions that have been seen since this
tablebase was entered.

Major Cat wrote:
Mr. Richerby, thank you for your most informative posts on chess
ending tablebases. We could do with way more posts like yours
around here! 8)

You're welcome. For my next trick, I'll try to work out why I was
posting great screeds about computer chess to rgc.analysis. :-)


Dave.
--
David Richerby Natural Projector (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a 16mm film projector but it's
completely natural!

Raimund Klein wrote:
schrieb:

The question *if* chess is solvable is not a question of belief:
1) In any state of the game, either side only has a limited number of
legal moves available.
2) In any state of the game, both sides have full information about it.
3) There is a precisely defined finite set of final states.

4) The defined finite set of final states is complete.

If there are ways the game could be played that no final state is
reached, the game would be undecided. Therefore the assurance that every
possible move order leads to a final state must be included. In practise
this is forced by the repetition of position draw rule.

I'm not even sure if 1) or 2) are necessary if 3) and 4) are fulfilled.

Claus-Juergen