Value Function Approach to Tic-Tac-Toe
A value function stores estimated probabilities of winning for game states.
A Number Beside Every Board
Imagine pausing a tic-tac-toe game after every move and writing one number beside the current board. That number represents the estimated probability that the player using X will win from that game state. The collection of board states and their numbers is called a value function.
The value function is a table that maps each game state to an estimated winning probability for X.
Mapping States to Values
A game state is the condition of the tic-tac-toe board at a particular point in the game. The value function stores one value for that state. To initialize the table, the state is first classified according to its winning condition. The classification comes before assigning the number: first identify whether X has won, O has won, the board is filled, or the game is still unfinished. Then assign the corresponding initial value.
| State category | Initial value | Meaning for X |
|---|---|---|
| X-winning state | 1 | X has won in this state |
| O-winning state | 0 | X has not won in this state |
| Filled state | 0 | The initialization assigns zero to this category |
| Other unfinished state | 0.5 | The state is neither a completed X win nor one of the zero-valued terminal categories |
Initial value assignments in the value function
Classifying a Board Before Scoring It
Four Board Categories
Assign the initial value to each of four described tic-tac-toe states.
Classify the first state: The state is described as an X-winning state, so it receives the initial value 1.
Classify the second state: The state is described as an O-winning state, so it receives the initial value 0.
Classify the third state: The board is filled, so it receives the initial value 0.
Classify the fourth state: The state is unfinished and belongs to the other-state category, so it receives the initial value 0.5.
The four initial values are 1 for an X win, 0 for an O win, 0 for a filled state, and 0.5 for another unfinished state.
This example shows why the first operation is classification rather than calculation. The value is selected from the state's category. An unfinished state is not treated in the same way as a completed X win, and a completed X win is not treated in the same way as an O win or filled state.
Why Terminal Values Differ
The values are defined from X's point of view. An X-winning state receives 1 because it represents the desired winning outcome for X. An O-winning state receives 0 because X has not won. A filled state also receives 0 under the stated initialization. Other states receive 0.5 as their initial value.
Comparing Two Game States
Once states have values, the values provide a direct way to compare them. If one state has a higher stored value than another, that state is currently estimated to be better for X. The comparison does not require treating the boards as identical; it uses their stored value estimates as the basis for deciding which state is better for X.
Choosing the Higher Estimate
Suppose one game state has value 0.5 and another has value 0. Compare them from X's point of view.
Read the first value: The first state has the stored value 0.5.
Read the second value: The second state has the stored value 0.
Compare the values: Because 0.5 is higher than 0, the first state is currently estimated to be better for X.
The state with value 0.5 is the higher-valued state and is therefore currently better for X according to the value function.
Common Classification Mistakes
Assigning 1 to every state that looks favorable for X
The initial value 1 is assigned specifically to an X-winning state, not to every state that seems favorable.
Fix:
First classify the state. An other unfinished state receives the initial value 0.5.Treating the values as equally meaningful for both players
The value function described here estimates winning probabilities from X's point of view.
Fix:
Interpret higher values as indicating states that are currently better for X.Forgetting that a filled state is initialized with 0
The stated initialization assigns 0 to a filled state.
Fix:
Use the category specified by the initialization: filled states receive 0.Choosing the lower-valued state as better for X
State values provide a comparison in which the higher value indicates the state currently better for X.
Fix:
Compare the stored numbers and select the higher value when evaluating which state is better for X.
Practice the Value Lookup
A value-function table contains three states: State A is an X-winning state, State B is an unfinished other state, and State C is a filled state. Assign each initial value, then identify which state is currently best for X according to the stored values.
Hints
- Use the classification before comparing the numbers.
- An X-winning state receives 1.
- An unfinished other state receives 0.5.
- A filled state receives 0.
- The higher value indicates the state currently better for X.
What do you think happens?
Which state will have the higher initial value: an unfinished other state or a filled state?
Reveal answer
Answer: The unfinished other state
The unfinished other state receives 0.5, while the filled state receives 0. The higher value makes the unfinished other state currently better for X according to the value function.
Value Function Recap
- A value function stores estimated probabilities of winning for tic-tac-toe game states.
- Initialization begins by classifying each state according to its winning condition.
- An X-winning state receives initial value 1.
- An O-winning state or filled state receives initial value 0, while other states receive 0.5.
- Comparing stored values shows which state is currently estimated to be better for X.
Key Takeaways
- A value function maps tic-tac-toe states to estimated winning probabilities for X.
- The state category must be identified before its initial value is assigned.
- The initial assignments are 1 for an X win, 0 for an O win or filled state, and 0.5 for other states.
- A higher value means the state is currently estimated to be better for X.