The dynamic evaluation
The objective of this evaluation is to examine, beyond the current situation, what can occur in the future. The ideal is to find, among the possible paths, the one which leads to a victory, imparable by the adversary.
We saw that for the moment the computer cannot reach this ideal from the begining of the game, and we can only look in a limited future.
We will try to understand this evaluation by thinking like a rather very limited program.
So, we will represent the possible choices by " a tree ", and don't ask me why this tree has the head in bottom and the trunk in top, it is like that which the computers specialists (which undoubtedly know badly nature) represent them.
They are so uncultivated besides that they call root the top (the base of the trunk) and node each departure of branch. In the case represented below by the diagram nø1, there is only one node, confused with the root.
Diagram n° 1
Let us examine this tree. The computer is in a position P0. It has N possibilities of play. The first possibility leads it to the position P1, the second to the position P2... and the nth one to the position Pn.
It "imagines" that it moves the first piece possible from position P0, and arrives to position P1 (but, of course, it does not show anything of that on the screen). Then it applies to this position the static evaluation which we presented in the preceding article. It finds a value, A1, that it places in its memory.
It comes back to position P0 (taking back the first piece) and moves the second possible piece. It arrives to the position P2, which it evaluates with a value A2, that it compares with A1 in its memory. If A2 is better than A1, it says that P2 is a better position, and it will know that the move which leads from P0 to P2 is better than the one which leads to P1. So, it replace A1 by A2. In the opposite, if A2 is worse than A1, it lets A1 in the memory.
Then, it does the same thing to get the values A3..., and so on up to the An value of the last possibility among n.
By these successive comparison, it has kept the best value, corresponding to the best move.
Now, it can choose its move, it is the one which gave the best value.
We made there a dynamic evaluation of first level, i.e. we studied a flow chart stopping at the first half-move (a half move is a move completed by one side only).
I had said that our program was very limited, because it is obvious that a player, even a bad one, will think further and will wonder which are the possible answers to each move.
Let us go a little further.
Diagram n° 2
Us here in front of a diagram of second level (diagram n° 2), where each possibility P is followed by various possibilities Q for answer.
The points P and Q, from which start the branches of the flow chart, are the nodes of which we already spoke.
The computer will evaluate each position obtained in Q11,..Q1m,Q21,..Q2r...,Qn1,..Qns. You see that we must make a lot of computing at level 2 (for only 2 half moves, or 1 complete move, by both white and black).
It is better of course to go further, and to consider the answer of the computer to its opponent, then the answer of the opponent to the computer, etc..., and thus you increase the size of the flow chart of 2 levels (the move of the computer and the one of the opponent) for each complete move.
The flow chart becomes quickly gigantic. If you have an average of 10 possibilities by levels, the total of positions to be evaluated is :
level 1: 10
level 2: 100
level 3: 1000
level 4: 10000
level 5: 100000
level 6: 1 million
level 7: 10 million
level 8: 100 million etc...
You see that at this rather moderate rate (10 possibilities per half-move), you reach one million possibilities within 6 levels, i.e. 3 moves, and one billion in 9 levels (4 moves 1/2).
It will obviously be necessary to use a good method (the computer has memory, but it is to better avoid making him retain and compare billion figures) and also to plan how to make pruning in this tree.