rubot/
tree.rs

1//! A tree implementation used in examples and tests.
2
3use crate::Game;
4use std::convert::TryInto;
5use std::fmt::Debug;
6use std::num::Wrapping;
7use std::ops::Range;
8
9/// A tree node, implements [`Game`][game].
10///
11/// # Examples
12///
13/// ```rust
14/// use rubot::{Bot, ToCompletion, tree::Node};
15///
16/// # #[rustfmt::skip]
17/// let tree = Node::root().with_children(&[
18///     Node::new(false, 4),
19///     Node::new(false, 7).with_children(&[
20///         Node::new(true, 5),
21///         Node::new(true, 3),
22///     ])
23/// ]);
24///
25/// let mut bot = Bot::new(true);
26/// assert_eq!(bot.select(&tree, ToCompletion), Some(0));
27/// ```
28/// [game]: ../trait.Game.html
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct Node {
31    player: bool,
32    // always from the perspective of the tested player
33    fitness: i8,
34    children: Vec<Node>,
35}
36
37impl Game for Node {
38    type Player = bool;
39    type Action = usize;
40    type Fitness = i8;
41    type Actions = Range<usize>;
42
43    fn actions(&self, player: Self::Player) -> (bool, Self::Actions) {
44        (player == self.player, 0..self.children.len())
45    }
46
47    fn execute(&mut self, action: &Self::Action, _: Self::Player) -> Self::Fitness {
48        *self = self.children[*action].clone();
49        // fitness of the child
50        self.fitness
51    }
52
53    fn look_ahead(&self, action: &Self::Action, _: Self::Player) -> Self::Fitness {
54        self.children[*action].fitness
55    }
56
57    fn is_upper_bound(&self, fitness: Self::Fitness, _: Self::Player) -> bool {
58        fitness == i8::MAX
59    }
60
61    fn is_lower_bound(&self, fitness: Self::Fitness, _: Self::Player) -> bool {
62        fitness == i8::MIN
63    }
64}
65
66impl Node {
67    /// Creates a root node, this is equal to `Node::new(true, 0)`.
68    pub fn root() -> Self {
69        Self::new(true, 0)
70    }
71
72    /// Creates a new node with no children.
73    pub fn new(player: bool, fitness: i8) -> Self {
74        Self {
75            player,
76            fitness,
77            children: Vec::new(),
78        }
79    }
80
81    /// Generates a tree from `bytes`, the total amount of tree nodes, excluding the root,
82    /// is currently `bytes.len() - 4`.
83    ///
84    /// The exact algorithm is not specified, so while the output is deterministic, it is not stable between versions
85    /// and changing it will not be a breaking change.
86    pub fn from_bytes(bytes: &[u8]) -> Self {
87        match bytes[0..4].try_into() {
88            Ok(seed) => {
89                let mut seed = u32::from_be_bytes(seed);
90                if seed == 0 {
91                    seed = 0xBAD_5EED;
92                }
93
94                struct XorShiftRng {
95                    x: Wrapping<u32>,
96                    y: Wrapping<u32>,
97                    z: Wrapping<u32>,
98                    w: Wrapping<u32>,
99                }
100
101                impl XorShiftRng {
102                    fn next_u32(&mut self) -> u32 {
103                        let x = self.x;
104                        let t = x ^ (x << 11);
105                        self.x = self.y;
106                        self.y = self.z;
107                        self.z = self.w;
108                        let w = self.w;
109                        self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
110                        self.w.0
111                    }
112                }
113
114                let mut rng = XorShiftRng {
115                    x: Wrapping(seed),
116                    y: Wrapping(seed),
117                    z: Wrapping(seed),
118                    w: Wrapping(seed),
119                };
120
121                let mut root = Node::new(true, 0);
122                for &i in bytes[4..].iter() {
123                    let mut pos = Some(&mut root);
124                    let mut next =
125                        rng.next_u32() as usize % (pos.as_ref().unwrap().children.len() + 1);
126                    while next != pos.as_ref().unwrap().children.len() {
127                        pos.take().map(|node| {
128                            pos = Some(&mut node.children[next]);
129                        });
130                        next = rng.next_u32() as usize % (pos.as_ref().unwrap().children.len() + 1);
131                    }
132
133                    pos.unwrap()
134                        .children
135                        .push(Node::new(rng.next_u32() % 2 == 0, i as i8));
136                }
137
138                root
139            }
140            Err(_) => Self::root(),
141        }
142    }
143
144    /// Sets the children of `self` to `children`.
145    /// Previous children are forgotten.
146    pub fn with_children(mut self, children: &[Node]) -> Self {
147        self.children.clear();
148        self.children.extend_from_slice(children);
149        self
150    }
151
152    // Add a `child` node to `self`
153    pub fn push_child(&mut self, child: Node) {
154        self.children.push(child);
155    }
156
157    /// Returns how many children this node possesses
158    pub fn child_count(&self) -> usize {
159        self.children.len()
160    }
161
162    /// Returns whether or not this node is a leaf, meaning that
163    /// it does not have any children
164    pub fn is_leaf(&self) -> bool {
165        self.children.is_empty()
166    }
167}
rubot/tree.rs

rubot/
tree.rs
