Learning the rules of chess

Question

A similar question asks whether a computer can learn to play optimally in chess by analyzing thousands of games.

If a machine can look at the state of the board for a few games of chess (or a few games of checkers) in the beginning and after each move, can it be programmed to learn the rules of the game?

If it can, to what extent (e.g., would it be able to account for castling or promotion) would this work? Which machine learning algorithms would make this possible?

Answer 1

If a machine can look at the state of the board for a few games of chess (or a few games of checkers) in the beginning and after each move, can it be programmed to learn the rules of the game?

Certainly not for a few games of chess; you'd need to analyse incredibly large numbers of them to stop it from making invalid moves. How much, I don't know; this problem belongs to the area of computational learning theory, PAC learning and the problem of learnability in the limit.

The classification algorithms suggested by the other posters might be able to discriminatively learn chess rules: given two board setups, they might answer "yes" or "no" to the question of whether a valid move transforms one into the other. With some effort, they might also be used to generate moves. They will then, however, either only generate moves they've seen in games they've been trained on, or generate a combination of valid and invalid moves, each with a score stating how probable they consider the move in question, with invalid rules hopefully getting very small probabilities.

(I.e., either the program would not recognize some valid moves at its disposal; or you might be able to cheat without it noticing; or you'd have to train it for so long that you lose all interest in the game.)

For techniques that can learn rules, check out inductive logic programming and genetic programming. I'm not sure if anyone has ever tried to apply them to chess learning; since the rules of chess are fixed, it's much more interesting (even for academia) to build good chess playing programs rather than ones that have to learn the basic rules from scratch.

Answer 2

In theory - yes it can. It can even become a grandmaster in chess. The answer you are looking for is neural networks. Neural networks are in essence the same thing that happens inside our brain. Moreover, given the perfectly (read - impossibly perfect) designed neural network and a perfect hardware - it can learn everything a human being can learn in same or even better ways.

Read more about it:

• Neural network (wiki)
• Artifical neural network (wiki)
• Self-organizing map (wiki)
• Machine learning (wiki)

Answer 3

Yes and No

I'm not sure if you're asking if it's possible to learn the rules of chess using machine learning/neural networks or whether it's possible to train a "grand master" level chess machine using it.

You can certainly teach a computer the rules and some level of chess using those. However I do not think you can feasibly train it to a higher level using it. Computer Science has as yet afaik failed to produce a machine that can "understand" chess from a positional/intuitive point of view. All current chess computers use an extensive database, brute force calculations and a possibly machine learning on top of that.

Guess it depends if you count using a reference database as cheating or not :) Also, it's hard to know whether you actually can separate knowing lot's of games from being good at it. Human's that are good at chess are good precisely because they've seen so many games which are referenced by the part of the brain that is typically known to recognize faces. From this recall it seems human chess players are able to develop an "intuition" of the strength of a position.

Answer 4

As many of the comments have said, this is almost a philosophical question debating the definition of 'learn'. Most artificial intelligence programs rely on determining rational solutions. Given enough data a learning chess a.i. program will determine a list of moves that are rational to make in certain situations. This does not mean that it knows the rules of chess, it merely understands what moves are beneficial and which ones are not. Even if the data set includes players making illegal moves, the illegal move will cause an instant loss so the a.i. will ignore it and never use that move because it is never beneficial.

It does not matter whether neural networks or evolutionary algorithms or any other kind of learning algorithm is used, an a.i. can never explicitly learn rules from watching something, it can only determine a list of rationally beneficial options.

Answer 5

If you think of the rules of Chess as the physics engine of the game and the Laws of Physics as the permanent and unbending accepted rules of the universe then think about how few actual "Laws" there are in our natural universe. It is EXTREMELY hard if not impossible to make a hard and fast RULE, but we can make a number of tested and accepted theories as of a specific point in time.

It COULD be possible assuming that the computer observes and logs moves, but does NOT make assertions about valid moves directly.

For example, it would observe a pawn moving forward one piece and make new hypotheses that all pieces can move forward only one space, and another that a pawn can move forward only one space. It will form as many restrictive hypotheses as possible until the next move occurs and a number of them can be thrown our or made more liberal.

Eventually after so many moves you will have a set of solid theories but it will be a living dataset permanently approaching 0 but never reaching it.

So the answer is that a computer could make a really good guess but it will (EDIT: NOT) know the rules for sure.

Answer 6

The rules of chess are pretty complex and some very rarely executed in a game.

For instance the en passant rule. How many games will you need to observe in order to deduce it is only allowed the first move after the two-step-forward move?

Another example. The b-square can be attacked in long castling. How many games do you see where this happen?

In other words you will need many, many, many games to derive all the rules correctly.

But, perhaps, Google will find a corner of their cloud for a complete archive of chess games "soon"...

Answer 7

I think it can learn the moves that it is allowed to make just by analyzing, but how would it learn the moves it is not allowed to make? For example, the pawn never seems to move forward one square when an opposing piece is in front of it. How does the computer know whether this is by player choice or that it is not allowed to do it? You can come up with some algorithm that says if 99.99% of the time or greater an event doesn't happen then that means you aren't allowed to do it, but it could also be that 99.99% of the time that is considered a bad move, but that 0.01% of the time it is the move that wins the game. So, my answer is no, it can't learn all the rules simply by analyzing games, but it can probably learn enough to play a game.

Answer 8

This is a philosophical question. You might as well ask if a person could learn to play chess solely by observing people while they play chess. In fact it is basically the same kind of question Nelson Goodman asks in his great book Fact, Fiction, and Forecast: how can we move from a finite set of observations already made to a prediction of future observations. The observations already made would be the observed chess moves so far and the future observations would be all chess moves that haven't happend yet. The questions is, is there a nomological relation between past observations and future observations (as opposed to the purely causal relation between past events and future events)?

If we interpret the word nomological as by a law of nature or logic and nothing can ever happen in disaccord to this law then, there is certainly no such relation, since the first person who moves a castle diagonally, would break the law of nature and the universe as we know it would collapse.

But even if, in fact, by some freak accident of nature, every move any chess player in the world would make from now on, was valid (nobody would ever make any mistakes or try to cheat and even people clueless about the rules of chess would start pushing chess pieces around randomly across the board, but accidently always according to the rules), that would not convince us that there is a law of nature (or a law of logic) that forced all of this. We'd consider it purely accidental.

Ludwig Wittgenstein covered similar ground in his Philosophical Investigations. He insists that any set of observations is in accordance to arbitrarily many, and even conflicting, rules. For example, if all chess games observed by me would have happend in the afternoon, then my rule could be in the afternoon the bishop can only be moved diagonally. That the time of day is unimportant to the game is something that couldn't have been observed by me since I haven't observed chess games during different times of the day. Or, incidentally, if I have never observed a woman playing chess, then the rule could be the bishop can only be moved by men at all. What is relevant to an observation and what is not is determined as a prerequisite to the observation and cannot be part of the observation itself.

BTW: Wittgenstein's solution to the problem is quite similar to that of Goodman. I won't spoil the surprise, though ;-)

Addendum:

In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.

"What are you doing?", asked Minsky.
"I am training a randomly wired neural net to play Tic-tac-toe", Sussman replied.
"Why is the net wired randomly?", asked Minsky.
"I do not want it to have any preconceptions of how to play", Sussman said.

Minsky then shut his eyes.
"Why do you close your eyes?" Sussman asked his teacher.
"So that the room will be empty."
At that moment, Sussman was enlightened. 

Answer 9

No

Because simply learning patterns (via which ever method) is not the same as "learning to play chess optimally".

This requires planing & Strategy, which is very distinct from just merely learning set patterns.