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

//! Monte Carlo Tree Search expansion strategies.

use std::error::Error;
use std::fmt::Debug;
use std::hash::Hash;

use petgraph::graph::NodeIndex;
use petgraph::{Direction, Graph};

use super::Node;
use crate::prelude::{Game, GameError};

/// MCTS expansion strategy.
///
/// Add one or more nodes to the tree from the provided node.
pub trait Expansion<const N: usize, G: Game<N>, T> {
    /// Errors returned by the expansion strategy.
    type Error: Error;

    /// Expand the set of children on a node.
    fn expand(
        &self,
        game: &G,
        tree: &mut Graph<Node<N, G::State, T>, G::Action>,
        node_idx: NodeIndex,
    ) -> Result<(), Self::Error>;
}

/// Errors associated with the [`Greedy`] [`Expansion`] strategy.
#[derive(Debug, thiserror::Error)]
pub enum GreedyError<const N: usize, G: Game<N>> {
    /// Errors in the [`Game`].
    #[error(transparent)]
    GameError(G::Error),
}

impl<const N: usize, G, E> From<E> for GreedyError<N, G>
where
    G: Game<N, Error = E>,
    E: GameError,
{
    fn from(value: G::Error) -> Self {
        Self::GameError(value)
    }
}

/// Greedy [`Expansion`] method.
///
/// Expands the first child that has not been visited yet.
#[derive(Debug, Default)]
pub struct Greedy;

impl<const N: usize, G, T> Expansion<N, G, T> for Greedy
where
    G: Game<N>,
    G::Action: Hash + Eq + Debug + Clone,
    G::State: Clone,
    T: Default + Copy + Debug,
{
    type Error = GreedyError<N, G>;

    fn expand(
        &self,
        game: &G,
        tree: &mut Graph<Node<N, G::State, T>, G::Action>,
        node_idx: NodeIndex,
    ) -> Result<(), Self::Error> {
        let node = &tree[node_idx];
        log::debug!("running the greedy expansion strategy from {:?}", node);

        let expanded_actions = tree
            .edges_directed(node_idx, Direction::Outgoing)
            .map(|er| er.weight())
            .collect::<Vec<_>>();
        for action in game.available_actions(&node.state)? {
            if !expanded_actions.contains(&&action) {
                let newstate = game.do_action(&action, node.state.clone())?;
                let newnode = Node::new(newstate);
                let newnode_idx = tree.add_node(newnode);
                tree.add_edge(node_idx, newnode_idx, action);
                return Ok(());
            }
        }
        log::debug!("nothing to expand");
        Ok(())
    }
}