Home * Search
AufderSuche.jpg

Because having a perfect evaluation is impossible, chess programs must 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.
Bernd Besser, Auf der Suche [1]

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.
negaSearch_JRP-2012.jpg
negaSearch function at the heart of every chess program

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.

Opponent Model


Parallel Search


Using Time


Related Issues


See also


Publications

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

2015 ...


Forum Posts

2005 ...

2010 ...

2015 ...


External Links


References

  1. ^ Schach Bilder Welten - Bernd Besser - Galerie
  2. ^ Claude Shannon (1949). Programming a Computer for Playing Chess. pdf
  3. ^ Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam; N.V. Noord-Hollandse Uitgevers Maatschappij, Amsterdam. Translated with the help of George Baylor, with additions (in 1965) as Thought and Choice in Chess. Mouton Publishers, The Hague. ISBN 90-279-7914-6. (amazon)
  4. ^ Excellent Computer-Chess Overview Paper Found! by Ernst A. Heinz, rgcc, March 6, 1997
  5. ^ Great article for people who wants to write a chess engine by Miguel A. Ballicora, CCC, April 03, 2002
  6. ^ Re: A new(?) technique to recognize draws by Dan Andersson, June 01, 2002
  7. ^ Re: Aquarium IDEA, repetitions, and minimax over cycles by syzygy, OpenChess Forum, September 22, 2012
  8. ^ Khet (game) from Wikipedia
  9. ^ Information and search in computer chess (Godescu) by BB+, OpenChess Forum, December 12, 2011
  10. ^ A new algorithm accounting for the uncertainty in eval funcs by Tom Holden, CCC, November 12, 2014

Up one level