Game Development Reference
In-Depth Information
Evaluation functions are how we turn '' . . . best moves . . . '' in our reasonably
simple question given in the first paragraph into code. The simplest evaluation
function for Tic-Tac-Toe would look at any game and return one of four values:
n Victory: Three in a row for our side.
n Loss: Three in a row for their side.
n Tie: All moves have been taken without a victor.
n Unknown: The game is still in play.
While this method always gives a correct answer, we should consider its draw-
backs. An AI using this evaluation of the board will always get back unknown
until the fifth move. It will not always know with certainty in some games
without looking ahead to the ninth move. Looking ahead to the ninth move
means looking at all possible games.
How many moves have to be evaluated to get to the end of every possible game?
Tic-Tac-Toe has nine different beginning moves, eight different secondmoves, and
so on until it has one final move. To get the total number of outcomes, we multiply
those numbers together to get 362,880, also know as 9 factorial, which is written as
9!. A 1MHz computer of 25 years ago could do this after a very long pause; modern
hardware running a thousand times faster makes it seem nearly effortless. How-
ever, any function that has factorial cost must be kept to small numbers. Factorial
functions start out slow but grow more rapidly than linear functions, faster than
polynomial functions, even faster than exponential functions. Think of a factorial
function as a grenade; after a short while, it explodes. When this happens in a
game, the player's computer becomes an expensive space heater, appearing to do
nothing but blow warm air for very long periods of time.
A more useful evaluation function would attempt to foretell the outcome of an
indeterminate gameāone not yet played to completion. Our reasonably simple
question asked ''. . . will I win in the end?'' It would be nice if we could predict
the end without playing to the end. We ignore the fact that we can state from the
outset that if both sides play to win, Tic-Tac-Toe always ends in a tie. But if
one side makes a mistake, we would like our evaluation function to be able to
indicate victory while using the smallest amount of looking ahead. We want our
evaluation function to generate good advice from indeterminate games. Tic-Tac-
Toe does not provide meaningful insight into this kind of evaluation function.