Created
November 22, 2014 12:32
-
-
Save maghoff/cf75e61187329fccd902 to your computer and use it in GitHub Desktop.
A perfect and pessimistic AI for tic-tac-toe
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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), | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment