Game Theory and Adversarial Search

Flashcards covering key terms and concepts in Game Theory, Adversarial Search, and Zero-Sum Games.

Game Theory

A branch of Artificial Intelligence and mathematics that studies strategic decision-making between two or more intelligent players.

Characteristics of Game Theory

• Involves two or more players.

• Players act rationally.

• Every player tries to maximize their own payoff.

• The outcome depends on the actions of all players.

• Used in competitive and cooperative situations.

Components of Adversarial Search

• Initial State

• Players (MAX and MIN)

• Legal Moves

• Terminal State

• Utility Function

Working of Adversarial Search

1. Start from the current game state.

2. Generate all possible moves.

3. Predict opponent's responses.

4. Evaluate each outcome.

5. Choose the move that provides the highest benefit.

Characteristics of zero sum game

• Two-player competitive game.

• One winner and one loser.

• Interests of players are completely opposite.

• Total payoff remains constant.

• No cooperation between players.

Advantages of Zero-Sum Games

• Simple mathematical analysis.

• Useful for competitive AI.

• Helps develop optimal strategies.

• Widely used in game-playing algorithms.

Limitations in zero sum game

• Not suitable for cooperative situations.

• Many real-world problems are not zero-sum.

• Assumes rational players.

• Ignores possibilities of mutual benefit.

Characteristics of Game Theory

• Involves two or more players.

• Players act rationally.

• Every player tries to maximize their own payoff.

• The outcome depends on the actions of all players.

• Used in competitive and cooperative situations.

Players

The individuals or agents participating in a game (e.g., Player A and Player B).

Strategies

The possible actions available to each player in a game (e.g., Rock, Paper, and Scissors in Rock-Paper-Scissors).

Payoff

The reward or result received after choosing a strategy, which may represent profit, points, or utility.

Rules

The components of a game that define how it is played.

Outcome

The final result achieved after all players make their decisions.

Adversarial Search

A search technique used in Artificial Intelligence where one player's gain is another player's loss, commonly used in two-player competitive games.

MAX Player

The player in adversarial search who attempts to maximize the score, representing the AI or computer.

MIN Player

The player in adversarial search who attempts to minimize the score, representing the opponent.

Zero-Sum Game

A type of game in which one player's gain is exactly equal to another player's loss, represented mathematically as $\text{Gain of Player A} + \text{Gain of Player B} = 0$.

Tic-Tac-Toe Zero-Sum Payoff Table

A payoff matrix demonstrating a zero-sum game where an X Win gives Player X $+1$ and Player O $-1$, an O Win gives Player X $-1$ and Player O $+1$, and a Draw gives both $0$.

Matching Pennies Game Table

A game matrix showing that Player A wins when both choices match (Head/Head or Tail/Tail) and Player B wins when choices differ (Head/Tail or Tail/Head).