Introduction to Artificial Intelligence with Python

Instructor: Brian Yu

In this class, we explore ideas, techniques, and algorithms foundational to artificial intelligence (AI).

What is AI?

• Computer performing tasks that seem intelligent or rational.
• Examples: face recognition, game playing, natural language understanding.

Class Overview

1. Search: AI finding solutions to problems, e.g., driving directions, tic-tac-toe moves.
2. Knowledge: AI representing and drawing inferences from information.
3. Uncertainty: Dealing with probabilities and uncertain events.
4. Optimization: Finding the best or better ways to solve problems.
5. Machine Learning: Learning from data and improving task performance.
6. Neural Networks: AI drawing inspiration from the human brain's structure.
7. Language: Understanding and processing natural human languages.

Focus Today: Search

• AI finding solutions from an initial state to a goal state.
• Examples: solving the 15 puzzle, navigating mazes, finding driving directions.

Key Terminology

• Agent: Entity that perceives and acts on its environment.
• State: Configuration of the agent in its environment.
• Initial State: The starting point for the search algorithm.
• Actions: Choices available in a given state, defined as a function actions(S) returning a set of actions.
• Transition Model: Describes the outcome state after performing an action, defined as a function result(S,A).
• State Space: Set of all states reachable from the initial state.
• Goal Test: Determines if a state is a goal state.
• Path Cost: Numerical cost associated with a path, aiming to minimize it.

Search Problem Components

1. Initial state
2. Actions available in each state
3. Transition model for actions
4. Goal test to identify goal state
5. Path cost function to evaluate paths

Representing Nodes

• Store state, parent, action, and path cost.
• Nodes help backtrack from goal to initial state to form the solution path.

Search Algorithm (Pseudocode)

1. Initialize the frontier with the initial state.
2. Repeat:
   • If the frontier is empty, there is no solution.
   • Remove a node from the frontier.
   • If the node contains a goal, return the solution.
   • Expand the node and add resulting nodes to the frontier.
3. Keep track of explored states to avoid infinite loops.

Depth First Search (DFS)

• Uses a stack (LIFO) for the frontier.
• Explores the deepest nodes first.
• Not necessarily optimal.
• May explore more states than needed.

Breadth First Search (BFS)

• Uses a queue (FIFO) for the frontier.
• Explores the shallowest nodes first.
• More efficient in finding an optimal solution (shortest path).

Advantages and Limitations

• DFS: Can be memory efficient but not always optimal.
• BFS: Finds optimal solution but can be memory intensive.

Greedy Best-First Search

• Expands the node that appears to be closest to the goal using a heuristic function h(n).
• Uses a heuristic for estimating distance to the goal, e.g., Manhattan distance.
• Not necessarily optimal.

A* Search

• Combines path cost (g(n)) and heuristic cost (h(n)), considering g(n) + h(n).
• Optimal if the heuristic is admissible (never overestimates) and consistent.

Adversarial Search

• Minimax Algorithm: For games with two players making alternating moves.
  • maxValue: Calculates the maximum value if it's the max player's turn.
  • minValue: Calculates the minimum value if it's the min player's turn.
• Alpha-Beta Pruning: Optimization to eliminate unnecessary branches.

Practical Use Case: Games

• E.g., Tic-Tac-Toe, Chess.
• Turns the game into a tree of possible moves, evaluating with Minimax and pruning.
• Depth-limited Minimax for complex games with evaluation functions to estimate game state utility.

Conclusion

• Today's lecture focused on search algorithms in AI.
• Next lecture will discuss how AI represents knowledge and draws inferences.