Informed Searching - Artificial Intelligence

• Heuristic
• Game playing

Heuristic

• Basic
  • Rule of Thumb => Using Greedy method
  • Heuristic Value
    • Euclidean Distance
    • Manhattan Distance
      • Number of squares away from Goal node
  • Finds good solution but not guaranteed to find Optimal solution
• Generate and Test
  • Basic
    • Uses DFS with backtracking, Heuristic
  • Step
    • Generate a possible solution
    • Check if it is Goal, if not then repeat
  • Properties of good generators
    • Complete
    • Non Redundant
    • Informed
• Greedy Search
  • Basic
    • Not complete
    • Not optimal
  • Algorithm
    • Expands node that seems closest to the goal node
• Best First Search
  • Basic
    • Informed, Heuristic
    • Finds good solution but not guaranteed to find Optimal solution
    • Complete
  • Time Complexity
    • Worst Case = O(Branching factor^Depth)
  • Algorithm
    • Push Start node in Priority Queue
    • Till Queue is Empty
      • Pop a Node and check if it is Goal node
        • If goal then return path
      • Go to all its adjacent unvisited elements and push in Queue based on their Heuristic values
• Beam Search Algorithm
  • Basic
    • Space complexity = Constant
    • Not Complete
  • Beam width (B)
    • Number of nodes to keep in queue
  • Algorithm
    • Like Best First search but nodes are sorted to choose one with lowest HV
• Hill Climbing Algorithm
  • Basic
    • Local search Algo, Greedy approach, No backtracking
    • Beam width (B) = 1
  • Problems
    • Local Maximum
    • Plateau/Flat Maximum
    • Ridge
  • Algorithm
    • Evaluate initial state
    • Loop until solution is found or no operators left
      • Select and Apply a new operator
      • Evaluate a new state
        • If goal found then quit
        • If a state better than current state then it is new current state
• A*
  • Basic
    • Informed, BFS based, Heuristic given
    • f(N) = g(N) + h(N) = Actual cost from Start node to n + Estimation cost from n to Goal node
    • Time Complexity = O(V+E) = O(Branching factor^Depth)
    • Space Complexity = O(Branching factor^Depth)
  • Under-Estimation
    • If estimated value is less than actual value
    • Admissible => Guarantee Solution
    • Guarantee Optimal
  • Overestimation
    • If estimated value is more than actual value
    • May not get optimal
• AO* (AND/OR)
  • Basic
    • Informed, BFS based, Heuristic given
    • Problem Decomposition => Breakdown into smaller pieces
    • Admissible => Guarantee Solution
    • Doesn't explore all the solution paths once it got a solution
  • Algorithm
    • Find the Estimation (Heuristic Value) at each level
    • Choose the minimum value and Update till Root
• Problems
  • 8-Puzzle Problem with Heuristic
    • Heuristic Value = Number of Misplaced tiles
    • Worst Case Time Complexity = 3²⁰
    • Average Branching Factor = 2.6 ≈ 3

Game playing

• Basic
  • Game tree/Search tree/Space graph
    • Choices and options selected
  • Utility
    • 0 sum game
  • Depth (Ply)
• Mini-max Algorithm
  • Basic
    • Backtracking Algorithm
    • Best move strategy used
    • Time Complexity = O(Branching factor^Depth)
  • Algorithm
    • First choose Max then choose Min
    • Max will try to maximize its utility (Best Move)
    • Min will try to minimize utility (Worst move)
• α-β Pruning
  • Basic
    • Cut off search by exploring less number of nodes
    • Min node => Beta
    • Max node => Alpha
    • Time Complexity (Best Case) = O(Branching factor^Depth/2)
  • Algorithm
    • Don't explore the nodes from which worst solution is guaranteed