4 ms·

You should probably wait for an AMA with someone who's actually an expert in AI, and ask them this question. Since you asked me, though, I did a quick Google s

You should probably wait for an AMA with someone who's actually an expert in AI, and ask them this question. Since you asked me, though, I did a quick Google search and found the following paper: https://arxiv.org/pdf/1711.09667.pdf https://arxiv.org/pdf/1711.09667.pdf where indeed they use machine learning to induce the rules of chess from a large number of played games (and then learn to play better than any human). It doesn't surprise me at all that this would be feasible with current tools, although I haven't studied the paper yet, and would be curious to know how many games you need before you've learned all the rules around, e.g., castling, en passant, promotion of pawns, and perpetual check. My guess is that for a machine to learn the rules of the games of love and politics will take somewhat longer. :-)

YeGoblynQueenne 8y ago
>> where indeed they use machine learning to induce the rules of chess from a large number of played games (and then learn to play better than any human). They didn't induce the rules of chess! What they did was learn an evaluation function for chess moves, from scratch, i.e. without giving it the rules or any hand-crafted features. So they learned a classifier for good/bad board states, which was later used in an alpha-beta minimax search. However, the classifier didn't learn the rules of the game, only a mapping from board positions to labels, good/bad. This is not made explicit in the text, but minimax typically has a rule-base to generate moves as successor states for the search; so the rules of the game were hand-crafted, but did not contribute to the learning of the evaluation function. It's extremely hard to induce a set of rules with neural nets, or indeed any statistical machine learning algorithm. I mean, imagine representing the rules of chess as a function; let alone trying to learn that function from data. (Full disclosure: I study algorithms that learn rules from data; they're not neural nets).
- ScottAaronson 8y ago
  Aha, thanks for that extremely useful clarification! I was also confused from the abstract and intro about exactly what the inputs and outputs were. Yes, the clear impression was created that they learned the rules---in the sense that they could then generate moves that would (usually? almost always?) obey the rules---when it sounds like really they just learned an evaluation function that encodes lots of implicit knowledge about the rules, of course, but that still requires a piece of code that knows the rules explicitly as a "guardrail" when generating moves. Since you obviously know this subject, what are the best current results in the direction of inducing the rules of chess from played games?
  - ScottAaronson 8y ago
    On further thought, we should distinguish two problems: (1) "Induce" the rules, in the sense that after training on millions of played games, you now have a neural net or whatever that plays mostly or entirely according to the rules even though it can't articulate them. (2) Output an explicit description of the rules. I could easily believe that (2) is beyond the current abilities of AI, even if it turns out that (1) is doable.
    - YeGoblynQueenne 8y ago
      >> Since you obviously know this subject, what are the best current results in the direction of inducing the rules of chess from played games? To be honest, I don't think there's much work on inducing the rules of chess, in particular. It's probably considered a) easy enough to do by hand and b) too hard to machine-learn. >> On further thought, we should distinguish two problems: (1) - Yep. The most likely approach would be a classifier trained to label moves as legal/ illegal. The resulting model would be a vector of numerical parameters so not a traditional rule base. It would also only be correct within some margin of error, probably not 0, limiting its uses (e.g. it wouldn't make sense to train it to play and then pit it against a player with a correct rulebase; they wouldn't be playing the same game). >> I could easily believe that (2) is beyond the current abilities of AI, even if it turns out that (1) is doable. Also yes. Exactly on point in fact. When we're talking about learning rules, we 're talking about learning automata, the subject of inductive inference, an older branch of machine learning (well, ish) that fell out of favour after a bunch of theoretical results showed it was basically impossible to learn any interesting class of automata from examples (the most famous is Mark E. Gold's result from Language Identification in the Limit; only finite languages can be learned from finite examples, anything else is only learnable "in the limit", from infinitely many examples, or an all-knowning oracle, etc). Modern machine learning starts with Valiant's A Theory of the Learnable, which introduced PAC learning and a relaxation in the assumptions of inductive inference, about what should (and, therefore, can) be learned. In short, the difference is that inductive inference attempted to learn complete definitions of various automata, whereas modern machine learning attempts to approximate them; well, strictly speaking it's about approximating functions, not automata as such. So yeah, pretty much, like you say: (2) is, in principle, not possible whereas (1) might even be possible in practice. Now, normally this is where I'd plug my own research, but I've already written plenty :)

YeGoblynQueenne 8y ago

>> where indeed they use machine learning to induce the rules of chess from a large number of played games (and then learn to play better than any human). They didn't induce the rules of chess! What they did was learn an evaluation function for chess moves, from scratch, i.e. without giving it the rules or any hand-crafted features. So they learned a classifier for good/bad board states, which was later used in an alpha-beta minimax search. However, the classifier didn't learn the rules of the game, only a mapping from board positions to labels, good/bad. This is not made explicit in the text, but minimax typically has a rule-base to generate moves as successor states for the search; so the rules of the game were hand-crafted, but did not contribute to the learning of the evaluation function. It's extremely hard to induce a set of rules with neural nets, or indeed any statistical machine learning algorithm. I mean, imagine representing the rules of chess as a function; let alone trying to learn that function from data. (Full disclosure: I study algorithms that learn rules from data; they're not neural nets).

ScottAaronson 8y ago
Aha, thanks for that extremely useful clarification! I was also confused from the abstract and intro about exactly what the inputs and outputs were. Yes, the clear impression was created that they learned the rules---in the sense that they could then generate moves that would (usually? almost always?) obey the rules---when it sounds like really they just learned an evaluation function that encodes lots of implicit knowledge about the rules, of course, but that still requires a piece of code that knows the rules explicitly as a "guardrail" when generating moves. Since you obviously know this subject, what are the best current results in the direction of inducing the rules of chess from played games?
- ScottAaronson 8y ago
  On further thought, we should distinguish two problems: (1) "Induce" the rules, in the sense that after training on millions of played games, you now have a neural net or whatever that plays mostly or entirely according to the rules even though it can't articulate them. (2) Output an explicit description of the rules. I could easily believe that (2) is beyond the current abilities of AI, even if it turns out that (1) is doable.
  - YeGoblynQueenne 8y ago
    >> Since you obviously know this subject, what are the best current results in the direction of inducing the rules of chess from played games? To be honest, I don't think there's much work on inducing the rules of chess, in particular. It's probably considered a) easy enough to do by hand and b) too hard to machine-learn. >> On further thought, we should distinguish two problems: (1) - Yep. The most likely approach would be a classifier trained to label moves as legal/ illegal. The resulting model would be a vector of numerical parameters so not a traditional rule base. It would also only be correct within some margin of error, probably not 0, limiting its uses (e.g. it wouldn't make sense to train it to play and then pit it against a player with a correct rulebase; they wouldn't be playing the same game). >> I could easily believe that (2) is beyond the current abilities of AI, even if it turns out that (1) is doable. Also yes. Exactly on point in fact. When we're talking about learning rules, we 're talking about learning automata, the subject of inductive inference, an older branch of machine learning (well, ish) that fell out of favour after a bunch of theoretical results showed it was basically impossible to learn any interesting class of automata from examples (the most famous is Mark E. Gold's result from Language Identification in the Limit; only finite languages can be learned from finite examples, anything else is only learnable "in the limit", from infinitely many examples, or an all-knowning oracle, etc). Modern machine learning starts with Valiant's A Theory of the Learnable, which introduced PAC learning and a relaxation in the assumptions of inductive inference, about what should (and, therefore, can) be learned. In short, the difference is that inductive inference attempted to learn complete definitions of various automata, whereas modern machine learning attempts to approximate them; well, strictly speaking it's about approximating functions, not automata as such. So yeah, pretty much, like you say: (2) is, in principle, not possible whereas (1) might even be possible in practice. Now, normally this is where I'd plug my own research, but I've already written plenty :)