by Albert Major

Introduction to Artificial Intelligence

Adversarial Search and Games

Adversarial search is a technique used in AI for decision-making in situations where you have competing players/opponents trying to win against each other

Different Types of Games Analyzed

• Golf
  • Single player focused
  • Other players don't directly affect your moves
  • Non-deterministic (outcomes have uncertainty)
  • Imperfect information
• Chess
  • Two players directly competing
  • Players' moves directly affect each other
  • Deterministic (moves have predictable outcomes)
  • Perfect information (all game state visible)
  • Turn-based gameplay
• Poker
  • Multiple players possible
  • Hidden information (cards)
  • Non-deterministic
  • Imperfect information
  • Involves probability and psychology

Classical AI Game Characteristics

1. Deterministic Properties:
   • Every move has a predictable outcome
   • No element of chance involved
   • State transitions are fixed and known
2. Two-Player Structure:
   • Exactly two opponents
   • Simplifies modeling and analysis
   • Makes game theory more straightforward
3. Turn-Taking Mechanics:
   • Players alternate moves
   • No simultaneous actions
   • Clear sequence of play
4. Perfect Information:
   • All game state information visible to both players
   • No hidden elements
   • Complete knowledge of possible moves
5. Zero-Sum Property:
   • One player's gain equals other's loss
   • Wins typically valued at +1
   • Losses valued at -1
   • Draws valued at 0
   • Total always sums to zero

Minimax Algorithm Deep Dive

Minimax is a strategy where one player (MAX) tries to get the highest possible score while assuming their opponent (MIN) will make the best moves to minimize MAX's score, leading both players to make the most optimal moves possible given perfect play.

Basic Principles

1. Game Tree Creation:
   • Root node represents current state
   • Branches show possible moves
   • Leaves represent terminal states
2. Value Assignment:
   • Terminal states get concrete values
   • Wins: +1
   • Losses: -1
   • Draws: 0