I've started to learn machine learning using the book 'Machine Learning' by Tom Mitchell. The first chapter introduces the reader to machine learning and to the first problem: learning to play checkers. It starts by choosing a target function $V: Board \rightarrow \mathbb{R}$, which maps a particular board setting to a score (how good the current board state is). A score of $100$ means the game was won, $-100$ it was lost, $0$ draw. It then chooses a representation for the board: features.

$$V = w_0 + x_1*w_1 + x_2*w_2 + ...$$

where $w_i$ are weights and $x_i$ are features (for example the number of pieces you currently have on the board).

Features can be determined from the board configuration itself, but the weights have to be adjusted by the training examples. Each training example is a pair of the form $\langle b, V_{train}(b)\rangle$, where $b$ is the board state described by its features and $V_{train}(b)$ is the training value for $b$. Determining $V_{train}(b)$ for boards that are won or lost are easy, but we also need training examples for intermediate board states.

This is where I start being confused. It states a good approximation for intermediate boards is $V_{train}(b) \leftarrow V(successor(b))$, where $successor(b)$ denotes the next board state following $b$ for which it is again the program's turn to move (i.e., the board state following the program's move and the opponent's response). How am I supposed to know what's $successor(b)$? Which move am I supposed to make and how do I know what will be the opponent's move?

  • $\begingroup$ Sounds a lot like an awful way to start teaching machine learning--confusing the reader with an unrelated problem. $\endgroup$
    – bayerj
    Jul 15, 2014 at 20:44

1 Answer 1


successor(b) is calculated by our current approximation of V. Our next move would be calculated by the move which maximizes V and the opponent's move would be which minimizes the function V.


Your Answer

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

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