use crate::bot::Bot;
use crate::bot::random_numbers;
use crate::game::Cell;
use crate::game::GameState;
use crate::game::LINE_LENGTH;
use crate::game::Player;
use rand::rngs::StdRng;
use rand::seq::IndexedRandom;
const WIN: i32 = 1_000_000;
const INFINITY: i32 = WIN * 2;
const DIRECTIONS: [(isize, isize); 4] = [(1, 0), (0, 1), (1, 1), (1, -1)];
#[derive(Debug, Clone)]
pub struct SearchBot {
random_numbers: StdRng,
depth: Option<u32>,
}
impl SearchBot {
pub fn from_entropy() -> Self {
Self::with_seed(None)
}
pub fn seeded(seed: u64) -> Self {
Self::with_seed(Some(seed))
}
pub fn with_depth(seed: u64, depth: u32) -> Self {
Self {
depth: Some(depth),
..Self::seeded(seed)
}
}
pub(crate) fn with_seed(seed: Option<u64>) -> Self {
Self {
random_numbers: random_numbers(seed),
depth: None,
}
}
}
impl Default for SearchBot {
fn default() -> Self {
Self::from_entropy()
}
}
impl Bot for SearchBot {
fn choose_move(&mut self, state: &GameState) -> Option<usize> {
if state.is_over() {
return None;
}
let mut position = Position::of(state);
let depth = self.depth.unwrap_or_else(|| position.sensible_depth());
let (_, best) = position.best_moves(depth);
best.choose(&mut self.random_numbers).copied()
}
fn name(&self) -> &'static str {
"Searching bot"
}
}
#[derive(Debug, Clone)]
struct Position {
column_count: usize,
row_count: usize,
cells: Vec<Option<Player>>,
heights: Vec<usize>,
to_move: Player,
played: usize,
order: Vec<usize>,
lines: Vec<[usize; LINE_LENGTH]>,
}
impl Position {
fn of(state: &GameState) -> Self {
let column_count = state.column_count();
let row_count = state.row_count();
let mut position = Self {
column_count,
row_count,
cells: vec![None; column_count * row_count],
heights: vec![0; column_count],
to_move: state.current_player(),
played: 0,
order: columns_from_the_middle(column_count),
lines: lines_of(column_count, row_count),
};
for row in 0..row_count {
for column in 0..column_count {
if let Some(player) = state.piece_at(Cell::new(column, row)) {
position.cells[row * column_count + column] = Some(player);
position.heights[column] += 1;
position.played += 1;
}
}
}
position
}
fn best_moves(&mut self, depth: u32) -> (i32, Vec<usize>) {
let mut best = Vec::new();
let mut best_rank = (-INFINITY, -INFINITY);
for index in 0..self.order.len() {
let column = self.order[index];
if !self.can_play(column) {
continue;
}
let rank = self.rank_of_playing(column, depth);
if rank > best_rank {
best_rank = rank;
best.clear();
}
if rank == best_rank {
best.push(column);
}
}
(best_rank.0, best)
}
fn rank_of_playing(&mut self, column: usize, depth: u32) -> (i32, i32) {
if self.wins_with(column) {
return (win_score(self.played), 0);
}
self.play(column);
let score = -self.best_score(depth.saturating_sub(1), -INFINITY, INFINITY);
let board = -self.evaluate();
self.undo(column);
(score, board)
}
fn best_score(&mut self, depth: u32, mut alpha: i32, beta: i32) -> i32 {
if !self.has_moves() {
return 0;
}
if self.winning_move().is_some() {
return win_score(self.played);
}
if depth == 0 {
return self.evaluate();
}
for index in 0..self.order.len() {
let column = self.order[index];
if !self.can_play(column) {
continue;
}
self.play(column);
let score = -self.best_score(depth - 1, -beta, -alpha);
self.undo(column);
if score >= beta {
return score;
}
alpha = alpha.max(score);
}
alpha
}
fn evaluate(&self) -> i32 {
let mut score = self.centre_control();
for line in &self.lines {
score += self.line_balance(line);
}
score
}
fn line_balance(&self, line: &[usize; LINE_LENGTH]) -> i32 {
let mut mine = 0;
let mut theirs = 0;
let mut reach = usize::MAX;
for index in line {
match self.cells[*index] {
Some(player) if player == self.to_move => mine += 1,
Some(_) => theirs += 1,
None => reach = reach.min(self.discs_below(*index)),
}
}
match (mine, theirs) {
(mine, 0) => room_value(mine, reach),
(0, theirs) => -room_value(theirs, reach),
_ => 0,
}
}
fn discs_below(&self, index: usize) -> usize {
let column = index % self.column_count;
let row = index / self.column_count;
row.saturating_sub(self.heights[column])
}
fn centre_control(&self) -> i32 {
let middle = self.column_count / 2;
(0..self.row_count)
.filter_map(|row| self.piece(middle, row))
.map(|player| if player == self.to_move { 3 } else { -3 })
.sum()
}
fn has_moves(&self) -> bool {
self.played < self.cells.len()
}
fn can_play(&self, column: usize) -> bool {
self.heights[column] < self.row_count
}
fn winning_move(&self) -> Option<usize> {
self.order
.iter()
.copied()
.find(|column| self.wins_with(*column))
}
fn wins_with(&self, column: usize) -> bool {
if !self.can_play(column) {
return false;
}
let row = self.heights[column];
DIRECTIONS.iter().any(|(along, up)| {
let forwards = self.run(column, row, (*along, *up));
let backwards = self.run(column, row, (-*along, -*up));
1 + forwards + backwards >= LINE_LENGTH
})
}
fn run(&self, column: usize, row: usize, step: (isize, isize)) -> usize {
let mut count = 0;
let mut column = column;
let mut row = row;
loop {
let (Some(next_column), Some(next_row)) = (
column.checked_add_signed(step.0),
row.checked_add_signed(step.1),
) else {
return count;
};
if self.piece(next_column, next_row) != Some(self.to_move) {
return count;
}
column = next_column;
row = next_row;
count += 1;
}
}
fn piece(&self, column: usize, row: usize) -> Option<Player> {
if column >= self.column_count || row >= self.row_count {
return None;
}
self.cells[row * self.column_count + column]
}
fn play(&mut self, column: usize) {
let row = self.heights[column];
self.cells[row * self.column_count + column] = Some(self.to_move);
self.heights[column] += 1;
self.to_move = self.to_move.opponent();
self.played += 1;
}
fn undo(&mut self, column: usize) {
self.heights[column] -= 1;
let row = self.heights[column];
self.cells[row * self.column_count + column] = None;
self.to_move = self.to_move.opponent();
self.played -= 1;
}
fn sensible_depth(&self) -> u32 {
match self.cells.len() {
0..=42 => 6,
43..=100 => 5,
_ => 4,
}
}
}
fn win_score(played: usize) -> i32 {
WIN - i32::try_from(played).unwrap_or(0)
}
fn room_value(discs: usize, reach: usize) -> i32 {
match (discs, reach) {
(3, 0) => 120,
(3, 1) => 30,
(3, _) => 10,
(2, 0 | 1) => 8,
(2, _) => 3,
(1, _) => 1,
_ => 0,
}
}
fn columns_from_the_middle(column_count: usize) -> Vec<usize> {
let middle = column_count / 2;
let mut columns: Vec<usize> = (0..column_count).collect();
columns.sort_by_key(|column| column.abs_diff(middle));
columns
}
fn lines_of(column_count: usize, row_count: usize) -> Vec<[usize; LINE_LENGTH]> {
let mut lines = Vec::new();
for row in 0..row_count {
for column in 0..column_count {
for (along, up) in DIRECTIONS {
if let Some(line) = line_from(column, row, (along, up), column_count, row_count) {
lines.push(line);
}
}
}
}
lines
}
fn line_from(
column: usize,
row: usize,
step: (isize, isize),
column_count: usize,
row_count: usize,
) -> Option<[usize; LINE_LENGTH]> {
let mut line = [0; LINE_LENGTH];
for (offset, cell) in line.iter_mut().enumerate() {
let distance = isize::try_from(offset).ok()?;
let line_column = column.checked_add_signed(step.0 * distance)?;
let line_row = row.checked_add_signed(step.1 * distance)?;
if line_column >= column_count || line_row >= row_count {
return None;
}
*cell = line_row * column_count + line_column;
}
Some(line)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::game::Game;
fn position_after(moves: &[usize]) -> GameState {
let game = Game::from_moves(moves.iter().copied()).expect("the moves are legal");
game.state().clone()
}
fn answer_to(moves: &[usize]) -> Option<usize> {
SearchBot::seeded(1).choose_move(&position_after(moves))
}
const HORIZONTAL: [usize; 6] = [0, 0, 1, 1, 2, 2];
const VERTICAL: [usize; 6] = [2, 3, 2, 3, 2, 4];
const RISING: [usize; 10] = [0, 1, 1, 2, 2, 3, 2, 3, 3, 0];
const FALLING: [usize; 10] = [6, 5, 5, 4, 4, 3, 4, 3, 3, 0];
#[test]
fn it_takes_a_win_in_any_direction() {
assert_eq!(answer_to(&HORIZONTAL), Some(3));
assert_eq!(answer_to(&VERTICAL), Some(2));
assert_eq!(answer_to(&RISING), Some(3));
assert_eq!(answer_to(&FALLING), Some(3));
}
#[test]
fn it_takes_a_win_however_shallow_it_is_looking() {
for depth in 0..4 {
let mut bot = SearchBot::with_depth(1, depth);
assert_eq!(
bot.choose_move(&position_after(&HORIZONTAL)),
Some(3),
"a bot looking {depth} moves ahead missed a win in one"
);
}
}
#[test]
fn it_blocks_the_only_threat_against_it() {
assert_eq!(answer_to(&[0, 5, 1, 6, 2]), Some(3));
}
#[test]
fn it_takes_its_own_win_before_stopping_one() {
assert_eq!(answer_to(&[0, 4, 1, 5, 2, 6]), Some(3));
}
#[test]
fn it_does_not_carry_the_other_player_up_to_a_win() {
let answer = answer_to(&[1, 2, 0, 3, 3, 1, 0, 0, 0, 2]).expect("the game is live");
assert!(answer != 0 && answer != 4, "the bot answered {answer}");
}
#[test]
fn it_has_nothing_to_say_about_a_finished_game() {
assert_eq!(answer_to(&[3, 4, 3, 4, 3, 4, 3]), None);
}
#[test]
fn it_answers_the_same_way_twice() {
let state = position_after(&[3, 3, 4]);
let ask = |seed| SearchBot::seeded(seed).choose_move(&state);
assert_eq!(ask(4), ask(4));
}
#[test]
fn a_position_mirrors_the_board_it_was_made_from() {
let state = position_after(&[3, 3, 4, 5, 3]);
let position = Position::of(&state);
assert_eq!(position.played, 5);
assert_eq!(position.to_move, state.current_player());
assert_eq!(position.heights, vec![0, 0, 0, 3, 1, 1, 0]);
assert_eq!(position.piece(3, 0), state.piece_at(Cell::new(3, 0)));
assert_eq!(position.piece(3, 2), state.piece_at(Cell::new(3, 2)));
assert_eq!(position.piece(0, 0), None);
assert_eq!(position.piece(9, 9), None);
}
#[test]
fn taking_a_move_back_leaves_the_position_as_it_was() {
let mut position = Position::of(&position_after(&[3, 3, 4]));
let before = position.clone();
for column in 0..7 {
position.play(column);
position.undo(column);
assert_eq!(position.cells, before.cells, "column {column} left a mark");
assert_eq!(position.heights, before.heights);
assert_eq!(position.played, before.played);
assert_eq!(position.to_move, before.to_move);
}
}
#[test]
fn it_sees_a_line_coming_in_any_direction() {
for (moves, column) in [
(HORIZONTAL.as_slice(), 3),
(VERTICAL.as_slice(), 2),
(RISING.as_slice(), 3),
(FALLING.as_slice(), 3),
] {
let position = Position::of(&position_after(moves));
assert!(position.wins_with(column), "missed a win at {column}");
for other in 0..7 {
if other != column {
assert!(!position.wins_with(other), "imagined a win at {other}");
}
}
}
}
#[test]
fn an_empty_board_favours_neither_player() {
let position = Position::of(&GameState::new());
assert_eq!(position.evaluate(), 0);
}
#[test]
fn a_line_is_worth_more_the_closer_it_is_to_being_finished() {
assert!(room_value(3, 0) > room_value(2, 0));
assert!(room_value(2, 0) > room_value(1, 0));
assert!(room_value(1, 0) > room_value(0, 0));
}
#[test]
fn a_line_is_worth_more_when_its_empty_slot_can_be_reached() {
assert!(room_value(3, 0) > room_value(3, 1));
assert!(room_value(3, 1) > room_value(3, 5));
assert!(room_value(2, 1) > room_value(2, 5));
}
#[test]
fn a_win_is_worth_more_the_sooner_it_comes() {
assert!(win_score(10) > win_score(12));
assert!(win_score(0) > win_score(42));
}
#[test]
fn the_middle_of_the_board_is_searched_first() {
assert_eq!(columns_from_the_middle(7), vec![3, 2, 4, 1, 5, 0, 6]);
assert_eq!(columns_from_the_middle(1), vec![0]);
}
#[test]
fn a_board_has_a_line_for_every_four_slots_that_fit_on_it() {
assert_eq!(lines_of(7, 6).len(), 69);
assert_eq!(lines_of(4, 1).len(), 1);
assert_eq!(lines_of(3, 3).len(), 0);
}
#[test]
fn a_winning_position_scores_as_a_win() {
let mut position = Position::of(&position_after(&HORIZONTAL));
let (score, best) = position.best_moves(4);
assert!(score > WIN / 2, "a win in one scored {score}");
assert_eq!(best, vec![3]);
}
#[test]
fn a_lost_position_scores_as_a_loss() {
let mut position = Position::of(&position_after(&[1, 6, 2, 6, 3]));
let (score, _) = position.best_moves(4);
assert!(score < -WIN / 2, "a loss in two scored {score}");
}
}