<p>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.</p>

<p>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). </p>

CC BY-SA 3.0
2011-08-17T15:21:25.090Z
@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?
Niklas Rosencrantz
CC BY-SA 3.0
2011-08-17T12:52:22.290Z
2011-08-17T12:57:25.153Z
2011-08-17T12:57:25.153Z
Joe Fitzsimons
<p>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 <a href="http://anselan.com/tutorial.html">here</a>. 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 <em>don't</em> need the flag is a genuine research problem. Another question: </p>

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

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

CC BY-SA 3.0
2011-08-17T14:16:53.103Z
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.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-17T14:30:46.497Z
@Joe: Yeah, how's this for a conjecture: it is PTIME computable (in n), regardless of the size of n?
Aaron Sterling
CC BY-SA 3.0
2011-08-17T15:05:28.843Z
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.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-17T15:18:50.070Z
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.
Niklas Rosencrantz
CC BY-SA 3.0
2011-08-17T18:06:18.933Z
@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](http://www.springerlink.com/content/y87641531hp807h9/).  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.
Aaron Sterling
CC BY-SA 3.0
2011-08-19T07:11:06.820Z
@Joe: What do you mean by 'playing the game backwards'?  That seems as though it would instantly gives you an exponential blowup, for exactly the same reason that there's an exponential blowup going forwards; if you consider the positions of, e.g., a white and black knight on the board, then there are roughly $O(8^t)$ sequences of the previous $t$ moves that could take the two pieces to their position; playing a game backwards isn't all that different from playing it forwards.
Steven Stadnicki
CC BY-SA 3.0
2011-08-19T09:31:26.110Z
@Steven: Not so, in going backwards the order of the moves matters far less, and there are a very large number of ways of returning to the start position. Also, going backwards isn't a game, you get to move both sets of pieces in a coordinated fashion. I imagine a general rule of thumb that would work well is the following: put the rooks back first followed by the bishops, then the queen and king, then the pawns and finally the knights. If you get stuck, you can move a piece (other than a pawn) out of the way and then replace it on a subsequent move.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-19T09:34:05.610Z
@Steven: That seems to work for most situations. If you have a continuous wall of pawns, which prevents a piece from returning, but this is a special case, and it seems straight forward to get around.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-17T13:43:42.737Z
2011-08-17T13:43:42.737Z
Aaron Sterling
<p>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?</p>
<p>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?</p>
<p>Is the logical consequence that I can't find a method to predict something like &quot;making this move must activate a new boolean variable.&quot;</p>
<p>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?.</p>
<h3>Edit:</h3>
<p>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.</p>

CC BY-SA 3.0
2011-08-17T07:58:47.067Z
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).
Bruno
CC BY-SA 3.0
2011-08-17T08:01:47.213Z
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).
Stefan Kratsch
CC BY-SA 3.0
2011-08-17T12:59:33.113Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-17T15:17:13.940Z
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?
Niklas Rosencrantz
CC BY-SA 3.0
2011-08-17T16:11:38.360Z
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.
Kaveh
CC BY-SA 3.0
2016-05-07T07:47:48.463Z
@Kaveh Is there an algorithm? is a research question and that's what I asked. The difference between deterministic and non-deterministic problem-solving is still open. Do you agree?
Niklas Rosencrantz
CC BY-SA 3.0
2016-05-07T13:23:56.967Z
Please check out [help/on-topic] to understand the scope of cstheory.
Kaveh
<ds.algorithms><co.combinatorics><proofs><puzzles>
Can we infer the next player in chess from the current board configuration?
Niklas Rosencrantz
# Can we infer the next player in chess from the current board configuration?

(Asked by: username_0 on 2011-08-17)

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.

**Tags:** ds.algorithms, co.combinatorics, proofs, puzzles
> **Comments:**
> **username_1**: 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).  
> **username_2**: 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).  
> **username_3**: 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.  
> **username_0**: 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?  
> **username_4**: 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.  
> **username_0**: @Kaveh Is there an algorithm? is a research question and that's what I asked. The difference between deterministic and non-deterministic problem-solving is still open. Do you agree?  
> **username_4**: Please check out [help/on-topic] to understand the scope of cstheory.  

---

## 2 answers

### Answer by username_6 on 2011-08-17. Score: 9 | Accepted answer

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](http://anselan.com/tutorial.html). 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.

> **Comments:**
> **username_5**: 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.  
> **username_6**: @Joe: Yeah, how's this for a conjecture: it is PTIME computable (in n), regardless of the size of n?  
> **username_5**: 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.  
> **username_0**: 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.  
> **username_6**: @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](http://www.springerlink.com/content/y87641531hp807h9/).  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.  
> **username_7**: @Joe: What do you mean by 'playing the game backwards'?  That seems as though it would instantly gives you an exponential blowup, for exactly the same reason that there's an exponential blowup going forwards; if you consider the positions of, e.g., a white and black knight on the board, then there are roughly $O(8^t)$ sequences of the previous $t$ moves that could take the two pieces to their position; playing a game backwards isn't all that different from playing it forwards.  
> **username_5**: @Steven: Not so, in going backwards the order of the moves matters far less, and there are a very large number of ways of returning to the start position. Also, going backwards isn't a game, you get to move both sets of pieces in a coordinated fashion. I imagine a general rule of thumb that would work well is the following: put the rooks back first followed by the bishops, then the queen and king, then the pawns and finally the knights. If you get stuck, you can move a piece (other than a pawn) out of the way and then replace it on a subsequent move.  
> **username_5**: @Steven: That seems to work for most situations. If you have a continuous wall of pawns, which prevents a piece from returning, but this is a special case, and it seems straight forward to get around.  

---

### Answer by username_5 on 2011-08-17. Score: 6

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).

> **Comments:**
> **username_0**: @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?  

---

