> You mentioned three proofs relating to go... could you post the links to the > papers?
the first two statements are consequences of the following: all two-person, finite, zero-sum games have solutions. * for a more precise statement, see john von neumann's 1928 paper: Von Neumann, J: Zur theorie der gesellschaftsspiele Math. Annalen. 100 (1928) 295-320 and the definitions of the terms used in the statement (*). or perhaps more helpfully, a modern treatment on the subject of game theory. the third statement is true simply because the minimax algorithm exists. i am not claiming that any of this has anything to do with the actual problem of beating a human. i am not making this claim because i also make the claim that beating humans at go is pretty much unrelated to the mathematics in these proofs. > I didn't ask for a mathematical proof saying if a computer can beat a human. > I asked in a roundabout way if this algorithm (or any known algorithm) has a > proven complexity that is somehow tractable or useful to beat humans. Just > by throwing human in does not mean you are out of the realms of math. What > about statistics? The object of many statistical models is a group of > people. So please don't say it makes no sense to ask about mathematical > proofs of anything related to humans. A mathematical proof can have a result > that affects humans. If it was proven tomorrow that there is a set of > algorithms that can solve the game in poly time.. we could draw relevant > conclusions with regards to beating a human being. Relating humans to math > does not destroy the accuracy of the relation. algorithms do not have complexities, problems do. algorithms may have asymptotic runtimes, but even this isn't always true. poly time doesn't mean tractable. just like exptime doesn't mean intractable. there's a coefficient in front of the polynomial (or exponential function) that can radically affect the real-world tractability of the problem. another thing is that complexity classes are used to describe problems like, "find me an algorithm that can solve the game of go for *any* sized board". in this sense, go is quite difficult. however, nobody on this list is seriously hoping to write a program to solve go for any sized board and hoping that it will succeed on a 19x19 board. what they are doing is trying to engineer very good programs to beat humans on a 19x19 board. > whether or not computers can beat humans at go on a > 19x19 board in a reasonable amount of time is unrelated > to mathematics. > > Why? Let's say you can prove that the game is solvable so that black wins. > Let's say that you can prove that it is solvable in linear time. You can > then infer that we could build a machine to play the solved game and beat a > human unconditionally. Why can't you use the math here to make a statement > about beating humans? what if the linear function is this one: time = 10^10^10^10^10^10^10 * (size of board) that doesn't imply tractability, but it is still linear. the problem that i mentioned earlier: "how much effort is required to completely solve the game of go for _any_ given boardsize" is known not to be linear. it's known not to be polynomial. the problem of "solve the game of go for a 19x19 board" is known to be a *constant*. since there are only a finite number of legal board situations, there are only a finite number of legal games. enumerating all of these takes a constant amount of time. storing these takes a constant amount of space. this is not useful to make good programs for playing go, however. the thing is, all of the talk of asymptotics that you seem to be referring to are perfectly useful to prove things about arbitrary games on arbitrary sized boards, but when you have a fixed-size board, what matters is much more an issue of engineering a fixed problem. s. > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
