Stop searching

The next step is that the Alpha-Beta-Search algorithm must be modified so that it calls the Eval heuristic function when it becomes necessary to stop the search. From the point of view of implementation, it is necessary to replace the two lines in the listing that mention the Terminal-Test function with the following line:

if Cutoff-Test (state, depth) then return Eval (state)

It is also necessary to envisage the performance of certain technical operations in order to increase the current depth depth value on each recursive call. The most straightforward approach to managing search volume is to set a fixed depth limit so that the Cutoff-Test function (state, depth) returns true for all depth values ​​that exceed a certain fixed depth d. (It should also return true for all terminal states, as was also provided in the Terminal-Test function.) Depth d is chosen so that the time used does not exceed the allowable time limit according to the rules of the game.

A more robust approach is to use an iterative deepening method. At the end of the allotted time, the program returns the move selected according to the results of the most in-depth completed search. However, such approaches can lead to errors due to the approximate nature of the evaluation function. Once again consider a simple evaluation function for chess, based on the advantages in the material. Suppose that the program performs a search to the depth limit, reaching the position shown in the figure, where Black has an advantage on one knight and two pawns.

The program would report this as the heuristic meaning of this state, thereby declaring that this state is likely to lead Black to victory. But on the next move, White takes the black queen without compensation. Therefore, in reality, this position is advantageous for whites, but one could find out about this only by looking ahead for another half-turn.

Obviously, a more complicated stop check is required. The evaluation function should be applied only to positions that are calm, i.e. characterized by a low probability that in them in the near future there will be dramatic changes in value. For example, in chess, such positions in which the desired taking of figures can be made are not calm for such an evaluation function, in which only material is taken into account. Troubled positions can be further deployed until calm positions are achieved. Such an additional search is called a search for calm positions; sometimes it is limited by the fact that it only considers certain types of moves, such as moves with taking pieces, which allows you to quickly remove all the uncertainties in this position.

The task of eliminating the horizon effect is more difficult. This effect occurs if a program encounters an opponent’s move that causes serious damage and is ultimately inevitable. Consider the chess position shown in the figure. Black is superior to White in terms of the amount of material, but if White can push his pawn from the seventh rank to the eighth, then the pawn will become the queen and ensure White’s easy victory. Black can delay this total by 14 half-moves, declaring the check to White with the rook, but the pawn will inevitably become the queen.

One of the drawbacks of searching for a fixed depth is that it is used when
This algorithm does not allow to determine that such distracting moves are not capable of preventing a move with the transformation of a pawn into a queen. In this case, it is considered that distracting moves bring the inevitable move with the transformation of the pawn into a queen "beyond the limits of the search horizon" - to the place where the dangerous move cannot be detected.

As the improvement of the hardware used for playing chess leads to an increase in the depth of search, it becomes increasingly possible that the horizon effect will not occur as often as the very long sequences of moves that allow you to delay the execution of an undesirable move rarely. To prevent the horizon effect without increasing the search cost too much, the use of single extensions was also very effective.

A single extension is called a move, which is “definitely better” compared to all other moves in this particular position. Search with a single extension allows you to go beyond the usual depth search limits without significant cost, because the branching factor is 1. (Finding a calm position can be considered as one of the options for single extensions.) In the figure, a search with a single extension allows you to find the pawn-to-queen turn, provided that Black’s moves with the check against the king and White’s moves can be defined as “certainly the best” compared to other options.

So far, it has been said that stopping the search at a certain level and performing alpha-beta-clipping does not seem to affect the result. It is also possible to perform preliminary clipping, which means that some moves in this particular node are cut off immediately, without further consideration. Obviously, most people playing chess consider only a few moves from each position (at least consciously). Unfortunately, this approach is quite dangerous, since there is no guarantee that the best move will not be cut off.

And if clipping is applied close to the root, the result can be catastrophic, because such situations arise too often that the program skips some “obvious” moves. Pre-pruning can be used safely in special situations (for example, if two moves are symmetrical or equivalent for some other signs, then only one of them should be considered) or when analyzing nodes that are deep in the search tree.

As a result of the joint use of all the methods described above, it becomes possible to create a program that plays chess (or other games) well. Suppose that the evaluation function for chess is implemented, a reasonable stop check is provided in conjunction with the search for a calm position, and a large table of transpositions is provided. In addition, let us assume that, having spent entire months on scrupulous development of programs operating at the bit level, we were able to form and estimate approximately one million nodes per second on the newest personal computer, which allows searching for approximately 200 million nodes per turn with standard time control (three minutes per turn). The branching ratio for chess is on average about 35, and 35 ⁵ is about 50 million, so when using the minimax search we will be able to look ahead only by about five half-moves.

Such a program, although not entirely incompetent, can easily be deceived by a person, a middle-level chess player, who is sometimes able to plan for six or eight half-moves ahead. Alpha-beta search allows you to reach a depth of approximately 10 half-moves, which leads to the strengthening of the game to the level of the master. Section 6.7 describes additional clipping methods that allow you to increase the effective search depth to about 14 half-moves. To reach the level of a grandmaster, a carefully tuned evaluation function and a large database with records of optimal moves in the opening and endgame are required. It would not hurt to have a supercomputer to operate such a program on it!