Evaluation and Tic-Tac-Toe
Traditional go evaluation does not depend upon whose turn it is and assumes perfect play. Minimax evaluation depends upon whose turn it is and assumes perfect play. Winrate evaluation depends upon whose turn it is and assumes imperfect play (except when the winrate is 100% or 0%). OC, for Tic-Tac-Toe we know perfect play.
Lately I have been wondering how to introduce the idea of traditional go evaluation to those who know nothing about it, and the idea of using Tic-Tac-Toe came to mind. I learned a little something about Tic-Tac-Toe and I thought I would write it up.
Despite not knowing perfect play in go we can evaluate the empty board. Because of symmetry it has an average value of zero. The result with perfect play when Black plays first has to be the negative of perfect play when White plays first, and their average is zero. The same reasoning applies to Tic-Tac-Toe. Traditional go evaluation has not been very successful in making a strong go player. One reason for that is that another variable, that of temperature, is important. You can’t simply rely upon the average value of a position. Tic-Tac-Toe provides a good example of this, which I shall illustrate using go diagrams.
- Click Here To Show Diagram Code
[go]$$Bc Value 0
$$ -------
$$ | . . . |
$$ | . . . |
$$ | . . . |
$$ -------[/go]
The empty board has a value of zero and the final board also has a value of 0, counting a win for Black as +1 and a win for White as -1. It’s temperature is 0.
- Click Here To Show Diagram Code
[go]$$Bc Value 0
$$ -------
$$ | . . 1 |
$$ | . . . |
$$ | 2 . . |
$$ -------[/go]
After
takes one corner,
takes the opposite corner. By symmetry we know that this board also has an average value of 0. But it has a temperature of 1. Whoever plays first can win with perfect play.
- Click Here To Show Diagram Code
[go]$$Bc Value 1
$$ -------
$$ | 5 a 1 |
$$ | . b 4 |
$$ | 2 . 3 |
$$ -------[/go]
forces
, and then
produces a won position. Even if White plays first Black has the miai of “a” and “b” to win; if White takes one, Black takes the other. The players could stop play now and declare a Black win.
When I was a kid I was unaware of this little trick, because I always made my first play in the center, whether as X or O.
It’s a good illustration of why simply knowing the traditional go value of a position is not enough to base play on. After
White may reason that
is OK because it returns the board to its original value of 0. But
raises the temperature to 1 and allows Black to win. I believe that using minimax evaluation chess programs used to (and maybe still do) evaluate only quiescent positions, for a similar reason.
Suppose we did not know perfect play for Tic-Tac-Toe. What would the winrate value of the first play? We do not know, because winrate values depend upon imperfect play, and we do not know the error functions of the players. However, I think we can say something about error rates, even without that knowledge.
- Click Here To Show Diagram Code
[go]$$Bc Error
$$ -------
$$ | . 1 5 |
$$ | 2 3 . |
$$ | . 4 . |
$$ -------[/go]
is a mistake. Opening on the side gives the second player 2 potential errors out of 8 plays (1 out of 5 if you eliminate symmetrical plays.)
- Click Here To Show Diagram Code
[go]$$Bc Error
$$ -------
$$ | 3 . 5 |
$$ | 2 1 . |
$$ | . . 4 |
$$ -------[/go]
is a mistake. Opening in the center gives the second player 4 potential errors out of 8 plays (1 out of 2) if you eliminate symmetrical plays.)
- Click Here To Show Diagram Code
[go]$$Bc Error
$$ -------
$$ | 2 . 1 |
$$ | . . . |
$$ | . . 3 |
$$ -------[/go]
is a mistake.
transposes to a win we have already seen (by symmetry).
- Click Here To Show Diagram Code
[go]$$Bc Error
$$ -------
$$ | . 2 1 |
$$ | . 5 4 |
$$ | . . 3 |
$$ -------[/go]
is a mistake.
- Click Here To Show Diagram Code
[go]$$Bc Error
$$ -------
$$ | 3 . 1 |
$$ | 2 . . |
$$ | . . . |
$$ -------[/go]
is a mistake.
transposes to the win in the previous diagram.
Opening in the corner gives the second player 7 possible errors out of 8 plays (4 out of 5 if you eliminate symmetrical plays).
My guess is that a bot trained on winrate evaluation, but not to perfect play, would be quite likely to make the first play in a corner.