use crate::error::{Error, Result};
use crate::game::ExplicitGame;
pub use crate::rng::SplitMix64;
pub fn bnf(kind: u8, n: usize, seed: u64) -> Result<ExplicitGame> {
if n < 2 {
return Err(Error::InvalidArgument("プレイヤー数は 2 以上".into()));
}
let n64 = n as u64;
let mut rng = SplitMix64::new(seed);
let full = (1u64 << n) - 1;
let values: Vec<f64> = match kind {
1 => (1..=full)
.map(|mask| {
let size = mask.count_ones() as u64;
if size == 1 {
0.0
} else if mask == full {
rng.range(100 * (n64 - 2), 100 * n64) as f64
} else {
rng.range(1, 100 * size) as f64
}
})
.collect(),
2 => (1..=full)
.map(|mask| {
if mask.count_ones() == 1 {
0.0
} else {
rng.range(1, 50 * n64) as f64
}
})
.collect(),
3 => (1..=full)
.map(|mask| {
let size = mask.count_ones() as usize;
if mask == full || (size + 2 >= n && rng.next_f64() < 0.9) {
1.0
} else {
0.0
}
})
.collect(),
4 => (1..=full)
.map(|mask| {
if mask.count_ones() == 1 {
0.0
} else {
rng.range(1, n64) as f64
}
})
.collect(),
5 => {
if n < 7 {
return Err(Error::InvalidArgument("タイプ 5 は n >= 7".into()));
}
let big = ((n - 3) / 2) as f64;
let weights: Vec<f64> = (0..n).map(|i| if i < 5 { big } else { 1.0 }).collect();
let quota = 4.0 * big + n as f64 - 4.0;
return weighted_voting(&weights, quota);
}
_ => {
return Err(Error::InvalidArgument(format!(
"未知のゲームタイプ {kind}(1-5)"
)));
}
};
ExplicitGame::from_binary(&values)
}
pub fn weighted_voting(weights: &[f64], quota: f64) -> Result<ExplicitGame> {
ExplicitGame::from_fn(weights.len(), |coalition| {
let weight: f64 = coalition.members().map(|i| weights[i]).sum();
if weight >= quota { 1.0 } else { 0.0 }
})
}
pub fn bankruptcy(estate: f64, claims: &[f64]) -> Result<ExplicitGame> {
if claims.iter().any(|d| *d < 0.0) || estate < 0.0 {
return Err(Error::InvalidArgument("請求額と遺産は非負".into()));
}
ExplicitGame::from_fn(claims.len(), |coalition| {
let outside: f64 = (0..claims.len())
.filter(|&j| !coalition.contains(j))
.map(|j| claims[j])
.sum();
(estate - outside).max(0.0)
})
}
pub fn random_convex(n: usize, seed: u64) -> Result<ExplicitGame> {
let mut rng = SplitMix64::new(seed);
let size = 1usize << n;
let mut values = vec![0.0; size];
for value in values.iter_mut().skip(1) {
*value = rng.next_f64();
}
for bit in 0..n {
for mask in 0..size {
if mask >> bit & 1 == 1 {
values[mask] += values[mask ^ (1 << bit)];
}
}
}
ExplicitGame::from_binary(&values[1..])
}
pub fn random_superadditive(n: usize, seed: u64) -> Result<ExplicitGame> {
let mut rng = SplitMix64::new(seed);
let size = 1usize << n;
let mut values = vec![0.0; size];
for (mask, value) in values.iter_mut().enumerate().skip(1) {
*value = rng.next_f64() * mask.count_ones() as f64;
}
superadditive_cover(&mut values, |a, b| a + b);
ExplicitGame::from_binary(&values[1..])
}
fn superadditive_cover<T: PartialOrd>(values: &mut [T], add: impl Fn(&T, &T) -> T) {
for mask in 1..values.len() {
let mut part = (mask - 1) & mask;
while part > 0 {
let rest = mask & !part;
if part < rest {
let sum = add(&values[part], &values[rest]);
if sum > values[mask] {
values[mask] = sum;
}
}
part = (part - 1) & mask;
}
}
}
pub fn by_class(class: &str, n: usize, seed: u64) -> Result<ExplicitGame> {
match class {
"bnf1" => bnf(1, n, seed),
"bnf2" => bnf(2, n, seed),
"bnf4" => bnf(4, n, seed),
"superadditive" => random_superadditive(n, seed),
"convex" => random_convex(n, seed),
"voting" => random_weighted_voting(n, seed),
other => Err(Error::InvalidArgument(format!("未知のクラス {other:?}"))),
}
}
pub fn random_superadditive_exact(n: usize, seed: u64) -> Result<crate::game::exact::ExactGame> {
use crate::game::exact::{Rational, to_rational};
if n == 0 || n > crate::game::MAX_PLAYERS {
return Err(Error::TooManyPlayers {
players: n,
max: crate::game::MAX_PLAYERS,
});
}
let mut rng = SplitMix64::new(seed);
let size = 1usize << n;
let mut values: Vec<Rational> = vec![Rational::from_integer(0.into()); size];
for (mask, value) in values.iter_mut().enumerate().skip(1) {
*value = to_rational(rng.next_f64() * mask.count_ones() as f64)?;
}
superadditive_cover(&mut values, |a, b| a + b);
values.remove(0);
crate::game::exact::ExactGame::from_binary(values)
}
pub fn random_weighted_voting(n: usize, seed: u64) -> Result<ExplicitGame> {
let mut rng = SplitMix64::new(seed);
let weights: Vec<f64> = (0..n).map(|_| rng.range(1, 10) as f64).collect();
let quota = (weights.iter().sum::<f64>() / 2.0).floor() + 1.0;
weighted_voting(&weights, quota)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::game::Coalition;
#[test]
fn bnf_type5_is_weighted_voting() {
let game = bnf(5, 7, 0).unwrap();
assert_eq!(game.value(Coalition::from_players(&[0, 1, 2, 3, 4])), 0.0);
assert_eq!(
game.value(Coalition::from_players(&[0, 1, 2, 3, 4, 5])),
1.0
);
}
#[test]
fn random_convex_is_supermodular() {
let game = random_convex(4, 7).unwrap();
let full = 1u64 << 4;
for a in 1..full {
for b in 1..full {
let lhs = game.value(Coalition(a | b)) + game.value(Coalition(a & b));
let rhs = game.value(Coalition(a)) + game.value(Coalition(b));
assert!(lhs >= rhs - 1e-12);
}
}
}
}