# 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.
• @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. – Discrete lizard Feb 22 '18 at 18:33