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?
Best Answer
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.