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

use std::cmp::Ordering;
use std::fmt::{Debug, Formatter};

use internal_iterator::InternalIterator;
use rand::Rng;

use crate::ai::Bot;
use crate::ai::minimax::{Heuristic, minimax, minimax_value};
use crate::board::{Board, Outcome, Player};
use crate::wdl::POV;

/// Heuristic with `bound()-length` for win, `-bound()+length` for loss and 0 for draw.
/// This means the sign of the final minimax value means forced win, forced loss or unknown, and the selected move is
/// the shortest win of the longest loss.
#[derive(Debug)]
pub struct SolverHeuristic;

impl<B: Board> Heuristic<B> for SolverHeuristic {
    type V = i32;

    fn bound(&self) -> Self::V {
        i32::MAX
    }

    fn value(&self, board: &B, length: u32) -> i32 {
        board.outcome().map_or(0, |p| {
            p.pov(board.next_player()).sign::<i32>() * (i32::MAX - length as i32)
        })
    }
}

/// Return which player can force a win if any. Both forced draws and unknown results are returned as `None`.
pub fn find_forcing_winner(board: &impl Board, depth: u32) -> Option<Player> {
    let value = minimax_value(board, &SolverHeuristic, depth);
    match value.cmp(&0) {
        Ordering::Less => Some(board.next_player().other()),
        Ordering::Equal => None,
        Ordering::Greater => Some(board.next_player()),
    }
}

/// Return whether this board is a double forced draw, ie. no matter what either player does the game can only end in a draw.
/// Returns `None` if the result is unknown.
pub fn is_double_forced_draw(board: &impl Board, depth: u32) -> Result<bool, ()> {
    if board.outcome() == Some(Outcome::Draw) { return Ok(true); }
    if board.outcome().is_some() { return Ok(false); }
    if depth == 0 { return Err(()); }

    //TODO this is kind of ugly, consider writing a function try_fold or something
    //  that handles this back and forth conversion
    let result = board.available_moves().find_map(|mv| {
        let child = board.clone_and_play(mv);

        match is_double_forced_draw(&child, depth - 1) {
            Ok(true) => None,
            Ok(false) => Some(false),
            Err(()) => Some(true),
        }
    });

    match result {
        Some(true) => Err(()),
        Some(false) => Ok(false),
        None => Ok(true)
    }
}

pub struct SolverBot<R: Rng> {
    depth: u32,
    rng: R,
}

impl<R: Rng> Debug for SolverBot<R> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "SolverBot {{ depth: {} }}", self.depth)
    }
}

impl<R: Rng> SolverBot<R> {
    pub fn new(depth: u32, rng: R) -> Self {
        assert!(depth > 0);
        SolverBot { depth, rng }
    }
}

impl<B: Board, R: Rng> Bot<B> for SolverBot<R> {
    fn select_move(&mut self, board: &B) -> B::Move {
        minimax(board, &SolverHeuristic, self.depth, &mut self.rng).best_move.unwrap()
    }
}