Editing Computer chess (section)

==== Minimax search====
{{further|Alpha–beta pruning|minimax}}

One particular type of search algorithm used in computer chess are [[minimax]] search algorithms, where at each ply the "best" move by the player is selected; one player is trying to maximize the score, the other to minimize it. By this alternating process, one particular terminal node whose evaluation represents the searched value of the position will be arrived at.  Its value is backed up to the root, and that evaluation becomes the valuation of the position on the board.  This search process is called minimax.

A naive implementation of the minimax algorithm can only search to a small depth in a practical amount of time, so various methods have been devised to greatly speed the search for good moves. [[Alpha–beta pruning]], a system of defining upper and lower bounds on possible search results and searching until the bounds coincided, is typically used to reduce the search space of the program.

In addition, various selective search heuristics, such as [[quiescence search]], forward pruning, search extensions and search reductions, are also used as well. These heuristics are triggered based on certain conditions in an attempt to weed out obviously bad moves (history moves) or to investigate interesting nodes (e.g. check extensions, [[passed pawn]]s on seventh [[rank (chess)|rank]], etc.). These selective search heuristics have to be used very carefully however. If the program overextends, it wastes too much time looking at uninteresting positions. If too much is pruned or reduced, there is a risk of cutting out interesting nodes.