last edited by dshin
@cuikui I'm repeating myself a bit, but the result of the paper is not concerned with the number of possible moves or number of possible game states. You are right to note that these numbers are large, but the authors don't care about these numbers at all. They are not considering algorithms that try to compute these numbers.
Rather, they only consider game states where neither player has any more decisions to make. In MTGO terms, both players are essentially in "F6" mode. The question is, if we restrict ourselves to only those types of game states, is it possible to write an algorithm that determines who will win the game after the remaining forced actions and triggered effects are processed? The paper proves that the answer to this question is no.
To be very precise on what this means, consider the problem of adding two numbers, x and y. Here are 3 candidate algorithms (written in python) to solve this problem:
- algorithm1 will always return something. The problem is, that something is not always correct - it will output 4 as the sum of 1 and 2, which is incorrect.
- algorithm2 is better in some sense - it never returns an incorrect output. However, it has another problem - it sometimes runs forever, never returning anything. For instance, if you ask for the sum of 0 and 1, it recursively calls itself, which calls itself, etc., going into an infinite loop.
- algorithm3 gets the best of both worlds - it always returns something, and it never returns an incorrect value
The authors proved that if you consider the universe of all possible algorithms that accept a game state of Magic as input (even if we restrict ourselves to those "F6-mode" states where there are no more decisions left to be made by either player), and outputs a winner as output, then every single algorithm in that universe will be like algorithm1 or algorithm2 in my example. In other words, any such algorithm will either return an incorrect output on some inputs, or go into an infinite loop on some inputs. If someone tells you, "hey, I wrote a computer program that correctly outputs the winner given an F6-mode game state as input, without infinite-looping", that'd be like someone saying, "hey, I discovered an integer that is neither even nor odd!" It's simply a mathematical impossibility, a claim that can be rejected on its face, without even looking at the code.