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