Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    Lecture 19 Game Tree

    Uploaded by

    Rana Babar

    Copyright:

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

    Lecture 19 Game Tree

    Uploaded by

    Rana Babar
    3 views30 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    Lecture 19 Game Tree

    Uploaded by

    Rana Babar

    Copyright:

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

    ITEC4119-Artificial Intelligence

    Lecture 19
    Muhammad Umar Farooq
    Summary of previous lectures

    • Local search
    – Hill climbing
    – Beam search
    – Genetic algorithm
    Genetic algorithm
    1. Generate a random population of chromosomes
    (this is the first generation).
    2. If the termination criteria are satisfied, stop.
    Otherwise, continue with step 3.
    3. Determine the fitness of each chromosome.
    4. Apply crossover / mutation to selected
    chromosomes from the current generation to
    generate a new population of chromosomes—
    the next generation.
    5. Return to step 2.
    Polynomial fitting problem

    • Suppose you have points(x, y)


    – {(1,5),(3,9)}
    Fit the polynomial (1 degree) through these data
    points.
    Solution found

    • The value of [m c] is [2 3]
    • The equation of line is y = 2x+3 for data
    points(x, y) {(1,5),(3,9)}
    Adversarial Search:
    • Often known as games
    • Multiagent environment
    – Two player game
    – competitive environments
    • Deterministic or fully observable environment
    – in which two agents act alternately and in which
    the utility values at the end of the game are
    always equal and opposite
    Tic tac toe

    Player 1: Player 2:
    Player 1: Won Player 2:
    Player 1: Won Player 2:
    Tic tac Toe

    Player 1: Player 2:
    Player 1: Player 2:
    Player 1: Player 2:
    Player 1: Player 2:
    Player 1: Player 2:
    Player 1: Player 2:
    Player 1: Player 2:
    Player 1: Player 2:
    How many terminal Nodes for this problem?
    9
    9

    8
    9

    7
    9

    Total number of terminal nodes=9!=362, 880


    • Chess has an average branching factor of
    about 35, and games often go to 50 moves by
    each player, so the search tree has about
    35100 or 10154 nodes
    • Total number of terminal nodes for tic tac
    toe=9!=362, 880
    Game tree algorithm
    • Min-Max
    • Alpha beta pruning
    Thank you

    Any question ?

    You might also like