7 ms·
Probably. I think it basically proves that any rule structured game without randomness is solvable.
by kenshaw 10y ago
Probably. I think it basically proves that any rule structured game without randomness is solvable.
- hyeonwho2 10y agoProbably still solvable with randomness. Add a few more layers of convolution networks.
- inimino 10y agoGames like go and chess are necessarily solveable by definition, right? If you mean solveable in our lifetimes, by current technology, that's something else entirely, and much less likely. Beating human players in go is like finding a good heuristic for an NP-complete problem. Solving 19*19 go is like proving P!=NP, i.e. we don't even have tools that can approach the problem.
- malteof 10y agoNot sure if this is true for Go. I'm not sure, but it seems to me that at some point a problem becomes "too complex" to solve. I.e. Go has about 2.08168199382×10^170 legal positions [1] and the number of atoms in the observable universe is only up to ~4×10^81. I don't know if there are some theorems, thoughts, philosophies about whether this means it can't be solved, but at least it must be extremely difficult. [1] https://en.wikipedia.org/wiki/Go_and_mathematics#Legal_positions https://en.wikipedia.org/wiki/Go_and_mathematics#Legal_posit...
- zachrose 10y agoWhile mind-boggling, I'm not sure it's generally meaningful to compare counts of actual things (even atoms) with counts of possible arrangements. The latter are in a world of their own[1]. [1] https://en.m.wikipedia.org/wiki/Orders_of_magnitude_(numbers) https://en.m.wikipedia.org/wiki/Orders_of_magnitude_(numbers...
- inimino 10y agoIn a theoretical sense, Go is certainly solvable, as we can easily construct a Turing machine that plays out every possible move, and provably terminates (given an appropriate ruleset). Practically, the universe will certainly be expected to terminate first. There may be other ways to solve the game, but we don't know what they are. Because we know it is theoretically solvable, we cannot rule out a practical approach to solving it by some mathematical magic even if we have no idea what that would look like. By analogy, we can prove many things about infinitely many integers by mathematical induction, but if we didn't have that technique, such proofs might seem impossible.
- nightcracker 10y agoThere is a trivial disproof of your claim. Two players write a turing machine with at most n states with two symbols. The player that produced a terminating turing machine that produces the most 1 symbols on the tape before terminating wins. The optimal strategy for this game is producing a busy beaver, a feat shown not to be computable.
- andorov 10y agoBut no one could play because you can't create a Turing machine that provably halts, no?
- SAI_Peregrinus 10y agoYou can prove that any given Turing machine halts or does not halt, but there's no single algorithm that can prove that for every Turing machine. The trivial case of a Turing machine that can be proven to halt is one with only one state: halted.
- dsp1234 10y agoThe trivial disproof still doesn't disprove anything about go and/or chess. Both chess and go have rules preventing repetition of moves (three fold repetition, and rule 8, respectively), and have a limited pool of possible future states. Therefore, there is no game of go or chess that does not halt. Thus, "Games like go and chess are necessarily solvable by definition, right?"
- andorov 10y agoYes but this case requires Turing machines that produce very very large (BB large) outputs and then halt. Is that provable for a specific machine?
- mafuy 10y agoAny specific machine can be proved to terminate or not terminate - albeit not always in ZFC. For instance, BB(10) can be computed, just as BB(10000) can, just that the latter cannot be computed in ZFC.