jja 0.9.1

//
// jja: swiss army knife for chess file formats
// src/merge.rs: PolyGlot Book Merging
//
// Copyright (c) 2023, 2024 Ali Polatel <alip@chesswob.org>
//
// SPDX-License-Identifier: GPL-3.0-or-later

use crate::polyglot::BookEntry;

/// Represents various strategies for merging two Polyglot opening books.
///
/// When merging two opening books, different strategies can be used to determine
/// how to combine the weights of the same moves in different books.
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum MergeStrategy {
    /// Calculates the average weight of the moves in both books.
    AvgWeight,
    /// Takes the maximum weight of the moves in both books.
    MaxWeight,
    /// Takes the minimum weight of the moves in both books.
    MinWeight,
    /// Prioritizes the moves of the first book, ignoring moves from the second book.
    Ours,
    /// Merges by computing the weighted average of percentage weights, taking into account the
    /// total number of entries in each book. This approach gives higher importance to moves from
    /// larger books versus smaller ones, ensuring that the resultant weights reflect the relative
    /// contributions of each book based on its size.
    PercentageAverage,
    /// Calculates the sum of the weights of the moves in both books.
    SumWeight,
    /// Calculates the weighted average weight of the moves in both books, considering the given
    /// weights for each book.
    ///
    /// The tuple contains the weights associated with the first and second books, respectively.
    WeightedAverageWeight(f64, f64),
    /// Merges based on the weighted distance each weight has to its maximum value.
    ///
    /// The `WeightedDistanceMerge` strategy works by first normalizing the weights to a range
    /// between 0 and 1. For each weight, it calculates the "distance" from the maximum possible
    /// value in the normalized scale (which is 1.0). The rationale behind this approach is to
    /// give more influence to the weight that is closer to its maximum potential, thus the one
    /// with a smaller distance to 1.0.
    ///
    /// The resultant merged weight is a blend of the two original weights, with the weight closer
    /// to its maximum having a slightly greater influence. This strategy ensures that both
    /// weights are considered, but it gives a nod to the more dominant weight.
    WeightedDistance,
    /// Merges using a Weighted Median approach.
    ///
    /// The Weighted Median Merge strategy is inspired by the statistical concept of a median,
    /// which is the value separating the higher half from the lower half of a data set.
    /// In the realm of this strategy, the weights are treated as a data set of two values.
    ///
    /// The principle behind this approach is to give prominence to the weight that lies closer
    /// to the median of the set. This ensures that if one weight is substantially larger or
    /// smaller than the other, its influence on the merged result will be correspondingly more significant.
    ///
    /// The steps involved are:
    /// 1. Sort the weights.
    /// 2. Calculate the median of the set.
    /// 3. Determine the distance of each weight from the median.
    /// 4. Compute the weighted median by considering each weight's distance from the median as its weight.
    ///
    /// The result is a merged weight that respects the relative importance of each original weight
    /// based on its proximity to the median. This strategy is particularly effective when the weights
    /// have significant disparity, ensuring that the merged weight reflects the relative importance
    /// of the higher or more significant weight in the set.
    WeightedMedian,
    /// Merges weights based on a dynamic midpoint determined by their difference.
    ///
    /// The `DynamicMidpoint` strategy calculates the difference between the two weights and
    /// defines a dynamic factor based on this difference. The merged weight is determined as a
    /// weighted position between the two original weights, leaning closer to the larger weight
    /// the more distinct they are.
    DynamicMidpoint,
    /// Merges using an entropy-based approach.
    ///
    /// The Entropy Merge strategy is inspired by the concept of entropy from Information Theory.
    /// Entropy, in this context, represents the amount of uncertainty or randomness in data.
    ///
    /// When merging two weights, each weight is first normalized to a probability value,
    /// ranging from 0 to 1, by dividing the weight by the maximum possible value (`u16::MAX`).
    /// The entropy for each probability is then computed. The formula for entropy of a probability
    /// p is given by:
    ///
    /// H(p) = -p log2(p)
    ///
    /// If p is either 0 or 1, the entropy is 0, indicating no uncertainty.
    ///
    /// The final merged weight is derived by averaging the entropies of the two weights
    /// and then scaling the result back to the range of u16. This method ensures that the
    /// resultant merged weight encapsulates the combined uncertainty or randomness from both
    /// original weights, providing a unique and mathematically rigorous way to combine values.
    Entropy,
    /// Geometric scaling strategy: The geometric scale focuses on multiplying numbers together
    /// rather than adding, which can help in equalizing disparities.
    GeometricScaling,
    /// Calculates the harmonic mean weight of the moves in both books. This approach tends to
    /// favor more balanced weights and is less influenced by extreme values.
    HarmonicMean,
    /// Merges using a logarithmic averaging approach. Given that logarithmic functions compress
    /// large values and expand small values, we can use them to get a merge strategy that's
    /// sensitive to differences in smaller weights while being more resistant to disparities in
    /// larger weights.
    LogarithmicAverage,
    /// Merges using the Quadratic Mean (Root Mean Square) approach. The Quadratic Mean (also
    /// known as the Root Mean Square) is a statistical measure of the magnitude of a set of
    /// numbers. It offers a more balanced view, especially when dealing with numbers of varying
    /// magnitudes.
    QuadraticMean,
    /// Remap the weights in a non-linear fashion using the sigmoid function. The idea here is to
    /// diminish the influence of extreme values, which might be causing the dissatisfaction in
    /// previous strategies.
    Sigmoid,
    /// Calculates weight based on relative position in sorted move entries.
    Sort,
    // Add more strategies here
}

/// Calculates the average of the weights of two book entries.
///
/// # Arguments
///
/// * `entry1` - The first book entry.
/// * `entry2` - The second book entry.
///
/// # Returns
///
/// * A `u16` representing the average weight of the two book entries.
///   In case of overflow, it returns `u16::MAX`.
pub fn average_weight(entry1: &BookEntry, entry2: &BookEntry) -> u16 {
    let entry1_weight: u32 = entry1.weight.into();
    let entry2_weight: u32 = entry2.weight.into();
    let sum = entry1_weight.saturating_add(entry2_weight);
    (sum / 2).try_into().unwrap_or(u16::MAX)
}

/// Calculates the weighted average of the weights of two book entries,
/// considering the given weights for each book.
///
/// # Arguments
///
/// * `entry1` - The first book entry.
/// * `entry2` - The second book entry.
/// * `book1_weight` - The weight associated with the first book.
/// * `book2_weight` - The weight associated with the second book.
///
/// # Returns
///
/// * A `u16` representing the weighted average weight of the two book entries,
///   taking into account the weights of each book.
///   In case of overflow, it returns `u16::MAX`.
pub fn weighted_average_weight(
    entry1: &BookEntry,
    entry2: &BookEntry,
    book1_weight: f64,
    book2_weight: f64,
) -> u16 {
    let total_weight = book1_weight + book2_weight;
    let normalized_book1_weight = book1_weight / total_weight;
    let normalized_book2_weight = book2_weight / total_weight;

    let entry1_weight: f64 = entry1.weight.into();
    let entry2_weight: f64 = entry2.weight.into();

    let weighted_sum =
        entry1_weight * normalized_book1_weight + entry2_weight * normalized_book2_weight;
    weighted_sum.min(f64::from(u16::MAX)).round() as u16
}

/// Calculates the sigmoid of a number.
///
/// The sigmoid function maps any number to a value between 0 and 1.
///
/// # Arguments
///
/// * `x` - The input number.
///
/// # Returns
///
/// A f64 value between 0 and 1.
fn sigmoid(x: f64) -> f64 {
    1.0 / (1.0 + (-x).exp())
}

/// Calculates the inverse of the sigmoid function.
///
/// # Arguments
///
/// * `y` - The input number between 0 and 1.
///
/// # Returns
///
/// A f64 value that is the inverse of the sigmoid function.
fn inverse_sigmoid(y: f64) -> f64 {
    (y / (1.0 - y)).ln()
}

/// Merges two u16 weights using a non-linear sigmoid-based strategy.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn sigmoid_merge(a: u16, b: u16) -> u16 {
    // Normalize weights
    let a_norm = sigmoid(f64::from(a) - 32768.0);
    let b_norm = sigmoid(f64::from(b) - 32768.0);

    // Compute average
    let m_norm = (a_norm + b_norm) / 2.0;

    // Denormalize
    let merged = 32768.0 + inverse_sigmoid(m_norm);

    merged.round() as u16
}

/// Merges two u16 weights using the harmonic mean strategy.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn harmonic_merge(a: u16, b: u16) -> u16 {
    // If either weight is zero, handle accordingly.
    // In this implementation, we'll simply return the non-zero weight.
    if a == 0 {
        return b;
    }
    if b == 0 {
        return a;
    }

    let merged = 2.0 / (1.0 / f64::from(a) + 1.0 / f64::from(b));

    merged.round() as u16
}

/// Merges two u16 weights using the geometric scaling strategy.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn geometric_scaling_merge(a: u16, b: u16) -> u16 {
    // Scale the weights
    let a_scaled = (f64::from(a) / f64::from(u16::MAX)) * f64::from(u32::MAX);
    let b_scaled = (f64::from(b) / f64::from(u16::MAX)) * f64::from(u32::MAX);

    // Compute geometric mean in the scaled space
    let m_scaled = (a_scaled * b_scaled).sqrt();

    // Rescale to u16 range
    let merged = (m_scaled / f64::from(u32::MAX)) * f64::from(u16::MAX);

    merged.round() as u16
}

/// Merges two u16 weights using the logarithmic strategy.
///
/// This strategy converts the weights into logarithmic space, averages them,
/// and then converts back to linear space.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn logarithmic_merge(a: u16, b: u16) -> u16 {
    // Convert weights to logarithmic space (adding 1 to avoid log(0))
    let log_a = (f64::from(a) + 1.0).log2();
    let log_b = (f64::from(b) + 1.0).log2();

    // Average the logarithmic values
    let avg_log = (log_a + log_b) / 2.0;

    // Convert back to linear space and round to nearest u16
    let merged_weight = 2.0f64.powf(avg_log) - 1.0;

    // Ensure it doesn't exceed the maximum u16 value
    merged_weight.min(f64::from(u16::MAX)).round() as u16
}

/// Merges two u16 weights using the Quadratic Mean strategy.
///
/// This strategy computes the Quadratic Mean (or Root Mean Square) of the two weights.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn quadratic_mean_merge(a: u16, b: u16) -> u16 {
    let squared_sum = (f64::from(a)).powi(2) + (f64::from(b)).powi(2);
    let quadratic_mean = (squared_sum / 2.0).sqrt();

    // Ensure it doesn't exceed the maximum u16 value
    quadratic_mean.min(f64::from(u16::MAX)).round() as u16
}

/// Computes the entropy for a given probability.
///
/// # Arguments
///
/// * `p` - The probability.
///
/// # Returns
///
/// A f64 value that is the entropy of the given probability.
fn entropy(p: f64) -> f64 {
    if p == 0.0 || p == 1.0 {
        return 0.0;
    }
    -p * p.log2()
}

/// Merges two u16 weights using the Entropy strategy.
///
/// This strategy calculates the entropy for each weight and then averages them.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn entropy_merge(a: u16, b: u16) -> u16 {
    // Convert weights to probabilities
    let p_a = f64::from(a) / f64::from(u16::MAX);
    let p_b = f64::from(b) / f64::from(u16::MAX);

    // Calculate entropies
    let entropy_a = entropy(p_a);
    let entropy_b = entropy(p_b);

    // Average the entropies and convert back to u16 range
    let avg_entropy = (entropy_a + entropy_b) / 2.0;
    let merged_weight = avg_entropy * f64::from(u16::MAX);

    // Ensure it doesn't exceed the maximum u16 value
    merged_weight.min(f64::from(u16::MAX)).round() as u16
}

/// Merges two u16 weights using the Weighted Median strategy.
///
/// This strategy treats the weights as a small data set and computes a weighted median.
/// The weight closer to the median has a stronger influence on the final merged value.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn weighted_median_merge(a: u16, b: u16) -> u16 {
    // Sort the weights
    let mut sorted_weights = [a, b];
    sorted_weights.sort();

    // Calculate the median
    let median = (f64::from(sorted_weights[0]) + f64::from(sorted_weights[1])) / 2.0;

    // Calculate distance of each weight from the median
    let distance_a = (f64::from(a) - median).abs();
    let distance_b = (f64::from(b) - median).abs();

    // Compute the weighted median
    let weighted_median =
        (f64::from(a) * distance_a + f64::from(b) * distance_b) / (distance_a + distance_b);

    // Convert to u16
    weighted_median.round() as u16
}

/// Merges two u16 weights using the weighted distance strategy.
///
/// This strategy merges the weights based on their relative distances to the maximum possible value.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn weighted_distance_merge(a: u16, b: u16) -> u16 {
    // Normalize the weights to [0,1]
    let norm_a = f64::from(a) / f64::from(u16::MAX);
    let norm_b = f64::from(b) / f64::from(u16::MAX);

    // Calculate distance of each weight to the maximum value (1.0)
    let distance_a = 1.0 - norm_a;
    let distance_b = 1.0 - norm_b;

    // Compute the weighted average based on the distances
    let merged_weight = (norm_a * distance_b + norm_b * distance_a) / (distance_a + distance_b);

    // Convert back to u16 range
    (merged_weight * f64::from(u16::MAX)).round() as u16
}

/// Merges two u16 weights using the dynamic midpoint merge strategy.
///
/// This strategy finds a dynamic midpoint between the two weights based on their difference.
///
/// # Arguments
///
/// * `a` - The first weight.
/// * `b` - The second weight.
///
/// # Returns
///
/// A u16 value that is the merged weight of the two input weights.
pub fn dynamic_midpoint_merge(a: u16, b: u16) -> u16 {
    let difference = f64::from((i32::from(a) - i32::from(b)).abs());
    let dynamic_factor = difference / f64::from(u16::MAX);

    // Compute the merged weight
    let merged_weight = (f64::from(a.min(b))) + dynamic_factor * difference;

    // Ensure it doesn't exceed the maximum u16 value
    merged_weight.min(f64::from(u16::MAX)).round() as u16
}