This assignment is based primarily on the material covered in lecture "Minimax" This assignment is based primarily on the material covered in lecture "Minimax". We will work with "Tic-Tac-Toe" as a simple game to help us work through various algorithms. Part 1 involves creating a starting state for analysis, then constructing the corresponding search tree. Part 2 involves applying the minimax algorithm to evaluate utility scores and determine the best move. Part 3 involves implementing alpha-beta pruning to optimize the search, and Part 4 explores a variation with a different pruning condition for extra credit.
Paper For Above instruction Introduction The Minimax algorithm is a fundamental decision rule used in artificial intelligence for zero-sum game playing, where two players make alternate moves aiming to maximize their own outcome while minimizing the opponent’s. The algorithm assumes both players are perfectly rational and employs a recursive evaluation of game states to select the optimal move. This paper illustrates the practical application of the Minimax algorithm using the game of Tic-Tac-Toe, focusing on constructing game trees, assigning utility scores, and incorporating alpha-beta pruning to improve computational efficiency. Part 1: Initial State and Search Tree Construction In this scenario, we begin with a partially played game of Tic-Tac-Toe, specifically the third-to-last move, which results in a state where four spaces are empty. This state was achieved by simulating a game with no winner, resulting in a draw, simplifying the computational considerations. For our purposes, the maximizing agent, "O", takes the role of Player Max, while "X" represents Player Min, the opponent. From this initial state, we construct a complete game tree considering all possible moves in a namespace employing top-left to bottom-right ordering, and alternating between Max’s and Min’s moves. The levels of the tree are marked to distinguish between Max and Min turns, providing a clear pathway for recursive evaluation in subsequent steps. Part 2: Utility Scores and Minimax Evaluation Terminal states within the search tree are assigned utility values based on their outcomes, calculated using a depth-adjusted scoring system. This score accounts for the number of moves played, the remaining available moves, and the game result. Utility is positive when Max wins, negative when Min wins, and