Efficient Algorithm for determining who wins a game of Chess 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).
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.