Game Theory in AI: Minimax and Alpha-Beta Pruning Quiz Quiz

Assess your understanding of Minimax, Alpha-Beta Pruning, and key game theory concepts in artificial intelligence with these easy questions focused on search strategies, decision-making, and practical scenarios in competitive games.

1. Basic Objective of Minimax

   What is the primary goal of the Minimax algorithm in two-player games such as chess or tic-tac-toe?

   1. To select random moves for variability
   2. To minimize the time it takes to compute all possible moves
   3. To maximize the minimum possible gain while minimizing the opponent's maximum gain
   4. To maximize the maximum possible loss

   Explanation: The Minimax algorithm aims to maximize the player's minimum gain while assuming the opponent plays optimally to minimize the player's score. Selecting random moves does not reflect rational play. Minimizing computational time is a goal of optimization but not the algorithm’s main objective. Attempting to maximize the maximum loss is not strategic nor reflective of Minimax logic.

2. Identifying MAX and MIN Players

   In the Minimax algorithm, what is the role of the 'MAX' player?

   1. To minimize the total number of possible outcomes
   2. To alternate randomly with the opponent
   3. To guarantee a win regardless of the opponent's move
   4. To maximize their own score during their turn

   Explanation: The 'MAX' player aims to choose moves that yield the highest evaluation value, maximizing their potential outcome. Minimizing outcomes is actually the strategy of the 'MIN' player. Alternating randomly has no strategic basis, and always guaranteeing a win is impossible unless the game is already won.

3. Minimax Tree Structure

   Which structure best represents the process used in the Minimax algorithm for searching possible moves?

   1. A cyclic loop without end
   2. A single-node graph
   3. A decision tree with alternating MAX and MIN levels
   4. A simple linear list of moves

   Explanation: Minimax explores a tree structure with alternating MAX (player's) and MIN (opponent's) levels to simulate turns. A linear list cannot model branching decisions. A single-node graph does not represent different choices, and a cyclic loop would indicate repeated (non-terminating) play, which is not allowed in standard Minimax applications.

4. Alpha-Beta Pruning Advantage

   What is the main advantage of Alpha-Beta Pruning when applied to the Minimax algorithm?

   1. It changes the game's rules to be easier
   2. It creates more possible moves for the opponent
   3. It guarantees you will always win the game
   4. It reduces the number of nodes evaluated in the search tree

   Explanation: Alpha-Beta Pruning skips branches that cannot influence the final decision, thus reducing unnecessary node evaluations. It does not guarantee victory, only efficiency. Creating more moves for the opponent or changing game rules is unrelated to the pruning process.

5. Alpha and Beta Values Meaning

   In Alpha-Beta Pruning, what does the 'alpha' value represent?

   1. The best value that the maximizer (MAX) currently can guarantee
   2. The number of child nodes in the current tree
   3. The best value that the minimizer (MIN) currently can guarantee
   4. The probability of winning at the current state

   Explanation: Alpha tracks the best (highest) value found so far along the path for the maximizing player. The beta value does this for the minimizing player. Counting child nodes or assigning probabilities of winning are unrelated to what alpha represents in this context.

6. When Pruning Occurs

   During Alpha-Beta Pruning, under which condition does the algorithm prune a branch?

   1. When the maximizing player always chooses the first move
   2. When the tree reaches its maximum depth only
   3. When the scores are equal at two consecutive levels
   4. When the alpha value is greater than or equal to the beta value

   Explanation: Pruning occurs when it is determined that continued exploration cannot yield a better result, specifically when alpha is greater than or equal to beta. Pruning is not based on reaching maximum depth alone or on equal scores at different levels. The maximizing player's move order does not directly trigger pruning.

7. Static Evaluation Function

   What purpose does a static evaluation function serve in Minimax-based AI searching a limited-depth game tree?

   1. It ensures the algorithm uses more memory
   2. It randomizes move selection for unpredictability
   3. It counts the total number of possible moves in the game
   4. It estimates the value of non-terminal nodes at the search frontier

   Explanation: A static evaluation function is used to estimate board strength or desirability at cut-off depth, since the game may not be finished. Randomizing moves or increasing memory usage are not the function's purpose. Counting possible moves does not evaluate game state quality.

8. Game Types for Minimax

   Which type of game scenario is Minimax best suited for?

   1. Deterministic, two-player, zero-sum games
   2. Real-time arcade games with no turns
   3. Non-deterministic games with unpredictable rules
   4. Cooperative or single-player games

   Explanation: Minimax is most effective for games where outcomes are fully determined by players' actions, with two opponents and zero-sum rewards (one player's gain is another's loss). Cooperative or single-player games usually require different approaches, while non-deterministic or real-time games do not fit the turn-based, fully-informed model.

9. Tie-Breaking in Minimax

   If multiple moves yield the same Minimax value, which approach should an AI typically use to select among them?

   1. Choose any of them, as all are equally optimal in terms of evaluation
   2. Discard all options and do not make a move
   3. Randomly select from all moves except the optimal ones
   4. Always pick the first move in the list only

   Explanation: When multiple moves are tied in score, any may be chosen, since each is equally optimal for the algorithm. Always picking the first is arbitrary and may be predictable. Not making a move is illegal in most games, and excluding optimal moves makes no sense logically.

10. Alpha-Beta Pruning Effect on Optimality

    How does Alpha-Beta Pruning affect the optimality of the solution found by the Minimax algorithm?

    1. It makes the solution less accurate
    2. It does not affect optimality; the same result is found as regular Minimax
    3. It only works for non-zero-sum games
    4. It depends entirely on move order, never finding optimal results

    Explanation: Alpha-Beta Pruning eliminates unnecessary calculations but does not affect the final result; it finds the same optimal move as traditional Minimax. Accuracy is unchanged, and while move ordering affects efficiency, not the correctness. Pruning works for zero-sum (not non-zero-sum) games.