Christian

deleted by creator

You don’t necessarily need to. There’s a possibility of defining instructions for winning without that. The idea may just be hard to imagine because chess is complicated.

You can make up stupid examples of games that defy this. Maybe we dream up a game with an ungodly number of states that has an action X that is an available option every turn. If the winning strategy is just “player 1 chooses action X every turn”, you can imagine there may be a way to show that’s true without needing to simulate every single state, and there’s certainly a way to easily store and communicate this strategy.

For a ludicrously dumb win condition, maybe the first playet to press X 10,000,000 times wins, in spite of having lots of other options each turn which introduce lots of other gamestates. You should be able to show that pressing X every turn is a winning strategy without computing every potential state. This can be true of more complicated games too, it would just be much less obvious. Just because no one has conceived of a way to do that yet with a game such as chess doesn’t mean no one ever will.

Still considering the magnitude of the numbers we’re talking about - this would still be a mind boggling undertaking.

Nowhere near to the degree you seem to think. If you want your computer to output a number in binary that has 10¹²⁰ digits, it sounds completely ludicrous, but if every digit is ‘0’, then a computer program to generate that number will take up virtually no space at all relative to storing each digit directly.

The algorithm is just outut ‘0’ 10¹²⁰ times and then halt, so the only difficult part is storing the 10¹²⁰. (This is trivial for literally 10¹²⁰, I’ve already described it in six characters counting the exponentiation operator, but let’s imagine it’s actually a similar-sized number that’s less friendly.) The number can be described in log_2(10¹²⁰) = 120log_2(10) bits, which is somewhere between 360 and 480 bits and can probably still be compressed more. So you’ve represented a binary number with 10¹²⁰ digits with a program that says repeat the digit ‘0’ and stop after you’ve done it x number of times, where x is a specific number that takes up like 400 bits of storage, probably less. That program can fit on a floppy disk, while the original 10¹²⁰-bit string itself is a bit too big.

So that’s an extremely simple example, but it shows that there exist 10¹²⁰-bit numbers that can fit on a floppy disk.

More generally, a massive amount of strings with 10¹²⁰ letters will have some pattern that can be exploited by a program requiring relatively minimal storage. The ones that don’t have a very high degree of randomness, but that’s extremely unlikely (I’m inclined to guess impossible) to be true of a string solving a real-world problem like chess games. Finding such an algorithm for your string though could be a herculean task.

I edited this comment about 500 times to make it readable and I feel inclined to apologize to everyone who saw this before it was done.

deleted by creator

I’m splitting hairs here, but wouldn’t the 10^96 number just need to be a bound on the Kolmogorov complexity, whose value would be uncomputable? I don’t think it’s possible (even theoretically) to conclude solution storage is impossible, it’s possible the Kolmogorov complexity is astonishingly low and there’s an algorithm that could be stored on a drive today. It would just require brilliant insight to find it and no one is going to devote time to that for a variety of reasons, one of which is that unless they’ve successfully finished the task of finding such an algorithm there’s no way to know if they’re searching for something that doesn’t exist.

deleted by creator