Scribd Logo
Upload

Welcome to Scribd!

  • 28 views

    Slide6-Search With Probality

    Uploaded by

    Nguyen Tran Quang
    The document discusses uncertainty in decision making and game theory. It introduces concepts like expectimax search which uses average probabilities of outcomes rather than worst-case analysis. It also discusses modeling assumptions versus reality, and how to appropriately incorporate probabilities and deal with different types of uncertainty. Multi-agent decision making is mentioned, where there are multiple utilities that need to be optimized.

    Copyright:

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

    Slide6-Search With Probality

    Uploaded by

    Nguyen Tran Quang
    28 views14 pages
    The document discusses uncertainty in decision making and game theory. It introduces concepts like expectimax search which uses average probabilities of outcomes rather than worst-case analysis. It also discusses modeling assumptions versus reality, and how to appropriately incorporate probabilities and deal with different types of uncertainty. Multi-agent decision making is mentioned, where there are multiple utilities that need to be optimized.

    Original Title

    slide6-search_with_probality

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses uncertainty in decision making and game theory. It introduces concepts like expectimax search which uses average probabilities of outcomes rather than worst-case analysis. It also discusses modeling assumptions versus reality, and how to appropriately incorporate probabilities and deal with different types of uncertainty. Multi-agent decision making is mentioned, where there are multiple utilities that need to be optimized.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    28 views14 pages

    Slide6-Search With Probality

    Uploaded by

    Nguyen Tran Quang
    The document discusses uncertainty in decision making and game theory. It introduces concepts like expectimax search which uses average probabilities of outcomes rather than worst-case analysis. It also discusses modeling assumptions versus reality, and how to appropriately incorporate probabilities and deal with different types of uncertainty. Multi-agent decision making is mentioned, where there are multiple utilities that need to be optimized.

    Copyright:

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

    Uncertainty and Utilities

    Uncertain Outcomes
    Worst Case vs Expected

    max

    min

    10 10 9 100

    - Idea: How many chance we ends up in 100 values


    - Need more knowledges(hiểu rõ đối thủ)
    Optimal search with maximal expectation
     The action could be uncertainty?
     Các điều kiện ngẫu nhiên khách quan: cờ cá ngựa max
     Đối thủ không đoán trước được: pacman
     Hành động có thể fail: điều khiển robot

    chance
     average-case: expectimax
     minimax: worst-case

     Expectimax search: using average of possibility


     Max nodes as in minimax search 10 10
    4 5
    9 100
    7
     uncertatinty nodes không xác định: use expectation
    Depth-Limited Expectimax

    Tính giá trị trung


    400 300 … bình của một
    nodes tốn nhiều
    thời gian trong
    … thực tế

    492 362 …
    Probabilities
    Reminder: Probabilities
     A random variable represents an event whose outcome is unknown
     A probability distribution is an assignment of weights to outcomes

     Example: Traffic on freeway


    0.25
     Random variable: T = whether there’s traffic
     Outcomes: T in {none, light, heavy}
     Distribution: P(T=none) = 0.25, P(T=light) = 0.50, P(T=heavy) = 0.25

     Some laws of probability (more later):


     Probabilities are always non-negative 0.50
     Probabilities over all possible outcomes sum to one

     As we get more evidence, probabilities may change:


     P(T=heavy) = 0.25, P(T=heavy | Hour=8am) = 0.60
     We’ll talk about methods for reasoning and updating probabilities later
    0.25
    Reminder: Expectations
     The expected value of a function of a random variable is the
    average, weighted by the probability distribution over
    outcomes

     Example: How long to get to the airport?


    Time: 20 min 30 min 60 min
    x + x + x 35 min
    Probability: 0.25 0.50 0.25
    Type of uncertainty
     We can split the uncertainty into sub-category
     uniform-distribution: tung xúc sắc
     complex model: dota/chess
     out-of-distribution uncertainty

     To guess the right outcome, we need:


     domain knowledge
     data
    Modeling Assumptions
    The Dangers of Optimism and Pessimism
    Dangerous Optimism Dangerous Pessimism
    Assuming chance when the world is adversarial Assuming the worst case when it’s not likely
    Assumptions vs. Reality

    "Huấn luyện" Ghost Ghost ngẫu nhiên

    Minimax Won 5/5 Won 5/5


    Pacman Avg. Score: 483 Avg. Score: 493

    Expectimax Won 1/5 Won 5/5


    Pacman Avg. Score: -303 Avg. Score: 503

    Trained Ghost: tìm kiếm với độ sâu bằng 2 với hàm ước lượng để bắt pacman Results from playing 5 games

    Best solutions: Đoán xem đang đối đấu với chiến thuật gì
    In practice: Cần nhiều kĩ năng engineering
    Multi-Agent Utilities
     Real world: Trò chơi với nhiều agent?

     Mô hình hóa trong bài toán tìm kiếm


    minimax:
     Trạng thái kết thúc có thể ứng với nhiều hàm
    utilities mỗi giá trị ứng với 1 agent
     Node trung gian: nhiều utilities
     Ở mỗi bước: người chơi sẽ cố tối ưu giá trị của
    mình
     Có thể hợp tác hoặc là đối thủ của nhau

    1,6,6 7,1,2 6,1,2 7,2,1 5,1,7 1,5,2 7,7,1 5,2,5


    How to model world
     Life is a multi-player game?
     How to learn the probability of following events:
     Thời tiết
     Tắc đường
     Điểm tốt nghiệp

    You might also like