Search

From Chessprogramming wiki
Jump to: navigation, 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.

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

Search versus Evaluation

Publications

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

2015 ...

2020 ...

Forum Posts

1999

2000 ...

2005 ...

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

2010 ...

2015 ...

2020 ...

External Links

A* search algorithm from Wikipedia
Jack DeJohnette, John McLaughlin, Herbie Hancock, Joe Henderson

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. Re: Interesting ideas by Karlo Bala Jr., CCC, September 09, 2015
  9. Khet (game) from Wikipedia
  10. Information and search in computer chess (Godescu) by BB+, OpenChess Forum, December 12, 2011
  11. A new algorithm accounting for the uncertainty in eval funcs by Tom Holden, CCC, November 12, 2014

Up one Level