I see the phrase Theory of Chess often mentioned, but am not sure what it
means. Most often I hear that the "theory" is the result of experience of
games played, etc... But is this "theory"?

Is there a system that can produce rules, as in geometry? Are there ways of
proving things, even ones that are a bit loose, as a mathematical Proof by
induction in mathematics? (loose because inductive proof assumes the
excluded middle...) It seems obvious that chess is calculable (by a Turing
machine, to be very general), but is there a model of such a machine? Is
chess decidable? NP complete? Is it complete (in the sense of Godel)? Many
questions, but I hope this is the right forum.

Paolo

Paolo Pignatelli wrote:
I see the phrase Theory of Chess often mentioned, but am not sure what
it means. Most often I hear that the "theory" is the result of
experience of games played, etc... But is this "theory"?

I would say that theory is all the games that have been played and all the
analysis that has been done on positions. Of course, much of this theory
has been lost and the material that one person has access to is likely to
be different from the material that another has. So, opening theory could
be described as the analysis of the starting position of the game, as
influenced by games that have been played. Likewise, endgame theory is
what we know about the final stages of the game, when there are few pieces
on the board.

When people say that a move or position is `known in to the theory' or
something like that, they mean that it's been seen before, probably in a
master game or in analysis of one.


Is there a system that can produce rules, as in geometry?

Not that I'm aware of.


Is chess decidable?

Yes. There are only finitely many possible games of chess because of the
fifty-move rule so you can decide the best result a player can force from
a position just by trying out all the possible continuations, though this
requires infeasible copmutational resources.


NP complete?

No. NP is the class of decision problems that can be solved on a
nondeterministic Turing machine in time bounded by some polynomial in the
size of the input. For chess, any measure of the size of the input will
be bounded by 64 times the number of bits required to represent a
square. In other words, it's effectively constant, so it doesn't make
sense to ask how the difficulty of determining who's going to win depends
on the size of the position. That means that it doesn't really make sense
to ask if chess is in any computational complexity class, such as NP.

You could generalize chess to an nxn board, at which point, it's complete
for the class EXPSPACE[1], i.e., it requires time exponential in n on a
deterministic (`normal') machine. This is probably harder than NP but
nobody's yet managed to prove that NP and EXPTIME are different classes.
Everything in NP is in EXPTIME and most people in the field of computa-
tional complexity believe that EXPTIME is a strict superset of NP.

The thing is, knowing that generalized chess is EXPTIME-complete tells us
very little about the difficulty of calculating strategies in 8x8 standard
chess.


Is it complete (in the sense of Godel)?

Goedel completeness refers to proof system. A proof system is complete if
it can prove exactly all the true facts in a system. Since chess is not a
proof system, it doesn't make sense to ask if it's Goedel complete.


Dave.

[1] A.S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for
n*n chess requires time exponential in n, Proc. 8th Int. Coll.
Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293
and J. Comb. Th. A 31 (1981) 199-214.

--
David Richerby Expensive Old-Fashioned Composer (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a pupil of Beethoven but
it's perfect for your grandparents
and it'll break the bank!

"David Richerby" wrote in message
...

Dave.

Hear Hear!

David Richerby wrote:


Yes. There are only finitely many possible games of chess because of the
fifty-move rule [...]

This is not true, there are (countably) infinite possible chess-games,
since end-of-game via either the 50-move rule or threefold-repetition
must explicitly be claimed. If both players refuse to claim, the game
can go on forever.

A position where this is somewhat relevant is this:

FEN "1kb5/1p1p4/1P1P4/6p1/8/1p1p3P/1P1P4/1KB5 w - - 0 1"

Here, both players would be ill-advised to claim the draw-by-repetition,
since the opponent could (theoretically) make a fatal mistake. It is my
assertion that with best play, this game will last forever. Even if you
disagree, it is still true that there's nothing in the laws to make this
game end, if both players persist in not claiming the draw.

Best regards,

Sidney

"Sidney Cadot" wrote
David Richerby wrote:


Yes. There are only finitely many possible games of chess because of the
fifty-move rule [...]

This is not true, there are (countably) infinite possible chess-games,
since end-of-game via either the 50-move rule or threefold-repetition
must explicitly be claimed. If both players refuse to claim, the game
can go on forever.

A position where this is somewhat relevant is this:

FEN "1kb5/1p1p4/1P1P4/6p1/8/1p1p3P/1P1P4/1KB5 w - - 0 1"

Here, both players would be ill-advised to claim the draw-by-repetition,
since the opponent could (theoretically) make a fatal mistake. It is my
assertion that with best play, this game will last forever. Even if you
disagree, it is still true that there's nothing in the laws to make this
game end, if both players persist in not claiming the draw.

Best regards,

Sidney


this would still be decidable due to inevitability of repetition.

Herc

|-|erc wrote:
"Sidney Cadot" wrote

David Richerby wrote:



Yes. There are only finitely many possible games of chess because of the
fifty-move rule [...]

This is not true, there are (countably) infinite possible chess-games,
since end-of-game via either the 50-move rule or threefold-repetition
must explicitly be claimed. If both players refuse to claim, the game
can go on forever.

A position where this is somewhat relevant is this:

FEN "1kb5/1p1p4/1P1P4/6p1/8/1p1p3P/1P1P4/1KB5 w - - 0 1"

Here, both players would be ill-advised to claim the draw-by-repetition,
since the opponent could (theoretically) make a fatal mistake. It is my
assertion that with best play, this game will last forever. Even if you
disagree, it is still true that there's nothing in the laws to make this
game end, if both players persist in not claiming the draw.

Best regards,

Sidney



this would still be decidable due to inevitability of repetition.

You and I can see this is a draw, but there is no provision in the rules
to force the game to be finite (the LoC don't talk about 'decidable').

And the repetition is not strictly inevitable: the opponent could always
move his pawn.


Best regards,

Sidney

"Sidney Cadot" wrote in
|-|erc wrote:
"Sidney Cadot" wrote

David Richerby wrote:



Yes. There are only finitely many possible games of chess because of the
fifty-move rule [...]

This is not true, there are (countably) infinite possible chess-games,
since end-of-game via either the 50-move rule or threefold-repetition
must explicitly be claimed. If both players refuse to claim, the game
can go on forever.

A position where this is somewhat relevant is this:

FEN "1kb5/1p1p4/1P1P4/6p1/8/1p1p3P/1P1P4/1KB5 w - - 0 1"

Here, both players would be ill-advised to claim the draw-by-repetition,
since the opponent could (theoretically) make a fatal mistake. It is my
assertion that with best play, this game will last forever. Even if you
disagree, it is still true that there's nothing in the laws to make this
game end, if both players persist in not claiming the draw.

Best regards,

Sidney



this would still be decidable due to inevitability of repetition.

You and I can see this is a draw, but there is no provision in the rules
to force the game to be finite (the LoC don't talk about 'decidable').

And the repetition is not strictly inevitable: the opponent could always
move his pawn.


Best regards,

Sidney


there's only so many pawn moves. you can make 499 moves then move a pawn,
499 moves, move a pawn, 499 moves, move a pawn... and make your opponent
move his king back and forth 20,000 times. but eventually the game will
wind up into a 'repeating state', whether you'd consider that an outcome.

wouldn't number of moves be a variable to analyse chess algorithm complexity, although
the function result would not be a solved game rather the best via heuristic move.
play VS win.

then 'chess complexity' would be exponential, actually non deterministic polynomial being
open to parallel attack and only having to 'select' the right move to start.
i.e. worst case is exponential, best case is linear, the exact traits of NP.

Herc

there's only so many pawn moves. you can make 499 moves then move a pawn,
499 moves, move a pawn,

49!

Herc

Sidney Cadot wrote:
David Richerby wrote:
Yes. There are only finitely many possible games of chess because of
the fifty-move rule [...]

This is not true, there are (countably) infinite possible chess-games,
since end-of-game via either the 50-move rule or threefold-repetition
must explicitly be claimed. If both players refuse to claim, the game
can go on forever.

This is, strictly speaking, true, but the context is whether chess is
decidable. That is, is there an algorithm which takes as its input a
chess position and determines, assuming best play, that either white has a
forced win, black has a forced win or neither? The key point is the
assumption of best play.

If either side does have a forced win, that win must be of finite length
and it must not fall foul of the threefold repetition or fifty-move rules
because best play for the losing side would be to claim the draw. Further,
if either side does have a forced win, there must be a forced win that
does not involve a repetition of the position because, if one path to the
win goes through positions A, B, A and C, there is a shorter one that just
goes through A and C. This means that the algorithm can immediately
abandon any path in the game tree that leads to a repetition.

If neither side has a forced win, we may assume for these purposes that
they will just agree to the draw and spend eternity doing something more
productive.

So, while you are right that there are infinitely many games of chess,
there are only finitely many games with best play and those are the ones
we're interested in to prove decidability.


Dave.

--
David Richerby Adult Painting (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ Renaissance masterpiece that you won't
want the children to see!

|-|erc wrote:

"Sidney Cadot" wrote in

|-|erc wrote:

"Sidney Cadot" wrote


David Richerby wrote:




Yes. There are only finitely many possible games of chess because of the
fifty-move rule [...]

This is not true, there are (countably) infinite possible chess-games,
since end-of-game via either the 50-move rule or threefold-repetition
must explicitly be claimed. If both players refuse to claim, the game
can go on forever.

A position where this is somewhat relevant is this:

FEN "1kb5/1p1p4/1P1P4/6p1/8/1p1p3P/1P1P4/1KB5 w - - 0 1"

Here, both players would be ill-advised to claim the draw-by-repetition,
since the opponent could (theoretically) make a fatal mistake. It is my
assertion that with best play, this game will last forever. Even if you
disagree, it is still true that there's nothing in the laws to make this
game end, if both players persist in not claiming the draw.

Best regards,

Sidney



this would still be decidable due to inevitability of repetition.

You and I can see this is a draw, but there is no provision in the rules
to force the game to be finite (the LoC don't talk about 'decidable').

And the repetition is not strictly inevitable: the opponent could always
move his pawn.


Best regards,

Sidney



there's only so many pawn moves. you can make 499 moves then move a pawn,
499 moves, move a pawn, 499 moves, move a pawn... and make your opponent
move his king back and forth 20,000 times. but eventually the game will
wind up into a 'repeating state', whether you'd consider that an outcome.

Yes. A repeating state is not an outcome according to the rules, unless
someone claims (50m-rule or threefold repetition).

wouldn't number of moves be a variable to analyse chess algorithm complexity, although
the function result would not be a solved game rather the best via heuristic move.
play VS win.

then 'chess complexity' would be exponential, actually non deterministic polynomial being
open to parallel attack and only having to 'select' the right move to start.
i.e. worst case is exponential, best case is linear, the exact traits of NP.

I don't understand what you're trying to say here.

Best regards,

Sidney