2
$\begingroup$

Presume that a program memory only includes the current state for instance of a chess board. Does it need the variable which player, black or white, has the next turn to move or is it redundant recognizing the state?

Clearly its redundant during the first moves and then chess has so many combinations that there are combinations that can't guarantee that its deducible from just the state whether white or black has the next move, it needs that variable that wasn't needed during the first moves. How can I know the existence or non-existence of an algorithm in this case to know how the state went from deterministically knowable whether white or black has the next move to a state later in the game where the only possibility appears to keep a side variable to know whether white or black has the next move?

Is the logical consequence that I can't find a method to predict something like "making this move must activate a new boolean variable."

I'm trying to answer whether there is a method to know or just practically using the boolean variable blackHasNextMove to also include the information who is next to move for a chess game and there might be no method but in that case how do I prove that there is no method?.

Edit:

I'm asking how to know if changing a state from computable to unknown has an algorithm and I'm very thankful you even brought up the idea of time bounds for a solution using ordo notation.

$\endgroup$
  • 3
    $\begingroup$ I do not really understand the goal: If you know that at some point you'll need the new variable blackHasNextMove, what is the point of not using it from the beginning? If I am not mistaken, your question can be solved if one solves the following problem: Given the state of a chess board, find all the possible paths from the start state to the current state. Knowing all these paths, you know whether the next player to play is defined by the current state. This problem is thus clearly decidable (try all possibilities), but I do not see any way to solve it efficiently (say in polytime). $\endgroup$ – Bruno Aug 17 '11 at 7:58
  • 12
    $\begingroup$ Who has the next move when both sides have a pawn two steps away from its starting position? It would be a stupid move, but you cannot tell whether a player wasted two turns to get there (all other figures in the starting position). $\endgroup$ – Stefan Kratsch Aug 17 '11 at 8:01
  • 7
    $\begingroup$ I cannot understand the question well, but as far as I can tell, the current title does not describe your question and the current tags are simply irrelevant. Please try harder to come up with a more descriptive title and to search relevant tags. $\endgroup$ – Tsuyoshi Ito Aug 17 '11 at 12:59
  • $\begingroup$ It has to do with being verifiable and how paradoxical it seems that I need a variable and I can't prove when since I don't need the variable in the beginning, how can I prove I ever need it without a rule, just realizing that the variable "obviously" is needed since otherwise there is no way of knowing if you just find a chessboard in the middle of a game with just a state and no memory? $\endgroup$ – Niklas Aug 17 '11 at 15:17
  • 3
    $\begingroup$ IMHO this doesn't seem to be a research level question in theoretical computer science, please refer to the FAQ to understand the scope of cstheroy. $\endgroup$ – Kaveh Aug 17 '11 at 16:11
9
$\begingroup$

There is, in fact, a subcategory of chess problems, the goal of which is to determine whose turn it is to move in the given position. Examples here. So while you need the "who moved flag" in general, for all the reasons given above, it seems to me that classification of all types of positions where you don't need the flag is a genuine research problem. Another question:

Given a mover-determinable position in chess on an n by n board, what is the complexity of determining who moved?

So you might want to look at things like that, if you want a theoretical project out of the problem.

$\endgroup$
  • $\begingroup$ The complexity of finding whos move it is seems low, since you canbasically play the game backwards and there is a very high number of ways to do this for any position, but perhaps there are some special cases which are hard. $\endgroup$ – Joe Fitzsimons Aug 17 '11 at 14:16
  • 1
    $\begingroup$ @Joe: Yeah, how's this for a conjecture: it is PTIME computable (in n), regardless of the size of n? $\endgroup$ – Aaron Sterling Aug 17 '11 at 14:30
  • $\begingroup$ that would be my guess, and I would think simply playing the game backwards works most of the time, but I'm not exactly sure how you define nxn chess. $\endgroup$ – Joe Fitzsimons Aug 17 '11 at 15:05
  • $\begingroup$ Many thanks for the references and suggestions. It's excellent to see someone else phrased the problem too. I want to understand why I can't prove anything about this problem - only realizing that the variable is required. $\endgroup$ – Niklas Aug 17 '11 at 15:18
  • $\begingroup$ @Joe: For $n \times n$ chess, there is one king on each side, and the number of pawns, bishops, rooks and queens on each side grows as fractional powers of $n$. If there is no limit on the number of moves, generalized chess is EXPTIME-hard. Seminal paper here. On the other hand, if there is a polynomial bound on the number of moves (a reasonable generalization of real-world chess's 50 moves rule), then chess is only PSPACE-hard. It is also PSPACE-complete, though I don't have a reference for how it simulates QBF. $\endgroup$ – Aaron Sterling Aug 17 '11 at 18:06
6
$\begingroup$

As Stefan points out, the answer is that you cannot infer which player's move it is simply because of the state of the chess board. This is simply down to the fact that it is possible for certain pieces to reach a common position with either an odd or even number of moves. An example of this is advancing a pawn it's initial two steps. However even if you neglect such special moves (along with castling, etc.), the queen, bishops, rooks and king can all move to certain positions in either one or two moves. For a king this is simply the three sides of a triangle, where as for the others this is achieved simply by moving along a permitted line of travel twice (as the net result could have been achieved with a single move). Thus you do need to keep track of whos move it is.

As you ask also about how you could work out the answer to this problem, the key is simply to make the observation that if you could determine whos move it was from the configuration of the board, then each configuration must necessarily be reachable by only either odd or even moves. This then gives you a conjecture which is easy to disprove (in this case by counter example, though there are other approaches which could have been taken).

$\endgroup$
  • $\begingroup$ @thank you Joe. It might still be possible to foresee something like "if I make this move then it will be undeciable who did it" though that seems somewhat contradictory to since how can I make the move and change the state from deciable to undecidible? $\endgroup$ – Niklas Aug 17 '11 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.