Value Function Approach to Tic-Tac-Toe

The value function is a table that maps each game state to an estimated winning probability for X.

Programming

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.

Key point

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.

How does a particular board position map to a stored value representing its estimated chance of winning for X?

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

Worked example

Four Board Categories

Assign the initial value to each of four described tic-tac-toe states.

1
Classify the first state
The state is described as an X-winning state, so it receives the initial value 1.
2
Classify the second state
The state is described as an O-winning state, so it receives the initial value 0.
3
Classify the third state
The board is filled, so it receives the initial value 0.
4
Classify the fourth state
The state is unfinished and belongs to the other-state category, so it receives the initial value 0.5.

Result

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.

How are different categories of board states classified and assigned their initial values?

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.

Why does an X-winning state map to 1 while an O-winning or filled state maps to 0?

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.

Worked example

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.

1
Read the first value
The first state has the stored value 0.5.
2
Read the second value
The second state has the stored value 0.
3
Compare the values
Because 0.5 is higher than 0, the first state is currently estimated to be better for X.

Result

The state with value 0.5 is the higher-valued state and is therefore currently better for X according to the value function.

How can comparing two table values show which board state has the higher estimated probability of winning for X?

Common Classification Mistakes

Common mistake
Assigning 1 to every state that looks favorable for X
What it looks like
An unfinished state is automatically given value 1 because X appears to have a strong position.
Why it fails
The initial value 1 is assigned specifically to an X-winning state, not to every state that seems favorable.
Do this instead
First classify the state. An other unfinished state receives the initial value 0.5.
Common mistake
Treating the values as equally meaningful for both players
What it looks like
A value of 0.5 is described as the probability that either X or O will win.
Why it fails
The value function described here estimates winning probabilities from X's point of view.
Do this instead
Interpret higher values as indicating states that are currently better for X.
Common mistake
Forgetting that a filled state is initialized with 0
What it looks like
A filled board is assigned 0.5 merely because it is no longer unfinished.
Why it fails
The stated initialization assigns 0 to a filled state.
Do this instead
Use the category specified by the initialization: filled states receive 0.
Common mistake
Choosing the lower-valued state as better for X
What it looks like
A state with value 0 is selected over a state with value 0.5 because both are not X wins.
Why it fails
State values provide a comparison in which the higher value indicates the state currently better for X.
Do this instead
Compare the stored numbers and select the higher value when evaluating which state is better for X.

Practice the Value Lookup

EASY

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.

Your attempt (not saved)

What do you think happens?

Which state will have the higher initial value: an unfinished other state or a filled state?

The unfinished other state
The filled state
They have the same value

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

1
A value function stores estimated probabilities of winning for tic-tac-toe game states.
2
Initialization begins by classifying each state according to its winning condition.
3
An X-winning state receives initial value 1.
4
An O-winning state or filled state receives initial value 0, while other states receive 0.5.
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.

More concepts starting with V