News for hackers. Stuff that matters.
Re:Algorithms Course Materials by Ntrails on Monday July 01, 2013 @07:23AM (#5969886)
"Describe and analyze an 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"

Ok, but [Hint: There is a one-line solution!]

Am I missing something obvious like "it's always a draw"?

Re:Algorithms Course Materials by algorias on Monday July 01, 2013 @10:23AM (#5970803)
You're missing that there is no need for the algorithm to be anywhere close to efficient. Just searching the whole game tree recursively will do it. Remember the draw rules in chess: if no one eats a figure for 50 turns or so, the game ends. Therefore, the game tree is actually of finite height, and the naive algorithm will eventually terminate.