UC Berkeley CS 188 Artificial Intelligence

Assignment code for UC Berkeley CS 188 Artificial Intelligence.

For open course material in edX, using this class: BerkeleyX: CS188.1x Artificial Intelligence

Projects

• Project 0: Python Refresher

* addition.py * buyLotsOfFruit.py * shopSmart.py

• Project 1: Search (Python 3 Version)

* search.py * searchAgents.py

Quizzes

• Lecture 2: Uninformed Search

* Quiz 1: Planning Agents vs. Reflex Agents * Quiz 2: Safe Passage * Quiz 3: State Space Graphs and Search Trees * Quiz 4: Depth-First Tree Search * Quiz 5: Depth-First Tree Search: Space and Time Complexity * Quiz 6: Breadth-First Tree Search * Quiz 7: Breadth-First Tree Search: Space and Time Complexity * Quiz 9: Which Search Algorithm? * Quiz 10: Which Search Algorithm? * Quiz 11: Uniform Cost Search * Quiz 12: Which Search Algorithm? * Quiz 13: Which Search Algorithm?

• Lecture 3: Informed Search

* Quiz 1: Search Execution * Quiz 2: Greedy Search Quiz 3: A Tree Search Quiz 4: A Tree Search * Quiz 5: Which Search Algorithm? * Quiz 6: Which Search Algorithm? * Quiz 7: Which Search Algorithm? * Quiz 8: Which Search Algorithm? * Quiz 9: Which Search Algorithm? * Quiz 10: Admissible Heuristics * Quiz 11: Combining Heuristics * Quiz 12: Consistency

• Lecture 4: CSPs

* Quiz 1: Constraints * Quiz 2: Constraint Graphs * Quiz 3: Constraints * Quiz 4: Backtracking Search * Quiz 5: Forward Checking * Quiz 6: Arc Consistency * Quiz 7: Arc Consistency * Quiz 8: Least Constraining Value

• Lecture 5: CSPs II

* Quiz 1: Tree-Structured CSPs * Quiz 2: Smallest Cutset * Quiz 3: Min-Conflicts * Quiz 4: Hill Climbing

• Lecture 6: Adversarial Search

* Quiz 1: Minimax * Quiz 2: Evaluation and Collaboration * Quiz 3: Alpha-Beta Pruning

• Lecture 7: Uncertainty and Utilities

* Quiz 1: Expectimax * Quiz 3: Other Games * Quiz 4: Monotonic Transformations * Quiz 5: Rationality * Quiz 6: Certainty Equivalent Values

• Lecture 8: Markov Decision Processes

* Quiz 1: MDP Notation * Quiz 2: Discounting * Quiz 3: Solving MDPs * Quiz 4: Value Iteration

• Lecture 9: Markov Decision Processes II

* Quiz 1: The Bellman Equation * Quiz 2: Policy Evaluation * Quiz 3: Policy Iteration

• Lecture 10: Reinforcement Learning

* Quiz 1: Reinforcement Learning * Quiz 2: Model-Based Learning * Quiz 3: Passive Reinforcement Learning * Quiz 4: TD Learning * Quiz 5: Q-Learning

• Lecture 11: Reinforcement Learning II

* Quiz 1: Exploration vs. Exploitation * Quiz 2: Feature-Based Representations

Homeworks

• Homework 1 - Search

* Question 1: Search Trees * Question 2: Depth-First Graph Search * Question 3: Breadth-First Graph Search Question 4: A Graph Search * Question 5: Hive Minds: Lonely Bug * Question 6: Hive Minds: Swarm Movement * Question 7: Hive Minds: Migrating Birds * Question 8: Hive Minds: Jumping Bug * Question 9: Hive Minds: Lost at Night * Question 10: Early Goal Checking Graph Search * Question 11: Lookahead Graph Search * Question 12: Memory Efficient Graph Search Question 13: A-CSCS

• Homework 1 - Search (Practice)

* Question 1: Search Trees/Question01-SearchTrees.pdf) * Question 2: Depth-First Graph Search/Question02-DepthFirstGraphSearch.pdf) * Question 3: Breadth-First Graph Search/Question03-BreadthFirstGraphSearch.pdf) Question 4: A Graph Search/Question04-AStarGraphSearch.pdf) * Question 5: Hive Minds: Lonely Bug/Question05-HiveMinds-LonelyBug.pdf) * Question 6: Hive Minds: Swarm Movement/Question06-HiveMinds-SwarmMovement.pdf) * Question 7: Hive Minds: Migrating Birds/Question07-HiveMinds-MigratingBirds.pdf) * Question 8: Hive Minds: Jumping Bug/Question08-HiveMinds-JumpingBug.pdf) * Question 9: Hive Minds: Lost at Night/Question09-HiveMinds-LostAtNight.pdf) * Question 10: Early Goal Checking Graph Search/Question10-EarlyGoalCheckingGraphSearch.pdf) * Question 11: Lookahead Graph Search/Question11-LookaheadGraphSearch.pdf) * Question 12: Memory Efficient Graph Search/Question12-MemoryEfficientGraphSearch.pdf) Question 13: A-CSCS/Question13-AStarCSCS.pdf)

• Homework 2 - CSPs

* Question 1: Campus Layout * Question 2: CSP Properties * Question 3: 4-Queens * Question 4: Tree-Structured CSPs * Question 5: Solving Tree-Structured CSPs * Question 6: Arc Consistency * Question 7: Arc Consistency Properties * Question 8: Backtracking Arc Consistency

• Homework 2 - CSPs (Practice)

* Question 1: Campus Layout/Question01-CampusLayout.pdf) * Question 2: CSP Properties/Question02-CSPProperties.pdf) * Question 3: 4-Queens/Question03-4Queens.pdf) * Question 4: Tree-Structured CSPs/Question04-TreeStructuredCSPs.pdf) * Question 5: Solving Tree-Structured CSPs/Question05-SolvingTreeStructuredCSPs.pdf) * Question 6: Arc Consistency/Question06-ArcConsistency.pdf) * Question 7: Arc Consistency Properties/Question07-ArcConsistencyProperties.pdf) * Question 8: Backtracking Arc Consistency/Question08-BacktrackingArcConsistency.pdf)

• Homework 3 - Games

* Question 1: Minimax * Question 2: Expectiminimax * Question 3: Unknown Leaf Value * Question 4: Alpha-Beta Pruning * Question 5.1: Non-Zero-Sum Games * Question 5.2: Properties of Non-Zero-Sum Games * Question 6: Possible Pruning * Question 7: Suboptimal Strategies * Question 8: Shallow Search * Question 9: Rationality of Utilities * Question 10: Certainty Equivalent Values * Question 11: Preferences and Utilities

• Homework 3 - Games (Practice)

* Question 1: Minimax/Question01-Minimax.pdf) * Question 2: Expectiminimax/Question02-Expectiminimax.pdf) * Question 3: Unknown Leaf Value/Question03-UnknownLeafValue.pdf) * Question 4: Alpha-Beta Pruning/Question04-AlphaBetaPruning.pdf) * Question 5.1: Non-Zero-Sum Games/Question05-NonZeroSumGames.pdf) * Question 5.2: Properties of Non-Zero-Sum Games/Question05-PropertiesOfNonZeroSumGames.pdf) * Question 6: Possible Pruning/Question06-PossiblePruning.pdf) * Question 7: Suboptimal Strategies/Question07-SuboptimalStrategies.pdf) * Question 8: Shallow Search/Question08-ShallowSearch.pdf) * Question 9: Rationality of Utilities/Question09-RationalityOfUtilities.pdf) * Question 10: Certainty Equivalent Values/Question10-CertaintyEquivalentValues.pdf) * Question 11: Preferences and Utilities/Question11-PreferencesAndUtilities.pdf)

• Homework 4 - MDPs

* Question 1: Solving MDPs * Question 2: Value Iteration Convergence Values * Question 3: Value Iteration: Cycle * Question 4: Value Iteration: Properties * Question 5: Value Iteration: Convergence * Question 6: Policy Evaluation * Question 7: Policy Iteration * Question 8: Policy Iteration: Cycle * Question 9: Wrong Discount Factor * Question 10: MDP Properties * Question 11: Policies

• Homework 4 - MDPs (Practice)

* Question 1: Solving MDPs/Question01-SolvingMDPs.pdf) * Question 2: Value Iteration Convergence Values/Question02-ValueIterationConvergenceValues.pdf) * Question 3: Value Iteration: Cycle/Question03-ValueIteration-Cycle.pdf) * Question 4: Value Iteration: Properties/Question04-ValueIteration-Properties.pdf) * Question 5: Value Iteration: Convergence/Question05-ValueIteration-Convergence.pdf) * Question 6: Policy Evaluation/Question06-PolicyEvaluation.pdf) * Question 7: Policy Iteration/Question07-PolicyIteration.pdf) * Question 8: Policy Iteration: Cycle/Question08-PolicyIteration-Cycle.pdf) * Question 9: Wrong Discount Factor/Question09-WrongDiscountFactor.pdf) * Question 10: MDP Properties/Question10-MDPProperties.pdf) * Question 11: Policies/Question11-Policies.pdf)

• Homework 5 - Reinforcement Learning

* Question 1: Model-Based RL: Grid * Question 2: Model-Based RL: Cycle * Question 3: Direct Evaluation * Question 4: Temporal Difference Learning * Question 5: Model-Free RL: Cycle * Question 6: Q-Learning Properties * Question 7: Exploration and Exploitation * Question 8: Feature-Based Representation: Actions * Question 9: Feature-Based Representation: Update

• Homework 5 - Reinforcement Learning (Practice)

* Question 1: Model-Based RL: Grid/Question01-ModelBasedRL-Grid.pdf) * Question 2: Model-Based RL: Cycle/Question02-ModelBasedRL-Cycle.pdf) * Question 3: Direct Evaluation/Question03-DirectEvaluation.pdf) * Question 4: Temporal Difference Learning/Question04-TemporalDifferenceLearning.pdf) * Question 5: Model-Free RL: Cycle/Question05-ModelFreeRL-Cycle.pdf) * Question 6: Q-Learning Properties/Question06-QLearningProperties.pdf) * Question 7: Exploration and Exploitation/Question07-ExplorationAndExploitation.pdf) * Question 8: Feature-Based Representation: Actions/Question08-FeatureBasedRepresentation-Actions.pdf) * Question 9: Feature-Based Representation: Update/Question09-FeatureBasedRepresentation-Update.pdf)

Midterm Exam

• Practice I

* Question 1: Search * Question 2: Hive Minds * Question 3: CSPs: Time Management * Question 4: Surrealist Pacman * Question 5: MDPs: Grid-World Water Park * Question 6: Short Answer: Search * Question 7: Short Answer: Iterative Deepening * Question 8: Short Answer: Dominance * Question 9: Short Answer: Heuristics * Question 10: Short Answer: CSP * Question 11: Short Answer: Games

• Practice I (Practice)

* Question 1: Search/Question01-Search.pdf) * Question 2: Hive Minds/Question02-HiveMinds.pdf) * Question 3: CSPs: Time Management/Question03-CSPs-TimeManagement.pdf) * Question 4: Surrealist Pacman/Question04-SurrealistPacman.pdf) * Question 5: MDPs: Grid-World Water Park/Question05-MDPs-GridWorldWaterPark.pdf) * Question 6: Short Answer: Search/Question06-ShortAnswer-Search.pdf) * Question 7: Short Answer: Iterative Deepening/Question07-ShortAnswer-IterativeDeepening.pdf) * Question 8: Short Answer: Dominance/Question08-ShortAnswer-Dominance.pdf) * Question 9: Short Answer: Heuristics/Question09-ShortAnswer-Heuristics.pdf) * Question 10: Short Answer: CSP/Question10-ShortAnswer-CSP.pdf) * Question 11: Short Answer: Games/Question11-ShortAnswer-Games.pdf)

• Practice II

* Question 1: Search * Question 2: Search: Heuristic Function Properties * Question 3: Search: Slugs * Question 4: Value Functions * Question 5: CSPs: CS188x Offices * Question 6: CSP Properties * Question 7: Games: Alpha-Beta Pruning * Question 8: Utilities: Low/High * Question 9: MDPs and Reinforcement Learning: Mini-Grids

• Practice II (Practice)

* Question 1: Search/Question01-Search.pdf) * Question 2: Search: Heuristic Function Properties/Question02-Search-HeuristicFunctionProperties.pdf) * Question 3: Search: Slugs/Question03-Search-Slugs.pdf) * Question 4: Value Functions/Question04-ValueFunctions.pdf) * Question 5: CSPs: CS188x Offices/Question05-CSPs-CS188xOffices.pdf) * Question 6: CSP Properties/Question06-CSPProperties.pdf) * Question 7: Games: Alpha-Beta Pruning/Question07-Games-AlphaBetaPruning.pdf) * Question 8: Utilities: Low/High/Question08-Utilities-LowHigh.pdf) * Question 9: MDPs and Reinforcement Learning: Mini-Grids/Question09-MDPsAndReinforcementLearning-MiniGrids.pdf)

• Practice III

* Question 1: CSPs: Final Exam Staff Assignments * Question 2: Solving Search Problems with MDPs * Question 3: X-Values * Question 4: Games with Magic * Question 5: Pruning and Child Expansion Ordering Question 6: A Search: Batch Node Expansion

• Practice III (Practice)

* Question 1: CSPs: Final Exam Staff Assignments/Question01-CSPs-FinalExamStaffAssignments.pdf) * Question 2: Solving Search Problems with MDPs/Question02-SolvingSearchProblemsWithMDPs.pdf) * Question 3: X-Values/Question03-XValues.pdf) * Question 4: Games with Magic/Question04-GamesWithMagic.pdf) * Question 5: Pruning and Child Expansion Ordering/Question05-PruningAndChildExpansionOrdering.pdf) Question 6: A Search: Batch Node Expansion/Question06-AStarSearch-BatchNodeExpansion.pdf)

• Exam

* Question 1: Pacman's Tour of San Francisco * Question 2: Missing Heuristic Values * Question 3: PAC-CORP Assignments * Question 4: k-CSPs * Question 5: One Wish Pacman * Question 6: AlphaBetaExpinimax * Question 7: Lotteries in Ghost Kingdom * Question 8: Indecisive Pacman * Question 9: Reinforcement Learning * Question 10: Potpourri