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.