tic-tac-toe

I came across this¹ fantastic resource from April 2000 while looking for a way to improve the computer for my tic-tac-toe game I developed to improve my Rust skills. It uses the negamax algorithm to determine the best move at the start of each turn by trying to win the game while making it as hard as possible for the opponent if the computer can't win in the next move. Negamax is a simplification of the minimax algorithm, which could also be implemented. I chose to use negamax because it felt more fun to play against in my testing.

Negamax algorithm

int SelectBestMove(player)
{
    max = -100
    for i = 1 to 9
        if A[i] is free
        {
            mark A[i]
            value = Goodness( )
            unmark A[i]
            if value > max
            {
                max = value
                best_locn = i
            }
        }
    return best_locn
}

int Goodness(player)
{
    if CheckWin(-player)
        return -128

    max = -200
    for i = 1 to 9
        if A[i] is free
        {
            mark A[i]
            value = -Goodness(-player) / 2
            unmark A[i]
            if value > max
                max = value
        }
    return max
}

Rewrite it in Rust

Here's my attempt at rewriting it in Rust. Hopefully it implements the logic correctly, but please send me a message if it doesn't! I'm still learning the algorithm in addition to Rust, so there's room for error. It seems to work well enough for now.

fn select_best_move(board: &Board, player: &Cell) -> Option<(usize, usize)> {
    let mut max_value = -100;
    let mut best_move: Option<(usize, usize)> = None;

    for row in 0..BOARD_SIZE {
        for col in 0..BOARD_SIZE {
            if board[row][col] == Cell::Empty {
                let mut predictive_board = board.clone();
                predictive_board[row][col] = *player;
                let move_value = check_move_strength(&predictive_board, &player);

                if move_value > max_value {
                    max_value = move_value;
                    best_move = Some((row, col));
                }
            }
        }
    }

    best_move
}

fn check_move_strength(board: &Board, player: &Cell) -> i32 {
    let opponent: Cell = match *player {
        Cell::X => Cell::O,
        Cell::O => Cell::X,
        Cell::Empty => panic!(),
    };

    // Check if opponent wins
    let winner = check_for_win(&board);
    if winner.is_some() {
        if winner.unwrap() == opponent {
            return -128;
        }
    }

    let mut max_value = -200;
    for row in 0..BOARD_SIZE {
        for col in 0..BOARD_SIZE {
            if board[row][col] == Cell::Empty {
                let mut predictive_board = board.clone();
                predictive_board[row][col] = opponent;
                let move_value = -check_move_strength(&predictive_board, &opponent) / 2;

                if move_value > max_value {
                    max_value = move_value;
                }
            }
        }
    }

    max_value
}

1. https://erwnerve.tripod.com/prog/recursion/tictctoe.htm ↩