4
$\begingroup$

I was reading Jeff E's lecture notes on Algorithms when I came upon the following question:

Describe and analyze an efficient algorithm that determines, given a legal arrangement of standard pieces on a standard chess board, which player will win at chess from the given starting position if both players play perfectly. [Hint: There is a trivial one-line solution!]

My only thought is to form a tree of possibilities and go down every tree to see where it ends. But this is neither one line or efficient. Any help is appreciated(I prefer hints to full solutions, and I will accept a hint as an answer if it leads me to the answer).

$\endgroup$
3
$\begingroup$

When talking about standard chess with an $8\times 8$ board, there is no asymptotics, so you can solve the problem in $O(1)$ time.

Your idea works fine, since for each position the size of the tree is bounded by some constant independent of the input (the tree size is bounded by the number of possible positions). You can now ask whether this solution is feasible or has any practical implications? The answer is obviously no, but when analyzing the asymptotic complexity of the algorithm, this doesn't matter.

$\endgroup$
  • $\begingroup$ why is the size of the tree boundend? For example, I can take the same piece and move it back and forth forever and this seems as a legal move, therefore we have a tree that is infinite. Of course that if the players are playing "perfectly", such a move won't happen but how can you define what is a perfect move? I would love your explanation on this, thanks! $\endgroup$ – Mickey Jun 12 '17 at 19:35
  • $\begingroup$ We can agree to declare a game ends in a draw when repetitions occur. This will not affect the answer to the question "does black/white have a winning strategy in this position", as this allows you to focus on different branches without losing any information. In classic competitive chess, a player can demand a draw when the position is repeated three times. $\endgroup$ – Ariel Jun 12 '17 at 20:15
  • $\begingroup$ @Mickey Even without the threefold repetition rule, we can still solve this in $O(1)$, as the number of distinct board states is finite. We then do have some states for which optimal play would be 'livelocking', effectively drawing by forcing to be play an infinite game. But we're able to determine all losing and winning states, at least. $\endgroup$ – Discrete lizard Feb 22 '18 at 18:33

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.