Scribd Logo
Upload

Welcome to Scribd!

  • 40 views

    AI and Search: Jonathan Schaeffer WWW - Cs.ualberta - Ca/ Jonathan

    Uploaded by

    Somil Kumar
    This document discusses the importance of search algorithms in artificial intelligence applications. It notes that while search is central to many AI problems, the focus in textbooks has shifted away from search over time. The key points are: - Search takes many forms, both explicit and implicit, in domains like game playing, optimization, planning, and more. - Enhancements to search algorithms can dramatically improve performance over brute force search, reducing execution time by orders of magnitude in some cases. - Choosing a base search algorithm is often trivial compared to implementing effective enhancements tuned for the specific application domain. These enhancements are what determine search performance.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    AI and Search: Jonathan Schaeffer WWW - Cs.ualberta - Ca/ Jonathan

    Uploaded by

    Somil Kumar
    40 views7 pages
    This document discusses the importance of search algorithms in artificial intelligence applications. It notes that while search is central to many AI problems, the focus in textbooks has shifted away from search over time. The key points are: - Search takes many forms, both explicit and implicit, in domains like game playing, optimization, planning, and more. - Enhancements to search algorithms can dramatically improve performance over brute force search, reducing execution time by orders of magnitude in some cases. - Choosing a base search algorithm is often trivial compared to implementing effective enhancements tuned for the specific application domain. These enhancements are what determine search performance.

    Original Title

    1.Introduction

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses the importance of search algorithms in artificial intelligence applications. It notes that while search is central to many AI problems, the focus in textbooks has shifted away from search over time. The key points are: - Search takes many forms, both explicit and implicit, in domains like game playing, optimization, planning, and more. - Enhancements to search algorithms can dramatically improve performance over brute force search, reducing execution time by orders of magnitude in some cases. - Choosing a base search algorithm is often trivial compared to implementing effective enhancements tuned for the specific application domain. These enhancements are what determine search performance.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    40 views7 pages

    AI and Search: Jonathan Schaeffer WWW - Cs.ualberta - Ca/ Jonathan

    Uploaded by

    Somil Kumar
    This document discusses the importance of search algorithms in artificial intelligence applications. It notes that while search is central to many AI problems, the focus in textbooks has shifted away from search over time. The key points are: - Search takes many forms, both explicit and implicit, in domains like game playing, optimization, planning, and more. - Enhancements to search algorithms can dramatically improve performance over brute force search, reducing execution time by orders of magnitude in some cases. - Choosing a base search algorithm is often trivial compared to implementing effective enhancements tuned for the specific application domain. These enhancements are what determine search performance.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 7

    AI and Search 1.

    Introduction
    Jonathan Schaeffer jonathan@cs.ualberta.ca www.cs.ualberta.ca/~jonathan

    Search is an integral part of many artificial intelligence applications It takes many forms:

    Explicit (e.g. game-playing programs, optimization, path-finding, planning, web agents, theorem proving, satisfiability, belief networks, NPcomplete problems, DNA sequence alignment) Implicit (e.g. Prolog deductions)

    Search is the heart of artificial intelligence

    Search and Knowledge

    Search is...

    Some will argue that AI consists of only two fundamental concepts: Knowledge

    Search is knowledge! Enhance the quality of explicit knowledge

    Refine the values of heuristic knowledge No need to include explicit knowledge that will be uncovered by the search Eliminate the knowledge acquisition bottleneck Chess with a random number evaluation function Bridge/poker/scrabble using simulations

    Representation and manipulation of factual and probabilistic knowledge Explore knowledge alternatives to arrive at the best quality answer

    Reduce knowledge required

    Search

    Used to uncover implicit knowledge


    AI Textbooks

    Changing Perceptions

    Open any introductory book on AI and examine the section on search


    Alpha-beta algorithm (games are popular) A* (puzzles, planning and optimization) AO* (theorem proving) Simulations (maybe, for probabilistic domains) SAT (maybe, for satisfiability)

    Over the years, the percent of pages devoted to search in introductory AI books has decreased

    Neilson (1980) 17% Rich (1983) 31% Russell and Norvig (1995) 12% Poole, Mackworth and Goebel (1998) 10% Russell and Norvig (2003) 13%

    Why?

    Search Reality

    Search algorithms are well understood No major advances in our basic understanding of the algorithms But is the algorithm alone enough to tell you how to use search in a highperformance program?

    Most of the core AI search algorithms can be expressed in 20 lines of code Is search really that simple?
    If the search algorithm is really 20 lines of code, then why is my search routine over 20 pages of code?
    M. Newborn, 1985

    Search is all about...

    The Message Is...

    Not the search algorithm!

    Usually trivial decision made based on the application to be solved Standard algorithms are often impractical The enhancements can reduce the execution time of a search by orders of magnitude

    The search enhancements!


    Efficient search is all about search enhancements Given an application domain, choice of algorithm is usually trivial 99% of the effort is spent implementing, debugging, tuning and analyzing search enhancements The AI textbooks have it backwards

    Brute-force Search

    The Challenge!

    Search enhancements make it possible for brute-force techniques to solve a problem Paradoxical that a dumb and exhaustive searcher can out-perform a smart and selective searcher This is one of the major advances in AI

    Build high-performance search programs Start with the basic algorithm and improve the search through:

    It took many years to get grudging respect from the AI community

    Better quality evaluation function Combination of search enhancements

    Heuristic Search

    Search Goals

    Combination of search and knowledge to explore a state space to find the best quality answer The goal is to dampen or eliminate the exponential growth of the search tree

    Optimizing

    Optimal solution(s) May not be achievable in reasonable time Come up with the best quality decision within given resource constraints Solution quality can be significantly worse than an optimal solution

    Satisficing

    Search Knowledge

    Ingredients in a Searcher?

    Optimal

    Terminal nodes of search tree are welldefined by the application domain E.g., win/loss/draw; length/cost of solution Cant reach all the terminal nodes Stop search at leaf nodes and approximate result Use a heuristic evaluation function

    Application-dependent information Successor state generator Algorithm


    Satisficing

    Next node to expand Backup rule

    Heuristic evaluation function

    Example
    X
    Application-dependent information State generation

    Algorithms?

    Adversary search

    X O X
    Even X O X O

    Maximize O
    Branching factor

    Alpha-beta and variants A* and variants Simulations Expecticmax and variants Many other algorithms for handling specific cases

    Single-agent search

    X X X loses X O O X X O wins X O O O

    Imperfect information

    Terminal node

    Heuristic node

    X O Even X O X O

    S D e e a p r t c h h

    Minimize

    Stochastic

    Backup rule

    Other

    Its All About the Algorithm?

    Its All About Enhancements!

    Choice of algorithm is often trivial given a statement of the problem

    Pre-packaged code is usually readily available Just need to put in application-dependent information

    Generic search algorithms get poor performance There are a plethora of enhancements in the literature that can dramatically improve the efficiency of search

    Exponential Search Growth!?


    IDA* Example
    15-Puzzle (test set of 100 positions): Full-width search 1,000,000,000,000, 000,000,000,000 000,000,000,000 DAG, not a tree ~10,000,000,000,000 IDA* 36,302,808,031 Enhanced search [1] 21,261,747 Further work [2] ~1,000,000 Hot off the press! [3] 19,540

    Branching factor = b Search depth = d Nave search = bd nodes Smart search?

    Alpha-beta Example
    Checkers program:

    Conclusion

    Need I say more? Minimax search: 100,000,000,000,000 Alpha-beta search: 310,000,000 Enhanced search: 7,000,000

    References
    [1] Joseph Culberson and Jonathan Schaeffer. Pattern Databases, Computational Intelligence, Vol. 14, No. 4, pp. 318-334, 1998. [2] Richard Korf and Ariel Felner, Disjoint Pattern Database Heuristics, Artificial Intelligence, vol. 134, no. 1-2, pp. 922, 2002. [3] Ariel Felner, Robert Holte, Jonathan Schaeffer, and Uzi Zahavi. Unpublished, 2004.

    You might also like