Learning Evaluation Functions
An evaluation function improves the minimax and alpha-beta algorithms by cutting off the search earlier, so that moves in the game can be made in reasonable amount of time. The evaluation function converts non terminal nodes into terminal leaves. It returns an estimate of utility value of a game from a given position. A well designed evaluation function will improve the performance of the game playing programs.
A well evaluation function can be learned by neural, networks. The TD GAMMON program is learned to play Backgammon by fully connected feed forward neural network. The network outputs a set of estimates q1, q2, q3, q4 that represents possible outcomes of game. The concluded value is obtained by,
v = q1 + 2 q2 - q3 - 2q4
The best value of v is selected such that if it is white's move highest value of v is selected. If it is black's move least value of v is selected.
When evaluation function is trained by temporal difference learning, the network plays game against itself. In this type of learning the weights of nodes are adjusted when a move is made and it use back propagation technique to predict value of v.
Assume, at time t, the network estimate is vt and at time t + 1, the network estimate is vt+1, then the weights of nodes are adjusted based on following rule.
∆Qt = S(Vt+1 - Vt ) (ძvt / ძQ)
Where Qt, is weight vector in the network at time t.
Fig: The RD-GAMMON Network
