The Search Efficiency of the Alpha Beta Procedure
The effectiveness of the ∝-β procedure depends greatly on the order in which paths are examined. In case if the worst paths are examined first, then no cutoffs will occur at all. However, if the best path is known in advance, so that we may examine it first, the search process would not be needed. However, if we know how effective the pruning technique is in the perfect case, we would have an upper bound on its performance in other situations. It is possible to prove that for a uniform tree whose depth is d and branching factor is b the minimax algorithm evaluates all the nodes which corresponds to examining bd nodes. For the modified minimax algorithm ∝-β cut offs, the number of nodes to be examined is (best case and tree is balanced).
= (2bd/2 - 1) with d even And
= {b(d+1)/2 + b(d-1)/2 - 1} with d odd.
But there is a need to observe a restrain the formula is valid for only the special case in which a tree is perfectly arranged. As such the above formula is an approximation, if there were a way of arranging the tree with the best moves on the left, clearly there would be no point in using ∝-β pruning. However, this does not mean that the exercise of ∝-β have been fruitless it establishes the lower bound on the number of static evaluations which would be needed in a real game. It is a lower bound which may or may not be close to the real result, depending on how well the moves are infact arranged. The real result must lie somewhere between the worst case, for which static values must be somewhere between the worst case for which static values must be computed for all bd leaf nodes and the best case, for which static values must be computed for approximately 2bd/2 leaf nodes. In practice, the number of static evaluations are nearer to the best' case than the worst case.
Still the amount of work required becomes impossibly large with increasing depth. The ∝-β procedure merely wins a temporary reprieve from the effects of the explosive exponential growth and the procedure does not prevent the explosive growth.
Other Important Matters
In addition to ∝-β procedure there are a few other refinements to the minimax procedure which can also improve its performance. A number of heuristics are available for additional pruning of the game tree to permit a reasonable number of plies to be searched in a reasonable time.
Quiescence Search: The evaluation function should be applied only to positions which are quiescent that is unlikely to exhibit wild savings in value in the near future. To make sure that short term measures do not influence our choice of move, we should continue the search until no drastic change occurs from one level to the next. This is called waiting for quiescence.
In chess, for example positions in which favorable captures can be made are not quiescent for an evaluation function which just counts material. Non quiescent positions can be expanded further until quiescent positions are reached. This extra search is called a quiescence search. Sometimes it is restricted to consider only certain types of moves, such as capture moves, which will quickly resolve the uncertainties in the position.
Horizon Effect:
It is the most difficult effect to be eliminated.
It arises when the program is facing a move by the opponent that causes serious damage and is ultimately unavoidable.
Example: In chess game, consider that the black is ahead in material but if white can advance its pawn from the 7th row to the eighth, the pawn will become a queen and create an easy win for white.
Thus, the problem with fixed depth first search is that the stalling moves push the inevitable queening move "Over the search the search horizon" to a place where it cannot be detected.
Solution:
First solution to avoid the horizon effect is to use singular extensions without adding too much search cost.
1) Singular Extension: Singular extension is a move that is "Clearly better" than all other moves in a given position.
It can go beyond the normal depth limit without increasing much cost because its branching factor is 1.
2) Forward Pruning: The second solution is to use forward pruning. This pruning the moves at a given node without further consideration.
