Please enable JavaScript.
Coggle requires JavaScript to display documents.
Adversarial Search - Coggle Diagram
Adversarial Search
Introduction
Definition: Mini-Max algorithm is a decision-making algorithm used in artificial intelligence, particularly in game theory and computer games. It is designed to minimize the possible loss in a worst-case scenario (hence "min") and maximize the potential gain (therefore "max").
Max and Min Players
Two agents take turns
MAX tries to maximize the utility value (e.g., winning).
MIN tries to minimize the utility value (e.g., make MAX lose).
-
-
Game Tree Representation
The game is modeled as a tree, where
-
-
-
Formal Description of a Game: The algorithm is built on a precise model of a game using the following components
-
-
-
Result(s, a): Returns the next state after action a in state s.
Terminal-Test(s): Returns true if the game is over (i.e., s is terminal).
Utility(s, p): Numerical value of state s for player p (e.g., +1 win, –1 loss, 0 draw).
-
Min-Max Formula
Maximizing Player's Turn
-
Result(s,a) is the resulting state from taking action a in state s.
-
-
-
-
-
-
-
Stochastic Games
Examples : (e.g., Backgammon)
-
-
-
Probability Reminder (for Dice-Based Games): Important in estimating expected utilities for CHANCE nodes.
-
Introduction
Definition:
Stochastic games in AI combine game theory, probability, and decision-making to model uncertain, real-world interactions. Unlike deterministic games, they include randomness like dice rolls or random events helping AI make decisions in unpredictable environments.
-
-
Monte Carlo Roll-Out
-
-
-
-
Common in Monte Carlo Tree Search (MCTS) for Go, Backgammon, etc.
-
Game Theory
-
-
-
Definition: "The study of mathematical models of conflict and cooperation between intelligent, rational decision-makers."
-
Central to understanding adversarial AI, negotiations, and resource sharing.
-
-
Zero-Sum Games
Perfect Information
-
-
Examples: Tic-Tac-Toe, Chess, Checkers, Othello, Go.
-
Abstract Games
-
Clear, limited set of rules and actions.
-
-
-
Multi-agent Environments
-
Turn-taking
Agents take alternating turns to act (e.g., in board games).
-
-
Real-world Complexity
Real environments are often partially observable, stochastic, and have many agents.
-
-
AND-OR Search Trees
-
-
-
Solution as a Tree
-
-
Key Idea: The agent is not just planning "what to do," but "what to do if something happens."
Introduction
Definition: Adversarial Search is a search technique in AI used in competitive environments where agents try to defeat each other, like in games.
Uses in AI
Game playing – e.g., chess, tic-tac-toe, Go.
-
-
-
-
-
