Timeline for Decidability of chess on an infinite board
Current License: CC BY-SA 2.5
46 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 26, 2010 at 3:01 | comment | added | Dan Brumleve | Tsuyoshi, your interpretation of the strategy is basically correct. I deleted a previous comment which claimed that such a mod3 gadget is possible but now I think that it is not, and that translating by 2 squares is sufficient. This gadget would seemingly require a Knight but any translation would only alter the time of this Knight's migration by a constant amount. Without Bishops and Queens, translation by 1 square would be sufficient. | |
| Aug 25, 2010 at 19:50 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
better english
|
| Aug 25, 2010 at 12:39 | comment | added | Tsuyoshi Ito | As for the downvote, I do not think it is healthy to worry about it too much. People can upvote or downvote for various, sometimes pretty arbitrary, reasons. I can imagine that many users vote a post up just because a poster is famous or just because the poster sounds confident. Similarly, I can imagine that some (hopefully not many) users vote a post down just because someone says it is wrong or simply because the voter lacks the knowledge required to understand it. | |
| Aug 25, 2010 at 12:22 | comment | added | Tsuyoshi Ito | I am still unconvinced that your equivalence relation can be made well-defined. As you wrote, the parity sometimes matters. But is it the only thing that matter? For example, suppose that there are two clusters of pieces on the board which are very far from each other. If I translate one whole cluster by two squares, the new configuration should be equivalent to the old configuration if I understand your proof strategy correctly, but how can we be sure that there is no gadget to somehow constrain Black’s move on the i-th turns for i such that i mod 3 = 0? | |
| Aug 25, 2010 at 7:34 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
don't mix optimism with worst-case bounds, it is unclear
|
| Aug 25, 2010 at 7:26 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
italicize the important property
|
| Aug 25, 2010 at 7:19 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
the construction is vague because it's just an adjective to technique
|
| Aug 25, 2010 at 6:22 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
put "only" in the really right place
|
| Aug 25, 2010 at 6:11 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
say what "it" is
|
| Aug 25, 2010 at 6:01 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
put "only" in the right place
|
| Aug 25, 2010 at 5:53 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
grammar, move only
|
| Aug 25, 2010 at 5:40 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
clarify what i am trying to do
|
| Aug 25, 2010 at 5:32 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
fix grammar
|
| Aug 25, 2010 at 5:13 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
clarify annlulus
|
| Aug 25, 2010 at 4:48 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
doh i'm still not explaining the bound properly. wil try third paragraph again tomorrow.
|
| Aug 25, 2010 at 4:41 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
explain bound better
|
| Aug 25, 2010 at 2:26 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
remove third paragraph which i am no longer sure about
|
| Aug 25, 2010 at 1:56 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
make metaphor more explicit again
|
| Aug 25, 2010 at 1:34 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
give bound for board size
|
| Aug 25, 2010 at 1:26 | comment | added | Dan Brumleve | Now I believe I can equate the solution of any game on an infinite board with that of an equivalent game on some finite board with extra rules. If a King goes to a boundary square then the game is considered drawn. If any other piece goes to a boundary square then that piece is considered captured. In the general situation this finite board may be quite large compared to the number of pieces. | |
| Aug 25, 2010 at 0:17 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
include checkers
|
| Aug 25, 2010 at 0:06 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
make it clear that i am inventing new terms
|
| Aug 24, 2010 at 23:34 | comment | added | Dan Brumleve | Andrej, I tried to give a better definition of the equivalence in an earlier comment. I'm not sure how to state it more precisely without enumerating all the cases, but the important fact in constructing it is that there are two types of pieces: ultra-mobile which move in constant time, and para-mobile which move in linear time. By "structure" I just mean a tree labeled with positions, identity of the player to move, and extra data to classify final states (leaves of the tree) | |
| Aug 24, 2010 at 21:29 | comment | added | Dan Brumleve | Carl, thinking about the case of two Kings and a Rook again, it is apparent to me that an ordinary 8x8 chess board is large enough to contain the complete set of equivalences. To make the equivalence classes match the infinite board exactly, play with the additional rule that if Black puts his King on an edge or corner then the game is immediately called as a draw. This is a simpler alternative to what I described as "clipping" the solution but I'm not yet sure how to explain more complex piece combinations in terms of such an extra rule. | |
| Aug 24, 2010 at 20:07 | comment | added | Dan Brumleve | Carl, the algorithm would first solve this position on a sufficiently large board, and then clip the tree whenever a position contains a piece too close to an edge or corner. The clipped structure is equivalent to the solution of an infinite board. In this case all of White's checkmates would be clipped (because they require forcing Black to the edge), and the tree is finite, so the algorithm can return "no". | |
| Aug 24, 2010 at 11:41 | comment | added | Andrej Bauer | This looks to me like a very fuzzy suggestion on how one might be able to do something, but more likely not. There are too many unclarified concepts (structure, what structure? What equivalence classes precisely?), and my feeling is they can never be clarified. | |
| Aug 24, 2010 at 11:08 | comment | added | Carl Mummert | The more important issue for my own understanding of your solution is that I don't understand the algorithm, and in particular I don't understand the equivalence relation. I don't yet see how solving the game on larger and larger finite boards gives a solution for infinite boards. A test case is when black has only a king and white has only a rook and a king. Then white can force mate on any finite board, but not on an infinite board. How would your algorithm work (what exactly would it do) for a game that starts with just those three pieces scattered on the board? | |
| Aug 24, 2010 at 8:46 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
deleted 172 characters in body
|
| Aug 24, 2010 at 6:15 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
explain edits
|
| Aug 24, 2010 at 4:39 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
syntax, simplify; Post Made Community Wiki
|
| Aug 24, 2010 at 4:33 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
clarify
|
| Aug 24, 2010 at 4:26 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
cover more cases
|
| Aug 24, 2010 at 3:58 | comment | added | Dan Brumleve | You cannot create a universal machine nor emulate an arbitrary problem with a finite number of pieces. It must be encoded by the distance between pieces but the solution structure is only sensitive to a bounded amount of information about this distance table. | |
| Aug 24, 2010 at 2:09 | comment | added | Dan Brumleve | Carl, I don't understand what exactly is the input convention or why it matters? I am attempting to answer the question for all starting positions with a finite number of pieces. I consider the position not as a function from locations to pieces, but as a an injection from pieces (identities, not types) to locations. | |
| Aug 24, 2010 at 1:30 | comment | added | Tsuyoshi Ito | I had once voted this answer up because I thought that it was “obviously correct,” but I canceled my upvote because I realized that I cannot be sure about its correctness. It is plausible that your idea works, but I cannot tell whether it really works or not from this sketch. | |
| Aug 23, 2010 at 22:42 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
explain other pieces
|
| Aug 23, 2010 at 21:55 | comment | added | Dan Brumleve | I think a sketch is the only appropriate answer in this forum (short of a reference to a solution elsewhere) because a complete formal solution would take up too much space. I will continue to attempt to clarify the argument and if it is flawed I hope someone will indicate why. Not sure why I've been down-voted. | |
| Aug 23, 2010 at 21:11 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
correction
|
| Aug 23, 2010 at 21:06 | comment | added | Dan Brumleve | Or think about it this way: whenever it is to one player's advantage to continue increasing the variance of the position forever, the other player is willing to accept a draw. | |
| Aug 23, 2010 at 20:28 | comment | added | Dan Brumleve | Two positions are equivalent if we can cluster each of them into subpositions, separated from each other by a large distance, with identical subpositions and identical relevant geometric relationships between clusters. To the extent that we can emulate a traveling-salesman race or some such thing with Knights between distant clusters, we only need to know the distance between clusters to a certain relative precision, so we are always constrained by a finite number of pieces. | |
| Aug 23, 2010 at 20:13 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
clarify edge and corner cases
|
| Aug 23, 2010 at 11:06 | comment | added | Carl Mummert | This is an intriguing idea for a solution, but it's not precise enough to be a proof yet. For example, the input convention matters (see my answer) but the sketch doesn't refer to it. Do you have a formal definition of the equivalence relation in mind? | |
| Aug 23, 2010 at 2:57 | comment | added | Charles | Nitpick: the bishops are still limited in parity. | |
| Aug 23, 2010 at 2:34 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
clarify again
|
| Aug 23, 2010 at 2:22 | history | edited | Dan Brumleve | CC BY-SA 2.5 |
clarify
|
| Aug 23, 2010 at 2:12 | history | answered | Dan Brumleve | CC BY-SA 2.5 |