5 ms·
> Games like chess and GO are games of complete information. Its just a matter of brute processing power, even if currently computers don't have the processing
by nandemo 11y ago
> Games like chess and GO are games of complete information. Its just a matter of brute processing power, even if currently computers don't have the processing power to "solve" them.
That's like saying public-key encryption is broken because we can brute force decryption.
When we talk about solving a game (or solving an optimization problem, etc), we aren't simply interested in whether the problem is computable. We want a efficient, polynomial-time algorithm if we're interested in the generalized problem (the size of the board is a parameter), otherwise at least something that runs and completes in a reasonable time if we're OK with solving only a particular board size (an instance, in terms of computational complexity).
The generalized go problem is PSPACE-hard or EXPTIME-complete depending on the ruleset you adopt. So it's not just a matter of brute processing power.
Now, most people outside theoretical computer science research don't care much about generalized games and asymptotics, they're fine with solving 19x19 Go instead of n x n Go. But that doesn't help you much: the only board size that has been solved is 5x5 [0], and there are only about 10^10 legal positions in a 5x5 board. The standard 19x19 has 10^170 legal positions! Good luck brute forcing it.
[0] http://erikvanderwerf.tengen.nl/5x5/5x5solved.html http://erikvanderwerf.tengen.nl/5x5/5x5solved.html
- StanislavPetrov 11y ago>That's like saying public-key encryption is broken because we can brute force decryption. No, that's like saying that public-key encryption will eventually be broken because at the end of the day its just about having enough brute force processing. >When we talk about solving a game (or solving an optimization problem, etc), we aren't simply interested in whether the problem is computable. No we aren't. But games of complete information that ARE computable, such as chess and GO can be removed from discussion. There is no question that these games of complete information are "solvable" with or without AI, since every move, from start to finish, can be calculated before the game even begins - its just a matter of processing power. Which brings us to the question of AI and games of incomplete information. By definition full-ring no-limit hold-em is not computable. Even with infinite processing power, with every possible permutation calculated, there is no guarantee that a brute-force computer player is going to win full-ring no-limit hold-em. If there are multiple unknown players to act behind you, there is no way to compute with certainty what the outcome will be. This is where AI becomes really interesting as far as gaming is concerned.
- terryf 11y ago> No we aren't. But games of complete information that ARE computable, such as chess and GO can be removed from discussion. There is no question that these games of complete information are "solvable" with or without AI, since every move, from start to finish, can be calculated before the game even begins - its just a matter of processing power. In a theoretical universe, sure. In the one that we live in - no. Let's assume that we can turn every atom in the entire universe that we know of into a 4Ghz processor, further assume that we can perfectly parallelize the search and that we can check one board position in one cycle on one of those processors. How long would it take to check all possible 19x19 go positions? (1 * 10^80 processors) * (4 * 10^9 checks) = 10^89 checks per second. Total number of valid go board states: 10^170, therefore it would still take 10^79 seconds to check all the positions in order to find a perfect game. Clearly, it is not possible to ever brute-force go, no matter what kind of advances computing technology will take.