3 ms·

Its just blatantly false to suggest that this victory means "games are solved". Games like chess and GO are games of complete information. Its just a matter of

Its just blatantly false to suggest that this victory means "games are solved". 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. Games of incomplete information, like poker, are much harder, if not impossible for computers to master without actual AI. It was only recently that heads-up, limit poker was "solved". Even in this case, the "solution" meant only that the computer could put forth a strategy that would not lose significantly over time, not a winning strategy. Games like no-limit hold em are infinitely more complex. This is true of heads-up, but vastly more so for full-ring games. AlphaGo's victory has certainly been very impressive, but its also predictable. Given enough computing power, winning any game of complete information is just a matter of brute computing force. We'll see how computers (and real AI) can do in the future in regards to other games.

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.
    - 11y ago
im3w1l 11y ago
> impossible for computers to master without actual AI Many times before, claims like this have been disproved.
- xigency 11y ago
  There is a difference between going unproved and being disproved.
lazyant 11y ago
> Given enough computing power, winning any game of complete information is just a matter of brute computing force. If by "brute force" you mean exploring all possible moves then in theory yes, in practice the computing power and time is larger than the universe for chess or go, so no.
leni536 11y ago
> Even in this case, the "solution" meant only that the computer could put forth a strategy that would not lose significantly over time, not a winning strategy. It's even true for rock-paper-scissors and the "solution" is trivial, and there is no better strategy. The lack of winning strategy can be the property of the game itself. It's entirely not trivial if a "winning strategy" to a game like poker even exists.

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.
  - 11y ago

im3w1l 11y ago

> impossible for computers to master without actual AI Many times before, claims like this have been disproved.

xigency 11y ago
There is a difference between going unproved and being disproved.

lazyant 11y ago

> Given enough computing power, winning any game of complete information is just a matter of brute computing force. If by "brute force" you mean exploring all possible moves then in theory yes, in practice the computing power and time is larger than the universe for chess or go, so no.

leni536 11y ago

> Even in this case, the "solution" meant only that the computer could put forth a strategy that would not lose significantly over time, not a winning strategy. It's even true for rock-paper-scissors and the "solution" is trivial, and there is no better strategy. The lack of winning strategy can be the property of the game itself. It's entirely not trivial if a "winning strategy" to a game like poker even exists.