Adversarial Search and Game Theory Concepts

This set of flashcards covers key vocabulary and concepts related to adversarial search methods and game theory as presented in the lecture notes.

Adversarial Search

A search method based on game theory involving two competitive agents with conflicting goals.

Game Tree

A structure that visualizes all possible moves in a game, helping to determine optimal moves.

Pruning

A technique used to ignore unnecessary portions of a search tree to improve efficiency and speed.

Heuristic Evaluation Function

A function that estimates the cost or value at each level in a search tree before reaching the goal.

Utility Function

A function that assigns a value representing the payoff of game outcomes, used to determine the winner.

Minimax Algorithm

An algorithm that aims to minimize the possible loss for a worst-case scenario by maximizing the minimum gain.

Alpha-Beta Pruning

An optimization technique for the minimax algorithm that eliminates branches of the game tree which don't need to be explored.

Nash Equilibrium

A situation in a game where no player can benefit by changing their strategy while the others keep theirs unchanged.

Zero-Sum Game

A type of game where the total gains and losses among the players always equal zero, implying one player's gain is another player's loss.

Dominant Strategy

A strategy that provides a better outcome for a player regardless of what the other player does.

Mixed Strategy

A strategy that randomizes over possible moves, typically in games lacking a clear dominant strategy.

Forward Checking

A technique in CSP that maintains a list of remaining legal values for unassigned variables to detect failure early.

Constraint Satisfaction Problem (CSP)

A problem defined by a set of constraints that must be satisfied, often represented using variables and their domain values.

Arc Consistency

A condition in which, for every value of a variable, there exists a compatible value in the connected variable's domain.

Game Theory

The mathematical study of strategic interactions among rational decision-makers.