Let us improve the program
A program which could carry out all the analyses which were exposed, and which especially could carry out them quickly, would undoubtedly be a good program. But it would suffer from some defects :
- the horizon effect
If your computer is programmed to stop its evaluation on level N, you will understand very well that it is not worried in what it occurs on the level N+1 and beyond. However it can occur there very interesting things. We will see an example.
At level N-3, the blacks have men on squares 7,11,14,20. The white have a man on square 8.
Diagram n° 7
The computer (black) sees that, if it plays one of the men 11, 14 or 20 on the level N-2, its opponent will have a king with the half-move N-1, that it will still have at level N.
But a king is worth 3 men, and even more at the end of the game, that's what we explained to it. On the other hand, by playing the man 7 at the move N-2, the computer loses certainly 2 men, but its adversary does not make a king at the level N-1 (it captures). The computer will thus choose this solution, thinking it leads to a more favorable position. And, thus, it will transform a victory (the king would have been lost on the level N+1 on 11-16 and 20-25) into a defeat (men 14 and 20 will never pass).
How to avoid this horizon effect ? Well, it is impossible to remove it completely, there will be always a horizon. But one can make it go further, by examining the significant solutions further. It is advisable in particular to further look at the sequences with captures, for example by increasing the maximum level of one unit each time that there is a capture, or, it is equivalent, by not incrementing * the current level when there is a capture (but you must maintain however a reasonable limit to prevent the computer of studying the gift to the opponent of all the men on the checkerboard). In the case which we studied above, the computer would then have seen that, on the level N+1, the adversary made in any way a king after the sacrifice of the 2 men.
This method concerning the change of maximum level the jumps offers moreover the advantage of generally avoiding the consequences of shots, by a better investigation when there are captures..
We can also look at certain positions further, independently of the sequence of moves (with or without captures) which led us there. Thus, we saw in a previous chapter that the narrow branches were to be explored further. In the same way, the positions where a player is near the king line are to be studied further.
- control of time
In fact, much of programs does not control correctly their time of game (in particular Dames 2020). They offer to you to play certain degree of difficulty, but you do not know if they will answer you in 5 seconds or 3 minutes.
Iterative search, that I could have presented to you in the chapter concerning alpha-beta because it constitutes an improvement of it, allows a better regularity in the answer times.
Contrary to the techniques presented up to now, iterative search does not decrease the number of examined solutions, but increases them. Then, what is its interest, will you say to me ?
Listen at me, and you will understand. Iterative search proceeds in the following way :
You initially study the tree of the solutions up to a level N (for example 2).
Then the solutions you found are to be ordered.
Then, you re-examine since the beginning the tree up to a level M, higher with N (generally N+1). This new investigation at level M will be generally more efficient than if you had made it directly from the very start, since a good solution at level N have a good probability to remain good at level M, according to the theory previously exposed.
The new solutions are ordered. You analyze again from the beginning to the level P, higher than M.
.....and so on.
Even if we suppose that we did not gain anything in alpha-beta prunings, the increase in the calculating time is relatively weak. Indeed, if we suppose that the average number of branch is D, and that the number of levels to be examined is of p, an iterative search up to level 1, then 2... then p is equivalent, without alpha-beta, to the examination of D p+d p-1+.....d final nodes, that is to say (D p+1-d)/(d-1), instead of D p if this method had not been used. The relationship between the 2 numbers of examined solutions is equivalent to d/(d-1) when p is large, and is close to 1 if D is large (that means that profitability is better in chess - average D is close to 35 - than in checkers - average D is close to 10-).
But, you will say to me, which is the relationship with the control of time?
Well, with such a method, the computer can always propose a solution considered to be good, up to a certain level of examination. Thus, if its time of thinking is limited to 5 seconds, it will examine for example the game up to level 2 in 1/100 of a second, up to level 3 in 1/10 of seconds, up to level 4 in one second, then, it will begin the investigation of level 5 but it will stop it for lack of time. But it will have already a solution available, the one of level 4.
This makes possible that the computer answer you in indicated time (for example 50 blows in 2 hours). You will thus understand that a program provided with this improvement plays differently according to the computer on which you install it. Thus, placed on an old PC 8086, such program appears bad to you when it thinks less than one minute. Placed on a 486 DX4-100, 60 times faster, you obtain the same quality of answer in one second, and if you let it reflect one minute by move, as on the old one, the level is that in the past obtained in one hour. On a Pentium 1000, 40 times faster than a 486 DX4-100, 1 second of thinking is like 40 hours on a 8086 !
If your friend says to you that he wins against the program T..., whereas this program always wins against you, ask him which computer he uses.
- thinking on opponent's time
When you play against an adversary, you generally use his thinking time for thinking on your side. Some programs can do that, which allows them, if the management of time is well made (and in particular if they are provided with the improvement presented above) to have studied the the opponent's answer and the possible against-answers before the opponent plays. This allows then, in the same time, to examine the tree further.
Now let us try to check all that we learned, and to see how the computer play when they have all that I presented :
- the computer examines the tree of the solutions up to level N,
- at the beginning of each branch, it looks at if the solution were already examined,
- it checks that the solution leading to this branch is not absurd (useless sacrifice),
- it makes a static evaluation of the position obtained at each end of the branch (the leaf),
- it goes up this solution at the higher levels by the method of minimax,
- it examines whether it can use on each level a pruning alpha-beta,
- having examined all the tree on level N, it orders the solutions obtained,
- it starts again this work on the level N+1.....
- and so on, until the time which was assigned to him has been reached,
- it plays the solution which it adopted like the best in its search.
- it continues its search while the adversary thinks, in order to be ready when its turn comes, without using too much time in computing.
Here, this series of articles is finished, it does not remain you more that to beat your computer by using the strengths and weaknesses that you detected, and, why not, to build a program by yourself.
Bibliography :
A. K. Dewdney : Récréations informatiques, les ordinateurs qui jouent aux dames ; dans Pour la Science, Novembre 1984 - (N.B. : it concerns American checkers).
J.L. Lauriere : Intelligence artificielle, résolutions de problèmes par l'homme et la machine ; Eyrolles 1987.
David Levy : Les jeux et l'ordinateur ; série de 20 articles dans L'Ordinateur Individuel, n°16 (avril 1980) à 35 (mars 1982).
David Levy : Chess and Computers, Bastford, London 1976.
Jonathan Schaeffer, Norman Treloar, Paul Lu and Robert Lake : Man versus machine for the World Checkers Championship ; dans A.I. Magazine, summer 1993.
Fédération Française d'Othello, BP 147, 75062 Paris CEDEX 02. This federation has a very important documentation about algorithms, and they let me use it (many thanks to Bruno de La Boisserie).