Hacker News Reader

Comment by ScottAaronson | Hacker News Reader

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?

View on HN

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.

>> 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 :)

Dah. Hang on, what am I talking about- chess has a finite number of moves so the "language" is finite. That means it's learnable in polynomial time, from finite examples ... in principle :)

Right, but even if chess were infinite, we could still imagine an algorithm that would output the smallest explicit rule set that was consistent with all the games it had seen so far, and that would quickly (though how quickly?) converge on the correct rules in the case of chess, even if it would be up against undecidability when trying to do the same thing for a completely arbitrary game.

It depends on how you mean "converge". It would certainly tend towards the full ruleset, learning more of them, or more accurate versions of them, the more examples it saw. It would not really terminate though, at least according to the learnability results from inductive inference.

Results from inductive inference show that you’re not going to converge in general. In the specific case of chess, however, my point was that we, because we know the complete list of rules, could plausibly look in from the outside and say after some finite point: “ah yes, now the system has gotten all of them.”

Oh, I see. Yes, for sure. That'd be the active learning framework [1]. I get the feeling it's not very popular because it inserts a human in the process. Many machine learning people are rather allergic to anything that a) introduces "human bias" to the learning process and b) reduces the potential for end-to-end automation.

The article you quoted above is a good example. It's main claim is that an evaluation function was learned without knowledge of rules or hand-crafted features, i.e. explicit human participation.

It's a political issue, really. And a silly one- there are domains where very useful background knowledge is available; physics, language, mathematics, etc. There's no reason not to use it.

In chess, for example, it might be possible to learn a decent set of rules just by carefuly choosing the examples to feed to the learner. Or, indeed, evaluating the learning so-far, therefore acting as an all-knowing Oracle.

___________________

[1] Well, strictly speaking active learning is where the system asks the user for examples/ counterexamples, but there's different options and what you suggest would fit in there.

Reply on news.ycombinator.com