Scribd
Upload
4 views2 pages

Adversarial Search and Game Strategies

The document discusses adversarial search in games, focusing on the Minimax algorithm and its application in decision-making for two-player games like chess and tic-tac-toe. It also covers Alpha-Beta pruning as an optimization technique to improve the efficiency of the Minimax algorithm by eliminating unnecessary branches, and addresses the challenges of making imperfect real-time decisions in time-constrained scenarios. Examples include the use of heuristics in games like Pacman to balance decision quality and speed.

Uploaded by

vinithantharam31
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Adversarial Search and Game Strategies

The document discusses adversarial search in games, focusing on the Minimax algorithm and its application in decision-making for two-player games like chess and tic-tac-toe. It also covers Alpha-Beta pruning as an optimization technique to improve the efficiency of the Minimax algorithm by eliminating unnecessary branches, and addresses the challenges of making imperfect real-time decisions in time-constrained scenarios. Examples include the use of heuristics in games like Pacman to balance decision quality and speed.

Uploaded by

vinithantharam31
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Unit II: Problem Solving by Search-II and Propositional Logic

2.1.1 Games, Optimal Decisions in Games

1. Adversarial search is used in games involving opponents (e.g., chess, tic-tac-toe).

2. It involves two players: MAX (tries to maximize score) and MIN (tries to minimize score).

3. The Minimax algorithm helps in decision-making by simulating all possible moves.

4. Each node represents a game state; levels alternate between MAX and MIN.

5. Leaf nodes contain utility values (e.g., +1 for win, -1 for loss).

6. The value of a node is determined based on whether it's a MAX or MIN level.

7. The root node's value determines the best move for the current player.

8. Used for zero-sum games: one player's gain is another's loss.

9. Limitation: computationally expensive due to large game trees.

10. Example: In tic-tac-toe, if you can win in the next move, minimax suggests it.

2.1.2 Alpha-Beta Pruning

1. An optimization over the minimax algorithm.

2. Eliminates branches that won't affect the final decision.

3. Uses two parameters: alpha (alpha) = best MAX can guarantee, beta (beta) = best MIN can guarantee.

4. If beta alpha, remaining branches are pruned.

5. Reduces the number of nodes evaluated, improving efficiency.

6. Doesn't affect the final decisionjust speeds it up.

7. Works best when moves are ordered optimally.

8. In the best case, reduces time complexity from O(b^d) to O(b^(d/2)).

9. Example: In chess, if one move leads to a guaranteed loss, others are not checked.

10. Used in many game AIs like Chess, Checkers, etc.

2.1.3 Imperfect Real-Time Decisions

1. Real-world games often involve time constraints.

2. Perfect decisions aren't always possible within time limits.

3. Uses cutoff tests to decide when to stop tree expansion.

4. Applies evaluation functions to estimate utility of non-terminal nodes.

5. Functions are heuristic-based and not always accurate.

6. Horizon effect: poor decisions made due to limited foresight.


7. Example: Pacman uses depth-limited search with heuristics.

8. Used in AI for real-time strategy (RTS) games.

9. Often combines evaluation function with minimax.

10. Balances decision quality and speed.

You might also like