Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    AI-Chapter5Part1-Dr.Esraa

    Uploaded by

    emoh47973
    Ai agent

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    AI-Chapter5Part1-Dr.Esraa

    Uploaded by

    emoh47973
    2 views15 pages
    Ai agent

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Ai agent

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views15 pages

    AI-Chapter5Part1-Dr.Esraa

    Uploaded by

    emoh47973
    Ai agent

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 15

    Introduction to Artificial

    Intelligence

    Adversarial Search
    Dr. Esra’a Alshdaifat
    In which we examine the problems that arise when we try
    to plan ahead in a world where other agents are planning
    against us.
    GAMES
     In multiagent environments, each agent needs to
    consider the actions of other agents and how they
    affect its own welfare.
     In this chapter we cover competitive
    environments, in which the agents’ goals are in
    conflict, giving rise GAME to adversarial search
    problems—often known as games.
    GAMES
     In AI, the most common games are of a rather
    specialized kind—what game theorists call
    deterministic, turn-taking, two-player, ZERO-SUM
    GAMES of perfect information (such as chess).
     In our terminology, this means deterministic, fully
    observable environments in which two agents act
    alternately and in which the utility values at the
    end of the game are always equal and opposite. For
    example, if one player wins a game of chess, the
    other player necessarily loses. It is this opposition
    between the agents’ utility functions that makes
    the situation adversarial.
    GAMES
     A game can be formally defined as a kind of search
    problem with the following elements:
     S0: The initial state, which specifies how the game is set
    up at the start.
     PLAYER(s): Defines which player has the move in a state.
     ACTIONS(s): Returns the set of legal moves in a state.
     RESULT(s, a): The transition model, which defines the
    result of a move.
     TERMINAL-TEST(s): A terminal test, which is true when the
    game is over and false otherwise. States where the game
    has ended are called terminal states.
     UTILITY(s, p): A utility function (also called an objective
    function or payoff function), defines the final numeric
    value for a game that ends in terminal state s for a player
    p.
    Utility Function
     In chess, the outcome is a win, loss, or draw, with
    values +1, 0, or ½ .
     Some games have a wider variety of possible
    outcomes; the payoffs in backgammon range from 0
    to +192.
     A zero-sum game is (confusingly) defined as one
    where the total payoff to all players is the same for
    every instance of the game. Chess is zero-sum
    because every game has payoff of either 0 + 1, 1 + 0
    or ½+ ½ .
    Game Tree
     game tree for the game—a tree where the nodes are
    game states and the edges are moves.
     Example: game tree for tic-tac-toe.
     Play alternates between MAX’s placing an X and MIN’s
    placing an O until we reach leaf nodes corresponding
    to terminal states such that one player has three in a
    row or all the squares are filled.
     The number on each leaf node indicates the utility
    value of the terminal state from the point of view of
    MAX; high values are assumed to be good for MAX and
    bad for MIN (which is how the players get their names).
     For tic-tac-toe the game tree is relatively small—fewer
    than 9! = 362, 880 terminal nodes.
    A (partial) game tree for the
    game of tic-tac-toe
    MINIMAX Algorithm

     In two-player zero-sum games with


    perfect information, the minimax
    algorithm can select optimal moves by a
    depth-first enumeration of the game tree.
    MINIMAX Algorithm

    Terminal nodes: values calculated from the


    utility function, evaluates how good/bad the
    state is at this point.
    Minimax tree

    Even a simple game like tic-tac-toe is too


    complex for us to draw the entire game tree on
    one page, so we will switch to the trivial game
    tree.
    Minimax example
    Minimax example
    Properties of MINIMAX

     Complete: Yes (if tree is finite)


     Optimal: Yes (against an optimal opponent)
     Time complexity: A complete evaluation takes time b^m
     Space complexity: A complete evaluation takes space b*m
     (depth-first exploration)
    References
     S. Russell and P. Norvig: Artificial Intelligence: A Modern Approach,
    Fourth Edition, Prentice Hall, 2020.
     WolfgangErtel,IntroductiontoArtificialIntelligence,2ndEdition,Springer,
    2017.
     M. Jarrar: Lecture Notes on Heuristic Informed Search, 2018

    You might also like