ncpig 0.6.1

Non-Cooperative Perfect Information Games, and algorithms to play them.
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
106
107

//! Search algorithms for determining an [`Action`] to take at the [`State`] of a [`Game`].

pub mod maxn;
pub mod mcts;
pub mod random;
pub mod user_input;

use std::cmp::Ordering;
use std::collections::HashMap;
use std::error::Error;
use std::hash::Hash;

use crate::game::Game;
#[cfg(doc)]
use crate::game::{Action, State};

/// A search algorithm that gives all the available actions a relative score.
///
/// It is generic over `N`-player [`Game`]s.
pub trait SearchScore<const N: usize, G: Game<N>>
where
    G::Action: Hash + Eq,
{
    /// The error type returned by a [`SearchScore`] algorithm.
    type Error: SearchError;

    /// The type representing the relative score given to each action.
    ///
    /// Note that this does not have to be the same thing as the [`Game::Score`].
    type Score: PartialOrd;

    /// Give each of the actions at the current [`Game`] [`State`] a relative score.
    ///
    /// Note that larger scores should indicate better results.
    fn score_actions(
        &self,
        game: &G,
        state: &G::State,
    ) -> Result<HashMap<G::Action, Self::Score>, Self::Error>;
}

/// A search algorithm that ranks the actions from those available.
///
/// It is generic over `N`-player [`Game`]s.
pub trait SearchRank<const N: usize, G: Game<N>> {
    /// The error type returned by a [`SearchRank`] algorithm.
    type Error: SearchError;

    /// Rank the actions (from worst to best), to take at the current [`State`] of the [`Game`].
    ///
    /// The worst action to take is at index 0 and the best action you can take by [`Vec::pop`]ing
    /// off the last element.
    fn rank_actions(&self, game: &G, state: &G::State) -> Result<Vec<G::Action>, Self::Error>;
}

/// blanket impl of [`SearchRank`] for everything that impl [`SearchScore`]
impl<const N: usize, G, T> SearchRank<N, G> for T
where
    G: Game<N>,
    G::Action: Hash + Eq,
    T: SearchScore<N, G> + InternalSearch,
{
    type Error = <T as SearchScore<N, G>>::Error;

    fn rank_actions(&self, game: &G, state: &G::State) -> Result<Vec<G::Action>, Self::Error> {
        let scores = self.score_actions(game, state)?;
        let mut score_pairs = scores.into_iter().collect::<Vec<_>>();
        score_pairs.sort_unstable_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(Ordering::Equal));
        Ok(score_pairs.into_iter().map(|(action, _)| action).collect())
    }
}

/// A search algorithm that chooses a single "best" action from those available.
///
/// It is generic over `N`-player [`Game`]s.
pub trait SearchChoose<const N: usize, G: Game<N>> {
    /// The error type returned by a [`SearchChoose`] algorithm.
    type Error: SearchError;

    /// Determine the best action to take in the [`Game`] given the current [`State`].
    fn choose_action(&self, game: &G, state: &G::State) -> Result<Option<G::Action>, Self::Error>;
}

/// blanket impl of [`SearchChoose`] for everything that impl [`SearchRank`]
impl<const N: usize, G, T> SearchChoose<N, G> for T
where
    G: Game<N>,
    G::Action: Hash + Eq,
    T: SearchRank<N, G> + InternalSearch,
{
    type Error = <T as SearchRank<N, G>>::Error;

    fn choose_action(&self, game: &G, state: &G::State) -> Result<Option<G::Action>, Self::Error> {
        let mut rank = self.rank_actions(game, state)?;
        Ok(rank.pop())
    }
}

/// This is a dummy marker trait for search algorithms implemented internally in [`ncpig`].
///
/// This allows us to have the blanket impls for [`SearchRank`] & [`SearchChoose`] for these
/// internal algorithms. If anyone else every implemented an algorithm external to [`ncpig`] then
/// they wouldn't get the automatic implementations.
trait InternalSearch {}

/// Errors returned by a [`SearchScore`]/[`SearchRank`]/[`SearchChoose`] algorithm.
pub trait SearchError: Error {}