Search

From Chessprogramming wiki

Home * Search

Bernd Besser, Auf der Suche^[1]

Because finding or guessing agood move in achess position is hard to achieve statically,chess programs rely on some type ofSearch in order to play reasonably. Searching involves looking ahead at differentmove sequences and evaluating the positions aftermaking the moves. Formally, searching a two-playerzero-sum board game withperfect information impliestraversing and min-maxing atree-like data-structure by varioussearch algorithms.

Shannon's Types

Claude Shannon categorized searches into two types^[2] :

Type A - abrute-force search looking at every variation to a givendepth
Type B - aselective search looking at "important" branches only

Inspired by the experiments ofAdriaan de Groot^[3] , Shannon and early programmers favored Type B strategy. Type B searches use some type of static heuristics in order to only look at branches that look important - with some risk to oversee some serious tactics not covered by the plausible move selector. Type B was most popular until the 1970's, when Type A programs had enough processing power and more efficient brute force algorithms to become stronger. Today most programs are closer to Type A, but have some characteristics of a Type B as mentioned inselectivity.

The Search Tree

Thesearch tree as subset of thesearch space is adirected graph ofnodes, the alternating white and black to movechess positions - and edges connecting two nodes, representing themoves of either side. Theroot of the search-tree is the position we like to evaluate to find thebest move. Because oftranspositions due to different move sequences, nodes inside the tree may occur from various ancestors - even within a different number of moves. The search tree contains various cycles, since both sides mayrepeat a former position with the minimum of two reversible moves each, or fourplies. Cycles are usually eliminated and not searched twice, which results in searching adirected acyclic graph DAG.

Search Algorithms

Most chess-programs use a variation of thealpha-beta algorithm to search the tree in adepth-first manner to attain an order of magnitude performance improvement over a pureminimax algorithm. Althoughmove ordering doesnt affect the performance of a pure mini-max search (as all branches and nodes are searched) — it becomes crucial for the performance of alpha beta search and enhancements such asPVS,NegaScout andMTD(f).Hans Berliner's chess-programHiTech andUlf Lorenz's programP.ConNerS usedbest-first approaches quite successfully.

Depth-First Search

Depth-First search starts at the root and explores as far as possible along each branch before backtracking. Memory requirements are moderate, since only one path from the root to one leaf is kept in memory. The giga bytes ofRAM in recent computers is utilized by atransposition table. Minimax and Negamax are mentioned for educational reasons as the prototypes for the more advanced algorithms. They otherwise have no practical relevance in software, except traversing a minimax tree inside aperft framework fortesting themove generator. Depth-first algorithms are generally embedded inside aniterative deepening framework fortime control andmove ordering issues.

Alpha-Beta Enhancements

Obligatory

Selectivity

Scout and Friends

Alpha-Beta goes Best-First

Best-First Search

Best-First approaches build a search-tree by visiting the most promising nodes first.They usually have huge memory requirements, since they keep an exponentially growing search space in memory.