Tablebases and decidability

Date: 30 Jan 2006 16:17:50
From: [email protected]
Subject: Tablebases and decidability

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?

k Adkins
[email protected]

Date: 08 Feb 2006 08:03:06
From:
Subject: Re: Tablebases and decidability

David Richerby wrote:
> <[email protected]> wrote:
> > Claus-J=FCrgen Heigl wrote:
> >> [email protected] wrote:
> >>> Who says that the previous position was not in the tablebase?
> >>
> >> For a problem to be decidedable means that it can be solved with finite
> >> means in a finite amount of time.
> >
> > This is not correct. Decidable means that there is a true/false answer
> > in the system being used. I think the word you are looking for is
> > computable.
>
> `Decidable' and `computable' are synonymous. There's no real
> distinction between problems with yes/no answers and function problems
> as you can always rephrase the question, `What's White's best move
> here?' as a sequence of questions, `Should White play 1.e4? Should
> White play 1.d4? ...' More generally, you can always rephrase it as a
> sequence of questions, `What's the first bit of the answer? What's
> the second? ...'
>
> The reason we focus on decision problems (yes/no answers) is that the
> theory is simpler and it still tells us all we want to know about
> function problems.
>
>
> Dave.
>
> --
> David Richerby Sadistic Lotion (TM): it's like a
> www.chiark.greenend.org.uk/~davidr/ soothing hand lotion but it wants to
> hurt you!

As generally used, decidability has nothing to to do with
computability. For example, Godel's famed theorems showed that
arithmetic is either undecidable or unsound.

But if you want to define it differently, that is OK.

Date: 09 Feb 2006 16:12:54
From: David Richerby
Subject: Re: Tablebases and decidability

<[email protected] > wrote:
> As generally used, decidability has nothing to to do with
> computability.

Incorrect, sorry.

`A problem whose language is recursive is said to be decidable.'
`... the _recursive sets_, which are those languages accepted by at
least one Turing machine that halts on all inputs.'
-- Hopcroft and Ullman, `Introduction to Automata Theory, Languages
and Computation'. Addison-Wesley, 1979.

`Let $M$ be a Turing machine such that, for any string $x\in\Sigma^*$,
if $x\in L$ then $M(x) =$ ``yes'' and if $x\notin L$ then $M(x) =$
``no''. Then we say that $M$ \emph{decides} $L$.'
-- Papadimitriou, `Computational Complexity'. Addison-Wesley, 1994.

`Membership in a recursive language is decidable: the computations of
a Turing machine that halts for all inputs provide a decision
procedure for determining membership.'
-- Sudkamp, `Languages and Machines.' 2nd Ed., Addison-Wesley, 1997.

`Church's Thesis... asserts that the recursive functions coincide with
the computable functions for _any_ reasonable ``abstract theory of
computation.'' '
-- Johnstone, `Notes on Logic and Set Theory'. CUP 1987.

`The halting problem is therefore called noncomputable or undecidable.'
-- Wikipedia article on `Computability theory'
http://en.wikipedia.org/wiki/Computability_theory_%28computer_science%29

Dave.

--
David Richerby Edible Voodoo Drink (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a refreshing juice beverage that has
mystical powers but you can eat it!

Date: 02 Feb 2006 07:23:10
From:
Subject: Re: Tablebases and decidability

Claus-J=FCrgen Heigl wrote:
> [email protected] wrote:
> > Who says that the previous position was not in the tablebase?
>
> For a problem to be decidedable means that it can be solved with finite
> means in a finite amount of time.

This is not correct. Decidable means that there is a true/false answer
in the system being used. I think the word you are looking for is
computable.

Date: 03 Feb 2006 12:28:26
From: David Richerby
Subject: Re: Tablebases and decidability

<[email protected] > wrote:
> Claus-J=FCrgen Heigl wrote:
>> [email protected] wrote:
>>> Who says that the previous position was not in the tablebase?
>>
>> For a problem to be decidedable means that it can be solved with finite
>> means in a finite amount of time.
>
> This is not correct. Decidable means that there is a true/false answer
> in the system being used. I think the word you are looking for is
> computable.

`Decidable' and `computable' are synonymous. There's no real
distinction between problems with yes/no answers and function problems
as you can always rephrase the question, `What's White's best move
here?' as a sequence of questions, `Should White play 1.e4? Should
White play 1.d4? ...' More generally, you can always rephrase it as a
sequence of questions, `What's the first bit of the answer? What's
the second? ...'

The reason we focus on decision problems (yes/no answers) is that the
theory is simpler and it still tells us all we want to know about
function problems.

Dave.

--
David Richerby Sadistic Lotion (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ soothing hand lotion but it wants to
hurt you!

Date: 03 Feb 2006 02:51:38
From: =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?=
Subject: Re: Tablebases and decidability

[email protected] wrote:
> Claus-J=FCrgen Heigl wrote:
>>
>>For a problem to be decidedable means that it can be solved with finite=

>>means in a finite amount of time.
>=20
> This is not correct. Decidable means that there is a true/false answer=

> in the system being used. I think the word you are looking for is
> computable.

My fault was that I mixed solvable with decidable which have a different =

meaning in computability theory.

Strictly speaking problems solved with finite means in finite time are a =

subset of the set of decidable problems. For determining if a problem is =

decidable infinite means (storage) are allowed, the time though has to=20
be finite. Computable means that there is no finite end in time where=20
the problem is solved, but there exists an algorithm that produces=20
partial solutions and it can't be decided if the solutions are complete.

For chess, you don't need infinite means as the number of possible=20
positions is limited and the number of moves in a position that connects =

to another position is limited also. You "just" have to build a=20
decision graph over a finite number of possible positions, this can be=20
constructed in a finite amount of time. That makes chess a decidable=20
problem which is a subset of computable problems.

Claus-Juergen

Date: 31 Jan 2006 18:02:54
From: [email protected]
Subject: Re: Tablebases and decidability

David Richerby wrote:
> [email protected] <[email protected]> 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.

k Adkins
[email protected]

Date: 02 Feb 2006 15:44:35
From: =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?=
Subject: Re: Tablebases and decidability

[email protected] wrote:
> Who says that the previous position was not in the tablebase?

For a position to be decided it is not relevant if the previous position
is stored in the tablebase. To decide the outcome of a position it is
only necessary to regard the possible positions that can arise out of
this position.

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

Again, this is irrelevant in regard of determining the outcome of a
certain position. To decide the game itself it is sufficient to have a
tablebase of the starting position. There are no previous positions of that.

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

A tablebase contains all information of all possible positions of a
certain material distribution and of all possible positions that can
arise out of them. This is sufficient to decide the outcome of a given
position covered by a tablebase.

> 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).

For a problem to be decidedable means that it can be solved with finite
means in a finite amount of time. It is long known that chess is
solvable in principle because it is has a finite amount of possible
states. Tablebases provide a method (an algorithm) to decide the outcome
of chess. Having a method does not imply any practibility. The current
wisdom is that there are too many states for the game of chess that it
can be solved using tablebases with practical means. For solving chess
with tablebases you need a storage that is approximately the size of
earth. This doesn't change the insight that in theory this method works.

Claus-Juergen

Date: 01 Feb 2006 11:25:55
From: David Richerby
Subject: Re: Tablebases and decidability

[email protected] <[email protected] > 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!

Date: 01 Feb 2006 12:50:17
From: Major Cat
Subject: Re: Tablebases and decidability

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.

Date: 02 Feb 2006 11:55:41
From: David Richerby
Subject: Re: Tablebases and decidability

Major Cat <[email protected] > 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!

Date: 02 Feb 2006 14:31:09
From: Major Cat
Subject: Re: Tablebases and decidability

David Richerby wrote:
>
> Major Cat <[email protected]> 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. :-)

Certainly not a capital offense... Besides, there is a very
close connection between the analysis of chess endings and
chess ending tablebase topics.

Date: 01 Feb 2006 08:43:53
From: Raimund Klein
Subject: Re: Tablebases and decidability

[email protected] 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.

Date: 02 Feb 2006 15:06:28
From: =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?=
Subject: Re: Tablebases and decidability

Raimund Klein wrote:
> [email protected] 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

Date: 02 Feb 2006 11:28:32
From: David Kane
Subject: Re: Tablebases and decidability

"Claus-J�rgen Heigl" <[email protected] > wrote in message
news:[email protected]...
> Raimund Klein wrote:
> > [email protected] 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.

Claiming a draw upon three-fold repetition or 50 moves
is not mandatory. The assumption of a final state requires
additional hypotheses about the motivations of the players.

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

Date: 03 Feb 2006 02:01:02
From: =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?=
Subject: Re: Tablebases and decidability

David Kane wrote:
> Claiming a draw upon three-fold repetition or 50 moves
> is not mandatory. The assumption of a final state requires
> additional hypotheses about the motivations of the players.

Yes, but this motivation is included in the question: "does chess have a =

solution?" meaning "does chess have a winner when both sides play the=20
best moves?".

The repetition rule is only an indecision breaker if claiming the draw=20
is mandatory. When determining if chess has a solution the repetition=20
rule is meant to be such. It makes sense to call the game a draw when=20
the best moves are a repetition of position.

Claus-J=FCrgen

Date: 03 Feb 2006 02:29:26
From: David Kane
Subject: Re: Tablebases and decidability

"Claus-J�rgen Heigl" <[email protected] > wrote in message
news:[email protected]...
>David Kane wrote:
>> Claiming a draw upon three-fold repetition or 50 moves
>> is not mandatory. The assumption of a final state requires
>> additional hypotheses about the motivations of the players.
>
>Yes, but this motivation is included in the question: "does chess
have a
>solution?" meaning "does chess have a winner when both sides play the
>best moves?".
>
>The repetition rule is only an indecision breaker if claiming the
draw
>is mandatory. When determining if chess has a solution the repetition
>rule is meant to be such. It makes sense to call the game a draw when
>the best moves are a repetition of position.

Sensible, yes, but not the rules of
chess. In general there is no guarantee
of reaching a position that is a final state
according to the rules (e.g. stalemate).

Chess games can also end for reasons
unrelated to the board position (e.g.
one side runs out of time). Imagine two
players in a "drawn" position, but both
valuing draws no higher than a loss
(e.g. they need a full point to get to
the prize, and 0 or 1/2 points are worth
nothing) In that case it would be irrational
to claim a draw and moves (so long as
they aren't losing in the time remaining)
become secondary to time.

Date: 03 Feb 2006 16:02:26
From: Major Cat
Subject: Re: Tablebases and decidability

David Kane wrote:
> >> Claiming a draw upon three-fold repetition or 50 moves
> >> is not mandatory.

Chess, in a game-theoretic framework, is a distillation of
the essential elements of competitive chess as reflected in
FIDE's rules and regulations. As such, it is an imperfect
model of actual competitive play.

>From a game-theoretic standpoint, the most efficient way to
deal with the issue of final states is to do away with FIDE's
"3-fold repetition" and "50-move" rules and adopt instead a
"first repetition" rule.

> >> The assumption of a final state requires
> >> additional hypotheses about the motivations of the players.

In game-theoretic terms, other than both sides ordinarily
being _required_ to play optimally (i.e., solvability), no.

> >
> >Yes, but this motivation is included in the question: "does chess
> >have a
> >solution?" meaning "does chess have a winner when both sides play the
> >best moves?".

This is, of course, the key question in game-theoretic terms.

> >
> >The repetition rule is only an indecision breaker if claiming the
> >draw
> >is mandatory. When determining if chess has a solution the repetition
> >rule is meant to be such. It makes sense to call the game a draw when
> >the best moves are a repetition of position.

Interestingly enough, the "repetition" rule ensures that no game
of chess goes on forever even if play is sub-optimal! Sub-optimal
play defeats, of course, the purpose of considering solvability as
the key question of game theory.

>
> Sensible, yes, but not the rules of
> chess. In general there is no guarantee
> of reaching a position that is a final state
> according to the rules (e.g. stalemate).
>
> Chess games can also end for reasons
> unrelated to the board position (e.g.
> one side runs out of time). Imagine two
> players in a "drawn" position, but both
> valuing draws no higher than a loss
> (e.g. they need a full point to get to
> the prize, and 0 or 1/2 points are worth
> nothing) In that case it would be irrational
> to claim a draw and moves (so long as
> they aren't losing in the time remaining)
> become secondary to time.

Yes, real "chessic" life is way richer than any game-theoretic
modelling approximation will ever be! 8 >)

Date: 06 Feb 2006 11:02:50
From: David Richerby
Subject: Re: Tablebases and decidability

Major Cat <[email protected] > wrote:
> Interestingly enough, the "repetition" rule ensures that no game
> of chess goes on forever even if play is sub-optimal!

No it doesn't. :-) Sub-optimal play may include not claiming a draw
when there is one to be claimed.

> Sub-optimal play defeats, of course, the purpose of considering
> solvability as the key question of game theory.

Not quite. (Strong) solvability requires a winning strategy for one
player even if the other does not play optimally.

Dave.

--
David Richerby Natural Dish (TM): it's like a fine
www.chiark.greenend.org.uk/~davidr/ ceramic dish but it's completely
natural!

Date: 06 Feb 2006 17:20:08
From: Major Cat
Subject: Re: Tablebases and decidability

David Richerby wrote:
>
> Major Cat <[email protected]> wrote:
> > Interestingly enough, the "repetition" rule ensures that no game
> > of chess goes on forever even if play is sub-optimal!
>
> No it doesn't. :-) Sub-optimal play may include not claiming a draw
> when there is one to be claimed.

Elsewhere in this thread it was stated that, for the purposes of
game-theoretic discussion, the "repetition" rule may be viewed as
mandatory in its application, certainly in contravention of FIDE
intent and practice! 8 >)

>
> > Sub-optimal play defeats, of course, the purpose of considering
> > solvability as the key question of game theory.
>
> Not quite. (Strong) solvability requires a winning strategy for one
> player even if the other does not play optimally.

This seems to be an interesting point. Before I respond, I would
kindly ask you for some working definition of strong solvability
as opposed, perhaps, to weak(?) solvability.

Date: 07 Feb 2006 11:04:56
From: David Richerby
Subject: Re: Tablebases and decidability

Major Cat <[email protected] > wrote:
> David Richerby wrote:
>> Major Cat <[email protected]> wrote:
>>> Sub-optimal play defeats, of course, the purpose of considering
>>> solvability as the key question of game theory.
>>
>> Not quite. (Strong) solvability requires a winning strategy for
>> one player even if the other does not play optimally.
>
> This seems to be an interesting point. Before I respond, I would
> kindly ask you for some working definition of strong solvability
> as opposed, perhaps, to weak(?) solvability.

Actually, I mis-spoke. The standard game-theoretic definitions of
`solved' are as follows:

determined: we know that one player must have a winning strategy from
the initial position.

ultra-weakly solved: we know which player has a winning strategy
from the initial position of the game.

weakly solved: we know what the winning strategy is from the initial
position.

strongly solved: we know a strategy for achieving the game-theoretic
result from any position.

We know that chess is determined. It's a finite two player game of
perfect information. For the purposes of this post, I'll mainly
assume that there are no draws in chess. This doesn't affect the game
theory because we can define two new games called White-chess and
Black-chess, which have the same rules as chess except that White wins
all `drawn' positions in white-chess and Black wins them in Black-
chess. Ordinary chess is a forced win for White if White wins
Black-chess, a forced win for Black if Black wins White-chess and a
forced draw if White wins White-chess and Black wins Black-chess.
(The alternative would be to define determined as meaning, `we know
that either one player must have a winning strategy or both players
have a drawing strategy' but that just makes the discussion longer.)

Chess would be ultra-weakly solved if we knew that, e.g., White has a
forced win from the initial position, without knowing how to actually
get the win. An example of an ultra-weakly solved game is chomp,
where we know that the first player must have a winning strategy but
have no idea what it is, except in some special cases.

Chess would be weakly solved if, in addition to knowing which player
has the forced win from the initial position and we know how to get
that win against any possible play, even sub-optimal play. So, when I
wrote `(Strong) solvability' above, I really meant `(Weak) solvabil
ity', though the statement is true as I wrote it.

Our strategy that weakly solves chess doesn't need to say anything
about positions that can't occur when the strategy is followed. For
example, if we prove that 1.e4 gives White a forced win, our strategy
must tell us what to play in response to any possibly moves by Black
but it doesn't need to tell us what to do when White plays 1.d4, even
if that would also be a forced win for White. Nor does it need to
tell us how White saves the draw in a drawn K vs KP ending because
White will never get there.

For strong solution, we need to know all of these cases. Our strategy
must tell us how to win all positions where best play wins and how to
draw all positions where best play draws. Strong solution requires us
to be able to play best-possible chess from any position, while weak
solution only requires us to be able to play best-possible chess from
the initial setup. If you like, weak solution lets you become world
champion; strong solution lets you become world problem-solving
champion, too.

Note that I've carefully avoided the use of the word `algorithm' so
far in this post: I've just stated that we know what the strategy is.
It's not required that the winning strategy be computable. Of course,
the case we're interested in, chess, is a finite game (at least, it is
in its game-theoretic analysis) so any strategy must be computable.
I've avoided bringing computability into things so far so that what I
say is still true of infinite games, where it's possible that there
are non-computable winning strategies. If we stick to chess, you can
think of a winning strategy as an algorithm for playing perfect chess.

Dave.

--
David Richerby Fluorescent Metal Chainsaw (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a lethal weapon that's made of
steel but it'll hurt your eyes!

Date: 07 Feb 2006 16:15:18
From: Major Cat
Subject: Re: Tablebases and decidability

Dave,

Thank you very much for your valuable contributions to this
thread. As we are progressively moving away from computer
science and getting deeper into game theory, it occurred to
me that we might need a brand new thread! I will start one
in rec.games.chess.misc entitled "Mathematical Modelling of
Chess Aspects" shortly. I hope to see you there. By the way,
I fully intend to revisit many of the points that you have
already made in the present thread. I also intend to subject
my proposed thread to frequent technical rants and tirades! 8 >)
Ether is rather forgiving. I hope that this will be the case
with some of the posters/lurkers as well...

David Richerby wrote:
>
> Major Cat <[email protected]> wrote:
> > David Richerby wrote:
> >> Major Cat <[email protected]> wrote:
> >>> Sub-optimal play defeats, of course, the purpose of considering
> >>> solvability as the key question of game theory.
> >>
> >> Not quite. (Strong) solvability requires a winning strategy for
> >> one player even if the other does not play optimally.
> >
> > This seems to be an interesting point. Before I respond, I would
> > kindly ask you for some working definition of strong solvability
> > as opposed, perhaps, to weak(?) solvability.
>
> Actually, I mis-spoke. The standard game-theoretic definitions of
> `solved' are as follows:
>
> determined: we know that one player must have a winning strategy from
> the initial position.
>
> ultra-weakly solved: we know which player has a winning strategy
> from the initial position of the game.
>
> weakly solved: we know what the winning strategy is from the initial
> position.
>
> strongly solved: we know a strategy for achieving the game-theoretic
> result from any position.
>
> We know that chess is determined. It's a finite two player game of
> perfect information. For the purposes of this post, I'll mainly
> assume that there are no draws in chess. This doesn't affect the game
> theory because we can define two new games called White-chess and
> Black-chess, which have the same rules as chess except that White wins
> all `drawn' positions in white-chess and Black wins them in Black-
> chess. Ordinary chess is a forced win for White if White wins
> Black-chess, a forced win for Black if Black wins White-chess and a
> forced draw if White wins White-chess and Black wins Black-chess.
> (The alternative would be to define determined as meaning, `we know
> that either one player must have a winning strategy or both players
> have a drawing strategy' but that just makes the discussion longer.)
>
> Chess would be ultra-weakly solved if we knew that, e.g., White has a
> forced win from the initial position, without knowing how to actually
> get the win. An example of an ultra-weakly solved game is chomp,
> where we know that the first player must have a winning strategy but
> have no idea what it is, except in some special cases.
>
> Chess would be weakly solved if, in addition to knowing which player
> has the forced win from the initial position and we know how to get
> that win against any possible play, even sub-optimal play. So, when I
> wrote `(Strong) solvability' above, I really meant `(Weak) solvabil
> ity', though the statement is true as I wrote it.
>
> Our strategy that weakly solves chess doesn't need to say anything
> about positions that can't occur when the strategy is followed. For
> example, if we prove that 1.e4 gives White a forced win, our strategy
> must tell us what to play in response to any possibly moves by Black
> but it doesn't need to tell us what to do when White plays 1.d4, even
> if that would also be a forced win for White. Nor does it need to
> tell us how White saves the draw in a drawn K vs KP ending because
> White will never get there.
>
> For strong solution, we need to know all of these cases. Our strategy
> must tell us how to win all positions where best play wins and how to
> draw all positions where best play draws. Strong solution requires us
> to be able to play best-possible chess from any position, while weak
> solution only requires us to be able to play best-possible chess from
> the initial setup. If you like, weak solution lets you become world
> champion; strong solution lets you become world problem-solving
> champion, too.
>
> Note that I've carefully avoided the use of the word `algorithm' so
> far in this post: I've just stated that we know what the strategy is.
> It's not required that the winning strategy be computable. Of course,
> the case we're interested in, chess, is a finite game (at least, it is
> in its game-theoretic analysis) so any strategy must be computable.
> I've avoided bringing computability into things so far so that what I
> say is still true of infinite games, where it's possible that there
> are non-computable winning strategies. If we stick to chess, you can
> think of a winning strategy as an algorithm for playing perfect chess.
>
> Dave.

Date: 03 Feb 2006 13:25:25
From: David Kane
Subject: Re: Tablebases and decidability

"Major Cat" <[email protected] > wrote in message
news:[email protected]...
>
> Yes, real "chessic" life is way richer than any game-theoretic
> modelling approximation will ever be! 8>)
>

That was my point. And I agree with you
that the "mathematical" chess you have
described is solvable.

Date: 03 Feb 2006 12:12:08
From: Raimund Klein
Subject: Re: Tablebases and decidability

David Kane schrieb:
> "Claus-J�rgen Heigl" <[email protected]> wrote in message
> news:[email protected]...
>
>>David Kane wrote:
>>
>>>Claiming a draw upon three-fold repetition or 50 moves
>>>is not mandatory. The assumption of a final state requires
>>>additional hypotheses about the motivations of the players.
>>
>>Yes, but this motivation is included in the question: "does chess
>
> have a
>
>>solution?" meaning "does chess have a winner when both sides play the
>>best moves?".
>>
>>The repetition rule is only an indecision breaker if claiming the
>
> draw
>
>>is mandatory. When determining if chess has a solution the repetition
>>rule is meant to be such. It makes sense to call the game a draw when
>>the best moves are a repetition of position.
>
>
>
> Sensible, yes, but not the rules of
> chess. In general there is no guarantee
> of reaching a position that is a final state
> according to the rules (e.g. stalemate).
>
> Chess games can also end for reasons
> unrelated to the board position (e.g.
> one side runs out of time). Imagine two
> players in a "drawn" position, but both
> valuing draws no higher than a loss
> (e.g. they need a full point to get to
> the prize, and 0 or 1/2 points are worth
> nothing) In that case it would be irrational
> to claim a draw and moves (so long as
> they aren't losing in the time remaining)
> become secondary to time.

Time is not an issue in the theory of the game. For viewing chess the
way we do here, only the game completions given in FIDE Article 5.1 a)
(checkmate), 5.2 a) (stalemate) and 5.2 d) (draw by repetition) should
be considered (with 5.2 d) mandatory, not activated by request, as
Claus-J�rgen already stated). (5.2 b) (dead positions) and 5.2 e) (50
move rule) are covered by either one of the other two drawing rules given.)

Date: 03 Feb 2006 16:14:21
From: Major Cat
Subject: Re: Tablebases and decidability

Raimund Klein wrote:
> > Sensible, yes, but not the rules of
> > chess. In general there is no guarantee
> > of reaching a position that is a final state
> > according to the rules (e.g. stalemate).
> >
> > Chess games can also end for reasons
> > unrelated to the board position (e.g.
> > one side runs out of time). Imagine two
> > players in a "drawn" position, but both
> > valuing draws no higher than a loss
> > (e.g. they need a full point to get to
> > the prize, and 0 or 1/2 points are worth
> > nothing) In that case it would be irrational
> > to claim a draw and moves (so long as
> > they aren't losing in the time remaining)
> > become secondary to time.
>
> Time is not an issue in the theory of the game. For viewing chess the
> way we do here, only the game completions given in FIDE Article 5.1 a)
> (checkmate), 5.2 a) (stalemate) and 5.2 d) (draw by repetition) should
> be considered (with 5.2 d) mandatory, not activated by request, as
> Claus-J�rgen already stated). (5.2 b) (dead positions) and 5.2 e) (50
> move rule) are covered by either one of the other two drawing rules given.)

Thanks for providing us with the exact references. Modelling
real life situations by logico-mathematical means has never
been a cakewalk...

Date: 03 Feb 2006 11:56:39
From: =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?=
Subject: Re: Tablebases and decidability

David Kane wrote:
> In general there is no guarantee
> of reaching a position that is a final state
> according to the rules (e.g. stalemate).
>
> Chess games can also end for reasons
> unrelated to the board position (e.g.
> one side runs out of time).
> In that case it would be irrational
> to claim a draw and moves (so long as
> they aren't losing in the time remaining)
> become secondary to time.

This is all true in a competition situation. But it is not important in
the question if chess has a solution in the mathematical sense, because
here there are no players. When regarding chess in this way it is
reasonable to change the rules in such a way that reaching a final state
is guaranteed. The only rule change that is needed is a repetition breaker.

Claus-Juergen

Date: 03 Feb 2006 16:09:47
From: Major Cat
Subject: Re: Tablebases and decidability

Claus-J�rgen Heigl wrote:
>
> David Kane wrote:
> > In general there is no guarantee
> > of reaching a position that is a final state
> > according to the rules (e.g. stalemate).
> >
> > Chess games can also end for reasons
> > unrelated to the board position (e.g.
> > one side runs out of time).
> > In that case it would be irrational
> > to claim a draw and moves (so long as
> > they aren't losing in the time remaining)
> > become secondary to time.
>
> This is all true in a competition situation. But it is not important in
> the question if chess has a solution in the mathematical sense, because
> here there are no players. When regarding chess in this way it is
> reasonable to change the rules in such a way that reaching a final state
> is guaranteed. The only rule change that is needed is a repetition breaker.

In this context, FIDE's present "50-move" rule is superfluous.
FIDE's "3-fold repetition" breaker is unnecessarily...generous.
Single repetition of a position will do! 8 >)

Date: 02 Feb 2006 15:03:12
From: David Richerby
Subject: Re: Tablebases and decidability

=?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?= <[email protected] > wrote:
> Raimund Klein wrote:
>> 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.

Or just say that all infinite plays are drawn.

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

2) is certainly necessary. Without it, we have to consider totally
random games like tossing a coin and there can be no `winning
strategy' in a game like that.

I've a feeling that 3) and 4) more or less implies 1) but they're rather
vaguely worded and I have a cold so I've not thought about it very
hard.

Dave.

--
David Richerby Poetic.com (TM): it's like an
www.chiark.greenend.org.uk/~davidr/ E-commerce portal but it's in verse!

Date: 03 Feb 2006 01:50:17
From: =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?=
Subject: Re: Tablebases and decidability

David Richerby wrote:
> =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?= <[email protected]> wrote:
>
>>Raimund Klein wrote:
>>
>>>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.

> Or just say that all infinite plays are drawn.

This is not so easy. How to determine that the play is infinite? Any
player could break the repetition pattern, if he choses so somewhere in
the future. It can not be decided beforehand if and when a player breaks
the pattern, but the possibility exists. When a player breaks the
repetition pattern, there can be other results than a draw. Therefore,
as long as you don't have a rule to limit the number of repetitions, the
game would be undecided.

>>I'm not even sure if 1) or 2) are necessary if 3) and 4) are fulfilled.
>
> 2) is certainly necessary. Without it, we have to consider totally
> random games like tossing a coin and there can be no `winning
> strategy' in a game like that.

No, incomplete information doesn't have to include randomness although
it can. Take for example the Kriegspiel. This is the game of chess,
where both players are allowed to see only their own pieces (it is
played on two boards with pieces of only one colour per board) and the
only information they get about the their opponents move is whether the
opponent put them in check or if he captured a piece. To prevent illegal
moves an arbiter is needed. Clearly a solution of the game exists
although no player has full information. The same holds for a card game
where the players both have incomplete information and even randomness
is included. The last example is Backgammon where both players have full
information but there is randomness. What those examples have in common
is a finite number of states the game can be in and clearly defined
rules of how to get from one state to another.

I'm also not sure if a limited number of game states is a necessary
condition for a game to be decidable. Take the game of Risk (new rules
edition). This is basically an unlimited game because every time new
armies are traded for cards the amount of fresh armies grows. The
infinity breaker is the fight rule that favors the attacker (attacker
rolls up to three dice, defender only two). There will be a point in the
game when it is very probable that the freshly traded in armies will
roll over anything else that is on the board. I'm pretty sure this game
is not going on forever with best play whatever the initial position.

> I've a feeling that 3) and 4) more or less implies 1) but they're rather
> vaguely worded and I have a cold so I've not thought about it very
> hard.

I think that 4) may be badly worded. What I meant is that the rules of
the game have to ensure that a final state is reached whatever the
moves. But this would define only the subset of games where there are
only a limited number of game states. If there are unlimited games which
are decidable, then 4) is not a necessary condition, but it is
sufficient (in the mathematical sense).

In this sense both 3) and 4) may not be necessary rules. I know a game
where rule making is the heart of the game. In the start there is a rule
which defines the process how new rules are introduced and some more
rules. (http://www.earlham.edu/~peters/nomic.htm) This game specifically
may not be decidable but I can imagine that there exists a game that is
decidable but has not entirely fixed rules.

Claus-Juergen

Date: 03 Feb 2006 12:20:56
From: David Richerby
Subject: Re: Tablebases and decidability

=?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?= <[email protected] > wrote:
> David Richerby wrote:
>> =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?= <[email protected]> wrote:
>>>Raimund Klein wrote:
>>>> 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.
>
>> Or just say that all infinite plays are drawn.
>
> This is not so easy. How to determine that the play is infinite?

Well, when we're at the point of considering infinite games, we're
being entirely theoretical anyway. So you determine that a play is
infinite after it has `finished' by observing that it has no last
state and no state in it is won for either player. You don't have to
look at the game in progress and say, ``Looks like this one's going to
be infinite.''

> Any player could break the repetition pattern, if he choses so
> somewhere in the future. It can not be decided beforehand if and
> when a player breaks the pattern, but the possibility exists. When a
> player breaks the repetition pattern, there can be other results
> than a draw.

As soon as one of these other results happens (i.e., checkmate), the
play is not infinite as it has a last state. On the other hand, every
infinite play must have at least one position that occurs infinitely
often (and, in particular, more than three times) and must have an
infinite sequence of consecutive moves including no captures or pawn
moves (and, in particular, must have such a sequence of more than
fifty such moves). So any infinite play must be claimable as a draw
under the rules of regular chess. Therefore, replacing the threefold
repetition and fifty move rules with a rule saying that infinite games
are drawn results in a game with exactly the same game-theoretic
properties as chess.

>>> I'm not even sure if 1) or 2) are necessary if 3) and 4) are
>>> fulfilled.
>>
>> 2) is certainly necessary. Without it, we have to consider totally
>> random games like tossing a coin and there can be no `winning
>> strategy' in a game like that.
>
> No, incomplete information doesn't have to include randomness although
> it can.

Exactly. I didn't say that randomness was required for imperfect
information; it's just that the simplest game of imperfect information
that came to mind was a random game so I used that as my example.

> Take for example the Kriegspiel. This is the game of chess, where
> both players are allowed to see only their own pieces (it is played
> on two boards with pieces of only one colour per board) and the only
> information they get about the their opponents move is whether the
> opponent put them in check or if he captured a piece. To prevent
> illegal moves an arbiter is needed. Clearly a solution of the game
> exists although no player has full information.

That depends on what you mean by `solution'. If you mean that every
game of Kriegspiel is finite, I agree. But it's by no means clear
that either player has a winning strategy (i.e., a sequence of moves
that wins against all possible plays by the opponent). Indeed, off
the top of my head, I think it likely that neither player has such a
strategy.

> The same holds for a card game where the players both have
> incomplete information and even randomness is included.

Ditto. Many (but not all) card games have the property that every
play is finite but, again, it's not clear that there are winning
strategies.

> The last example is Backgammon where both players have full
> information but there is randomness. What those examples have in
> common is a finite number of states the game can be in and clearly
> defined rules of how to get from one state to another.

Actually, backgammon isn't a very good example here as it's possible
(albeit with probability zero) for a backgammon play to be infinite so
it's not guaranteed that either player will win.

> I'm also not sure if a limited number of game states is a necessary
> condition for a game to be decidable.

That depends on what you mean by `decidable'. To a game theorist, it
would probably mean that the player who has a winning strategy has a
one that can be implemented by a Turing machine. In that sense, any
finite game is decidable.

I suspect you mean that every game must end in one of the terminal
states. (In chess, these would be checkmate and stalemate positions
and plays ending in draw claims by the threefold repetition and
50-move rules.) I'm not sure if there's a game-theoretic name for
that kind of game but let's call them `decisive' games. So, in this
sense, chess, Kriegspiel and many card games are decisive; other card
games and backgammon are not.

There are decisive games with infinite state spaces. A simple example
is the game where we both guess an integer and I win if we guess the
same number and you win otherwise. There are infinitely many states
-- all pairs (my number, your number) -- but every game ends after
exactly one move.

There are also decisive games that go on infinitely long. Chess with
the `infinite plays are drawn' rule is an example of this.

> Take the game of Risk (new rules edition). [...] I'm pretty sure
> this game is not going on forever with best play whatever the
> initial position.

I don't know anything about Risk so I can't comment on that particular
case. What I can say, though, is that there might not be any `best
play' in a game of imperfect information.

>> I've a feeling that 3) and 4) more or less implies 1) but they're
>> rather vaguely worded and I have a cold so I've not thought about
>> it very hard.
>
> I think that 4) may be badly worded. What I meant is that the rules
> of the game have to ensure that a final state is reached whatever
> the moves. But this would define only the subset of games where
> there are only a limited number of game states.

The main vagueness is this use of the word `limited'. Is it supposed
to mean `finite', for example?

> If there are unlimited games which are decidable, then 4) is not a
> necessary condition, but it is sufficient (in the mathematical
> sense).

There are games with infinite (even uncountable) state spaces that are
`determined'. This means that they are not only decisive but one of
the players has a winning strategy.

> I know a game where rule making is the heart of the game. In the
> start there is a rule which defines the process how new rules are
> introduced and some more rules. (http://www.earlham.edu/~peters/nomic.htm)
> This game specifically may not be decidable but I can imagine that
> there exists a game that is decidable but has not entirely fixed
> rules.

I've not looked into nomic in detail but I'm pretty sure it's non-
terminating. That said, mathematics can't say anything interesting
about nomic because there's no requirement that the new rules be
expressed in any formal language. Even if there were such a
requirement, the whole point of the game is that that rule could be
changed.

Dave.

--
David Richerby Accelerated Happy Umbrella (TM):
www.chiark.greenend.org.uk/~davidr/ it's like an umbrella that makes your
troubles melt away but it's twice
as fast!

Date: 02 Feb 2006 16:37:57
From: Raimund Klein
Subject: Re: Tablebases and decidability

David Richerby schrieb:
> =?ISO-8859-1?Q?Claus-J=FCrgen_Heigl?= <[email protected]> wrote:
>
>>Raimund Klein wrote:
>>
>>>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.
>
> Or just say that all infinite plays are drawn.
>
>>I'm not even sure if 1) or 2) are necessary if 3) and 4) are fulfilled.
>
> 2) is certainly necessary. Without it, we have to consider totally
> random games like tossing a coin and there can be no `winning
> strategy' in a game like that.
>
> I've a feeling that 3) and 4) more or less implies 1) but they're rather
> vaguely worded and I have a cold so I've not thought about it very
> hard.

It was not my intention to give a full proof as in Theoretical Computer
Science here, so the given premises might be redundant. Yet, they're
absolutely *not* "vaguely worded". I only remembered from the AI
lectures that this kind of properties (including the one that
Claus-J�rgen gave, which I had actually missed - thanks for that) imply
that a game is solvable.

Date: 03 Feb 2006 10:48:02
From: David Richerby
Subject: Re: Tablebases and decidability

Raimund Klein <[email protected] > wrote:
> David Richerby schrieb:
>>> Raimund Klein wrote:
>>>> 1) In any state of the game, either side only has a limited number
>>>> of legal moves available.
>>
>> I've a feeling that 3) and 4) more or less implies 1) but they're rather
>> vaguely worded and I have a cold so I've not thought about it very
>> hard.
>
> It was not my intention to give a full proof as in Theoretical Computer
> Science here, so the given premises might be redundant. Yet, they're
> absolutely *not* "vaguely worded".

Um, yes they are. When you say ``a limited number'', what is the
limit? Is it necessarily finite, for starters?

Dave.

--
David Richerby Solar-Powered Simple Dictator (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a totalitarian leader but
it has no moving parts and it doesn't
work in the dark!

Date: 03 Feb 2006 12:03:06
From: Raimund Klein
Subject: Re: Tablebases and decidability

David Richerby schrieb:
> Raimund Klein <[email protected]> wrote:
>
>>David Richerby schrieb:
>>
>>>>Raimund Klein wrote:
>>>>
>>>>>1) In any state of the game, either side only has a limited number
>>>>> of legal moves available.
>>>
>>>I've a feeling that 3) and 4) more or less implies 1) but they're rather
>>>vaguely worded and I have a cold so I've not thought about it very
>>>hard.
>>
>>It was not my intention to give a full proof as in Theoretical Computer
>>Science here, so the given premises might be redundant. Yet, they're
>>absolutely *not* "vaguely worded".
>
>
> Um, yes they are. When you say ``a limited number'', what is the
> limit? Is it necessarily finite, for starters?

"Limited", in this context, means finite, yes (after all, we're talking
about natural numbers, so a limited set will always be finite). What the
concrete limit is can be determined by looking at the position and
considering the FIDE Laws of Chess, Article 3.

Date: 31 Jan 2006 12:09:45
From: David Richerby
Subject: Re: Tablebases and decidability

[email protected] <[email protected] > 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!

Date: 31 Jan 2006 09:47:31
From: Raimund Klein
Subject: Re: Tablebases and decidability

Date: 31 Jan 2006 00:31:50
From: ZucchiniMann
Subject: Re: Tablebases and decidability

[email protected] 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?
>
> k Adkins
> [email protected]
>

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