hw(4/AI): Add solution

3 files changed, 204 insertions, 0 deletions

diff --git a/Year 4/Artificial Intelligence/hw04/Cargo.lock b/Year 4/Artificial Intelligence/hw04/Cargo.lock
new file mode 100644
index 0000000..3efefac
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw04/Cargo.lock
@@ -0,0 +1,16 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "hw04"
+version = "0.1.0"
+dependencies = [
+ "text_io",
+]
+
+[[package]]
+name = "text_io"
+version = "0.1.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d5f0c8eb2ad70c12a6a69508f499b3051c924f4b1cfeae85bfad96e6bc5bba46"
diff --git a/Year 4/Artificial Intelligence/hw04/Cargo.toml b/Year 4/Artificial Intelligence/hw04/Cargo.toml
new file mode 100644
index 0000000..5261991
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw04/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "hw04"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+text_io = "0.1.12"
diff --git a/Year 4/Artificial Intelligence/hw04/src/main.rs b/Year 4/Artificial Intelligence/hw04/src/main.rs
new file mode 100644
index 0000000..6bc55d0
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw04/src/main.rs
@@ -0,0 +1,179 @@
+use text_io::{read};
+use std::cmp::{max, min};
+
+fn print_board(board: [[Tile; 3]; 3]) {
+    for row in board {
+        for col in row {
+            match col {
+                Tile::O => print!("O"),
+                Tile::X => print!("X"),
+                Tile::Empty => print!("_"),
+            }
+            print!(" ");
+        }
+        println!("");
+    }
+}
+
+#[derive(PartialEq, Clone, Copy)]
+enum Tile {
+    Empty,
+    X, // Player
+    O, // Computer
+}
+
+#[derive(PartialEq)]
+enum BoardResult {
+    Continue,
+    WinX,
+    WinO,
+}
+
+fn win_line(a: &Tile, b: &Tile, c: &Tile) -> bool {
+    (*a == *b) && (*b == *c) && (*c != Tile::Empty)
+}
+
+fn game_over(board: &[[Tile; 3]; 3]) -> BoardResult {
+    for row in 0..3 {
+        if win_line(&board[row][0], &board[row][1], &board[row][2]) {
+            return if board[row][0] == Tile::O { BoardResult::WinO } else { BoardResult::WinX };
+        }
+    }
+    for col in 0..3 {
+        if win_line(&board[0][col], &board[1][col], &board[2][col]) {
+            return if board[0][col] == Tile::O { BoardResult::WinO } else { BoardResult::WinX };
+        }
+    }
+    // Diagonal 1
+    if win_line(&board[0][0], &board[1][1], &board[2][2]) {
+        return if board[0][0] == Tile::O { BoardResult::WinO } else { BoardResult::WinX };
+    }
+    // Diagonal 2
+    if win_line(&board[0][2], &board[1][1], &board[2][0]) {
+        return if board[0][2] == Tile::O { BoardResult::WinO } else { BoardResult::WinX };
+    }
+    return BoardResult::Continue;
+}
+
+fn evaluate(board: &[[Tile; 3]; 3]) -> i32 {
+    match game_over(board) {
+        BoardResult::WinO =>  10,
+        BoardResult::WinX => -10,
+        BoardResult::Continue => 0,
+    }
+}
+
+fn minimax(
+    board: &mut [[Tile; 3]; 3],
+    depth: i32,
+    mut alpha: i32,
+    mut beta: i32,
+    maximizer: bool,
+) -> (i32, usize, usize) {
+    let score = evaluate(board);
+    if score.abs() == 10 {
+        return (score, 0, 0);
+    }
+
+    if maximizer {
+        let mut max_eval = (i32::MIN, 0, 0);
+        for row in 0..3 {
+            for col in 0..3 {
+                if board[row][col] != Tile::Empty { continue; }
+
+                board[row][col] = Tile::O;
+                let eval = minimax(board, depth + 1, alpha, beta, false);
+                board[row][col] = Tile::Empty;
+
+                if eval.0 > max_eval.0 {
+                    max_eval = (eval.0 - depth, row, col);
+                }
+
+                alpha = max(alpha, eval.0);
+                if beta <= alpha {
+                    return max_eval;
+                }
+            }
+        }
+        return max_eval;
+    }
+    else {
+        let mut min_eval = (i32::MAX, 0, 0);
+        for row in 0..3 {
+            for col in 0..3 {
+                if board[row][col] != Tile::Empty { continue; }
+
+                board[row][col] = Tile::X;
+                let eval = minimax(board, depth + 1, alpha, beta, true);
+                board[row][col] = Tile::Empty;
+
+                if eval.0 < min_eval.0 {
+                    min_eval = (eval.0 + depth, row, col);
+                }
+
+                beta = min(beta, eval.0);
+                if beta <= alpha {
+                    return min_eval;
+                }
+            }
+        }
+        return min_eval;
+    }
+}
+
+fn player_move(board: &mut [[Tile; 3]; 3]) {
+    let (mut x, mut y): (usize, usize);
+    loop {
+        print!("Player move: ");
+        (x, y) = (read!(), read!());
+        if board[x][y] != Tile::Empty {
+            println!("Position not available! Try again!");
+            continue;
+        }
+        break;
+    }
+    board[x][y] = Tile::X;
+}
+
+fn computer_move(board: &mut [[Tile; 3]; 3]) {
+    let (_, x, y) = minimax(board, 0, i32::MIN, i32::MAX, false);
+    println!("Computer move: {x} {y}");
+    board[x][y] = Tile::O;
+}
+
+fn main() {
+    let mut board = [[Tile::Empty; 3]; 3];
+    print!("Computer first? ");
+    let computer_first: bool = read!();
+    let mut turn = 0;
+    loop {
+        if ! computer_first || turn > 0 {
+            player_move(&mut board);
+            print_board(board);
+            if game_over(&board) != BoardResult::Continue {
+                println!("Player won!");
+                break;
+            }
+            turn += 1;
+        }
+
+        if turn == 9 {
+            println!("Draw!");
+            break;
+        }
+
+        computer_move(&mut board);
+        print_board(board);
+        if game_over(&board) != BoardResult::Continue {
+            println!("Computer won!");
+            break;
+        }
+
+        turn += 1;
+
+        if turn == 9 {
+            println!("Draw!");
+            break;
+        }
+    }
+}