Week3_AdversarialSearch

Sheffield Hallam University

  • Knowledge Applied

  • Artificial Intelligence & Machine Learning

Adversarial Search

  • Week 3

Content Overview

  • Games

  • Adversarial Search

  • Mini-Max & Alpha Beta Pruning

  • Connect4 Game

Types of Games

  • Various types:

    • Deterministic vs. Stochastic

    • One, two, or more players

    • Zero-sum games: win-lose scenarios

    • Perfect information games: visibility of game state

  • Objective: Develop algorithms to calculate strategies for optimal moves from given game states.

Deterministic Games

  • Formalization:

    • States: S (start at s0)

    • Players: P = {1...N} (players usually alternate turns)

    • Actions: A (dependent on player/state)

    • Transition Function: S x A → S

    • Terminal Test: S → {true, false}

    • Terminal Utilities: S x P → R

  • A player's solution involves deciding on a policy: S → A

Zero-Sum Games

  • Definition:

    • Opponents have opposing utilities, maximizing one player's gain results in the other's loss.

    • Focus on pure competition within adversarial contexts.

  • General Games:

    • Agents may have independent utilities, involving cooperation, indifference, and competition.

Adversarial Search

  • Important insights on game dynamics and strategies.

Single-Agent Trees

  • Illustrates possible game states and transitions relevant to calculating routes or strategies.

Value of a State

  • Non-Terminal States yield different potential outcomes:

    • Example State Values: 8, 2, 0, 2, 6, 4, 6

  • Terminal States reflect the best achievable outcomes (utilities) from the current state.

Adversarial Game Trees

  • Structures representing potential moves and outcomes, aiding strategy evaluation and decision-making.

Mini-Max Algorithm

  • Overview:

    • Evaluates game states to determine optimal moves within constraints of adversarial play.

    • Terminology:

      • Terminal States: concrete outcomes determined at game finish.

      • States Controlled by the agent must have calculated values based on choices of opposing players.

      • MiniMax values are recursively computed to reflect potential game strategies.

MiniMax Implementation

  • Algorithms:

    def min-value(state):
    initialize v = +∞ 
    for each successor of state:
        v = min(v, max-value(successor))
    return v 
    def max-value(state):
   initialize v = -∞ 
   for each successor of state:
       v = max(v, min-value(successor))
   return v

MiniMax Example

  • Sequential move value determination illustrated: 3, 12, 8, 2, 4, 6, 14, 5, 2, 15

Alpha Beta Pruning

  • Concept of pruning tree nodes to enhance efficiency in minimax finding by eliminating unnecessary computations.

Example of Alpha-Beta:

  • Initial Values:

    • α (Alpha): Best option for maximizer

    • β (Beta): Best option for minimizer

  • Evaluation Iterations:

    • Allows some child nodes to be ignored if they won't affect the outcome.

Connect4 Game

  • Game setup and possible winning moves.

  • Strategic computations to apply mini-max and alpha-beta pruning in gameplay.

Next Week's Agenda

  • IT Session: Adversarial search focused on Tic-Tac-Toe Game and machine learning topics.

Bibliography

  • Dan Klein, Pieter Abbeel, "Intro to AI, UC Berkeley Spring 2014"

Questions?

  • Available for inquiries and clarifications.