深度优先Tic Tac Toe

  1. #[allow(unused_imports)]
  2. use std::io;
  4. //Interactive Tic-Tac-Toe play needs the "rand = "0.8.3" crate.
  5. //#[cfg(not(test))]
  6. //extern crate rand;
  7. //#[cfg(not(test))]
  8. //use rand::Rng;
  10. #[derive(Copy, Clone, PartialEq, Debug)]
  11. struct Position {
  12.     x: u8,
  13.     y: u8,
  14. }
  16. #[derive(Copy, Clone, PartialEq, Debug)]
  17. pub enum Players {
  18.     Blank,
  19.     PlayerX,
  20.     PlayerO,
  21. }
  23. #[derive(Copy, Clone, PartialEq, Debug)]
  24. struct SinglePlayAction {
  25.     position: Position,
  26.     side: Players,
  27. }
  29. #[derive(Clone, PartialEq, Debug)]
  30. pub struct PlayActions {
  31.     positions: Vec<Position>,
  32.     side: Players,
  33. }
  35. #[allow(dead_code)]
  36. #[cfg(not(test))]
  37. fn main() {
  38.     let mut board = vec![vec![Players::Blank; 3]; 3];
  40.     while !available_positions(&board).is_empty()
  41.         && !win_check(Players::PlayerX, &board)
  42.         && !win_check(Players::PlayerO, &board)
  43.     {
  44.         display_board(&board);
  45.         println!("Type in coordinate for X mark to be played. ie. a1 etc.");
  46.         let mut input = String::new();
  47.         io::stdin()
  48.             .read_line(&mut input)
  49.             .expect("Failed to read line");
  51.         let mut move_position: Option<Position> = None;
  52.         input.make_ascii_lowercase();
  53.         let bytes = input.trim().trim_start().as_bytes();
  54.         if bytes.len() as u32 == 2
  55.             && (bytes[0] as char).is_alphabetic()
  56.             && (bytes[1] as char).is_numeric()
  57.         {
  58.             let column: u8 = bytes[0] - b'a';
  59.             let row: u8 = bytes[1] - b'1';
  61.             if column <= 2 && row <= 2 {
  62.                 move_position = Some(Position { x: column, y: row });
  63.             }
  64.         }
  66.         //Take the validated user input coordinate and use it.
  67.         if let Some(move_pos) = move_position {
  68.             let open_positions = available_positions(&board);
  70.             let mut search = open_positions.iter();
  71.             let result = search.find(|&&x| x == move_pos);
  72.             if result.is_none() {
  73.                 println!("Not a valid empty coordinate.");
  74.                 continue;
  75.             } else {
  76.                 board[move_pos.y as usize][move_pos.x as usize] = Players::PlayerX;
  78.                 if win_check(Players::PlayerX, &board) {
  79.                     display_board(&board);
  80.                     println!("Player X Wins!");
  81.                     return;
  82.                 }
  83.             }
  85.             //Find the best game plays from the current board state
  86.             let recusion_result = minimax(Players::PlayerO, &board);
  87.             match recusion_result {
  88.                 Some(x) => {
  89.                     //Interactive Tic-Tac-Toe play needs the "rand = "0.8.3" crate.
  90.                     //#[cfg(not(test))]
  91.                     //let random_selection = rand::thread_rng().gen_range(0..x.positions.len());
  92.                     let random_selection = 0;
  94.                     let response_pos = x.positions[random_selection];
  95.                     board[response_pos.y as usize][response_pos.x as usize] = Players::PlayerO;
  96.                     if win_check(Players::PlayerO, &board) {
  97.                         display_board(&board);
  98.                         println!("Player O Wins!");
  99.                         return;
  100.                     }
  101.                 }
  103.                 None => {
  104.                     display_board(&board);
  105.                     println!("Draw game.");
  106.                     return;
  107.                 }
  108.             }
  109.         }
  110.     }
  111. }
  113. #[allow(dead_code)]
  114. fn display_board(board: &[Vec<Players>]) {
  115.     println!();
  116.     for (y, board_row) in board.iter().enumerate() {
  117.         print!("{} ", (y + 1));
  118.         for board_cell in board_row {
  119.             match board_cell {
  120.                 Players::PlayerX => print!("X "),
  121.                 Players::PlayerO => print!("O "),
  122.                 Players::Blank => print!("_ "),
  123.             }
  124.         }
  125.         println!();
  126.     }
  127.     println!("  a b c");
  128. }
  130. fn available_positions(board: &[Vec<Players>]) -> Vec<Position> {
  131.     let mut available: Vec<Position> = Vec::new();
  132.     for (y, board_row) in board.iter().enumerate() {
  133.         for (x, board_cell) in board_row.iter().enumerate() {
  134.             if *board_cell == Players::Blank {
  135.                 available.push(Position {
  136.                     x: x as u8,
  137.                     y: y as u8,
  138.                 });
  139.             }
  140.         }
  141.     }
  142.     available
  143. }
  145. fn win_check(player: Players, board: &[Vec<Players>]) -> bool {
  146.     if player == Players::Blank {
  147.         return false;
  148.     }
  150.     //Check for a win on the diagonals.
  151.     if (board[0][0] == board[1][1]) && (board[1][1] == board[2][2]) && (board[2][2] == player)
  152.         || (board[2][0] == board[1][1]) && (board[1][1] == board[0][2]) && (board[0][2] == player)
  153.     {
  154.         return true;
  155.     }
  157.     for i in 0..3 {
  158.         //Check for a win on the horizontals.
  159.         if (board[i][0] == board[i][1]) && (board[i][1] == board[i][2]) && (board[i][2] == player) {
  160.             return true;
  161.         }
  163.         //Check for a win on the verticals.
  164.         if (board[0][i] == board[1][i]) && (board[1][i] == board[2][i]) && (board[2][i] == player) {
  165.             return true;
  166.         }
  167.     }
  169.     false
  170. }
  172. //Minimize the actions of the opponent while maximizing the game state of the current player.
  173. pub fn minimax(side: Players, board: &[Vec<Players>]) -> Option<PlayActions> {
  174.     //Check that board is in a valid state.
  175.     if win_check(Players::PlayerX, board) || win_check(Players::PlayerO, board) {
  176.         return None;
  177.     }
  179.     let opposite = match side {
  180.         Players::PlayerX => Players::PlayerO,
  181.         Players::PlayerO => Players::PlayerX,
  182.         Players::Blank => panic!("Minimax can't operate when a player isn't specified."),
  183.     };
  185.     let positions = available_positions(board);
  186.     if positions.is_empty() {
  187.         return None;
  188.     }
  190.     //Play position
  191.     let mut best_move: Option<PlayActions> = None;
  193.     for pos in positions {
  194.         let mut board_next = board.to_owned();
  195.         board_next[pos.y as usize][pos.x as usize] = side;
  197.         //Check for a win condition before recursion to determine if this node is terminal.
  198.         if win_check(Players::PlayerX, &board_next) {
  199.             append_playaction(
  200.                 side,
  201.                 &mut best_move,
  202.                 SinglePlayAction {
  203.                     position: pos,
  204.                     side: Players::PlayerX,
  205.                 },
  206.             );
  207.             continue;
  208.         }
  210.         if win_check(Players::PlayerO, &board_next) {
  211.             append_playaction(
  212.                 side,
  213.                 &mut best_move,
  214.                 SinglePlayAction {
  215.                     position: pos,
  216.                     side: Players::PlayerO,
  217.                 },
  218.             );
  219.             continue;
  220.         }
  222.         let result = minimax(opposite, &board_next);
  223.         let current_score = match result {
  224.             Some(x) => x.side,
  225.             _ => Players::Blank,
  226.         };
  228.         append_playaction(
  229.             side,
  230.             &mut best_move,
  231.             SinglePlayAction {
  232.                 position: pos,
  233.                 side: current_score,
  234.             },
  235.         )
  236.     }
  237.     best_move
  238. }
  240. //Promote only better or collate equally scored game plays
  241. fn append_playaction(
  242.     current_side: Players,
  243.     opt_play_actions: &mut Option<PlayActions>,
  244.     appendee: SinglePlayAction,
  245. ) {
  246.     if opt_play_actions.is_none() {
  247.         *opt_play_actions = Some(PlayActions {
  248.             positions: vec![appendee.position],
  249.             side: appendee.side,
  250.         });
  251.         return;
  252.     }
  254.     let mut play_actions = opt_play_actions.as_mut().unwrap();
  256.     //New game action is scored from the current side and the current saved best score against the new game action.
  257.     match (current_side, play_actions.side, appendee.side) {
  258.         (Players::Blank, _, _) => panic!("Unreachable state."),
  260.         //Winning scores
  261.         (Players::PlayerX, Players::PlayerX, Players::PlayerX) => {
  262.             play_actions.positions.push(appendee.position);
  263.         }
  264.         (Players::PlayerX, Players::PlayerX, _) => {}
  265.         (Players::PlayerO, Players::PlayerO, Players::PlayerO) => {
  266.             play_actions.positions.push(appendee.position);
  267.         }
  268.         (Players::PlayerO, Players::PlayerO, _) => {}
  270.         //Non-winning to Winning scores
  271.         (Players::PlayerX, _, Players::PlayerX) => {
  272.             play_actions.side = Players::PlayerX;
  273.             play_actions.positions.clear();
  274.             play_actions.positions.push(appendee.position);
  275.         }
  276.         (Players::PlayerO, _, Players::PlayerO) => {
  277.             play_actions.side = Players::PlayerO;
  278.             play_actions.positions.clear();
  279.             play_actions.positions.push(appendee.position);
  280.         }
  282.         //Losing to Neutral scores
  283.         (Players::PlayerX, Players::PlayerO, Players::Blank) => {
  284.             play_actions.side = Players::Blank;
  285.             play_actions.positions.clear();
  286.             play_actions.positions.push(appendee.position);
  287.         }
  289.         (Players::PlayerO, Players::PlayerX, Players::Blank) => {
  290.             play_actions.side = Players::Blank;
  291.             play_actions.positions.clear();
  292.             play_actions.positions.push(appendee.position);
  293.         }
  295.         //Ignoring lower scored plays
  296.         (Players::PlayerX, Players::Blank, Players::PlayerO) => {}
  297.         (Players::PlayerO, Players::Blank, Players::PlayerX) => {}
  299.         //No change hence append only
  300.         (_, _, _) => {
  301.             assert!(play_actions.side == appendee.side);
  302.             play_actions.positions.push(appendee.position);
  303.         }
  304.     }
  305. }
  307. #[cfg(test)]
  308. mod test {
  309.     use super::*;
  311.     #[test]
  312.     fn win_state_check() {
  313.         let mut board = vec![vec![Players::Blank; 3]; 3];
  314.         board[0][0] = Players::PlayerX;
  315.         board[0][1] = Players::PlayerX;
  316.         board[0][2] = Players::PlayerX;
  317.         let responses = minimax(Players::PlayerO, &board);
  318.         assert_eq!(responses, None);
  319.     }
  321.     #[test]
  322.     fn win_state_check2() {
  323.         let mut board = vec![vec![Players::Blank; 3]; 3];
  324.         board[0][0] = Players::PlayerX;
  325.         board[0][1] = Players::PlayerO;
  326.         board[1][0] = Players::PlayerX;
  327.         board[1][1] = Players::PlayerO;
  328.         board[2][1] = Players::PlayerO;
  329.         let responses = minimax(Players::PlayerO, &board);
  330.         assert_eq!(responses, None);
  331.     }
  333.     #[test]
  334.     fn block_win_move() {
  335.         let mut board = vec![vec![Players::Blank; 3]; 3];
  336.         board[0][0] = Players::PlayerX;
  337.         board[0][1] = Players::PlayerX;
  338.         board[1][2] = Players::PlayerO;
  339.         board[2][2] = Players::PlayerO;
  340.         let responses = minimax(Players::PlayerX, &board);
  341.         assert_eq!(
  342.             responses,
  343.             Some(PlayActions {
  344.                 positions: vec![Position { x: 2, y: 0 }],
  345.                 side: Players::PlayerX
  346.             })
  347.         );
  348.     }
  350.     #[test]
  351.     fn block_move() {
  352.         let mut board = vec![vec![Players::Blank; 3]; 3];
  353.         board[0][1] = Players::PlayerX;
  354.         board[0][2] = Players::PlayerO;
  355.         board[2][0] = Players::PlayerO;
  356.         let responses = minimax(Players::PlayerX, &board);
  357.         assert_eq!(
  358.             responses,
  359.             Some(PlayActions {
  360.                 positions: vec![Position { x: 1, y: 1 }],
  361.                 side: Players::Blank
  362.             })
  363.         );
  364.     }
  366.     #[test]
  367.     fn expected_loss() {
  368.         let mut board = vec![vec![Players::Blank; 3]; 3];
  369.         board[0][0] = Players::PlayerX;
  370.         board[0][2] = Players::PlayerO;
  371.         board[1][0] = Players::PlayerX;
  372.         board[2][0] = Players::PlayerO;
  373.         board[2][2] = Players::PlayerO;
  374.         let responses = minimax(Players::PlayerX, &board);
  375.         assert_eq!(
  376.             responses,
  377.             Some(PlayActions {
  378.                 positions: vec![
  379.                     Position { x: 1, y: 0 },
  380.                     Position { x: 1, y: 1 },
  381.                     Position { x: 2, y: 1 },
  382.                     Position { x: 1, y: 2 }
  383.                 ],
  384.                 side: Players::PlayerO
  385.             })
  386.         );
  387.     }
  388. }