Artificial Intelligence
Search, A*, game playing, constraint solving, logic, Bayesian networks, hidden Markov models, MDPs and Q-learning, each built and run in plain Python.
- Level
- Advanced
- Time
- About 25 hours
- Modules
- 5
- Lessons
- 15
- Exercises
- 45
Artificial intelligence builds agents that decide what to do. This course covers the classic techniques that make that possible: searching for plans, playing against an opponent, satisfying constraints, reasoning with logic, reasoning under uncertainty with probabilities, and learning to act well from rewards.
Every technique is code you run in your browser. You write breadth-first search and A*, hill climbing and 2-opt, minimax with alpha-beta pruning, backtracking with forward checking and AC-3, truth tables, a SAT solver, chaining and unification, Bayesian network inference, filtering and Viterbi, value iteration and Q-learning. Learning from data itself is the subject of the Machine Learning course.
What you will learn
- Describe tasks as agents in environments and as search problems
- Solve problems with uninformed search, A*, local search and game-tree search
- Model and solve constraint satisfaction problems with backtracking and propagation
- Reason with propositional logic, inference rules and unification
- Reason under uncertainty with Bayes' rule, Bayesian networks and hidden Markov models
- Plan with Markov decision processes and learn policies with reinforcement learning
Skills you will gain
- State-space search and heuristics
- Game-tree search
- Constraint satisfaction
- Logical inference
- Probabilistic reasoning
- Planning under uncertainty and reinforcement learning
Before you start
- Python: functions, dictionaries, sets, recursion and classes (the Python course)
- Queues, stacks, heaps and graphs (the Data Structures and Algorithms courses)
- Basic probability helps: fractions, percentages and averages
Where it is used
- Route planning and pathfinding in games and robots
- Game-playing programs
- Scheduling, timetabling and puzzle solving
- Diagnosis, tracking and decision support under uncertainty
Modules
Module 1: Agents and search
What an intelligent agent is, how to state a task as a search problem, and how to solve it with breadth-first, depth-first, uniform-cost, greedy and A* search.
- 1
Intelligent agents Intermediate
An agent perceives its environment and acts on it. Learn the parts of an agent, how to describe a task with PEAS, the kinds of environment, and the step from simple reflex agents to agents that keep a model of the world.
- 2
Problem solving by search Intermediate
Turn a task into a search problem with states, actions, a goal and costs. Explore the state space with breadth-first, depth-first and uniform-cost search, and know which one finds the shortest or the cheapest solution.
- 3
Heuristics and A* search Intermediate
Guide search with an estimate of the distance to the goal. Compare greedy best-first search with A*, learn why an admissible heuristic makes A* optimal, and design heuristics such as Manhattan distance.
Module 2: Local search and games
Improving one candidate at a time with hill climbing, restarts and 2-opt, and choosing moves against an opponent with minimax, alpha-beta pruning and expectimax.
- 1
Local search and optimization Intermediate
When only the final state matters, improve one candidate step by step instead of searching for a path. Use hill climbing, random restarts and simulated annealing on the N-queens and travelling-salesman problems, and understand local optima.
- 2
Game playing with minimax Intermediate
Search when an opponent moves too. Represent a two-player game as a tree of moves, score the end positions, and use minimax to pick the move that is best against the best reply.
- 3
Alpha-beta pruning and chance Advanced
Get the same answer as minimax while searching far fewer positions by pruning branches that cannot change the decision. See how move ordering affects pruning, and extend minimax to games with dice using expectimax.
Module 3: Constraints and logic
Constraint satisfaction with backtracking, MRV, forward checking and AC-3, then propositional logic, model checking, SAT solving, chaining and unification.
- 1
Constraint satisfaction problems Intermediate
Describe problems as variables, domains and constraints, then solve them with backtracking search. Make the search much faster with the minimum-remaining-values heuristic and forward checking, on map colouring and Sudoku.
- 2
Constraint propagation and AC-3 Advanced
Shrink domains before and during search by removing values that cannot be part of any solution. Learn arc consistency, run the AC-3 algorithm, and see what propagation can and cannot decide on its own.
- 3
Propositional logic Intermediate
Represent facts as logical sentences, give them meaning with truth tables, and decide whether a conclusion follows from a knowledge base by checking every model. Learn validity, satisfiability and the classic equivalences.
- 4
Inference: chaining, resolution and unification Advanced
Derive new facts from rules without listing every model. Use forward chaining and backward chaining with if-then rules, prove things by resolution, and match patterns with variables using unification, the step towards first-order logic.
Module 4: Reasoning under uncertainty
Probability, Bayes' rule and belief updates, Bayesian networks with enumeration and d-separation, and hidden Markov models with filtering and the Viterbi algorithm.
- 1
Probability and Bayes' rule Intermediate
Reason with uncertainty. Use random variables, joint distributions, marginal and conditional probabilities, and Bayes' rule to update beliefs from evidence, as in medical tests and robot localization.
- 2
Bayesian networks Advanced
Represent a large joint distribution compactly as a graph of causes and effects with small conditional probability tables. Compute any probability by enumeration, and read independence from the graph with d-separation.
- 3
Hidden Markov models Advanced
Track a hidden state that changes over time from noisy observations. Use a transition model and a sensor model to predict, to filter with the forward algorithm, and to find the most likely sequence of states with the Viterbi algorithm.
Module 5: Decisions and learning from reward
Planning with Markov decision processes and value iteration, and learning without a model through returns, temporal-difference learning and Q-learning.
- 1
Markov decision processes Advanced
Plan when actions have uncertain results. Describe a task as a Markov decision process, write the Bellman equation, compute values with value iteration, and read the best policy from them.
- 2
Reinforcement learning Advanced
Learn to act well from rewards alone, without knowing the transition model. Compute returns, estimate values with temporal-difference learning, and learn action values with Q-learning and ε-greedy exploration.
Projects
- A Connect Four player Build a program that plays Connect Four well, using depth-limited minimax with alpha-beta pruning and an evaluation function, and show how strong it is.
- A robot that plans, tracks and learns Build a grid-world robot that finds paths with A*, keeps track of its position from noisy sensor readings, plans under slippery moves with value iteration, and learns the same task with Q-learning.
What to learn next
- Deep Learning Neurons, backpropagation, optimizers, normalization, CNNs, RNNs, embeddings, attention and transformers, every network built from scratch in Python.
- Machine Learning Machine learning from scratch in plain Python: regression, gradient descent, regularization, k-NN, logistic regression, metrics, trees, ensembles and k-means.
- Theory of Computation Finite automata, regular expressions, grammars, pushdown automata, Turing machines, the halting problem and P vs NP, every machine built and run in Python.