A perfect and pessimistic AI for tic-tac-toe

tictactoe.rs

extern crate core;
use std::io;
use std::rand;
use std::rand::distributions::{IndependentSample, Range};

#[deriving(PartialEq)]
enum Field {
	N,
	X,
	O,
}

impl core::fmt::Show for Field {
	fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
		write!(f, "{}", match *self {
			N => ' ',
			X => 'x',
			O => 'o',
		})
	}
}

fn other_player(player:Field) -> Field {
	match player {
		X => O,
		O => X,
		N => N,
	}
}

fn show(board:&[Field, ..9]) {
	print!("+---+\n");
	print!("|{}{}{}|\n", board[0], board[1], board[2]);
	print!("|{}{}{}|\n", board[3], board[4], board[5]);
	print!("|{}{}{}|\n", board[6], board[7], board[8]);
	print!("+---+\n");
}

// Should perhaps be refactored to iterator?
fn streaks(board:&[Field, ..9], streak_handler:|[Field, ..3]|->()) {
	for row in range(0u, 3u) {
		streak_handler([board[3*row + 0], board[3*row + 1], board[3*row + 2]]);
	}
	for col in range(0u, 3u) {
		streak_handler([board[3*0 + col], board[3*1 + col], board[3*2 + col]]);
	}
	streak_handler([board[3*0 + 0], board[3*1 + 1], board[3*2 + 2]]);
	streak_handler([board[3*0 + 2], board[3*1 + 1], board[3*2 + 0]]);
}

fn find_winner(board:&[Field, ..9]) -> Field {
	let mut winner:Field = N;
	streaks(board, |streak| {
 		if streak[0] != N && streak[0] == streak[1] && streak[1] == streak[2] {
			winner = streak[0];
		}
	});
	return winner;
}

fn free_pos(board:&[Field, ..9], pos_handler:|uint|->()) {
	for pos in range(0u, 9u) {
		if board[pos] == N {
			pos_handler(pos);
		}
	}
}

fn moves(board:&[Field, ..9], to_play:Field, move_handler:|uint, &[Field, ..9]|->()) {
	let mut new_board = *board;
	free_pos(board, |pos| {
		new_board[pos] = to_play;
		move_handler(pos, &new_board);
		new_board[pos] = N;
	});
}

fn finished(board:&[Field, ..9]) -> bool {
	if board.iter().find(|x| { **x == N }) == None {
		return true;
	}
	if find_winner(board) != N {
		return true;
	}
	return false;
}

fn score(board:&[Field, ..9], player:Field, to_play:Field) -> u32 {
	let winner = find_winner(board);
	if winner == player { return 2; }
	if winner == other_player(player) { return 0; }

	let mut scores:Vec<u32> = vec![];
	let next_player = other_player(to_play);
	moves(board, to_play, |_pos, new_board| {
		scores.push(score(new_board, player, next_player));
	});

	if player == to_play {
		return *scores.iter().max().unwrap_or(&1u32);
	} else {
		return *scores.iter().min().unwrap_or(&1u32);
	}
}

fn best_move(rng:&mut rand::TaskRng, board:&[Field, ..9], player:Field) -> uint {
	let mut scores:Vec<(uint, u32)> = vec![];
	let next_player = other_player(player);

	moves(board, player, |pos, new_board| {
		scores.push((pos, score(new_board, player, next_player)));
	});

	let max_score = scores.iter().fold(0u32,
		|max, &(_, score)| {
			if score > max { score } else { max }
		}
	);

	let good_moves = scores.iter()
		.filter(|&&(_, score)| { score == max_score })
		.collect::<Vec<&(uint, u32)>>();

	let choice = Range::new(0, good_moves.len()).ind_sample(rng);
	let (pos, _) = *good_moves[choice];
	return pos;
}

fn read_move(reader: &mut io::Buffer, &board: &[Field, ..9]) -> Result<uint, io::IoError> {
	loop {
		print!("X's move [0-8]: ");
		match from_str::<uint>(try! { reader.read_line() }.as_slice().trim()) {
			Some(n) => {
				if n > 8 {
					println!("out of range");
				} else if board[n] != N {
					println!("square is occupied");
				} else {
					return Ok(n);
				}
			},
			None => println!("enter an integer")
		}
	}
}

fn main_core() -> Result<int, io::IoError> {
	let mut rng = rand::task_rng();
	let mut board:[Field, ..9] = [
		N, N, N,
		N, N, N,
		N, N, N,
	];

	let mut reader = io::stdin();

	while !finished(&board) {
		show(&board);

		let xmove = try!{ read_move(&mut reader, &board) };
		board[xmove] = X;
		if finished(&board) {
			break;
		}

		show(&board);
		let omove = best_move(&mut rng, &board, O);
		print!("O's move [0-8]: {}\n", omove);
		board[omove] = O;
	}

	show(&board);
 	match find_winner(&board) {
		N => print!("Tie\n"),
		winner => print!("{} wins!\n", winner),
	};

	return Ok(0);
}

fn main() {
	match main_core() {
		Ok(_) => (),
		Err(err) => print!("Terminated with IO error: {}\n", err),
	}
}