Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Tom Mitchell's book "Machine Learning", Chap.1, a checkers game is used to illustrate how machine learning can be applied solve problems.

An experience propagation rule is described for iterative learning of a hypothesis. Suppose a game has been played and watched by the program, the state of the endgame is labeled 100 for winning and -100 for losing. For each of the states on the path toward the endgame, we label it as $\hat{V}(Successor)$, where $\hat{V}(state)$ is the current model output on some state. Then the model is trained by adding the new label, and iteratively, the model converges to a good checkers program.

Why does this experience propagation rule work? It is mentioned in the book that it works quite well for most chess games.

share|cite|improve this question
up vote 3 down vote accepted

Sutton's book on reinforcement learning explains it but probably in more detail than what you're looking for, so I'll try to explain it more briefly and clearly.

Start by thinking about the last position before the end of the game. The winning player can win in one move from that position, so that position is almost certainly good for that player and bad for the other player. Now Think about the second to last position: that's only one move away from the last position which we've just established is probably a good position for the player that won in the end. The same logic applies to the third-last, fourth-last, etc.

See also: Wikipedia's page on mathematical induction, which works in a similar way.

share|cite|improve this answer
But how do we control the model complexity? For example, if the model is way too complex, it might over fit the data, which leads to state values either 100 or -100. On the other hand, how do you believe a model not too complex can capture the internal relationship of states and actions? – Strin Dec 22 '12 at 1:51
@Strin There's no problem with state values being 100, 0, or -100 because that's what the actual mathematically correct state values are (see Game theory on wikipedia). The other kind of overfitting is avoided because the "training set" changes every time. As for models that are too simple: the simplest possible model just counts the pieces on each side and it still plays at a reasonable beginner level. – Jeremy List Dec 22 '12 at 3:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.