Trait alcibiades::Search [−] [src]

pub trait Search: SetOption {
    type Ttable: Ttable;
    type SearchNode: SearchNode;
    type ReportData;
    fn spawn(
        params: SearchParams<Self::SearchNode>, 
        tt: Arc<Self::Ttable>, 
        reports: Sender<SearchReport<Self::ReportData>>, 
        messages: Receiver<String>
    ) -> JoinHandle<Value>;
}

A trait used to execute depth-first searches.

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. Normally, this is done by traversing and min-maxing a tree-like data-structure by some algorithm.

There are two types of searches that should be distinguished:

  • Depth-first search (the Search trait).

    Starts at the root position and explores as far as possible along each branch before backtracking.

  • Iterative deepening search (the DeepeningSearch trait).

    A depth-first search is executed with a depth of one ply, then the depth is incremented and another search is executed. This process is repeated until the search is terminated or the requested search depth is reached. In case of a terminated search, the engine can always fall back to the move selected in the last iteration of the search.

To implement your own search algorithm, you must define a type that implements either Search or DeepeningSearch trait.

Note: You can use stock::Deepening to turn a depth-first search into an iterative deepening search.

Associated Types

The type of transposition table that the implementation works with.

The type of search node that the implementation works with.

The type of auxiliary data that search progress reports carry.

Required Methods

Spawns a new search thread.

A join handle is returned that gives the calculated evaluation for the root position, or VALUE_UNKNOWN if the search was terminated.

  • params specifies the exact parameters for the new search -- root position, search depth etc.

  • tt supplies a transposition table instance.

    The search thread must continuously update tt so that, at each moment, it contains the results of the work done so far.

  • reports gives the sending-half of progress reports' channel.

    The search thread must send periodic reports to reports, informing about the current progress of the search.

  • messages gives the receiving-half of control messages' channel.

    Control messages' format is not specified, but the implementation must meet the following requirements:

    • Unrecognized messages are ignored.

    • The message "TERMINATE" is recognized as a request to terminate the search.

    • Receiving two or more termination requests does not cause problems.

Implementors