use crate::error::Result;
use crate::game::{Coalition, ExplicitGame};
use crate::rng::SplitMix64;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct SearchOptions {
pub attempts: usize,
pub seed: u64,
pub shrink_budget: usize,
}
impl Default for SearchOptions {
fn default() -> SearchOptions {
SearchOptions {
attempts: 1_000,
seed: 0,
shrink_budget: 2_000,
}
}
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Counterexample {
pub game: ExplicitGame,
pub original: ExplicitGame,
pub attempt: usize,
pub shrink_steps: usize,
}
pub fn search(
mut generate: impl FnMut(&mut SplitMix64) -> Result<ExplicitGame>,
mut is_counterexample: impl FnMut(&ExplicitGame) -> bool,
options: SearchOptions,
) -> Result<Option<Counterexample>> {
let mut rng = SplitMix64::new(options.seed);
for attempt in 0..options.attempts {
let game = generate(&mut rng)?;
if is_counterexample(&game) {
let (shrunk, steps) = shrink(&game, &mut is_counterexample, options.shrink_budget);
return Ok(Some(Counterexample {
game: shrunk,
original: game,
attempt,
shrink_steps: steps,
}));
}
}
Ok(None)
}
fn complexity(game: &ExplicitGame) -> (usize, usize, f64) {
let values = &game.values()[1..];
(
game.players(),
values.iter().filter(|v| v.fract() != 0.0).count(),
values.iter().map(|v| v.abs()).sum(),
)
}
fn simpler(a: &ExplicitGame, b: &ExplicitGame) -> bool {
let (pa, fa, sa) = complexity(a);
let (pb, fb, sb) = complexity(b);
(pa, fa).cmp(&(pb, fb)).then(sa.total_cmp(&sb)).is_lt()
}
pub(crate) fn without_player(game: &ExplicitGame, removed: usize) -> Option<ExplicitGame> {
let n = game.players();
if n <= 1 {
return None;
}
game.subgame(Coalition(game.grand().0 & !(1 << removed)))
.ok()
}
fn with_value(game: &ExplicitGame, mask: usize, value: f64) -> Option<ExplicitGame> {
if game.values()[mask] == value {
return None;
}
game.with_value(Coalition(mask as u64), value).ok()
}
pub fn shrink(
game: &ExplicitGame,
is_counterexample: &mut impl FnMut(&ExplicitGame) -> bool,
budget: usize,
) -> (ExplicitGame, usize) {
let mut current = game.clone();
let mut evaluations = 0;
let mut steps = 0;
let mut try_candidate = |candidate: ExplicitGame, current: &mut ExplicitGame| -> Option<bool> {
if !simpler(&candidate, current) {
return Some(false);
}
if evaluations >= budget {
return None;
}
evaluations += 1;
if is_counterexample(&candidate) {
*current = candidate;
return Some(true);
}
Some(false)
};
loop {
let mut changed = false;
let mut player = 0;
while player < current.players() {
let Some(candidate) = without_player(¤t, player) else {
break;
};
match try_candidate(candidate, &mut current) {
None => return (current, steps),
Some(true) => {
steps += 1;
changed = true;
}
Some(false) => player += 1,
}
}
for mask in 1..current.values().len() {
loop {
let value = current.values()[mask];
let halved = if value.fract() == 0.0 {
(value / 2.0).trunc()
} else {
value / 2.0
};
let mut accepted = false;
for replacement in [0.0, value.round(), halved] {
let Some(candidate) = with_value(¤t, mask, replacement) else {
continue;
};
match try_candidate(candidate, &mut current) {
None => return (current, steps),
Some(true) => {
steps += 1;
changed = true;
accepted = true;
break;
}
Some(false) => {}
}
}
if !accepted {
break;
}
}
}
if !changed {
return (current, steps);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::properties;
#[test]
fn finds_and_shrinks_non_superadditive_game() {
let found = search(
|rng| {
crate::generators::bnf(1, 5, rng.next_u64()).map(|g| {
let mut values = g.values()[1..].to_vec();
values[2] = -values[2].abs() - 1.0;
ExplicitGame::from_binary(&values).unwrap()
})
},
|g| !properties::is_superadditive(g),
SearchOptions::default(),
)
.unwrap()
.expect("反例がある");
assert_eq!(found.attempt, 0);
assert!(!properties::is_superadditive(&found.game));
assert!(found.shrink_steps > 0);
assert!(simpler(&found.game, &found.original));
assert!(found.game.values().iter().all(|v| v.fract() == 0.0));
}
#[test]
fn shrinks_to_the_two_players_involved() {
let mut values = vec![3.0; 15];
values[0] = 2.0; values[1] = 2.0; values[2] = 1.0; values[14] = 100.0;
let game = ExplicitGame::from_binary(&values).unwrap();
let mut predicate = |g: &ExplicitGame| !properties::is_superadditive(g);
assert!(predicate(&game));
let (shrunk, _) = shrink(&game, &mut predicate, 10_000);
assert_eq!(shrunk.players(), 2);
assert_eq!(shrunk.values().iter().map(|v| v.abs()).sum::<f64>(), 1.0);
}
#[test]
fn subgame_drops_player() {
let game = ExplicitGame::from_lex(&[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0]).unwrap();
let sub = without_player(&game, 1).unwrap();
assert_eq!(sub.values(), &[0.0, 1.0, 3.0, 5.0]);
}
}