3 ms·
"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
by Ntrails 13y ago
"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"?
- algorias 13y agoYou'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.