6
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Strin
    Dec 22, 2012 at 1:51
  • $\begingroup$ @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. $\endgroup$
    – Jeremy List
    Dec 22, 2012 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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