1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280
//! Defines search-related types and traits. use std::thread; use std::time::Duration; use std::sync::Arc; use std::sync::mpsc::{Sender, Receiver, TryRecvError}; use uci::SetOption; use moves::Move; use value::*; use depth::*; use ttable::*; use search_node::SearchNode; /// Parameters describing a search. /// /// **Important note:** `lower_bound` and `upper_bound` fields /// together give the interval within which an as precise as possible /// evaluation is required. If during the search is determined that /// the exact evaluation is outside of this interval, the search may /// return a value that is closer to the the interval bounds than the /// exact evaluation, but always staying on the correct side of the /// interval (i.e. "fail-soft" semantics). #[derive(Clone, Debug)] pub struct SearchParams<T: SearchNode> { /// A number identifying the search. pub search_id: usize, /// The root position for the search. pub position: T, /// The requested search depth. /// /// Should be between `0` and `DEPTH_MAX`. pub depth: Depth, /// The lower bound for the search. /// /// Should be no lesser than `VALUE_MIN`. pub lower_bound: Value, /// The upper bound for the search. /// /// Should be greater than `lower_bound`, but no greater than /// `VALUE_MAX`. pub upper_bound: Value, /// Restricts the analysis to the supplied list of moves only. /// /// * All moves in the list should be legal. /// /// * The same move should not occur more than once. /// /// * If the root position is final, the supplied list of moves /// should be empty. /// /// The behavior of the search is *undefined* if the root position /// is not final, but `searchmoves` is empty. pub searchmoves: Vec<Move>, } /// A progress report from a search. #[derive(Clone, Debug)] pub struct SearchReport<T> { /// The ID assigned to the search. /// /// Should be the same for all reports from a given search. pub search_id: usize, /// The number of positions searched so far. /// /// Should be no lesser than the value sent in the previous /// report. pub searched_nodes: u64, /// The search depth completed so far. /// /// Should be no lesser than `0`. Also, no lesser than the value /// sent in the previous report, and no greater than the requested /// search depth. If the search has not been forcefully stopped, /// the last reported `depth` should be the requested search /// depth. /// /// **Note:** Depth-first searches should send `0` in all reports /// except the last one. pub depth: Depth, /// The evaluation of the root position so far, or `VALUE_UNKNOWN` /// if not available. /// /// If the search has not been forcefully stopped, the last report /// should contain the calculated final evaluation. /// /// **Note:** Depth-first searches should send `VALUE_UNKNOWN` in /// all reports except the last one. pub value: Value, /// Whether the search is done. /// /// Should be `false` for all reports except the last one. pub done: bool, /// Auxiliary data. /// /// For example, this may contain calculated principal /// variation(s). pub data: T, } /// A trait for executing iterative deepening 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. pub trait DeepeningSearch: SetOption { /// The type of transposition table that the implementation works /// with. type Ttable: Ttable; /// The type of search node that the implementation works with. type SearchNode: SearchNode; /// The type of auxiliary data that search progress reports carry. type ReportData; /// Creates a new instance. /// /// `tt` supplies a transposition table instance for the search /// algorithm to work with. fn new(tt: Arc<Self::Ttable>) -> Self; /// Starts a new search. /// /// This method must not block the current thread. After calling /// `start_search`, `wait_report` and `try_recv_report` will be /// called periodically until the returned report indicates that /// the search is done. A new search will not be started until the /// previous search is done. /// /// **Important note:** The executing search must generate /// periodic reports, informing about its current progress. Also, /// the executing search must continuously update the /// transposition table so that, at each moment, it contains the /// results of the work done so far. fn start_search(&mut self, params: SearchParams<Self::SearchNode>); /// Waits until a search progress report is available, timing out /// after a specified duration or earlier. fn wait_report(&self, timeout_after: Duration); /// Attempts to return a search progress report without blocking. fn try_recv_report(&mut self) -> Result<SearchReport<Self::ReportData>, TryRecvError>; /// Sends a message to the currently executing search. /// /// The message 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 current search. /// /// * Receiving two or more termination requests for the same /// search does not cause any problems. /// /// **Note:** Normally, after sending one or more `"TERMINATE"` /// messages, `wait_report` and `try_recv_report` methods will /// continue to be called periodically until the returned report /// indicates that the search is done. fn send_message(&mut self, msg: &str); } /// 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. pub trait Search: SetOption { /// The type of transposition table that the implementation works /// with. type Ttable: Ttable; /// The type of search node that the implementation works with. type SearchNode: SearchNode; /// The type of auxiliary data that search progress reports carry. type ReportData; /// 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. fn spawn(params: SearchParams<Self::SearchNode>, tt: Arc<Self::Ttable>, reports: Sender<SearchReport<Self::ReportData>>, messages: Receiver<String>) -> thread::JoinHandle<Value>; }