<commit_before>//! Upper confidence bound (UCB1) algorithm for graph search.

use crate::backprop::BackpropSelector;
use crate::game::{Game, State, Statistics};
use crate::graph::{EdgeData, VertexData};
use crate::rollout::RolloutSelector;
use log::{error, trace};
use rand::Rng;
use search_graph;

use std::cmp::Ordering;
use std::error::Error;
use std::f64;
use std::fmt;
use std::result::Result;

/// Represents success when computing the UCB score for a child.
pub enum UcbSuccess<'id> {
  /// No (finite) value can be computed, but the UCB policy indicates that
  /// this child should be selected. E.g., the child has not yet been visited.
  Select(search_graph::view::EdgeRef<'id>),
  /// A value is computed.
  Value(search_graph::view::EdgeRef<'id>, f64),
}

/// Represents error conditions when computing the UCB score for a child.
#[derive(Clone, Debug)]
pub enum UcbError {
  /// An error was encountered during computation of UCB score (such as
  /// encountering a `None` result when `PartialCmp`'ing two floating-point
  /// values).
  InvalidComputation,
}

unsafe impl Send for UcbError {}

/// Lazy iterator over UCB scores for a series of edges.
pub struct EdgeUcbIter<'a, 'b, 'id, G, I>
where
  G: Game,
  I: Iterator<Item = search_graph::view::EdgeRef<'id>>,
{
  log_parent_visits: f64,
  explore_bias: f64,
  graph: &'b search_graph::view::View<'a, 'id, G::State, VertexData, EdgeData<G>>,
  edges: I,
}

impl fmt::Display for UcbError {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    match *self {
      UcbError::InvalidComputation => write!(f, "Numerical error when computing UCB score"),
    }
  }
}

impl Error for UcbError {
  fn description(&self) -> &str {
    match *self {
      UcbError::InvalidComputation => "invalid computation",
    }
  }
}

impl<'a, 'b, 'id, G, I> EdgeUcbIter<'a, 'b, 'id, G, I>
where
  G: Game,
  I: Iterator<Item = search_graph::view::EdgeRef<'id>>,
{
  /// Constructs a new `EdgeUcbIter` that will compute UCB scores using the
  /// given constants. All floating-point values are assumed to be valid
  /// floating-point values and positive.
  ///
  ///  - `log_parent_visits`: ln(visits to parent vertex).
  ///  - `explore_bias`: scalar bias controlling tradeoff between search width
  ///    and search depth (lower = wider, higher = deeper).
  ///  - `role`: the game role whose score to maximize.
  ///  - `edges`: an iterator over edge handles for which to compute UCB
  ///    scores. This should usually be a list of child edges which share a
  ///    parent vertex.
  pub fn new(
    log_parent_visits: f64,
    explore_bias: f64,
    graph: &'b search_graph::view::View<'a, 'id, G::State, VertexData, EdgeData<G>>,
    edges: I,
  ) -> Self {
    EdgeUcbIter {
      log_parent_visits: log_parent_visits,
      explore_bias: explore_bias,
      graph,
      edges: edges,
    }
  }
}

impl<'a, 'b, 'id, G, I> Iterator for EdgeUcbIter<'a, 'b, 'id, G, I>
where
  G: Game,
  I: Iterator<Item = search_graph::view::EdgeRef<'id>>,<commit_msg>Delete docs for function parameter that doesn't exist anymore.<commit_after>//! Upper confidence bound (UCB1) algorithm for graph search.

use crate::backprop::BackpropSelector;
use crate::game::{Game, State, Statistics};
use crate::graph::{EdgeData, VertexData};
use crate::rollout::RolloutSelector;
use log::{error, trace};
use rand::Rng;
use search_graph;

use std::cmp::Ordering;
use std::error::Error;
use std::f64;
use std::fmt;
use std::result::Result;

/// Represents success when computing the UCB score for a child.
pub enum UcbSuccess<'id> {
  /// No (finite) value can be computed, but the UCB policy indicates that
  /// this child should be selected. E.g., the child has not yet been visited.
  Select(search_graph::view::EdgeRef<'id>),
  /// A value is computed.
  Value(search_graph::view::EdgeRef<'id>, f64),
}

/// Represents error conditions when computing the UCB score for a child.
#[derive(Clone, Debug)]
pub enum UcbError {
  /// An error was encountered during computation of UCB score (such as
  /// encountering a `None` result when `PartialCmp`'ing two floating-point
  /// values).
  InvalidComputation,
}

unsafe impl Send for UcbError {}

/// Lazy iterator over UCB scores for a series of edges.
pub struct EdgeUcbIter<'a, 'b, 'id, G, I>
where
  G: Game,
  I: Iterator<Item = search_graph::view::EdgeRef<'id>>,
{
  log_parent_visits: f64,
  explore_bias: f64,
  graph: &'b search_graph::view::View<'a, 'id, G::State, VertexData, EdgeData<G>>,
  edges: I,
}

impl fmt::Display for UcbError {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    match *self {
      UcbError::InvalidComputation => write!(f, "Numerical error when computing UCB score"),
    }
  }
}

impl Error for UcbError {
  fn description(&self) -> &str {
    match *self {
      UcbError::InvalidComputation => "invalid computation",
    }
  }
}

impl<'a, 'b, 'id, G, I> EdgeUcbIter<'a, 'b, 'id, G, I>
where
  G: Game,
  I: Iterator<Item = search_graph::view::EdgeRef<'id>>,
{
  /// Constructs a new `EdgeUcbIter` that will compute UCB scores using the
  /// given constants. All floating-point values are assumed to be valid
  /// floating-point values and positive.
  ///
  ///  - `log_parent_visits`: ln(visits to parent vertex).
  ///  - `explore_bias`: scalar bias controlling tradeoff between search width
  ///    and search depth (lower = wider, higher = deeper).
  ///  - `edges`: an iterator over edge handles for which to compute UCB
  ///    scores. This should usually be a list of child edges which share a
  ///    parent vertex.
  pub fn new(
    log_parent_visits: f64,
    explore_bias: f64,
    graph: &'b search_graph::view::View<'a, 'id, G::State, VertexData, EdgeData<G>>,
    edges: I,
  ) -> Self {
    EdgeUcbIter {
      log_parent_visits: log_parent_visits,
      explore_bias: explore_bias,
      graph,
      edges: edges,
    }
  }
}

impl<'a, 'b, 'id, G, I> Iterator for EdgeUcbIter<'a, 'b, 'id, G, I>
where
  G: Game,
  I: Iterator<Item = search_graph::view::EdgeRef<'id>>,
{'fraction_non_alphanumeric': 0.1412701044602885, 'fraction_numerical': 0.004311059525783452, 'mean_word_length': 3.661514683153014, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1823457', 'n_tokens_mistral': 2022, 'n_tokens_neox': 2035, 'n_words': 659}