Timeline for Checkmate in $\omega$ moves?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2012 at 0:35 | comment | added | Joel David Hamkins | Yes, agreed. In fact, Philip Schlicht and I are preparing a paper at the moment in which we prove that the mate-in-n problem is decidable, despite naive appearances that it might be something like $\Sigma_{2n}$ or $\Pi_{2n}$. One of us will post soon about that... | |
| Jan 23, 2012 at 0:23 | comment | added | Andreas Blass | Joel, I agree that "we have no reason to think that there is any hyperarithmetic full strategy, which works from any winning position" provided all we know is what I started my answer with --- recursiveness of the game tree. We might get a hyperarithmetic strategy if we use appropriate additional knowledge (which I certainly don't claim to have) specifically about chess . | |
| Jan 23, 2012 at 0:10 | comment | added | Joel David Hamkins | Ah, I was hung up on the fact that the overall strategy is asking $Pi^1_1$ questions---and so we would have no reason to think it is hyperarithmetic. Indeed, it does still appear that we have no reason to think that there is any hyperarithmetic full strategy, which works from any winning position. But your point is that if we should restrict it to the play from any particular winning position, then there is a hyperarithmetic strategy proceeding from that position, and so the omega one of chess is at most $\omega_1^{ck}$. Very nice! | |
| Jan 22, 2012 at 23:18 | comment | added | Andreas Blass | It pays to make mistakes. Apparently my edit, correcting my first answer, bumped the question to a visible place, where it got an upvote. | |
| Jan 22, 2012 at 23:14 | comment | added | Andreas Blass |
Stopping the induction at that stage $\alpha$, we'll have that $W_\alpha$ is hyperarithmetical. The ordinals at which nodes entered the union of the $W_\alpha$'s give the "number of moves" bounds for the original question. To get a hyperarithmetical winning strategy, I should have used slightly fancier $W_\alpha$'s, containing not only nodes from which White wins but, for each such node where it's White's turn to move, a pointer to a good move, with lower ordinal. Executive summary: The whole "computation" could be done in the first admissible set $L_{\omega_1^{CK}}$
|
|
| Jan 22, 2012 at 23:09 | comment | added | Andreas Blass |
After stabilization, $p$ will be in the union of the $W_\alpha$'s, because otherwise Black could win or draw or play forever by never moving into this union. The $W_\alpha$'s are the stages of an arithmetical, monotone, inductive definition (or they would be if I had remembered to put the elements of $W_0$ into all the later $W_\alpha$'s). Such an induction stabilizes in at most $\omega_1^{CK}$ steps, and any particular element that enters the $W_\alpha$'s does so at a stage $\alpha<\omega_1^{CK}$. In particular the root $p$ enters before stage `$\omega_1^{CK}$. Go to next comment.
|
|
| Jan 22, 2012 at 23:03 | comment | added | Andreas Blass |
Joel, I don't claim that the strategy from a won position $p$ is computable, but I do claim (until I see why I shouldn't) that it is hyperarithmetic. In the tree $T$ of plays starting from $p$, inductively define sets $W_\alpha$ of nodes as follows. $W_0$ consists of those terminal nodes where White has won. For $\alpha>0$, $W_\alpha$ consists of those nodes where either it is White's move and some child is in $\bigcup_{\beta<\alpha}W_\beta$ or it is Black's move and every child is in $\bigcup_{\beta<\alpha}W_\beta$. Continue until the process stabilizes, and go to the next comment.
|
|
| Jan 22, 2012 at 22:41 | comment | added | Joel David Hamkins | Andreas, I'm glad to hear that you agree with my objection. But I'm not sure that your new claim completely repairs the issue. If the strategy from a won position $p$ was computable, then I would agree that the ordinal rank of the resulting game tree (where white plays according to that computable strategy) would be a computable ordinal. But perhaps the winning strategy is not computable. In general, the best upper bound I know for this problem is at the level of $\Delta^1_2$, or slightly better: it is computable by infinite time Turing machines. | |
| Jan 22, 2012 at 22:34 | history | edited | Andreas Blass | CC BY-SA 3.0 |
added 419 characters in body
|
| Jan 22, 2012 at 22:31 | comment | added | Andreas Blass |
Joel, I think you're right. For any particular position p from which White has a forced win, there will be a recursive ordinal as I claimed, but as p varies, those ordinals could be cofinal in $\omega_1^{CK}$. As long as we're looking at the tree of moves from a particular p, there's an arithmetical monotone induction that marks the nodes where White wins, starting from the leaves and working toward the root. If White wins starting from p, that induction will eventually mark the root, and this happens at a recursive ordinal stage.
|
|
| Jan 22, 2012 at 20:40 | comment | added | Joel David Hamkins | Andreas, could you explain? I agree that the game tree of all possible plays from a given position is computable. But since this tree includes the bad moves as well as the good moves, it is in general not well-founded. The game value assignment would seem to require one to identify the well-founded nodes (or well-founded after having selected good moves from that position for the designated player), which would seem to have complexity $\Pi^1_1$. | |
| Apr 29, 2011 at 18:36 | history | answered | Andreas Blass | CC BY-SA 3.0 |