Data structures for proper monte carlo search

2 files changed, 98 insertions, 0 deletions

diff --git a/src/strategy/mod.rs b/src/strategy/mod.rs
index 5b6e779..ceb624b 100644
--- a/src/strategy/mod.rs
+++ b/src/strategy/mod.rs
@@ -1 +1,2 @@
 pub mod monte_carlo;
+pub mod monte_carlo_tree;
diff --git a/src/strategy/monte_carlo_tree.rs b/src/strategy/monte_carlo_tree.rs
new file mode 100644
index 0000000..b168bcd
--- /dev/null
+++ b/src/strategy/monte_carlo_tree.rs
@@ -0,0 +1,97 @@
+use engine::command::*;
+use engine::status::GameStatus;
+use engine::bitwise_engine::{Player, BitwiseGameState};
+use engine::constants::*;
+use engine::geometry::*;
+
+use rand::{Rng, XorShiftRng, SeedableRng};
+use time::{Duration, PreciseTime};
+
+
+enum SearchTree {
+    Leaf(NodeStats),
+    FullyExploredNode(FullyExploredStats),
+    PartiallyExploredNode(PartiallyExploredStats)
+}
+
+struct NodeStats {
+    wins: u32,
+    attempts: u32
+}
+
+struct FullyExploredStats {
+    wins: u32,
+    attempts: u32,
+    explored: Vec<(Command, SearchTree)>
+}
+
+struct PartiallyExploredStats {
+    wins: u32,
+    attempts: u32,
+    explored: Vec<(Command, SearchTree)>,
+    unexplored: Vec<Command>
+}
+
+impl SearchTree {
+    fn create_node(state: &Player) -> SearchTree {
+        SearchTree::PartiallyExploredNode(PartiallyExploredStats {
+            wins: 0,
+            attempts: 0,
+            explored: Vec::new(),
+            unexplored: Vec::new() //TODO
+        })
+    }
+}
+
+impl FullyExploredStats {
+    fn node_with_highest_ucb<'a>(&'a self) -> &'a (Command, SearchTree) {
+        //TODO
+        &self.explored[0]
+    }
+}
+
+impl PartiallyExploredStats {
+    fn add_node(&mut self, command: Command) {
+        //TODO
+    }
+}
+
+
+pub fn choose_move(state: &BitwiseGameState, start_time: PreciseTime, max_time: Duration) -> Command {
+    use self::SearchTree::*;
+    
+    // create root node as partially explored node
+    // creating a new node needs to populate all (valid) unexplored moves
+
+    let root = SearchTree::create_node(&state.player);
+
+    loop {
+        //tree_search(&state, &mut root);
+    }
+    
+    Command::Nothing    
+}
+
+/*
+fn tree_search(state: &BitwiseGameState, tree: &mut SearchTree) -> bool {
+    match tree {
+        Leaf(stats) => {
+            // ???
+            false
+        },
+        FullyExploredNode(stats) => {
+            let (next_command, next_tree) = stats.node_with_highest_ucb();
+            tree_search(state, &mut next_tree)
+            // TODO: Swap players?
+            // TODO: Back-propagation?
+        },
+        PartiallyExploredNode(stats) => {
+            //   choose random command and add as partially explored node to the tree
+            //   simulate to end with random commands
+            //   back-propagate (remember to keep a stack of commands to that point node)
+            //   convert to fully explored if applicable
+        }
+    }
+    
+}
+*/