Lesson4.3 - Choosing a Representation for the Target Function - Designing A Learning System -

In the previous section, we decided to represent the target function for the checkers problem based on a value for the board state. We saw that it is computationally expensive to derive this value and so we try to approximate the value of the board state.

Choosing the right representation for the target function (V(b)) in the checkers problem is crucial for its practical implementation. Here are some key factors to consider:

1. Expressiveness: The representation should be able to capture the important features of the game state that influence its value (e.g., piece count, position, potential captures, king status). A more expressive representation allows for better approximations of V(b) but might be computationally expensive.

2. Simplicity: A simpler representation is easier to learn and computationally efficient. However, it might not capture all the relevant information, leading to less accurate approximations of V(b).

3. Training data and learning algorithm: The representation should be compatible with the chosen training data (e.g., game records, expert evaluations) and learning algorithm (e.g., linear regression, neural networks).

Common representations for checkers:

·        A table specifying values for each possible board state
·        Collection of rules
·        Linear features: Number of pieces, kings, position-based features, potential captures, etc. This is a simple and computationally efficient representation, but its expressiveness might be limited.
·        Polynomials of features: Expands on linear features by including interactions between them. Increases expressiveness but also complexity.
·        Piece placement vectors: Each square on the board is represented by a binary value (1 if a piece, 0 otherwise). More expressive than linear features but computationally expensive.
·        Neural networks: Can learn complex non-linear relationships between features and V(b), but require large amounts of training data and computational resources.

Choosing the best representation:

There is no one-size-fits-all solution. The best representation depends on your specific needs and constraints, such as:

·        Desired accuracy: How close do you want the approximation of V(b) to be to the true value?

·        Computational resources: How much processing power and memory do you have available?

·        Training data: What kind of data do you have for training the learning algorithm?

By considering these factors and exploring different representations, you can find the one that best balances expressiveness, simplicity, and efficiency for your checkers-playing program.

Remember, it's often an iterative process. You can start with a simpler representation and refine it as you gather more data and learn more about the game.

Our Choice

Board features:

•        x1(b) — number of black pieces on board b

•        x2(b) — number of white pieces on b

•        x3(b) — number of black kings on b

•        x4(b) — number of white kings on b

•        x5(b) — number of white pieces threatened by black(can captured in next move)

•        x6(b) — number of black pieces threatened by white

Linear Combination

V'= w₀ + w₁ · x₁(b) + w₂ · x₂(b) + w₃ · x₃(b) + w₄ · x₄(b) +w₅ · x₅(b) + w₆ · x₆(b)

•        Where w₀ through w₆ are numerical coefficients or weights to be obtained by a learning algorithm.

•        Learned values for the weights

•      w₁ through w₆ will determine the relative importance of the various board features in determining the value of the board

•        w₀ will provide an additive constant to the board value

Partial design of a checkers learning program:

Task T:

Play checkers

Performance measure P: 

Percent of games won

Training experience E: 

Got by playing games against itself

Target function: 

V:Board --> R

Target function representation

V'= w₀ + w₁ · x₁(b) + w₂ · x₂(b) + w₃ · x₃(b) + w₄ · x₄(b) +w₅ · x₅(b) + w₆ · x₆(b)