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 th

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.