Introduction to Artificial Intelligence with Python PDF
Document Details
Uploaded by JoyousBrown8745
Silliman University
Tags
Summary
This document provides an introduction to Artificial Intelligence using Python. It covers fundamental concepts like search algorithms, knowledge representation, and game playing. The document is well-illustrated with diagrams and examples of problems.
Full Transcript
Introduction to Artificial Intelligence with Python Artificial Intelligence O Search X X O X P→Q Knowledge P Q Uncertainty Optimization Inbox Learning Spam Neural Networks NP...
Introduction to Artificial Intelligence with Python Artificial Intelligence O Search X X O X P→Q Knowledge P Q Uncertainty Optimization Inbox Learning Spam Neural Networks NP NP PP Language ADJ N P N artificial with intelligence python Search 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Search Problems agent entity that perceives its environment and acts upon that environment state a configuration of the agent and its environment 2 4 5 7 12 9 4 2 15 4 10 3 8 3 1 11 8 7 3 14 13 1 11 12 14 6 10 1 6 11 9 5 14 7 9 13 15 12 5 13 10 15 6 8 2 initial state the state in which the agent begins initial state 2 4 5 7 8 3 1 11 14 6 10 9 13 15 12 actions choices that can be made in a state actions ACTIONS(s) returns the set of actions that can be executed in state s 1 2 actions 3 4 transition model a description of what state results from performing any applicable action in any state transition model RESULT(s, a) returns the state resulting from performing action a in state s 2 4 5 7 2 4 5 7 8 3 1 11 8 3 1 11 RESULT( , )= 14 6 10 12 14 6 10 12 9 13 15 9 13 15 2 4 5 7 2 4 5 7 8 3 1 11 8 3 1 11 RESULT( , )= 14 6 10 12 14 6 10 9 13 15 9 13 15 12 transition model 2 4 5 7 2 4 5 7 8 3 1 11 8 3 1 11 RESULT( , )= 14 6 10 12 14 6 10 9 13 15 9 13 15 12 state space the set of all states reachable from the initial state by any sequence of actions 2 4 5 7 8 3 1 11 14 6 10 12 2 4 5 7 9 13 15 2 4 5 7 8 3 1 11 8 3 1 11 14 6 10 12 14 6 10 9 13 15 9 13 15 12 2 4 5 7 2 4 5 7 2 4 5 7 2 4 5 7 8 3 1 11 8 3 1 11 8 3 1 11 8 3 1 14 6 10 12 14 6 12 14 6 10 14 6 10 11 9 13 15 9 13 10 15 9 13 15 12 9 13 15 12 goal test way to determine whether a given state is a goal state path cost numerical cost associated with a given path A B C D E F G I K H J L M A 4 2 B 5 2 C 1 D 6 E F G 3 2 3 I 4 K 3 H 4 J 2 1 2 L M A 1 1 B 1 1 C 1 D 1 E F G 1 1 1 I 1 K 1 H 1 J 1 1 1 L M Search Problems initial state actions transition model goal test path cost function solution a sequence of actions that leads from the initial state to a goal state optimal solution a solution that has the lowest path cost among all solutions node a data structure that keeps track of - a state - a parent (node that generated this node) - an action (action applied to parent to get node) - a path cost (from initial state to node) Approach Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. If node contains goal state, return the solution. Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier A C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier B C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier C D C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier D C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier E D C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier D C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. Find a path from A to E. A B Frontier D C D Start with a frontier that contains the initial state. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. E If node contains goal state, return the solution. F Expand node, add resulting nodes to the frontier. What could go wrong? Find a path from A to E. A B Frontier C D E F Find a path from A to E. A B Frontier A C D E F Find a path from A to E. A B Frontier C D E F Find a path from A to E. A B Frontier B C D E F Find a path from A to E. A B Frontier C D E F Find a path from A to E. A B Frontier A C D C D E F Find a path from A to E. A B Frontier C D C D E F Revised Approach Start with a frontier that contains the initial state. Start with an empty explored set. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. If node contains goal state, return the solution. Add the node to the explored set. Expand node, add resulting nodes to the frontier if they aren't already in the frontier or the explored set. Revised Approach Start with a frontier that contains the initial state. Start with an empty explored set. Repeat: If the frontier is empty, then no solution. Remove a node from the frontier. If node contains goal state, return the solution. Add the node to the explored set. Expand node, add resulting nodes to the frontier if they aren't already in the frontier or the explored set. stack last-in first-out data type Find a path from A to E. A B Frontier C D Explored Set E F Find a path from A to E. A B Frontier A C D Explored Set E F Find a path from A to E. A B Frontier C D Explored Set A E F Find a path from A to E. A B Frontier B C D Explored Set A E F Find a path from A to E. A B Frontier C D Explored Set A B E F Find a path from A to E. A B Frontier C D C D Explored Set A B E F Find a path from A to E. A B Frontier C C D Explored Set A B D E F Find a path from A to E. A B Frontier C F C D Explored Set A B D E F Find a path from A to E. A B Frontier C C D Explored Set A B D F E F Find a path from A to E. A B Frontier C D Explored Set A B D F C E F Find a path from A to E. A B Frontier E C D Explored Set A B D F C E F Find a path from A to E. A B Frontier C D Explored Set A B D F C E F Depth-First Search depth-first search search algorithm that always expands the deepest node in the frontier Breadth-First Search breadth-first search search algorithm that always expands the shallowest node in the frontier queue first-in first-out data type Find a path from A to E. A B Frontier C D Explored Set E F Find a path from A to E. A B Frontier A C D Explored Set E F Find a path from A to E. A B Frontier C D Explored Set A E F Find a path from A to E. A B Frontier B C D Explored Set A E F Find a path from A to E. A B Frontier C D Explored Set A B E F Find a path from A to E. A B Frontier C D C D Explored Set A B E F Find a path from A to E. A B Frontier D C D Explored Set A B C E F Find a path from A to E. A B Frontier D E C D Explored Set A B C E F Find a path from A to E. A B Frontier E C D Explored Set A B C D E F Find a path from A to E. A B Frontier E F C D Explored Set A B C D E F Find a path from A to E. A B Frontier F C D Explored Set A B C D E F Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Depth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A Breadth-First Search B A uninformed search search strategy that uses no problem- specific knowledge informed search search strategy that uses problem-specific knowledge to find solutions more efficiently greedy best-first search search algorithm that expands the node that is closest to the goal, as estimated by a heuristic function h(n) Heuristic function? B A Heuristic function? B D C A Heuristic function? Manhattan distance. B D C A Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 11 9 7 3 2 B 12 10 8 7 6 4 1 13 12 11 9 7 6 5 2 13 10 8 6 3 14 13 12 11 9 7 6 5 4 13 10 A 16 15 14 11 10 9 8 7 6 Greedy Best-First Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 12 10 9 8 7 6 4 13 11 5 A 16 15 14 12 11 10 9 8 7 6 Greedy Best-First Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 12 10 9 8 7 6 4 13 11 5 A 16 15 14 12 11 10 9 8 7 6 Greedy Best-First Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 12 10 9 8 7 6 4 13 11 5 A 16 15 14 12 11 10 9 8 7 6 A* search search algorithm that expands node with lowest value of g(n) + h(n) g(n) = cost to reach node h(n) = estimated cost to goal A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 12 10 9 8 7 6 4 13 11 5 A 16 15 14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 12 10 9 8 7 6 4 13 11 5 A 1+16 15 14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 12 10 9 8 7 6 4 13 11 5 A 1+16 2+15 14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 12 10 9 8 7 6 4 13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 10 9 8 7 6 5 4 2 13 6+11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 9 8 7 6 5 4 2 13 6+11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 8 7 6 5 4 2 13 6+11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 7 6 5 4 2 13 6+11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 6 5 4 2 13 6+11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 11+6 5 4 2 13 6+11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 11+6 12+5 4 2 13 6+11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 13 6+11 5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 13 6+11 14+5 3 14 13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 13 6+11 14+5 3 14 6+13 5+12 10 9 8 7 6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 13 6+11 14+5 3 14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 10 9 8 7 6 5 4 3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 9 8 7 6 5 4 3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 8 7 6 5 4 3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 13+8 7 6 5 4 3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 13+8 14+7 6 5 4 3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 13+8 14+7 15+6 5 4 3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 13+8 14+7 15+6 16+5 4 3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 13+8 14+7 15+6 16+5 17+4 3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 13+8 14+7 15+6 16+5 17+4 18+3 2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 13+8 14+7 15+6 16+5 17+4 18+3 19+2 1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* Search 11+10 12+9 13+8 14+7 15+6 16+5 17+4 18+3 19+2 20+1 B 10+11 1 9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2 8+13 6+11 14+5 3 7+14 6+13 5+12 10 9 8 7 15+6 4 4+13 11 5 A 1+16 2+15 3+14 12 11 10 9 8 7 6 A* search optimal if - h(n) is admissible (never overestimates the true cost), and - h(n) is consistent (for every node n and successor n' with step cost c, h(n) ≤ h(n') + c) Adversarial Search O X O X X O X O X O X X O X Minimax O X X X O X O X O O O O X X O O X X X X O X O X -1 0 1 Minimax MAX (X) aims to maximize score. MIN (O) aims to minimize score. Game S0 : initial state PLAYER(s) : returns which player to move in state s ACTIONS(s) : returns legal moves in state s RESULT(s, a) : returns state after action a taken in state s TERMINAL(s) : checks if state s is a terminal state UTILITY(s) : final numerical value for terminal state s Initial State PLAYER(s) PLAYER( )= X PLAYER( X )= O ACTIONS(s) X O O ACTIONS( O X X )={ , O } X O RESULT(s, a) X O O X O O RESULT( O X X , )= O X X X O X O TERMINAL(s) O TERMINAL( O X ) = false X O X O X TERMINAL( O X ) = true X O X UTILITY(s) O X UTILITY( O X )= 1 X O X O X X UTILITY( X O ) = -1 O X O O X O O X X X X O VALUE: 1 MIN-VALUE: X O PLAYER(s) = O 0 O X X X O O X O X O MAX-VALUE: MAX-VALUE: 1 O X X 0 O X X X O X O O O X O X X O VALUE: O X X VALUE: O X X 1 0 X X O X O O MIN-VALUE: X O PLAYER(s) = O 0 O X X X O O X O X O MAX-VALUE: MAX-VALUE: 1 O X X 0 O X X X O X O O O X O X X O VALUE: O X X VALUE: O X X 1 0 X X O X O O MAX-VALUE: 1 X O PLAYER(s) = X O X X O MIN-VALUE: X O MIN-VALUE: X X O VALUE: X O 0 -1 1 O X X O X O X X O X O X X O O X O X O X X O X X O MAX-VALUE: MAX-VALUE: VALUE: MAX-VALUE: 1 O X X 0 O X X -1 O X O 0 O X X O X O O X O X O O O X O X X O X X O VALUE: O X X VALUE: O X X VALUE: O X X 1 0 0 X X O X O O X O O 9 5 3 9 8 9 8 5 3 9 2 8 Minimax Given a state s: MAX picks action a in ACTIONS(s) that produces highest value of MIN-VALUE(RESULT(s, a)) MIN picks action a in ACTIONS(s) that produces smallest value of MAX-VALUE(RESULT(s, a)) Minimax function MAX-VALUE(state): if TERMINAL(state): return UTILITY(state) v = -∞ for action in ACTIONS(state): v = MAX(v, MIN-VALUE(RESULT(state, action))) return v Minimax function MIN-VALUE(state): if TERMINAL(state): return UTILITY(state) v=∞ for action in ACTIONS(state): v = MIN(v, MAX-VALUE(RESULT(state, action))) return v Optimizations 4 4 5 3 2 4 8 5 9 3 7 2 4 6 4 4 5 ≤3 ≤2 4 8 5 9 3 2 Alpha-Beta Pruning 255,168 total possible Tic-Tac-Toe games 288,000,000,000 total possible chess games after four moves each 29000 10 total possible chess games (lower bound) Depth-Limited Minimax evaluation function function that estimates the expected utility of the game from a given state https://xkcd.com/832/ Search Introduction to Artificial Intelligence with Python
