# Difference between revisions of "Search"

Home * Search

Bernd Besser, Auf der Suche [1]

Because finding or guessing a good move in a chess position is hard to achieve statically, chess programs rely on some type of Search in order to play reasonably. Searching involves looking ahead at different move sequences and evaluating the positions after making the moves. Formally, searching a two-player zero-sum board game with perfect information implies traversing and min-maxing a tree-like data-structure by various search algorithms.

# Shannon's Types

Claude Shannon categorized searches into two types [2] :

Inspired by the experiments of Adriaan 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 in selectivity.

# The Search Tree

The search tree as subset of the search space is a directed graph of nodes, the alternating white and black to move chess positions - and edges connecting two nodes, representing the moves of either side. The root of the search-tree is the position we like to evaluate to find the best move. Because of transpositions 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 may repeat a former position with the minimum of two reversible moves each, or four plies. Cycles are usually eliminated and not searched twice, which results in searching a directed acyclic graph (DAG).

# Search Algorithms

Most chess-programs use a variation of the alpha-beta algorithm to search the tree in a depth-first manner to attain an order of magnitude performance improvement over a pure minimax algorithm. Although move 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 as PVS, NegaScout and MTD(f). Hans Berliner's chess-program HiTech and Ulf Lorenz's program P.ConNerS used best-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 of RAM in recent computers is utilized by a transposition 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 a perft framework for testing the move generator. Depth-first algorithms are generally embedded inside an iterative deepening framework for time control and move ordering issues.

## 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.

# Related Issues

Search versus Evaluation

# Forum Posts

## 2005 ...

Re: Search or Evaluation? by Mark Uniacke, Hiarcs Forum, October 14, 2007