1use crate::oracle::{OracleCase, probe_oracle};
2use crate::{
3 Algorithm, Cell, Column, GameResult, Move, Position, Score, ScoreKind, SearchLimits,
4 SearchReport, Side, iterative_search, perft, search,
5};
6use std::fmt::Write;
7use std::str::FromStr;
8#[cfg(not(target_arch = "wasm32"))]
9use std::time::Instant;
10
11pub struct Engine {
13 position: Position,
14 history: Vec<Move>,
15 algorithm: Algorithm,
16 last_report: Option<SearchReport>,
17 last_oracle: Option<Option<&'static OracleCase>>,
18}
19
20impl Default for Engine {
21 fn default() -> Self {
22 Self::new()
23 }
24}
25
26impl Engine {
27 pub fn new() -> Self {
28 Self {
29 position: Position::start(),
30 history: Vec::new(),
31 algorithm: Algorithm::default(),
32 last_report: None,
33 last_oracle: None,
34 }
35 }
36
37 pub fn command(&mut self, line: &str) -> Vec<String> {
38 let words: Vec<_> = line.split_whitespace().collect();
39 let Some(command) = words.first().copied() else {
40 return vec![error("empty_command", "command line is empty")];
41 };
42 match command {
43 "gai" => self.handshake(),
44 "isready" => vec!["readyok".to_owned()],
45 "newgame" => {
46 self.reset();
47 Vec::new()
48 }
49 "setoption" => self.set_option(&words[1..]),
50 "position" => self.set_position(&words[1..]),
51 "go" => self.go(&words[1..]),
52 "legal" => vec![format!(
53 "legalmoves {}",
54 self.position
55 .legal_moves()
56 .into_iter()
57 .map(|mv| mv.to_string())
58 .collect::<Vec<_>>()
59 .join(" ")
60 )],
61 "perft" => self.run_perft(&words[1..]),
62 "oracle" => self.oracle(&words[1..]),
63 "state" => vec![format!("state {}", self.diagnostic_snapshot_json())],
64 "quit" => Vec::new(),
65 _ => vec![error("unknown_command", command)],
66 }
67 }
68
69 pub fn snapshot_json(&self) -> String {
70 self.serialize_snapshot(false)
71 }
72
73 fn diagnostic_snapshot_json(&self) -> String {
74 self.serialize_snapshot(true)
75 }
76
77 fn serialize_snapshot(&self, diagnostics: bool) -> String {
78 let mut json = String::with_capacity(if diagnostics { 8_192 } else { 512 });
79 if diagnostics {
80 json.push_str("{\"game\":\"connect4\",\"columns\":[");
81 } else {
82 json.push_str("{\"columns\":[");
83 }
84 for column_index in 0..Column::COUNT {
85 if column_index > 0 {
86 json.push(',');
87 }
88 json.push('[');
89 for row in 0..Cell::ROWS {
90 if row > 0 {
91 json.push(',');
92 }
93 let cell = Cell::new(Column::new(column_index as u8), row as u8);
94 match self.position.side_at(cell) {
95 Some(Side::Red) => json.push_str("\"R\""),
96 Some(Side::Yellow) => json.push_str("\"Y\""),
97 None => json.push_str("null"),
98 }
99 }
100 json.push(']');
101 }
102 write!(
103 json,
104 "],\"sideToMove\":\"{}\",\"result\":\"{}\",\"winner\":{},",
105 self.position.side_to_move(),
106 result_name(self.position.result()),
107 winner_json(self.position.result())
108 )
109 .expect("writing to String cannot fail");
110
111 json.push_str("\"winningLine\":[");
112 for (index, cell) in self.position.winning_cells().iter().enumerate() {
113 if index > 0 {
114 json.push(',');
115 }
116 write!(json, "\"{cell}\"").expect("writing to String cannot fail");
117 }
118 json.push_str("],\"legalMoves\":[");
119 for (index, mv) in self.position.legal_moves().into_iter().enumerate() {
120 if index > 0 {
121 json.push(',');
122 }
123 write!(json, "\"{mv}\"").expect("writing to String cannot fail");
124 }
125 json.push_str("],\"history\":[");
126 for (index, mv) in self.history.iter().enumerate() {
127 if index > 0 {
128 json.push(',');
129 }
130 write!(json, "\"{mv}\"").expect("writing to String cannot fail");
131 }
132 if diagnostics {
133 write!(json, "],\"algorithm\":\"{}\",\"oracle\":", self.algorithm)
134 .expect("writing to String cannot fail");
135 match self.last_oracle {
136 None => json.push_str("null"),
137 Some(None) => json.push_str("{\"status\":\"miss\"}"),
138 Some(Some(case)) => {
139 write!(
140 json,
141 "{{\"status\":\"hit\",\"source\":\"gamesolver-tutorial\",\"notation\":\"{}\",\"ponsScore\":{},\"outcome\":\"{}\",\"description\":\"{}\"}}",
142 case.notation,
143 case.pons_score,
144 case.outcome.name(),
145 case.description
146 )
147 .expect("writing to String cannot fail");
148 }
149 }
150 json.push_str(",\"analysis\":");
151 if let Some(report) = &self.last_report {
152 write_report_json(&mut json, report);
153 } else {
154 json.push_str("null");
155 }
156 } else {
157 json.push_str("],\"analysis\":");
158 if let Some(report) = &self.last_report {
159 json.push_str("{\"bestMove\":");
160 match report.best_move {
161 Some(mv) => {
162 write!(json, "\"{mv}\"").expect("writing to String cannot fail");
163 }
164 None => json.push_str("null"),
165 }
166 json.push('}');
167 } else {
168 json.push_str("null");
169 }
170 }
171 json.push('}');
172 json
173 }
174
175 fn reset(&mut self) {
176 self.position = Position::start();
177 self.history.clear();
178 self.last_report = None;
179 self.last_oracle = None;
180 }
181
182 fn handshake(&self) -> Vec<String> {
183 vec![
184 "id name ai-connect4".to_owned(),
185 "id author Nick Gustafson".to_owned(),
186 "id game connect4".to_owned(),
187 "option name Algorithm type combo default tt var plain var alpha-beta var ordered var tt"
188 .to_owned(),
189 "option name Depth type spin default 7 min 1 max 42".to_owned(),
190 "extension go iterative depth <depth> [nodes <budget>]".to_owned(),
191 "gaiok".to_owned(),
192 ]
193 }
194
195 fn set_option(&mut self, words: &[&str]) -> Vec<String> {
196 if words.len() != 4
197 || !words[0].eq_ignore_ascii_case("name")
198 || !words[1].eq_ignore_ascii_case("algorithm")
199 || !words[2].eq_ignore_ascii_case("value")
200 {
201 return vec![error(
202 "bad_setoption",
203 "expected: setoption name Algorithm value <algorithm>",
204 )];
205 }
206 match Algorithm::from_str(words[3]) {
207 Ok(algorithm) => {
208 self.algorithm = algorithm;
209 self.last_report = None;
210 Vec::new()
211 }
212 Err(message) => vec![error("bad_option_value", message)],
213 }
214 }
215
216 fn set_position(&mut self, words: &[&str]) -> Vec<String> {
217 if words.first().copied() != Some("startpos") {
218 return vec![error(
219 "bad_position",
220 "Connect Four supports: position startpos [moves ...]",
221 )];
222 }
223 let move_words = match words.get(1) {
224 None => &[][..],
225 Some(&"moves") => &words[2..],
226 Some(_) => {
227 return vec![error("bad_position", "expected 'moves' after 'startpos'")];
228 }
229 };
230 let mut moves = Vec::with_capacity(move_words.len());
231 for word in move_words {
232 match Move::from_str(word) {
233 Ok(mv) => moves.push(mv),
234 Err(message) => return vec![error("bad_move", message)],
235 }
236 }
237 match Position::from_moves(&moves) {
238 Ok(position) => {
239 self.position = position;
240 self.history = moves;
241 self.last_report = None;
242 self.last_oracle = None;
243 Vec::new()
244 }
245 Err(move_error) => vec![error("illegal_move", &move_error.to_string())],
246 }
247 }
248
249 fn go(&mut self, words: &[&str]) -> Vec<String> {
250 let (iterative, limit_words) = match words.first() {
251 Some(&"iterative") => (true, &words[1..]),
252 _ => (false, words),
253 };
254 let Ok(limits) = parse_limits(limit_words) else {
255 return vec![error(
256 "bad_go",
257 "expected: go [iterative] depth <1..42> [nodes <positive integer>]",
258 )];
259 };
260 if self.position.result() != GameResult::Ongoing {
261 return vec![
262 "info string game is already over".to_owned(),
263 "bestmove (none)".to_owned(),
264 ];
265 }
266 #[cfg(target_arch = "wasm32")]
267 let started = js_sys::Date::now();
268 #[cfg(not(target_arch = "wasm32"))]
269 let started = Instant::now();
270
271 let (report, reported_nodes, completed_depth, iterations) = if iterative {
272 let iterative = iterative_search(self.position, self.algorithm, limits);
273 (
274 iterative.result,
275 iterative.total_nodes,
276 iterative.completed_depth,
277 iterative.iterations.len(),
278 )
279 } else {
280 let report = search(self.position, self.algorithm, limits);
281 let nodes = report.stats.nodes;
282 (report, nodes, limits.depth, 1)
283 };
284
285 #[cfg(target_arch = "wasm32")]
286 let elapsed_millis = (js_sys::Date::now() - started).max(0.0) as u128;
287 #[cfg(not(target_arch = "wasm32"))]
288 let elapsed_millis = started.elapsed().as_millis();
289 let millis = elapsed_millis.max(1);
290 let nps = u128::from(reported_nodes) * 1_000 / millis;
291 let pv = report
292 .principal_variation
293 .iter()
294 .map(ToString::to_string)
295 .collect::<Vec<_>>()
296 .join(" ");
297 let best_move = report
298 .best_move
299 .map_or_else(|| "(none)".to_owned(), |mv| mv.to_string());
300 let info = format!(
301 "info depth {} {} nodes {} iterationnodes {} nps {} time {} cutoffs {} tthits {} ttstores {} completed {} iterations {} pv {}",
302 completed_depth,
303 score_protocol(report.score),
304 reported_nodes,
305 report.stats.nodes,
306 nps,
307 elapsed_millis,
308 report.stats.cutoffs,
309 report.stats.tt_hits,
310 report.stats.tt_stores,
311 report.completed,
312 iterations,
313 pv
314 );
315 self.last_report = Some(report);
316 vec![info, format!("bestmove {best_move}")]
317 }
318
319 fn run_perft(&self, words: &[&str]) -> Vec<String> {
320 if words.len() != 1 {
321 return vec![error("bad_perft", "expected: perft <depth 0..12>")];
322 }
323 let Ok(depth) = words[0].parse::<u8>() else {
324 return vec![error("bad_perft", "depth must be an integer")];
325 };
326 if depth > 12 {
327 return vec![error("bad_perft", "depth must be between 0 and 12")];
328 }
329 let mut position = self.position;
330 #[cfg(target_arch = "wasm32")]
331 let started = js_sys::Date::now();
332 #[cfg(not(target_arch = "wasm32"))]
333 let started = Instant::now();
334
335 let nodes = perft(&mut position, depth);
336
337 #[cfg(target_arch = "wasm32")]
338 let elapsed_millis = (js_sys::Date::now() - started).max(0.0) as u128;
339 #[cfg(not(target_arch = "wasm32"))]
340 let elapsed_millis = started.elapsed().as_millis();
341
342 vec![format!(
343 "perft depth {depth} nodes {nodes} time {}",
344 elapsed_millis
345 )]
346 }
347
348 fn oracle(&mut self, words: &[&str]) -> Vec<String> {
349 if !words.is_empty() {
350 return vec![error("bad_oracle", "expected: oracle")];
351 }
352 let hit = probe_oracle(self.position);
353 self.last_oracle = Some(hit);
354 match hit {
355 Some(case) => vec![format!(
356 "oracle source gamesolver-tutorial notation {} score {} outcome {}",
357 case.notation,
358 case.pons_score,
359 case.outcome.name()
360 )],
361 None => vec!["oracle miss".to_owned()],
362 }
363 }
364}
365
366fn parse_limits(words: &[&str]) -> Result<SearchLimits, ()> {
367 if words.len() != 2 && words.len() != 4 {
368 return Err(());
369 }
370 let mut depth = None;
371 let mut nodes = None;
372 for pair in words.chunks_exact(2) {
373 match pair {
374 ["depth", value] => {
375 let value = value.parse::<u8>().map_err(|_| ())?;
376 if !(1..=42).contains(&value) {
377 return Err(());
378 }
379 if depth.replace(value).is_some() {
380 return Err(());
381 }
382 }
383 ["nodes", value] => {
384 let value = value.parse::<u64>().map_err(|_| ())?;
385 if value == 0 {
386 return Err(());
387 }
388 if nodes.replace(value).is_some() {
389 return Err(());
390 }
391 }
392 _ => return Err(()),
393 }
394 }
395 let depth = depth.ok_or(())?;
396 Ok(SearchLimits { depth, nodes })
397}
398
399fn score_protocol(score: Score) -> String {
400 match score.kind() {
401 ScoreKind::ForcedWin { plies } => format!("score win {plies}"),
402 ScoreKind::ForcedLoss { plies } => format!("score loss {plies}"),
403 ScoreKind::Estimate(value) => format!("score eval {value}"),
404 }
405}
406
407fn write_report_json(json: &mut String, report: &SearchReport) {
408 write!(
409 json,
410 "{{\"algorithm\":\"{}\",\"depth\":{},\"completed\":{},\"bestMove\":",
411 report.algorithm, report.requested_depth, report.completed
412 )
413 .expect("writing to String cannot fail");
414 match report.best_move {
415 Some(mv) => write!(json, "\"{mv}\"").expect("writing to String cannot fail"),
416 None => json.push_str("null"),
417 }
418 json.push_str(",\"score\":");
419 write_score_json(json, report.score);
420 json.push_str(",\"pv\":[");
421 for (index, mv) in report.principal_variation.iter().enumerate() {
422 if index > 0 {
423 json.push(',');
424 }
425 write!(json, "\"{mv}\"").expect("writing to String cannot fail");
426 }
427 write!(
428 json,
429 "],\"stats\":{{\"nodes\":{},\"leaves\":{},\"cutoffs\":{},\"ttProbes\":{},\"ttHits\":{},\"ttStores\":{},\"maxPly\":{}}},\"rootBranches\":[",
430 report.stats.nodes,
431 report.stats.leaves,
432 report.stats.cutoffs,
433 report.stats.tt_probes,
434 report.stats.tt_hits,
435 report.stats.tt_stores,
436 report.stats.max_ply
437 )
438 .expect("writing to String cannot fail");
439 for (index, branch) in report.root_branches.iter().enumerate() {
440 if index > 0 {
441 json.push(',');
442 }
443 write!(
444 json,
445 "{{\"move\":\"{}\",\"nodes\":{},\"cutoffs\":{},\"completed\":{},\"score\":",
446 branch.mv, branch.nodes, branch.cutoffs, branch.completed
447 )
448 .expect("writing to String cannot fail");
449 write_score_json(json, branch.score);
450 json.push('}');
451 }
452 json.push_str("]}");
453}
454
455fn write_score_json(json: &mut String, score: Score) {
456 match score.kind() {
457 ScoreKind::ForcedWin { plies } => {
458 write!(json, "{{\"kind\":\"win\",\"plies\":{plies}}}")
459 .expect("writing to String cannot fail");
460 }
461 ScoreKind::ForcedLoss { plies } => {
462 write!(json, "{{\"kind\":\"loss\",\"plies\":{plies}}}")
463 .expect("writing to String cannot fail");
464 }
465 ScoreKind::Estimate(value) => {
466 write!(json, "{{\"kind\":\"estimate\",\"value\":{value}}}")
467 .expect("writing to String cannot fail");
468 }
469 }
470}
471
472const fn result_name(result: GameResult) -> &'static str {
473 match result {
474 GameResult::Ongoing => "ongoing",
475 GameResult::Draw => "draw",
476 GameResult::Win(_) => "win",
477 }
478}
479
480fn winner_json(result: GameResult) -> &'static str {
481 match result {
482 GameResult::Win(Side::Red) => "\"R\"",
483 GameResult::Win(Side::Yellow) => "\"Y\"",
484 GameResult::Ongoing | GameResult::Draw => "null",
485 }
486}
487
488fn error(code: &str, message: &str) -> String {
489 format!("error code {code} message {}", message.replace('\n', " "))
490}