Home 
Search 
Today's Posts 
#1




What is Theory of Chess?
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 
#2




What is Theory of Chess?
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 fiftymove 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 EXPTIMEcomplete 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) 278293 and J. Comb. Th. A 31 (1981) 199214.  David Richerby Expensive OldFashioned 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! 
#3




What is Theory of Chess?
"David Richerby" wrote in message ... Dave. Hear Hear! 
#4




What is Theory of Chess?
David Richerby wrote:
Yes. There are only finitely many possible games of chess because of the fiftymove rule [...] This is not true, there are (countably) infinite possible chessgames, since endofgame via either the 50move rule or threefoldrepetition 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 illadvised to claim the drawbyrepetition, 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 
#5




What is Theory of Chess?
"Sidney Cadot" wrote
David Richerby wrote: Yes. There are only finitely many possible games of chess because of the fiftymove rule [...] This is not true, there are (countably) infinite possible chessgames, since endofgame via either the 50move rule or threefoldrepetition 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 illadvised to claim the drawbyrepetition, 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 
#6




What is Theory of Chess?
erc wrote:
"Sidney Cadot" wrote David Richerby wrote: Yes. There are only finitely many possible games of chess because of the fiftymove rule [...] This is not true, there are (countably) infinite possible chessgames, since endofgame via either the 50move rule or threefoldrepetition 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 illadvised to claim the drawbyrepetition, 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 
#7




What is Theory of Chess?
"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 fiftymove rule [...] This is not true, there are (countably) infinite possible chessgames, since endofgame via either the 50move rule or threefoldrepetition 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 illadvised to claim the drawbyrepetition, 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 
#8




What is Theory of Chess?
there's only so many pawn moves. you can make 499 moves then move a pawn,
499 moves, move a pawn, 49! Herc 
#9




What is Theory of Chess?
Sidney Cadot wrote:
David Richerby wrote: Yes. There are only finitely many possible games of chess because of the fiftymove rule [...] This is not true, there are (countably) infinite possible chessgames, since endofgame via either the 50move rule or threefoldrepetition 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 fiftymove 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! 
#10




What is Theory of Chess?
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 fiftymove rule [...] This is not true, there are (countably) infinite possible chessgames, since endofgame via either the 50move rule or threefoldrepetition 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 illadvised to claim the drawbyrepetition, 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 (50mrule 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 