Goal-Based (Teleological) Utility-Based (Happiness) Game Playing Learning
May involve search/plan Uses utility function World and opponent model
Week 2: Uninformed Search
A state space problem consists of: a state space, start state, set of actions, action function,
goal state, and path cost.
Uninformed Search methods:
, Week 3: Informed Search and Constraint Satisfaction Problems
Informed Search methods: All implemented using a priority queue.
A* Search = g(n) + h(n) = Uniform-cost search + Greedy search
Even after a goal node has been generated, A* will keep searching so long as there is a possibility of finding a
short solution. Once a goal node is selected for expansion, we know it must be optimal.
If h is not consistent but still admissible then A* admissibility is not guaranteed.
An admissible heuristic never overestimates the cost to reach the goal.
A heuristic is consistent if h(n) ≤ c(n, n’) + h(n’) where n’ is the successor of n.
A heuristic h1 is better than h2 if it means less nodes expanded (and therefore less time/memory) which happens
if h1(n) ≥ h2(n) for all n.
Constraint Satisfaction Problem methods:
Backtracking search: assign variables one by one, whenever a constraint is violated, go
abc to the most recently assigned variable and assign it a new value.
Improve backtracking search with:
1. Minimum remaining values (MRV): choose the variable with the fewest legal values
2. Degree heuristic: tie-breaker among MRV variables. Choose the variable with the
most constraints on remaining values
3. Least constraining value: choose the value that rules out the least values in the
remaining variables
4. Forwarding checking: keep track of remaining legal values for unassigned variables,
terminate search when any variable has no legal values, and backtrack.
5. Arc consistency: make each arc consistent i.e. for every x of X there is some allowed
y of Y for a function X → Y.
Variable elimination: combine tables where X appears to remove X and simply the
problem.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller laurac4. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.49. You're not tied to anything after your purchase.