rival 0.1.0

A framework for creating computer players for turn-based games
Documentation 
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

use std::hash::Hash;

use crate::cache::Cached;
use crate::game::Game;

pub(crate) type Value = i32;

#[derive(Clone, Debug)]
pub(crate) struct SearchResult<M, const N: usize> {
    depth: u32,
    value: [Value; N],
    pub best: Option<M>,
}

pub(crate) trait Search<const N: usize> {
    type Move;

    fn max_n(&mut self, depth: u32, scores: &mut [Value; N]) -> SearchResult<Self::Move, N>;
}

impl<G: ?Sized + Game<N>, const N: usize> Search<N> for G {
    type Move = G::Move;

    fn max_n(&mut self, depth: u32, scores: &mut [Value; N]) -> SearchResult<Self::Move, N> {
        let moves = self.moves();
        let turn = self.turn();

        if (depth <= 0 && self.quiet()) || moves.is_empty() {
            SearchResult {
                depth: 0,
                value: self.value(),
                best: None,
            }
        } else {
            let mut best = SearchResult {
                depth: 0,
                value: [Value::MIN; N],
                best: None,
            };

            for m in moves {
                self.perform(&m);
                let current = self.max_n(depth - 1, scores);
                self.revert(&m);

                if current.value[turn] > best.value[turn] {
                    best = SearchResult {
                        depth: current.depth + 1,
                        value: current.value,
                        best: Some(m),
                    };
                }
            }

            best
        }
    }
}

impl<G: Game<N> + Clone + Eq + Hash, const N: usize> Search<N> for Cached<G, N> where G::Move: Clone {
    type Move = G::Move;

    fn max_n(&mut self, depth: u32, scores: &mut [Value; N]) -> SearchResult<Self::Move, N> {
        if let Some(result) = self.cache.get(&self.game) {
            if result.depth >= depth {
                return result.clone();
            }
        }

        let moves = self.moves();
        let turn = self.turn();

        if (depth <= 0 && self.quiet()) || moves.is_empty() {
            SearchResult {
                depth: 0,
                value: self.value(),
                best: None,
            }
        } else {
            let mut best = SearchResult {
                depth: 0,
                value: [Value::MIN; N],
                best: None,
            };

            for m in moves {
                self.perform(&m);
                let current = self.max_n(depth - 1, scores);
                self.revert(&m);

                if current.value[turn] > best.value[turn] {
                    best = SearchResult {
                        depth: current.depth + 1,
                        value: current.value,
                        best: Some(m),
                    };
                }
            }

            self.cache.insert(self.game.clone(), best.clone());

            best
        }
    }
}